Celld 中的确定性模拟测试

# celld 中的确定性模拟测试：探索执行顺序并复现缺陷 · celld 来源：https://celld.dev/docs/engineering/deterministic-simulation-testing/ 我们正在构建celld (https://github.com/denoland/celld/blob/12d5b6333fe52717325addcfe1e99e9fd4f77bcd/README.md)，这是一个在你自己的机器上运行 Cloudflare Workers 和 Durable Objects 应用程序的运行时\. 它可以仅依赖一个兼容 S3 的对象存储作为外部服务运行\. celld 是一个分布式系统\. 要让分布式系统可靠运行很难，部分原因在于，即使我们知道有哪些陷阱，仍可能无意中依赖一些在实际环境中并不成立的假设\. Peter Deutsch 的《分布式计算的八大谬误》 (https://nighthacks.com/jag/res/Fallacies.html)列出了八个这样的假设，包括“网络是可靠的”和“延迟为零”\. 一个缺陷可能取决于延迟消息、写入失败和节点重启的特定发生顺序\. 在下一次测试运行中，这些事件可能以不同的顺序发生，从而使失败难以复现\. 我们需要能够重复发生失败的那次运行，以便调查原因，并检查所提出的修复是否真正解决了问题\. 这就是我们使用**确定性模拟测试 \(DST\)**的原因\. 我们的模拟器仍在开发中，尚未包含在 celld 的公开代码仓库中，但它已经发现了此前未知的缺陷\. 在本文中，我们将介绍 DST 在 celld 中的工作原理，以及它如何帮助我们发现、复现并修复其中一个缺陷\. ## DST 在 celld 中的工作原理 DST 在由模拟器控制的环境中运行 celld 的生产代码\. celld 中的一个**cell** (https://github.com/denoland/celld/blob/12d5b6333fe52717325addcfe1e99e9fd4f77bcd/README.md)运行应用程序代码，并拥有自己的 SQLite 数据库\. 在各个 cell 执行工作时，celld 会处理传入请求、存储操作完成和定时器触发等事件\. 选择下一个事件的代码与处理该事件的代码彼此分离\. 这使模拟器能够控制事件顺序，同时运行与生产环境相同的事件处理代码 (https://github.com/denoland/celld/blob/12d5b6333fe52717325addcfe1e99e9fd4f77bcd/crates/celld/actor.rs#L2461-L2491)\. 模拟器还控制异步任务何时运行 (https://github.com/denoland/celld/blob/12d5b6333fe52717325addcfe1e99e9fd4f77bcd/crates/celld/lib.rs#L309-L320)，以及对象存储如何响应 (https://github.com/denoland/celld/blob/12d5b6333fe52717325addcfe1e99e9fd4f77bcd/crates/celld/bucket.rs#L533-L551)\. 它可以延迟一次写入，也可以让写入失败\. 它可以推进模拟时间，而无需等待真实时间流逝\. 我们利用这种控制能力，测试重试和闹钟等依赖时间的行为如何与其他事件相互作用\. 我们配置模拟器可以探索哪些请求和故障\. 在这些限制内，它通过随机选择来生成请求、选择接下来运行什么、决定存储操作成功还是失败，以及选择发生哪些故障及其发生时间\. **种子**是其随机数生成器的初始值\. 使用相同的代码、设置和种子，我们就会得到相同的序列、中间状态和结果\. 我们可以通过更换种子探索不同的运行，再重复发生失败的那次运行，以追踪哪里出了问题\. 每次动作之后，检查器都会利用观察到的响应和已存储的数据来检验**不变量**：即我们定义的、系统在整个运行过程中必须始终满足的条件\. 测试会使用模拟环境初始化 celld，然后探索各种动作，直到达到配置的上限\. 用伪代码表示如下： `` const simulation = createSimulation({ settings, seed }); for (let step = 0; step < settings.maxActions; step++) { const candidates = simulation.availableActions(); if (candidates.length === 0) { checkCompletion(simulation); break; } const action = simulation.choose(candidates); simulation.run(action); checkInvariants(simulation); } `` 这里的动作是模拟器可以推进的事项：交付请求、让任务运行、推进模拟时钟，或完成存储操作\. 如果没有可执行的动作，测试就会检查完成条件，例如所有计划中的请求是否都已完成\. 下面的简化回放从 Cell A 已向 SQLite 插入一行之后开始\. 请留意，在 celld 收到确认之前，数据是如何保存到对象存储中的\. 在这个间隙中，其他请求或后台任务可以运行，而 celld 仍在等待向客户端返回成功响应\. 当这些操作以意想不到的方式交错执行时，就可能出现缺陷\. 模拟器分别控制这些步骤，使我们能够探索不同的执行顺序，并回放暴露缺陷的那些顺序\. 按**下一步**，逐步查看动作的选择、执行动画及其结果\. **候选动作** - 发送 SQLite 更改；让对象存储接收这些更改\. **已选动作** 客户端celld兼容 S3 的存储模拟Cell ACell BSQLiteCell CSQLiteSQLite等待数据◷ 等待插入行新行数据库更改II 响应客户端celld兼容 S3 的存储模拟Cell ACell BSQLiteCell CSQLiteSQLite等待数据◷ 等待插入行新行数据库更改II 响应 1. 选择 2. 执行 3. 结果 初始状态 该行已在 SQLite 中\. 客户端仍在等待成功响应\. 步骤**0**/ 12 上面的回放展示了一个成功的请求\. 接下来，我们将看看一种暴露了 celld 缺陷的执行顺序\. ## 模拟器发现的闹钟竞态 闹钟会安排一个 cell 在指定时间运行应用程序代码\. 在此之前，该 cell 无需一直驻留在内存中：celld 可以卸载空闲的 cell (https://github.com/denoland/celld/blob/12d5b6333fe52717325addcfe1e99e9fd4f77bcd/crates/logic/lib.rs#L5694-L5716)，为其他 cell 腾出空间，并及时重新加载它以运行闹钟\. 闹钟的计划触发时间存储在该 cell 的 SQLite 数据库中 (https://github.com/denoland/celld/blob/12d5b6333fe52717325addcfe1e99e9fd4f77bcd/crates/celld/storage.rs#L466-L472)\. 如果该 cell 已被卸载，仅通过 SQLite 查找它的闹钟就意味着需要再次打开它的数据库\. 对每个 cell 都这样做会带来很大开销，因此 celld 会改为扫描对象存储中的**唤醒条目** (https://github.com/denoland/celld/blob/12d5b6333fe52717325addcfe1e99e9fd4f77bcd/crates/celld/wake.rs#L33-L89)\. 每个条目都标明一个 cell 及其重新激活的时间\. cell 激活后，celld 会从 SQLite 读取计划触发时间，以确定何时运行闹钟\. 在我们发现这个缺陷时，celld 会复用唤醒条目，以减少对对象存储的写入次数\. 例如，应用程序可以删除一个 10:00 的闹钟，然后设置一个新的 10:05 闹钟\. 如果 10:00 的唤醒条目仍然存在，celld 就可以复用它，在 10:00 重新激活该 cell，这对于新闹钟来说足够早\. cell 激活后，celld 会从 SQLite 读取 10:05，并等待到该时间再运行闹钟\.1 (https://celld.dev/docs/engineering/deterministic-simulation-testing/#fn-eviction) 删除 10:00 的闹钟会从 SQLite 中清除其计划触发时间\. 一旦这一更改保存到对象存储中，celld 就会向客户端返回成功响应\. 一个独立的清理任务会在稍后移除 10:00 的唤醒条目，因此客户端无需等待这次额外的存储操作\. 所以，当旧的清理任务仍在等待运行时，客户端就可以设置 10:05 的闹钟\. 在 celld 确认 10:05 的闹钟已设置之后，必须保留一个能够在 10:05 之前或当时重新激活该 cell 的唤醒条目\. 模拟器会检查这一条件是否一直成立，直到闹钟运行或被取消\. 下图展示了当旧的清理任务在 10:05 的闹钟设置之后运行时，这个不变量如何遭到违反\. **候选动作** - 删除 Cell A 的 10:00 闹钟\. **已选动作** 客户端celld兼容 S3 的存储模拟Cell ASQLite 中的闹钟10:00等待中的任务删除 10:00 唤醒条目10:00 唤醒条目存在删除 10:00 闹钟已删除删除 10:00客户端celld兼容 S3 的存储模拟Cell ASQLite 中的闹钟10:00等待中的任务删除 10:00 唤醒条目10:00 唤醒条目存在删除 10:00 闹钟已删除删除 10:00 1. 选择 2. 执行 3. 结果 4. 检查 初始状态 Cell A 在 SQLite 中有一个 10:00 的闹钟，在对象存储中有一个 10:00 的唤醒条目\. 步骤**0**/ 21 在这次运行中，当旧的清理任务仍在等待时，删除 10:00 闹钟和设置新的 10:05 闹钟都已返回成功响应\. 当模拟器最终推进该清理任务时，它移除了新闹钟仍然需要的 10:00 唤醒条目\. 检查器报告了不变量违反：10:05 的闹钟仍然设置在 SQLite 中，但已没有任何唤醒条目可以重新激活该 cell\. 如果节点在 10:05 之前重启，缺失的唤醒条目可能导致闹钟无法运行，尽管此前已返回成功响应\. 模拟器通过探索请求和待处理工作，找到了这一导致失败的顺序\. 我们并没有编写一个预先规定这一序列的测试\. ## 复现并修复竞态 我们使用相同的代码、设置和种子回放了这次失败\. 每次运行都让我们能够检查旧的清理任务删除所需唤醒条目的那个时刻，而无需再次寻找导致失败的顺序\. 此后，我们修改了唤醒条目的设计\. 每次设置新闹钟，都会在对象存储中获得一个独立的条目\. 针对旧闹钟的延迟删除只能移除那个旧条目，使新条目保持完整\. 一旦 celld 确认旧条目不再需要，就会将其移除\. 我们将这次失败的运行转化为一个回归测试，重复上面展示的请求和清理顺序\. 它会检查新闹钟是否保留了可用的唤醒条目\. 回归测试会在运行过程中检查不变量，而不只是检查结束时的状态\. 如果唤醒条目消失后又被恢复，只检查最终状态就会漏掉这次违反\. ## 下一步 模拟器仍在开发中，但它已经帮助我们发现并修复了 celld 中此前未知的缺陷\. 接下来，我们将测试更多请求、存储故障和节点重启的组合\. 例如，节点可能在存储服务中断期间重启，并在存储恢复之前收到新请求\. 我们还将为 celld 的更多保证添加检查\. 例如，一个被报告为成功的写入必须在节点重启后仍然保留\. 当这些测试发现缺陷时，我们可以回放失败、修复缺陷，并将该序列保留为回归测试\. 1. 如果 celld 在等待 10:05 时需要逐出该 cell，它会先确保一个 10:05 的唤醒条目已就位\.↩ (https://celld.dev/docs/engineering/deterministic-simulation-testing/#fnref-eviction)