分布式系统中的持久性：共识艺术与备份系统设计

总结：

本次演讲深入探讨了分布式系统中持久性、可用性与共识之间的关系，揭示了共识是持久性转化为可用性的关键。演讲者从构建一个备份系统的第一性原理出发，详细介绍了如何实现严格可串行性（空间和时间上的一致性）和逻辑持久性。他指出，许多现有共识协议在处理磁盘故障和最大化可用性方面存在不足，因为它们通常假设存储完美或过度指定。通过引入预写日志（WAL）、日志结构合并树（LSM）以及双WAL和哈希链等高级技术，该系统不仅能有效防止数据丢失，还能在发生局部故障时保持逻辑可用性。最后，演讲展示了一个确定性模拟器，用于高效测试和修复分布式系统中的共识错误，强调了通过控制“逻辑时间”来加速调试的重要性，并以TigerBeetle数据库作为该理念的实际应用。

展示了三个机器上的数据复制与部分数据丢失的情况，演示了逻辑持久性下系统仍应保持可用并修复丢失副本 [ 00:05:40 ]

引言：共识的艺术与持久性 [0:00:46]

共识的魔力：将物理持久性转化为逻辑可用性 [0:00:53]
- 共识可以将三台物理机器或三个物理数据中心的持久性，转化为一个逻辑上高度持久和可用的单一逻辑机器。 [0:01:09]
- 共识的艺术在于理解物理到逻辑转换的核心是持久性与可用性的交换，效率越高，可用性越高。 [0:01:35]
构建备份系统：最低要求 [0:02:57]
- 1. 严格可串行性（Strict Serializability）: 这是最高级别的一致性，确保系统在空间和时间上都保持一致。 [0:03:11]
  - 松散地说，严格可串行性是空间和时间上的一致性，即请求必须能够原子地操作系统中的所有值，且操作结果按时间顺序可见。 [0:03:42]
  - 客户端必须看到数据具有逻辑一致性，系统作为一个整体必须呈现逻辑一致性，即使物理机器可能存在分区。 [0:04:21]
  - 缺乏一致性看起来很像数据丢失，因此需要防止数据丢失的表象和实际发生。 [0:04:42]
- 2. 逻辑持久性（Logical Durability）: 系统可能使用多台机器存储数据副本，即使部分副本丢失，如果足以重建数据，系统也不应表现为数据丢失，并且必须保持可用。 [0:05:07]
  - 如果所有副本都丢失，系统则应正确地保持不可用。 [0:05:25]
    
    在逻辑持久性下，即使多数数据副本丢失，系统仍应保持可用并修复丢失副本 [ 00:05:40 ]
  - 挑战现有协议：许多现有共识协议无法处理单个数据项多数副本丢失但整体数据可恢复的情况，例如Raft可能将整个集群视为已丢失，即使仍有足够的持久性来维持可用性。 [0:06:22]
  - 效率问题：常见做法是直接将故障机器从集群中移除并重新复制到新机器，这导致恢复时间膨胀，并丢弃了机器上其他未损坏数据的可用性，可能在修复完成前导致整个集群丢失。 [0:07:20]
  - 最优解：更优的方法是只复制丢失的数据（例如从机器0或1复制“a”到机器2），从而更快地修复持久性并最大化可用性。 [0:08:07]
效用函数：最大化逻辑可用性。 [0:08:50]
历史背景：Viewstamped Replication (VSR) 是Brian Oki在1988年提出的第一个能够容忍网络分区的共识协议，其标题就强调了“高可用性”，这表明了复制、持久性和高可用性之间的内在关系。 [0:09:01]
- 物理可用性与逻辑可用性：CAP定理中定义的可用性是物理或整体可用性的受限模型，即非故障节点接收到的每个请求都必须得到响应。 [0:10:00]
- CAP定理的阿喀琉斯之踵：CAP定理的证明是基于物理可用性，而非逻辑可用性，这限制了其适用范围。 [0:11:02]
- 关键在于区分：设计系统时，必须小心区分物理和逻辑概念，而不是混淆它们。 [0:11:29]

从第一性原理构建备份系统：持久性 (Durability) [0:15:05]

单机持久性：从一个简单的状态机函数fn execute开始。 [0:15:08]
- 函数特性：该函数返回void，意味着它内部不会失败且没有错误处理，所有操作都是同步的，以保持业务逻辑的简单性。 [0:15:36]
- 确定性：给定相同的请求序列，函数将达到相同的状态。 [0:16:00]
- 批量处理：每个请求可达1MB，可以批量处理数千个逻辑请求，分摊成本，并作为性能基准。 [0:16:09]
- 问题：目前所有状态都在内存中，不具备持久性，一旦断电将丢失数据。 [0:16:32]
引入预写日志（WAL）：为了实现持久性，在执行请求之前将其追加到磁盘上的预写日志文件中。 [0:17:08]
- WAL不仅保留了请求，还保留了它们的顺序，因此在启动时可以通过重放WAL来恢复到之前的状态。 [0:17:15]
- 真正的持久性：使用O_DSYNC | O_DIRECT等直接I/O方式写入磁盘，以确保数据真正写入并处理fsync失败。 [0:17:26]
WAL的挑战与解决方案：
- 启动时WAL大小确定：如何知道WAL中有多少请求？文件系统inode可能被损坏，导致错误的文件大小。 [0:17:57]
- 断电时日志截断：如果断电发生在请求只写入一半时，如何处理？ [0:18:15]
- 校验和不足：仅靠校验和无法区分断电导致的部分写入和数据位腐烂，盲目截断可能导致数据丢失。 [0:18:20]
- 数据库的假设：许多数据库如SQLite假设磁盘读取的数据与写入的完全一致，不期望存储故障。 [0:19:38]
- “协议感知恢复” (Protocol-Aware Recovery)：2018年的研究提出解决方案，使用两个WAL。 [0:19:09]
  
  通过双预写日志（WAL）机制，一个记录请求，另一个记录提交头，以确保在断电或数据损坏时的可靠恢复 [ 00:20:05 ]
  - 双WAL：第一个WAL记录完整的请求，第二个WAL记录一个小的提交头信息。 [0:20:01]
  - 恢复逻辑：启动时如果第一个WAL的校验和损坏，检查第二个WAL是否存在对应的提交记录。如果存在，表明数据已提交但后来损坏，需要修复；如果不存在，表明是断电，可以安全截断。 [0:20:17]
优化启动时间：日志结构合并树（LSM）与检查点 [0:20:46]
- LSM：将内存中的状态通过LSM树（Log-Structured Merge-tree）逐步地、增量地分页写入磁盘。 [0:20:50]
  - LSM对闪存友好，采用写时复制（copy-on-write）技术，从不原地覆盖数据块，而是写入新块。 [0:21:05]
  - 磁盘被视为固定大小数据块的简单数组，由LSM寻址。 [0:21:18]
  - LSM的写入过程独立于状态机函数，状态机仍然简单且不会失败。 [0:21:52]
- 检查点（Checkpoint）：定期执行检查点，将日志中所有已处理的请求都持久化到LSM树中，然后可以截断WAL，加速下次启动。 [0:22:07]
- 超级块（Superblock）：检查点信息写入一个特殊的“超级块”，它位于磁盘起始位置，包含LSM树的根指针和WAL的重放起始点。 [0:22:24]
- 磁盘是分布式系统：磁盘本身也是分布式系统，会发生诸如“潜在扇区错误”（latent sector errors）等问题，导致部分扇区暂时或永久分区。 [0:23:03]
  - 超级块的冗余：为确保超级块的可靠性，创建多份副本，并采用法定人数（quorum）机制来读取最新副本，从而容忍一定数量的故障。 [0:23:39]
  - 全局RAID优于本地RAID：整个系统作为一个“全局RAID”来管理，无需在每台机器上运行本地ZFS RAID，因为逻辑组合已经提供了所需的持久性。 [0:24:06]
持久性总结：通过上述方法，单台物理机器可以在磁盘扇区层面提供最大程度的持久性。然而，如果整台机器丢失，所有数据仍然会丢失，因此需要复制。 [0:24:32]

复制与共识 (Replication & Consensus) [0:25:09]

复制的必要性：为了实现逻辑持久性（即机器故障时数据不丢失），需要将状态机复制到多台机器上，进行实时备份。 [0:25:09]
- 两阶段提交：主节点在追加日志的同时，并行复制请求到至少一台备份机器，并等待收到其中一台的确认（ACK）后才回复客户端。 [0:25:38]
- 最优复制：这种“至少2/3机器”的复制方式，对于实现持久性而言，已接近最优。 [0:25:55]
- 手动故障转移：此时虽然有了逻辑持久性，但如果主节点故障，仍需要手动进行故障转移，导致停机时间甚至潜在的数据丢失。 [0:26:10]
共识的自动化：共识协议的作用是自动化故障转移过程，确保日志能够完美地拼接在一起，无需手动协调备份。 [0:26:22]
- 共识并非额外成本：如果已经关注持久性并进行了复制，共识协议的额外开销微乎其微。99%的时间是在进行复制，共识仅在故障转移的瞬间发挥作用。 [0:27:19]
VSR (Viewstamped Replication) 的先驱地位：
- VSR由Brian Oki在1988年开创，James Cowling和Barbara Liskov于2012年对其进行了修订，使其更易于理解。 [0:27:43]
- VSR与Raft的比较：Raft与VSR非常相似，但VSR有一个重要优势：它能通过简单的数字取模运算预测下一个主节点，无需复杂的选举过程。 [0:28:01]
- VSR还支持直接在磁盘上运行（如本备份系统），并提供了额外的恢复协议以应对频繁的机器崩溃。 [0:28:24]
协议感知恢复的实际应用：
- 处理多数副本丢失：即使A和B的多数副本丢失，但由于C的日志头有多数副本且通过哈希链指向A和B，系统可以知道A和B曾被多数提交，因此可以修复。 [0:29:07]
- 处理单机数据损坏：当发现一个副本损坏，但其他机器没有该数据副本时，协议会与集群多数节点确认该数据是否从未提交，如果确认，则可以安全地截断日志。 [0:30:07]
- 不仅是备份：这意味着系统不仅进行实时备份，还在持续测试和修复这些备份。 [0:30:57]
过度指定的问题与优化：
- Raft的规范：Raft协议要求领导者在将命令追加到日志并安全复制到多数节点后，才将其应用到状态机。 [0:31:11]
- 优化空间：实际上，只需在回复客户端之前等待复制完成即可。其他操作（追加、复制、甚至投机性执行）可以并行进行，只要能够在复制失败时撤销投机性执行。 [0:31:40]
- 投机性状态机执行：将CPU执行与复制操作并行进行，可以隐藏复制的延迟，使系统性能接近“光速基准”。 [0:32:26]
- 最终，可以构建一个关注持久性的备份系统，其速度几乎与不考虑持久性的缓存系统一样快。 [0:32:46]

共识的艺术：测试 (The Art of Testing Consensus) [0:33:16]

测试目标：测试逻辑一致性，并挑战逻辑可用性与逻辑持久性之间交换的效率。 [0:33:19]
物理时间的挑战：从外部对系统进行黑盒测试，寻找和修复bug非常耗时。 [0:33:45]
确定性模拟器：将物理时间转化为逻辑时间，使测试具有确定性。 [0:34:10]
- 控制时间和空间：模拟器就像一部可以快进、重放和重看电影，加速bug发现和修复过程。 [0:34:16]
- TigerBeetle的模拟器：TigerBeetle运行分布式数据库的实际代码，将其编译为WebAssembly并在浏览器中运行，上面叠加一个游戏引擎。 [0:34:27]
- 演示场景：
  - 场景1：完美世界，展示请求的复制和确认过程。 [0:35:04]
  - 场景2：引入网络分区、丢包和重放（1%的概率）。VSR协议成功选举新的主节点，系统保持可用。模拟器是“协议感知”的，它理解共识并检查可用性是否符合持久性。 [0:36:12]
  - 场景3（“放射性模式”）：引入严重的磁盘故障（读路径8%损坏，写路径9%损坏）和非确定性。系统仍然能够生存。 [0:37:37]
TigerBeetle的实践：TigerBeetle是一个用Zig语言编写的开源数据库，它将这些原则付诸实践。 [0:32:55]