hS：以子进程粒度进行推测性脚本重排（OSDI 2026）

原题：hS: Speculative Script Reordering at Subprocess Granularity

一句话总结：hS 假设 shell 脚本中跨命令、跨循环迭代的独立性无法可靠地从命令名静态推断，于是用运行时系统调用追踪和 OverlayFS 隔离，在不加注解的前提下推测执行并按原顺序提交；49 个真实 shell 脚本上相对 Bash 的几何平均加速为 2.6×，最高 9.3×，但 I/O 密集工作负载可能慢 3.2–7.2×。

问题与动机

shell 脚本经常把不同语言编写的程序、管道和领域工具串起来。现有的 PaSh、POSH 等优化器依赖命令注解来描述输入、输出和可并行化方式。对 GNU 工具维护注解尚且可行，对用户自编译的生物信息学工具或黑盒二进制则不现实。注解方案还主要暴露保持原顺序的数据并行，通常把 ;、条件分支和循环边界当作同步点。

论文的目标是利用脚本中本来就存在的命令调用独立性，同时保留原脚本的可观察行为。以 TERA-Seq 为例，不同样本的比对可以并行，某个样本完成比对后也不必等待所有样本再开始建索引或生成数据库。hS 将这些机会交给运行时发现，而不是要求开发者重写脚本或描述每个外部命令。

关键观察 / 隐含假设

观察 1：脚本的潜在并行性跨越了命令和循环的显式顺序。 TERA-Seq 中不同样本相互独立，且后处理可以在单个样本完成后提前启动；原脚本的顺序并不等于必须的依赖顺序（§2、图 1）。
- 依赖假设：不同命令的有效依赖可以由文件路径、shell 状态和系统调用行为近似捕获。
- 可能失效场景：依赖藏在共享数据库、网络服务、IPC、信号、设备状态或未被追踪的外部资源中时，文件读写集合不足以描述真实依赖。
观察 2：黑盒命令的隐式副作用必须在执行过程中发现。 samtools index 生成的索引文件名并不出现在参数中，而是由输入文件和数据规模决定（§2.2）。
- 依赖假设：系统调用追踪能在副作用造成不可逆外部影响前观察到它；对非延迟副作用可以安全阻断。
- 可能失效场景：命令在很晚才写出关键文件，会产生较高的错误推测成本；网络、IPC 和信号只能作为不安全命令执行，无法获得该命令的并行收益。
假设 1：推测结果可以隔离，提交可以保持原始顺序。 hS 用 OverlayFS 保存文件修改，用独立 shell 进程保存 shell 状态，并以原脚本顺序提交效果。该假设由 Alloy 有界模型检查支持，但模型假定命令最终终止，且只覆盖有限命令和文件状态，因此证据强度为中。
假设 2：目标工作负载的命令足够长、独立性足够多。 每个命令的固定执行器开销平均为 217 ms；短脚本或高度依赖的脚本无法摊薄该成本（§7.4）。证据强度为强，因为短脚本和严格依赖基准均出现减速。

核心方法

hS 先把脚本重写为由真实 shell 执行控制结构的程序骨架，以及由调度器管理的命令控制流图（CCFG）。一个可执行区域可以是简单命令、管道或需要保持同步语义的小段 shell，而不强行拆成单个 Unix 进程。shell 仍按原顺序决定分支、循环和短路逻辑；调度器只提前启动可能到达的后续实例。

调度器为每个命令实例维护就绪、直接执行、推测执行、推测完成、不安全和已提交等状态。推测命令结束后，执行器返回读取集合和写入集合。若此前命令没有改变该命令依赖的状态，推测结果可按原顺序提交；若发现写后读或其他冲突，则丢弃副作用并重新推测。网络访问、IPC、信号和 break、continue、return、exit 等无法安全隔离的行为会被阻断并标记为不安全命令，随后由原始骨架执行一次。每个不安全命令还会使其后的推测失效，以避免未知写集合破坏正确性（§3）。

执行器使用系统调用追踪收集路径级读写依赖。即使 stat 因路径不存在而失败，也被视为对该路径的读取，因为前置命令创建该路径会改变结果。父目录也被纳入依赖，以处理重命名等间接影响。文件副作用放入 OverlayFS 的 upper layer，shell 变量、当前目录、函数、选项、trap 和文件描述符则在独立 shell 中记录和恢复。Linux namespace 用于隔离网络、进程控制和设备等不可延迟副作用（§4）。

为减少重复执行，hS 在预处理阶段直接求值无副作用的纯变量赋值；运行时再流式检查追踪事件，一旦发现冲突就停止目标推测。调度器还把尚未提交但已完成的前置副作用叠加进后续推测的 OverlayFS lower layers，使后续命令尽量从最新状态启动（§5）。推测窗口限制同时运行的实例数，并允许在并行性和资源争用之间调节。

设计取舍

透明性换取执行器成本：不需要命令注解，能覆盖领域专用二进制；代价是每个命令都要经历追踪、隔离、状态复制和可能的重复执行。
保守地阻断不可延迟副作用：网络和 IPC 不会被错误重排，但这些命令成为并行化边界，且会使后续推测全部回滚。
按路径而非完整文件状态推理：避免复制整个文件系统，也能捕获隐式路径依赖；代价是路径级规则可能保守，写入大量小文件时追踪与提交成本很高。
固定的分支预测策略：当前对条件分支采用固定预测（例如选择 else），正确性不受影响但性能可能受损。论文把更好的预测策略留作后续工作。

实验与结果

在 10 组、共 49 个真实 shell 脚本（约 2.9k LOC）上，hS 相对 Bash 的几何平均加速为 2.6×，范围为 0.14–9.3×（§7.2、图 5）。所有比较运行均检查输出和退出状态与 Bash 一致。
在已由开发者用 & 和 wait 暴露部分并行性的 TERA-Seq 中，hS 仍使 9 个脚本中的 7 个加速，几何平均 1.5×，最高 3.5×。代表性工作流中，PaSh 可安全注解的 FASTQ 预处理仅占运行时间 1.6%，数据库修改和 SAM/BAM 处理需要领域专用拆分/合并支持，因而 PaSh 没有获得加速（§7.2）。
hS 的错误推测时间占总命令执行时间的 0–39%，平均 17%；Genomics 的一个执行轨迹达到 2.9× 加速，同时错误推测浪费 8% 时间（§7.3、图 6）。
固定执行器开销平均为每命令 217 ms，其中 sandboxing 占 120 ms。窗口为 0 时，相对 Bash 的整体开销为 2.4–49.0%，平均 23%（§7.4）。
I/O 压力测试中，写入大文件时 hS 比 Bash 慢 3.2–3.4×；创建大量小文件时慢 6.2–7.2×，追踪本身可带来 310% 开销（§7.4.2、图 7）。
推测窗口从 1 增至 15 时，各 benchmark 平均性能从 1.6×提升到 5.24×；NLP 在无限窗口下达到平均 9.1×，而 LogAnalysis 因过度推测在无限窗口下退化 33%（§7.5、图 8）。
受限 Python 前端在 5 个真实程序上相对标准 Python 的几何平均加速为 3.26×，范围为 1.75–8.40×；该前端要求外部调用可静态提取，且文件系统副作用主要经过外部命令（§6、§7.6、表 2）。

论断—证据表

论断	证据	评测边界	置信度
不依赖命令注解也能从真实 shell 脚本中提取可用并行性	49 个脚本相对 Bash 几何平均 2.6×，最高 9.3×（§7.2、图 5）	CloudLab 双路 32 核 AMD EPYC、256GB RAM、NVMe；真实脚本但规模和环境有限	强
动态依赖追踪可以覆盖黑盒领域工具	TERA-Seq 9 个脚本中 7 个加速，最高 3.5×；`samtools index` 的隐式索引依赖被运行时发现（§2.2、§7.2）	主要是生物信息学工作流；未覆盖更广泛的共享服务型副作用	中
推测回滚的成本在可接受范围内	平均错误推测浪费 17%，部分依赖延迟写入的工作负载达到 19–39%（§7.3、图 6）	时间占比不是 CPU 时间；未给出能耗、峰值资源和多租户影响	中
透明隔离机制适合长时间、计算密集型命令	每命令固定开销 217 ms；CPU 密集 benchmark 的相对开销低于 I/O 密集场景（§7.4）	大文件和小文件 I/O 分别慢 3.2–3.4×、6.2–7.2×	强

批判性分析

论证链条

论文的链条基本闭合：脚本存在未暴露的独立调用，运行时追踪能发现路径级依赖，沙箱能隔离延迟副作用，按顺序提交即可维持结果。TERA-Seq 和 Genomics 的轨迹说明设计确实能跨循环迭代提前运行。

仍有两个外推缺口。第一，hS 的安全性主要建立在路径、shell 状态和可阻断副作用之上；“任意 shell 脚本”不能等同于任意 Unix 程序，因为共享数据库、远程服务和设备状态不一定能被这些集合表示。第二，性能结论依赖长命令和独立工作；严格依赖脚本只能接近 Bash，而 PaSh 在某些数据并行场景可更快。

假设压力测试

最脆弱的假设是副作用可被完整隔离。OverlayFS 适合普通文件，但文件描述符只支持顺序读写，交互设备和其他设备类型超出范围。论文也没有系统评估 mmap、共享内存、GPU、特殊文件系统、数据库事务或恶意命令逃逸 namespace 的情形。非恶意程序假设降低了风险，但不是对语义覆盖范围的证明。

路径级冲突检测会在共享目录、父目录元数据和临时文件较多时趋于保守。相反，若真实依赖发生在网络服务或 IPC 中，系统会阻断并放弃推测收益。窗口过大还会增加资源争用和回滚，LogAnalysis 的退化说明“更多并行度”不是单调收益。

实验可信度

基线包含 Bash 和 PaSh，工作负载覆盖短脚本、长时间生物信息学流程、日志分析和大规模文件处理，且检查输出与退出状态。TERA-Seq 的领域工具使“无需注解”的主张具有说服力。

实验仍缺少生产环境中的多租户隔离、能耗、峰值内存、网络服务、失败恢复和不同文件系统的测试。PaSh 的完整对比排除了 TERA-Seq，只对一个代表性流程做了保守注解；这能说明注解和领域拆分的限制，但不能作为所有工作负载上的全面优越性证据。

系统性缺陷

hS 的实现包含 2.4k 行 Python、478 行 shell 沙箱代码和 285 行 Alloy 模型；Python 前端另有 547 行。每个命令都引入沙箱生命周期和可能的文件复制，运维上还需要处理 namespace、OverlayFS 挂载点和权限。论文未讨论异常退出、机器崩溃后清理临时层、外部信号语义以及推测进程的资源配额。对大量小文件的测量已经显示，追踪与提交路径可能吞噬全部并行收益。

局限与后续工作

局限 1：副作用模型不完整。 网络、IPC 和信号只能阻断；文件描述符支持也限于顺序读写。需要在包含 mmap、共享内存、数据库和设备访问的工作负载上定义并验证覆盖边界。
局限 2：错误推测可能很昂贵。 依赖在命令末尾才出现时，浪费可达 39%。可验证的后续方向是利用历史读写轨迹或命令摘要预测写入路径，并测量错误率、节省的执行时间和额外资源。
局限 3：推测窗口依赖工作负载。 当前策略是固定窗口和简单分支预测。可以实现基于运行时吞吐、冲突率、CPU 饱和度和命令长度的自适应策略，并在窗口变化实验之外报告 P95/P99 延迟和峰值并发。
局限 4：与数据并行优化互补但未融合。 hS 主要重排独立命令调用，不能拆分单个大文件上的严格依赖管道。将 hS 与 PaSh 的拆分/合并机制结合，并在相同领域工作流上做公平比较，是明确的设计空间。
局限 5：Python 前端范围窄。 当前限制了控制流、函数结构和文件副作用来源。后续应支持内置文件操作，并测量前端分析错误对安全性和并行度的影响。

Awesome System Papers Wiki

探索

paper-osdi26-liargkovas