返回资讯中心
外部精选
软件工程
#开发者实时流

为什么打乱执行顺序能发现更多 bug?

来源标题:Why does shuffling the schedule find so many bugs?

bug 本身并不罕见,罕见的是触发它的特定事件顺序。作者以 AWS RDS 为例:某 worker 暂停后心跳超时,SWF 将步骤转给另一 worker 完成,原 worker 醒来后误以为时间未流逝,继续执行旧步骤,导致顺序错乱。打乱调度正是为了复现这类罕见的时序组合。

Hacker News 最新speckx2026/11/4 · 13 天前30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

有个问题值得思考:bug 本身并不罕见,罕见的是触发它的那些事件顺序。这话是什么意思?

先讲一个小故事。我在 AWS 的 RDS(Relational Database Service)团队工作时,用工作流搭建了该服务的控制面,用的当然是 SWF(Simple Workflow)。这些工作流会执行一系列步骤来创建、修改或删除数据库实例。每隔一段时间,我们就会看到一些看似不可能的事情:某个工作流似乎把它的步骤执行乱了序。

我们实际观察到的其实是一次暂停。某个 worker 取走了一个步骤,然后意外地停了很长时间。在停住期间,它不再发送心跳,于是 SWF 判定它已经死亡,就把这个步骤重新分配给另一个 worker。新的 worker 完成了该步骤,工作流继续往下走。然后第一个 worker 醒了过来。在它看来时间根本没有流逝,于是它继续执行自己手里的那个步骤,结果留下一片狼藉。

time → worker 1 SWF worker 2 snapshot apply config paused last heartbeat heartbeat timeout apply config reboot apply config wakes up rejected the instance saw: snapshot → apply config → reboot → apply config

我们突然意识到,我们并没有充分地测试所有可能的事件顺序。工作流代码本身是正确的,但触发这个 bug 的那种顺序,我们在测试中从未见过。那是一种罕见的顺序,但并不是一个罕见的 bug。于是我们开始给每个步骤加上幂等 token,并确保每个步骤都能被重复执行而不破坏任何东西。这项工作很繁重,但它让系统健壮了许多。

我正在构建 Rewind VM,一个确定性 VM。它主要通过在多种不同的顺序下运行同一份代码来帮助发现软件中的 bug。¹ 单单是打乱顺序这一举动,迄今就已经发现了许多 bug。

被测的软件甚至都不是分布式系统,不像上面那个工作流的例子,然而很多 bug 依然依赖于执行顺序。并不需要 Jepsen 那套疯狂的测试套件。这怎么可能呢?这些项目都有测试,每次改动都会验证代码。为什么打乱顺序能发现这么多 bug,而那些测试却一个都没发现?

bug 并不罕见,罕见的是你的测试所运行的顺序。一台空闲、快速的机器几乎每次都跑同样的那几种顺序。测试之所以通过,是因为顺序从不改变,而代码可能也只处理过那一种顺序。

附注: 刚接触 Rewind?可以先看一个你只抓到过一次的 flaky build,以及 dafuq is a deterministic VM?

触发这些 bug 的,是各不相同的执行顺序,或者像上面工作流故事里那样意外的长时间暂停。bug 并不罕见,罕见的是触发它们的那些顺序。那它们到底有多罕见?

我所知的最小的竞态是来自两个线程的 counter++。

long counter; void increment(void) { counter++; increment: mov rax, [counter] ; load add rax, 1 ; add mov [counter], rax ; store ret }

两个线程各执行一次 increment。每个线程的三个步骤按顺序执行,但两个线程之间可以交错。一种顺序,就是选出 6 个位置中哪 3 个属于线程 A,所以共有 (\binom{6}{3}=20) 种。

我们可以把这 20 种选择画成网格上的路径。向右一步是线程 A 的一步,向下一步是线程 B 的一步,从左上角到右下角的每一条路径就是一种顺序。

load load add add store store thread A → thread B → shaded: both loaded, neither stored edges: AAABBB, BBBAAA. staircase: ABABAB the 20 orderings, and the counter after AAABBB 2 AABABB 1 AABBAB 1 AABBBA 1 ABAABB 1 ABABAB 1 ABABBA 1 ABBAAB 1 ABBABA 1 ABBBAA 1 BAAABB 1 BAABAB 1 BAABBA 1 BABAAB 1 BABABA 1 BABBAA 1 BBAAAB 1 BBAABA 1 BBABAA 1 BBBAAA 2

阴影方格包含四个点:两个线程都已加载 counter,但都还没有存回去。任何进入该方格的路径,最终 counter 的值都是 1,因为第二个写入者把过期的原始值存了回去。

只有沿着两条边的那两条路径能得到“正确结果”2,即 A 完全在 B 之前,或 B 完全在 A 之前。也就是说,20 种顺序中有 18 种会丢失一次更新。如果每种顺序出现的可能性相同,那么这个竞态在 10 次运行中会有 9 次触发。😱

这在真实机器上是什么样子呢?

我们来写一个小程序,运行这两个线程并记录它们步骤的顺序。这个程序比上面简单的 counter++ 要复杂一些,因为它必须记录步骤的顺序。它还必须小心,不要在记录过程中引入任何新的竞态。该程序利用 Rewind 的 rewind_point() 给 Rewind VM 提供一个切换线程的位置。²

/*

  • Two threads each add one to a shared counter in three steps: load the
  • counter, add one, store it back. No lock, so a thread that runs between
  • the other's load and store writes a stale value over it.
  • Each step first takes the next slot of a shared atomic sequence and
  • writes its thread's letter there, so the program prints the order the
  • six steps ran in, such as AABABB, and the final counter.
  • rewind_point() between the steps gives Rewind VM a place to switch
  • threads. main() calls it once before the threads start, so the one
  • failed open it makes outside Rewind happens there; on the host the
  • points inside the threads are a load and a branch.
  • Built with -DSTART_BARRIER, both threads wait on a barrier before the
  • first step, so they start as close together as the host allows.
  • The exit status encodes the outcome so rewind check reports it
  • without reading output: ordering index (0..19) * 2 + (1 if an update

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →