确定性模拟的背景、原理、框架及应用实例-五八三

作者：王润基 RisingWave Labs 内核开发工程师

确定性模拟（Deterministic Simulation）是一种独特的系统测试技术，它可以将整个分布式系统的各个组件运行在一个单线程模拟器上，从而实现系统的确定性执行。

这一技术的最大好处在于能够稳定地复现那些可能运行上千次才出现一次的 bug，并且运行速度非常快，能够在短时间内模拟现实中很长时间的行为。有了这一工具，我们就可以在有限的时间内尽可能多的测试系统在不同环境下的行为，而一旦发现了问题，也可以非常从容地去排查和除错。

这一技术曾经被应用在分布式 KV 数据库 FoundationDB 中，对提高该系统的稳定性与可靠性作出了不可磨灭的贡献。我们的 RisingWave 作为一个云原生分布式数据库，对于正确性和可靠性同样也有着非常苛刻的要求。因此我们也将这一技术应用在了 RisingWave 中，实现了自己的确定性测试框架 Madsim，并用它对 RisingWave 进行持续的端到端的模拟测试，帮助开发者提早发现并排除了大量潜在的并发和恢复问题。

本文中我们将介绍确定性模拟产生的背景、基本原理、测试框架的设计，以及我们在 RisingWave 中应用确定性测试的方法和经验。

神出鬼没的并发 Bug

我们知道，一个运行在真实世界上的分布式系统充满了各种各样的不确定性：多个节点之间，网络上的通信可能导致消息被延迟、丢失或者乱序；一个节点内部，多个线程的执行顺序无法预测，受到操作系统调度的影响；甚至一个线程内部，也会由于随机数的存在，导致每次运行都会产生不一样的结果。

而某些并发问题，恰恰只在某种特定的执行顺序下才会出现。它们可能潜伏在系统中长达数月，有一天机缘巧合突然发作，然后又继续消失不见。它们像就是悬在开发者头顶的一把达摩克利斯之剑，成为系统稳定性的最大隐患。

面对这一问题，学术界和工业界都提出过不同的解决方案。学界的主要思路倾向于形式化验证，或者对所有可能状态进行穷举，以证明系统 100% 正确。例如常用于证明分布式算法正确性的 TLA+ 语言，以及 Rust tokio 社区实现的验证并发正确性的 loom 框架。但是这种方法的局限性在于只适用于算法或小型系统，任何规模稍大的实际系统都会面临组合爆炸的问题，从而无法被有效验证。

工业界对此的解决方案倾向于通过大量测试覆盖尽可能多的可能性，其中比较知名的技术是混沌工程（Chaos Engineering）。混沌工程通过主动向系统中注入错误和随机性，使环境变得更加混乱，从而提高 Bug 出现的概率。例如攻破过无数分布式数据库的 Jepsen 框架，以及用于云原生系统的 Chaos Mesh 平台。这种方案可以有效验证实际系统在真实环境下的行为，但是有一点遗憾，那就是它们依然无法控制不确定性。发现了问题但无法保证 100% 的复现，这对开发调试依然是不友好的。

确定性模拟

原理与优势

确定性模拟是一种介于两种路线之间的方案，它的核心目标就是消除系统中的不确定性，使得任何问题都可以得到稳定复现。让我们再回顾一下上文提到的各种不确定因素，并想想如何才能消除它们：

对于单线程上的随机数，我们只需固定初始随机种子即可。
对于多线程的调度顺序问题，如果能把它们都压到一个线程上执行，那么就可以控制它们的执行顺序。
对于操作系统、网络等外部环境引起的随机因素，我们可以扩展 Mock 单元测试的方法，对整个环境构建一个模拟器，来确定性地模拟它们的行为。在此基础上，还可以受控地注入更多错误和随机性，达到确定性的混沌工程的效果。

以上就是确定性模拟的核心原理。

值得注意的是，在这里时间也是一个被模拟出来的变量。系统中所有的事件都会被分配一个确定性的发生时间，模拟器只需按照时间流逝的顺序依次处理这些事件即可。系统时间只是连续时间轴上一个个离散的点，所以这种方法又被称为离散事件模拟（Discrete-event Simulation）。离散事件模拟可以产生一种时间加速的效果：如果两个事件中间没有其它事件发生，即使它们之间相隔好几年，模拟器也可以直接移动时间轴跳到下一个时刻。这一特性使得我们可以在短时间内模拟系统在很长时间跨度下的行为，唯一的限制因素就是单核 CPU 的算力。因此这一技术对于 I/O 密集型应用可以发挥很大威力，而对计算密集型应用来说则没有那么显著的效果。

总的来说，确定性模拟有两大突出优势：确定性，执行快。可以极大提高我们发现问题、解决问题的效率。可是既然如此，为什么它没有被广泛应用呢？这就要提到它相对真实系统测试的最大劣势：对项目的侵入性强，工程实现难度大。

挑战与机遇

为了确保所有不确定性都被消除，在宏观上我们需要对系统依赖的所有外部环境构建模拟器，在微观上也就是所有对外的 API 调用都需要做 Mock。这本身就是不小的工作量。而一旦任何一处随机性的来源被漏掉，都会导致整个系统的确定性被破坏。因此这一工作必须做得彻底，并且很多第三方库都会因为内部的随机性而无法使用。最后，将所有节点上的所有代码都压到一个线程上执行，要么手工编写状态机和事件循环，要么需要引入协程。无论那种，对于代码基础架构都有很大挑战。

作为应用确定性测试的先驱者，FoundationDB 团队在十年前开始构建他们的确定性模拟器的时候，C++ 还没有对协程的语言级支持，也没有像今天 Rust 这样更现代的系统编程语言可供选择。因此他们首先为 C++ 语言打了个补丁，加入了基于 Actor 的无栈协程语法，创造了 Flow 语言。然后基于 Flow 构建了模拟器和上面的数据库。它们之间不可避免地形成了紧耦合关系，以至于目前还没有其它项目能够复用 FoundationDB 的测试框架。

而如今，我们有了更加现代的 Rust 语言。Rust 从 2019 年起稳定了语言内置的协程机制，并在社区的共同努力下形成了一套成熟、统一的异步编程生态。这为实现确定性模拟创造了良好的条件。社区中也先后有开发者进行过一些尝试，不过还没有形成一个像 Tokio 那样通用的、经过实际检验的框架出来^[1]。因此我们意识到，基于 RisingWave 的实际需求孵化一个开放、通用的确定性测试框架，无论对我们自己还是社区，都将是一件非常有价值的事情。

[1] Tokio 社区近期宣布了官方的确定性测试项目 turmoil，仍处在早期实验性阶段。

Madsim 测试框架

于是我们创立了 Madsim 项目，一个基于 Rust 异步编程生态实现的分布式系统确定性模拟器。它的角色就是一个类似于 Tokio 的异步运行时，只是在这里所有行为都是确定性的，并且其中诸如网络等环境是被模拟出来的。

下图展示了 madsim 的内部结构：

我们自底向上来看，它依次由这样几个模块构成：

全局伪随机数生成器：确定性模拟的核心是一个确定性的、全局的随机数生成器。系统中所有的随机因素，包括随机数、模拟器引入的延迟和错误等，都由这一个生成器产生。只要给定相同的随机种子，经由这个生成器即可产生相同的执行序列。
定时器：定时器是系统中所有事件的来源。它本质上是一个按时间戳排序的优先队列。模拟器执行时，不断从队列中取出最近的定时器、移动时间轴、触发事件并唤醒任务。任务在执行过程中，通过模拟器引入延时，创建新的定时器事件。由此构成模拟的事件循环。
任务调度器：维护所有就绪任务的队列。作为一个模拟分布式系统的运行时，其中的任务在逻辑上可能来自不同的节点，但在执行时我们都放在一个队列中统一进行调度。为了覆盖各种可能的执行顺序，这个队列被设计为先进随机出（FIRO），以最大限度挖掘潜在的并发问题。
环境模拟器：基于以上异步任务执行环境，我们即可构造各种模拟器，主要包括网络模拟器和文件系统（磁盘）模拟器。这些模拟器采用内存存储，在进程内部通过 channel 通信，因此执行效率也会比实际环境下快不少。

为了方便开发者使用，madsim 将上述功能包装成和 tokio 完全一致的 API。使得现有项目无需修改一行代码，只需修改少许配置即可使用。此外，madsim 还通过重载 libc 函数的方式，截获了部分关键的 std API。例如 Linux 和 macOS 下的 gettimeofday,clock_gettime,get_random,sysconf等，用来在模拟环境下提供确定性的时间、随机数、系统配置等信息，防止经由标准库和第三方库访问实际系统造成不确定性的泄露。对于这种方法仍然无法消除随机性的第三方库，我们只好通过手动打补丁的方式，通过 Cargo.toml 中的[patch] 功能来实现代码替换。这一切的目的都是为了能让现有项目无缝迁移、开箱即用。

除了标准的异步执行环境以外，RisingWave 作为一个云原生分布式数据库，还需要依赖 gRPC 进行内部通信，依赖 etcd 和 S3 等外部服务进行控制和存储，并且最终通过 Kafka 实现流数据的消费和生产。这些服务都需要通过网络进行信息传递，离开了它们 RisingWave 就无法作为一个完整系统运行起来。因此，我们在 madsim 核心功能的基础上，又基于网络模拟器先后实现了各种第三方服务的确定性模拟，并将它们包装在社区通用库的接口下，如 tonic, etcd-client, rust-rdkafka,aws-sdk-s3等。

其中，网络模拟器作为这些服务的公共基础，首先实现了 DNS、IP 地址解析等网络层拓扑的维护，然后在虚拟网络上实现了网络包路由、延迟和丢包的模拟，最后基于此提供了可靠传输（类 TCP）和数据报传输（类 UDP）两种通信原语，供上层服务使用。对于上层服务来说，只需要使用它们构造一个 RPC 服务，并实现服务接口的语义即可。值得一提的是，像 Etcd、Kafka、S3 这类分布式服务，它们的模拟器通常要比真实版本简单很多，因为我们只需要单节点单线程顺序执行，无需考虑并发、共识或容错。而它们发出的消息甚至无需序列化，直接在内存中传递对象指针即可。

实现了这些模拟器以后，像 RisingWave 这样的实际系统就可以在上面完整地运行了。除了 Mock 标准 API 以外，madsim 还在各层提供了额外的控制接口，用来在测试阶段控制模拟行为、获取系统信息，或者手动注入错误。例如：

任务：create_node, kill, restart, pause, resume（模拟节点崩溃或卡顿）
网络：set_ip ,clog, unclog（阻塞节点或链路）
磁盘：get_file_size, power_fail（模拟掉电丢失缓存）

具体的 API 定义可以参考 madsim 的 API 文档。

Madsim x RisingWave

最后我们来看看 RisingWave 是如何应用 madsim 对整个系统进行确定性测试的。

他们之间的关系可以用这样一张图来形象地表示：

图片截取自科幻动画 Rick and Morty。在这集故事中，外星人创造了一个非常逼真的世界模拟器，试图欺骗 Rick 来从他口中套取情报，而 Rick 识破了他们的诡计，使用一些技巧攻破并逃出了虚拟世界。对应到我们的系统中，Rick 就是即将接受测试的 RisingWave，外星人的模拟器就是 Madsim，而 Rick 的伙伴 Morty 则是像 Etcd、S3 这样的外部服务。虽然从图中很难看出来，但 Morty 其实也是外星人为了欺骗 Rick 而虚拟出来的，而这恰好也是我们系统中的做法。

下面我们会依次介绍 RisingWave 中已经应用的四种确定性测试，它们分别是：

单元测试
端到端测试
异常恢复测试
集群扩容测试

这些测试都已被集成到 CI 中，会在每次 PR 修改代码后自动运行，持续守护着代码质量和系统可靠性。

单元测试

单元测试作为最基础的测试项目，每个测例覆盖的模块和代码都比较小，而且测试逻辑相对简单固定。因此通过单元测试不太容易发现系统中潜在的并发问题。不过我们依然设立了确定性的单元测试，并据此发现了几个 Bug，它们都是由于测试逻辑本身的疏漏导致的。虽然没有挖掘到更深层的 Bug，但由于单元测试简单、易于集成，所以在初期对于 madsim 本身的开发和验证起到了很大帮助。

不过，确定性模拟对于单元测试还有其它方面的用途。比如对于超时处理的测试，在正常环境下就比较难做，因为要实际等待很长的时间。而在模拟器中，长时间的等待可以瞬间完成，测起来就很方便了。又比如，对依赖 etcd 的逻辑进行测试，需要启动一个 etcd 才能完成。而有了 etcd 模拟器之后，就可以在模拟环境下进行测试。这样同时也完成了对 etcd 模拟器的验证。

端到端测试

端到端测试是确定性模拟的主要应用场景。与单元测试相比，端到端测试覆盖了系统的各个组成部分，代码逻辑错综复杂，是最容易发生并发错误的场景。

要理解端到端测试，我们首先来看 RisingWave 的系统架构图：

图中实心颜色方块（Frontend，Compute，Meta Service，Compactor）是 RisingWave 的核心组件。每个方块代表一个进程，它们可能被部署在相同节点或不同节点上运行，之间通过 gRPC 进行通信。周边的图标代表与 RisingWave 进行交互的外部服务，包括维护元数据的 etcd，存储主要数据的 S3，以及以 Kafka 为代表的数据源和汇。用户可以通过 postgres 客户端与 Frontend 建立连接执行 SQL 命令，Frontend 则会将命令转发给多个 Compute，它们在 Meta Service 的协调下共同完成计算任务，过程中还可能向 S3 读写数据。

在传统的端到端测试中，我们会在一个节点上首先部署 etcd 和 minio（提供 S3 服务），然后启动一个 Meta Service 和若干 Frontend、Compute、Compactor 进程。接下来，我们使用 sqllogictest 程序读取预先写好的测试脚本，作为客户端向 RisingWave 集群发送命令并验证执行结果。在 CI 上跑完一轮完整测试大约需要 8 分钟左右。

而在确定性模拟测试中，上面提到的所有进程和服务，都被运行在一个单线程环境中。其中红色框内所依赖的外部服务则被替换成对应的模拟器。我们首先使用 madsim 提供的 API 创建虚拟节点，设置好它们的 IP 地址，然后在其中启动相关任务。建立起虚拟集群后，我们在“客户端节点”上调用 sqllogictest 的库函数，从真实系统中读取测试脚本，运行同样的测试内容。这样跑完一轮完整测试的时间只需约 2 分钟。

为了最大化并发带来的影响，sqllogictest 支持对不同的测试脚本并行执行（类似于 make -j），并且每个脚本会以独立的会话随机连接到不同的 Frontend。此时内部的处理逻辑以不可预知的顺序执行，偶尔就会引发错误。这时，我们只需拿着这次运行使用的随机种子，再重新执行一遍，就能得到一模一样的结果。接下来要做的就是打开日志，一点点排查并定位 Bug 的源头。如果觉得日志不够详细，还可以随时修改代码输出新的调试信息。这些都不会影响 Bug 的可复现性。

图：通过模拟器的 RPC 日志追踪一条 SQL 指令在多个节点上的执行过程

madsim 利用 tracing 库的 span 机制为每条日志加入了必要的上下文信息，如所在节点、任务和 RPC 请求，天然达到了真实系统中分布式追踪的效果。开发者通过阅读这一份日志即可理清系统中各个节点的行为和关联，提高了定位问题的效率。

通过确定性端到端测试，我们发现并修复了若干由并发引起的 Bug，包括 panic、死锁和计算错误。

异常恢复测试

如果说确定性模拟在正常的端到端测试中是牛刀小试，那么在异常环境下，它就开始大显神威了。

RisingWave 作为云上的分布式系统，需要容忍节点和网络故障等诸多异常情况。当任何一个节点掉线后，k8s 会及时拉起新的服务，并开始异常恢复步骤。如果此时集群中的其它节点同时崩溃，或者用户发来了新的请求，这些事件交织在一起就会导致非常刁钻的情况出现，很多是开发者在设计和编码时无法预料的。

为了充分检验 RisingWave 在各种异常环境下的可靠性，我们在上述端到端测试的基础上，不定期地随机杀掉各种节点，再将它们重新拉起来，然后观察系统是否还能向用户返回正确的结果。通常当系统发生内部故障时，客户端会收到一个错误响应。此时客户端会以指数退避的方式等待并重试若干次，如果长时间得不到正确结果就说明测试失败了。不过，我们暂时没有在数据修改的过程中注入异常，因为这些操作不具有原子性和幂等性，多次重试可能导致数据不是我们想要的结果。

在建立起异常恢复测试之后，我们的开发者经历了两个月相当痛苦的调试期，因为总有源源不断的新 Bug 被发现。比如没有错误处理导致的 panic，基于错误假设设置的断言，以及并发问题导致的结果错误（我们都记录在了这个 issue 里）。不过万幸的是，一旦这些问题被发现，就可以稳定的复现，从而很快被定位和修复。这对我们提升系统可靠性起到了非常大的帮助。

集群扩容测试

除了异常恢复以外，还有一个比较容易出错的场景是集群的扩容和缩容。RisingWave 作为云原生的一大特点就是可以根据任务负载对集群规模进行弹性伸缩，在负载重时添加节点增加算力，在负载轻时减少节点节约成本。每当集群配置发生变化，Meta Service 需要重新平衡各个节点负责的计算和数据。如果在任务迁移的过程中，又叠加了用户请求和异常恢复，对于系统的稳定性和正确性又是非常大的考验。

在集群扩容测试中，我们创建一个 Nexmark 数据源并建立好对应的查询管线，然后在不同节点之间随机调度任务分片，最后检查输出数据是否和没有调度时保持一致。这一测试同样帮助我们发现了大量问题，它们大致可以分为以下几类：

Compute 算子状态恢复和缓存过期的问题在正常端到端测试中，由于数据量较少，很多从对象存储拉数据的代码没有覆盖到。而在分片迁移的时候，各个节点都需要和对象存储同步数据，并且要及时清除自己的状态缓存。如果处理不当会导致严重的数据正确性问题。
Meta Service 上构建复杂数据流图的问题当多个分片同时发生迁移时，Meta Service 构建数据流图会发生比较复杂的情况。而在模拟器中我们可以十分方便地在短时间内给 Meta 发送密集的调度请求，模拟极端场景，大幅提高了代码覆盖率。
Source 数据源处理上的问题当新的数据流图下发到计算节点后，已有的数据流会被重新组合。此时容易发生数据遗漏或重复的问题。

这些还仅仅是单纯迁移时遇到的现象。今后我们会继续将集群扩容与异常恢复结合起来，进一步考验系统在极端场景下的稳定性。

持续集成

以上就是 RisingWave 中几种确定性测试的应用。但是只有测试本身是不够的，重要的是将它们加入到 CI 中，对每一次修改进行持续的测试，防止有新的 Bug 引入系统。

从一开始我们就提到，确定性模拟的一大优势就是运行速度快。上面的端到端测试也验证了这一结论，实测可以比实际运行快 4-5 倍左右。因此我们可以在相同的时间内运行更多的模拟测试，以提高 Bug 出现的几率。

RisingWave 的 CI 在一个 16 核 CPU 的容器环境中运行。因此我们会将每一项确定性测试用不同的种子并行执行 16 次，最大程度利用现有算力。同时尽量缩短执行时间，让每个 PR 都能在 20 分钟内跑完所有测试。除了 PR 以外，我们还会每天定时对 main 分支上的代码进行测试。而这时就没有了测试时间的限制，我们可以让它运行次数更多，从而提高问题出现的几率。

问题和局限

随着确定性测试一点点的落地应用，我们在享受它带来便利的同时，也逐渐体会到它的一些问题，并面临着新的挑战。

**测试时间的持续增长：**例如在持续集成测试中，随着新测例的不断加入和测试逻辑的日趋复杂，确定性测试的执行时间也在持续而缓慢的增长，最终超出我们的时限。尤其是有了错误注入之后，会有大量时间消耗在错误处理和异常恢复的逻辑中。一开始我们较为保守地设计为每条指令都触发一次异常恢复，这样的执行时间会是正常的几倍甚至几十倍。后来我们引入了一个触发异常的概率，可以手动在 0-1 之间调整。这样当时间比较紧时，就可以通过降低测试强度来换取执行速度。
需要进一步提高发现 Bug 的效率： 然而，简单粗暴的增加测试次数并不是挖掘更多 Bug 的正确方向。当最明显的 Bug 都被扫光之后，想要找到隐藏更深的问题，可能需要其它更聪明的办法。我们已经注意到业界做出的一些尝试，例如使用更加智能的任务调度策略，结合 Fuzzing 提高测试覆盖率等。这需要我们与软件测试领域的专家展开更多交流与合作。
局限于异步编程模式： Madsim 依赖于 Rust 语言的异步编程机制。但是 RisingWave 在实际开发中出于性能等方面的考虑，不可避免地在一些地方使用阻塞执行（例如 tokio::fs 存在性能问题，转而使用同步的 std::fs）。这些阻塞操作在单线程模拟器中不被支持。因此我们会通过条件编译的方法同时维护同步和异步两套代码，绕开这一问题。
局限于 Rust 语言项目： 近期 RisingWave 引入了越来越多的外部数据源连接器（如 Google Pub/Sub，MySQL CDC 等），以支持客户多样的需求。这些连接器可能使用其它语言或者依赖外部进程，为它们每一个编写模拟器的代价过高、收益较小。因此我们目前只维护了 Kafka 这一种数据源的模拟器。不过这一问题可能存在另一种解决方案：Facebook 近期公开了他们的确定性执行框架。与 madsim 不同，hermit 采用系统级别的技术方案，通过截获系统调用的方式来控制任意进程的执行顺序，不受编程语言的限制。目前我们也在尝试将其应用到 RisingWave 中进行跨进程的确定性测试，也许可以成为针对各种连接器的测试方案。

总结

这篇文章我们介绍了名为“确定性模拟”的测试技术，并展示了它在 RisingWave 中的应用。

确定性模拟通过将系统运行在单线程的模拟器上，使得 Bug 可以稳定复现，并且执行速度快，能够大幅提高我们发现问题、解决问题的效率。我们基于 Rust 语言的异步编程生态，开发了 Madsim 确定性测试框架，为 RisingWave 实现了多种场景的确定性测试。这些测试帮助我们发现了大量潜在问题，特别是在异常恢复和集群扩容方面，从而提升了 RisingWave 在各种极端场景下的可靠性。

我们理解这一技术的巨大价值和潜力，也深知如果没有 Rust 社区开发者打下的基础，这一切都不可能实现。因此我们也乐于尽己所能回馈社区。Madsim 从设计实现之初就和 RisingWave 完全解耦，因此适合于任何 Rust 语言项目。如果你也在用 Rust 构建分布式系统，欢迎使用 madsim 为你的项目实现确定性测试，共同分享系统测试的宝贵经验，一起消灭代码中的 Bug！