当前位置：首页 > news >正文

Raft算法学习（1）博士论文大纲

news 2025/5/21 6:17:51

参考资料
原文一共257页，其中前六章为算法重点介绍，第七章有点像A/B TEST

论文标题： 共识：连接理论与实践 (CONSENSUS: BRIDGING THEORY AND PRACTICE)
作者： Diego Ongaro
日期： 2014年8月
机构： 斯坦福大学 (哲学博士)

论文总体目标： 通过设计Raft——一个比现有替代方案（如Paxos）更易于理解和实践的共识算法，为学习共识和构建复制状态机创建一个更好的基础。

前置部分重点：

摘要 (Abstract):
- 指出了Paxos算法的难点。
- 提出了Raft算法，其设计目标是可理解性。
- Raft的核心：首先进行领导者选举，然后由领导者中心化地进行决策和日志复制。
- 领导者选举使用投票和随机化超时。数据从领导者流向其他服务器。
- 日志复制利用一个简单的不变性来减少状态空间。
- Raft具有实用性：解决了客户端交互、集群成员变更（一次一个服务器）和日志压缩等问题。
- 声称Raft在教学和实现方面优于Paxos，其论据包括用户研究、形式化规约/证明、良好的领导者选举性能以及与Multi-Paxos相当的性能。
前言 (Preface):
- 扩展了Ongaro和Ousterhout合著的论文 “In Search of an Understandable Consensus Algorithm” [89]。
- Raft网站 [92] 提供视频和可视化演示。
致谢 (Acknowledgments) (关键技术贡献者):
- David Mazières 和 Ezra Hoch：在早期Raft版本中发现bug。
- Hugues Evrard：在形式化规约中发现一个遗漏。
- 用户研究支持：Ali Ghodsi, David Mazières, Scott Klemmer, Nelson Ray。Paxos幻灯片改编自Lorenzo Alvisi。
- CoreOS (Blake Mizerany, Xiang Li, Yicheng Qin)：影响了更简单的单服务器成员变更方案。
- Anirban Rahut (Splunk)：指出了新服务器以空日志加入时的性能问题。
- Eddie Kohler, Maciej Smolen´ski：指出了提交规则下一个潜在的日志增长问题。
- Alexander Shraer：阐明了Zab中成员变更的工作方式。

第1章：引言 (Introduction)

问题背景： 现代数据中心系统是动态的，服务器/网络故障频繁。系统需要自动适应和容错。
共识的角色： 允许多台机器作为一个一致的整体工作，并在部分成员发生故障时仍能继续运行。是构建可靠大规模系统的基础。
现有解决方案的不足 (在撰写论文时):
- 许多系统存在单点故障或采用临时的、不安全的复制方案。
- Paxos是主流算法，但出了名地难以理解和实现。
- 其他算法 (Viewstamped Replication, Zab) 的设计并未将可理解性作为首要目标。
Raft的目标：
1. 可理解性 (首要目标): 让广大受众能够轻松学习并建立直观认识。
2. 完整性与实用性： 为构建系统提供完整的基础，减少开发者的设计工作。
3. 安全性： 在所有非拜占庭条件下都能正确运行。
4. 可用性： 在典型操作条件下功能正常。
5. 效率： 常见操作性能良好。
Raft为提高可理解性采用的设计技术：
1. 分解 (Decomposition): 将领导者选举、日志复制和安全性分开。
2. 状态空间简化 (State Space Reduction): 减少不确定性 (例如，日志不允许有空洞) 并简化服务器交互。使用随机化定时器简化领导者选举。
本论文的主要贡献：
1. Raft共识算法的设计、实现和评估 (源于可理解性关注点的新特性，例如更强的领导者角色)。
2. 通过用户研究评估Raft的可理解性 (与Paxos对比)。
3. Raft领导者选举机制的设计、实现和评估 (随机化定时器)。
4. Raft集群成员变更机制的设计和实现 (一次一个服务器)。
5. 对其他必要组件的深入讨论 (客户端交互、日志压缩)。
6. Raft的安全性和形式化规约证明。
LogCabin [86]: 作为本研究一部分开发的Raft开源实现。

第2章：动机 (Motivation)

2.1 通过复制状态机 (RSM) 实现容错：
- 共识算法用于构建RSM。
- 服务器计算状态的相同副本，并在部分服务器故障时仍能继续运行。
- 通常使用复制日志实现 (图2.1)。
- 共识模块保持日志一致。已提交的命令由确定性状态机应用。
- 实用共识算法的特性：
  - 安全性 (在非拜占庭条件下)。
  - 可用性 (如果多数服务器可操作且能够通信)。
  - 安全性的时间无关性 (异步模型)。
  - 效率 (常见情况：单轮RPC到多数节点)。
2.2 RSM的常见用例：
- 小型 (3-5台服务器) 共识组用于协调：组成员关系、配置管理、锁 (图2.2a)。
- 大型系统的领导者将其关键状态存储在RSM中以实现故障转移 (例如 GFS, HDFS, RAMCloud) (图2.2b)。
- 大规模存储系统将数据分区到多个RSM上，使用2PC进行跨分区操作 (例如 Megastore, Spanner, Scatter) (图2.3)。
2.3 Paxos的问题所在：
- Paxos (单提案Paxos和Multi-Paxos) 是最常被教授/使用的。
- 缺点1：异常难以理解。
  - 完整解释晦涩难懂。简化解释仍然具有挑战性。
  - 假设：晦涩源于以单提案子集为基础 (两个密集、微妙的阶段)。
- 缺点2：不是构建实用实现的良好基础。
  - 对于Multi-Paxos没有广泛认可的算法。
  - Lamport的描述多为草图；各种完善版本互不相同。
  - Paxos架构不适合实用系统 (单提案分解复杂)。围绕日志进行顺序追加设计更简单。
  - 对称的对等核心对于一系列决策不如基于领导者的方法直观。
- 结果： 实用系统通常与Paxos文献描述大相径庭 (例如 Chubby的引言 [15]: “最终系统将基于一个未经证明的协议”)。

第3章：Raft基础算法 (Basic Raft Algorithm)

3.1 为可理解性而设计： 重申分解和状态空间简化。
3.2 Raft概述：
- 图3.1：算法精简摘要。
- 图3.2：关键特性 (选举安全性、领导者只追加、日志匹配、领导者完整性、状态机安全性)。
- 分解：领导者选举、日志复制、安全性。
3.3 Raft基础：
- 服务器集群 (例如5台服务器容忍2台故障)。
- 服务器状态：Follower (跟随者), Candidate (候选人), Leader (领导者) (图3.3)。正常操作：1个领导者，其他为跟随者。
- 任期 (Terms)：任意长度，连续编号。作为逻辑时钟 (图3.4)。以一次选举开始。
  - 服务器交换当前任期号；任期号大的获胜。任期号过期的服务器转为跟随者。
- RPC (远程过程调用)：
  - RequestVote (请求投票)：由候选人在选举期间发起。
  - AppendEntries (追加条目)：由领导者为日志复制和心跳发起。
3.4 领导者选举 (Leader Election)：
- 心跳机制触发选举。
- 跟随者如果在election timeout (选举超时) 内未收到有效RPC，则开始选举。
- 候选人：增加当前任期号，转换到候选人状态，为自己投票，并行发出RequestVote RPC。
- 候选人的结果：
  1. 赢得选举：获得多数服务器对同一任期的投票。成为领导者，发送心跳。(每台服务器在每个任期最多为一个候选人投票，先到先得，并有§3.6的日志最新性限制)。
  2. 其他服务器成为领导者：如果新领导者的任期 (在AppendEntries RPC中) ≥ 候选人当前任期，候选人转为跟随者。
  3. 无获胜者 (选票分裂)：选举超时，候选人开始新一轮选举 (增加任期号)。
- 随机化选举超时 (Randomized Election Timeouts)： (例如150-300ms) 用于确保选票分裂罕见且能快速解决。分散服务器。
3.5 日志复制 (Log Replication)：
- 领导者将客户端命令追加到其日志，发出AppendEntries RPC进行复制。
- 当条目安全复制 (到多数节点) 后，领导者将其应用于其状态机，向客户端返回结果。
- 日志结构 (图3.5)：条目包含命令和任期号。顺序索引。
- 已提交条目 (Committed Entries)：复制到多数节点。提交领导者日志中所有在它之前的条目。领导者跟踪最高的commitIndex (已提交索引)。跟随者按顺序应用已提交条目。
- 日志匹配特性 (Log Matching Property)：
  1. 如果不同日志中的两个条目具有相同的索引和任期号，则它们存储相同的命令。
  2. 如果不同日志中的两个条目具有相同的索引和任期号，则它们之前的所有条目都相同。
  - 由AppendEntries一致性检查保证：RPC包含prevLogIndex (前一个日志索引) 和prevLogTerm (前一个日志任期)。如果不匹配，跟随者拒绝。
- 日志不一致 (图3.6)：领导者崩溃可能导致。领导者通过覆盖冲突条目来强制跟随者日志与其匹配。
- nextIndex (下一个索引)：领导者为每个跟随者维护，下一个要发送的条目的索引。
- 领导者从不覆盖/删除其自身日志中的条目 (领导者只追加特性)。
3.6 安全性 (Safety)：
- 3.6.1 选举限制 (Election Restriction)： 确保领导者完整性。候选人的日志必须至少与它联系的多数节点中的任何其他日志一样新。
  - “最新”：比较最后条目的索引和任期。任期大的获胜。任期相同，日志长的获胜。
  - 在RequestVote RPC中实现。如果投票者自己的日志更新，则拒绝投票。
- 3.6.2 提交先前任期的条目 (Committing Entries from Previous Terms)： (图3.7强调了为何这很棘手)
  - Raft 从不通过计算副本数来提交先前任期的日志条目。
  - 只有领导者当前任期的日志条目才通过计算副本数来提交。
  - 一旦当前任期的条目被提交，所有先前的条目都会因日志匹配而间接提交。
- 3.6.3 安全性论证 (领导者完整性证明草图) (Safety Argument (Proof Sketch for Leader Completeness))： (图3.8展示了一个关键投票者)
  - 假设领导者完整性不成立，导出矛盾。
  - 如果领导者T (任期T) 提交了一个条目，但领导者U (任期U > T) 没有存储它。
  - 必须有一个"投票者"服务器接受了来自T的条目并投票给了U。
  - 这个投票者的日志意味着U的日志也必须包含该条目。
  - 状态机安全特性：如果一台服务器应用了一个条目，则没有其他服务器会为相同的索引应用不同的命令。(由领导者完整性和按顺序应用条目得出)。
3.7 跟随者和候选人崩溃 (Follower and Candidate Crashes)： 通过RPC重试处理。Raft RPC是幂等的。
3.8 持久化状态和服务器重启 (Persisted State and Server Restarts)：
- 每台服务器持久化：currentTerm (当前任期)、votedFor (为谁投票)、日志条目。
- commitIndex可以在重启时重新初始化为0。
- 状态机可以是易失的 (从日志/快照重放) 或持久的 (如果是，则lastApplied (最后应用索引) 也必须持久化)。
3.9 时间和可用性 (Timing and Availability)：
- 安全性不得依赖于时间。可用性不可避免地依赖于时间。
- 时间要求：broadcastTime << electionTimeout << MTBF
  - broadcastTime (广播时间)：向所有服务器发送RPC并获得响应的时间。
  - electionTimeout (选举超时)：例如10-500ms。
  - MTBF (平均故障间隔时间)：数月。
3.10 领导权转移扩展 (可选) (Leadership Transfer Extension (Optional))：
- 可用于维护或首选领导者。
- 过程：前任领导者停止客户端请求，更新目标服务器的日志，向目标发送TimeoutNow RPC。目标开始选举，很可能获胜。
3.11 结论： Raft使用最少的机制来解决核心共识问题。简单性是为可理解性而设计的结果。为清晰起见，省略了一些优化 (例如更快的选票分裂检测)。

第4章：集群成员变更 (Cluster Membership Changes)

需要自动化配置变更 (替换服务器、更改复制级别) 以避免手动错误和停机。
Raft允许集群在变更期间正常运行。(图4.1 AddServer/RemoveServer RPC)。
4.1 安全性 (Safety)：
- 从旧配置 (Cold) 直接切换到新配置 (Cnew) 可能不安全 (图4.2，可能导致脑裂)。
- Raft将变更限制为一次添加/删除单个服务器。这确保了多数派总是重叠的 (图4.3)。
- 配置存储为特殊的日志条目。
- 当领导者收到对Cold的添加/删除请求时：
  1. 将Cnew条目追加到其日志。
  2. 使用正常的Raft机制复制Cnew条目。
  3. 服务器一旦在其日志中存储了Cnew条目就切换到Cnew (不等待提交)。
  4. Cnew条目的决策 (投票、提交) 使用Cnew规则。
- 一旦Cnew条目已提交：
  1. 领导者可以确认变更完成。
  2. 被移除的服务器 (如果有) 可以关闭。
  3. 可以开始进一步的配置变更 (防止不安全的重叠)。
4.2 可用性 (Availability)：
- 4.2.1 让新服务器追赶上来 (Catching Up New Servers)： (图4.4显示风险)
  - 新服务器首先作为非投票成员加入。
  - 领导者向其复制日志条目。
  - 一旦新服务器充分追赶上 (例如，经过固定轮数，最后一轮 < 选举超时，图4.5)，实际的重新配置才继续。
- 4.2.2 移除当前领导者 (Removing the Current Leader)：
  - 选项1：领导权转移 (§3.10)。
  - 选项2 (原始方案)：领导者管理自己的移除，在Cnew提交之后下台。(图4.6显示了为什么领导者必须在Cnew提交前保持领导地位)。
- 4.2.3 干扰性服务器 (Disruptive Servers)：
  - 一个从Cnew中移除的服务器可能收不到心跳，超时，增加任期，开始新的选举，干扰当前领导者。(图4.7)。
  - 预投票阶段 (候选人在增加任期前请求预投票) 不是一个完整的解决方案。
  - Raft解决方案：如果服务器在收到当前领导者心跳的最小选举超时内收到RequestVote，它不更新其任期也不投票。(防止在领导者健康时被过时服务器罢免)。
- 4.2.4 可用性论证 (Availability Argument)： 总结了为什么这些机制能确保可用性。
4.3 使用联合共识进行任意配置变更 (更复杂的原始方法) (Arbitrary Configuration Changes using Joint Consensus (More Complex Original Approach))：
- 一次处理多个服务器的变更。
- 集群过渡：Cold -> Cold,new (联合共识) -> Cnew。(图4.8时间线)。
- 联合共识 (Cold,new)：
  - 日志条目复制到Cold和Cnew中的所有服务器。
  - 任一配置中的任何服务器都可以担任领导者。
  - 达成一致 (选举、条目提交) 需要Cold和Cnew各自的多数派。
- 此方法比单服务器变更更复杂。
4.4 系统集成 (System Integration)：
- 暴露AddServer/RemoveServer RPC。
- 自动变更的策略 (例如，发生故障时) 很重要。
- 为提高弹性，最好先添加服务器再移除服务器。
- 引导启动：初始化一台服务器，其配置只包含它自己。其他服务器通过成员变更加入。
4.5 结论： 单服务器变更更简单、更安全。可用性处理非常重要，特别是对于干扰性服务器。

第5章：日志压缩 (Log Compaction)

日志增长，消耗空间并增加重放时间。压缩是必要的。
基本思想：丢弃过时的已提交信息。
没有万能的解决方案：取决于系统需求、状态机大小、磁盘/易失性内存。
Raft日志压缩的核心概念：
1. 每台服务器独立地压缩其日志的已提交前缀。
2. 状态机将其当前状态写入磁盘 (快照/其他)，然后通知Raft丢弃日志前缀。
3. Raft持久化：被丢弃前缀的lastIncludedIndex (最后包含索引)、lastIncludedTerm (最后包含任期)，以及该前缀的最新配置。
4. 状态机处理：重启时加载状态，为慢速跟随者提供一致的状态映像。
- 如果领导者发现跟随者需要的条目已被丢弃，领导者通过InstallSnapshot RPC发送快照 (图5.3)。
5.1 基于内存的状态机快照： (图5.1总结，图5.2示例)
- 概念上最简单。整个当前状态写入快照。
- 用于Chubby, ZooKeeper, LogCabin。
- 5.1.1 并发快照 (Snapshotting Concurrently)：
  - 使用写时复制 (copy-on-write)：不可变数据结构或操作系统fork()。LogCabin使用fork()。
  - 需要额外内存。流式写入磁盘至关重要。
- 5.1.2 何时快照 (When to Snapshot)：
  - 简单：当日志达到固定大小时 (例如 N * 快照大小)。
  - 权衡：磁盘带宽 vs. 空间利用率 vs. 恢复时间。
- 5.1.3 实现考虑 (Implementation Concerns)： 保存/加载、传输、消除不安全的日志访问、并发性、何时快照的逻辑。
5.2 基于磁盘的状态机快照 (Snapshotting Disk-Based State Machines)：
- 状态主要在磁盘上。应用日志条目会改变磁盘上的状态。
- 日志条目一旦反映到磁盘上即可丢弃。
- 仍需要写时复制 (例如磁盘块、LVM快照) 以向慢速跟随者发送一致的映像。提出了增量传输算法。
5.3 增量清理方法 (日志清理、LSM树) (Incremental Cleaning Approaches (Log Cleaning, LSM Trees))：
- 更复杂，但能分散负载，写入效率高。
- 5.3.1 日志清理基础 (Basics of Log Cleaning)： (LFS, RAMCloud) 日志分为段。清理器从选定段中将活动条目复制到日志头部，释放旧段。
- 5.3.2 日志结构合并树 (LSM树) 基础 (Basics of Log-Structured Merge Trees (LSM Trees))： (BigTable, LevelDB) 最近的写入在内存/小日志中。定期排序并作为不可变的"run"写入磁盘。压缩合并run。
- 5.3.3 Raft中的日志清理和LSM树 (Log Cleaning and LSM Trees in Raft)： (图5.4)
  - LSM树：Raft日志提供最近的条目；当满时，状态机写入新的run。
  - 日志清理：状态机最好拥有自己的日志，独立于Raft的连续日志，并独立清理。Raft日志不受影响。
5.4 替代方案：基于领导者的方法 (Alternative: Leader-Based Approaches)：
- 通常浪费资源 (网络带宽用于发送已压缩状态)。
- 5.4.1 在日志中存储快照 (Storing Snapshots in the Log)： (图5.5) 领导者创建快照，作为日志条目存储。
  - 机制经济，但领导者故障会留下部分快照，可能耗尽存储。
- 5.4.2 基于领导者的方法用于非常小的状态机 (Leader-Based for Very Small State Machines)： 如果快照适合单个日志条目。领导者停止、等待、快照、追加、恢复。小的可用性间隙。
5.5 结论： 多种方法适用于Raft框架。基于内存的快照很常见。增量方法可能效率最高。

第6章：客户端交互 (Client Interaction)

(图6.1总结了客户端RPC：ClientRequest, ClientQuery, RegisterClient)
6.1 找到集群 (Finding the Cluster)：
- 固定成员：静态配置文件。
- 动态成员：外部目录 (例如DNS，在变更前后更新) 或网络广播/多播。LogCabin使用DNS。
6.2 将请求路由到领导者 (Routing Requests to the Leader)：
- 客户端尝试随机服务器。如果不是领导者，服务器拒绝并返回已知的领导者地址 (LogCabin方法)。
- 替代方案：服务器将请求代理到领导者。
- 如果领导者在选举超时内未收到多数节点的心跳，则下台 (防止在分区时无限期延迟客户端)。
6.3 实现线性一致性语义 (Implementing Linearizable Semantics)：
- 问题：重试导致的至少一次语义可能导致命令重复 (图6.2)。
- 解决方案：过滤重复请求。
  - 每个客户端有唯一ID。
  - 客户端为命令分配唯一序列号。
  - 服务器为每个客户端维护一个会话：跟踪最新处理的序列号及其响应。
  - 如果命令的序列号已执行，则返回存储的响应。
- 会话过期 (Session Expiry)：
  - 必须在状态机之间是确定性的 (例如，基于会话数量的LRU，或基于时间)。
  - LogCabin：领导者为命令添加时间戳；状态机用此进行基于时间的过期。客户端发送保活请求。
- 处理会话过期后的客户端 (Dealing with Client after Session Expiry)：
  - 使用RegisterClient RPC获取新的会话和ID。如果命令到达时会话未知，则返回错误。
6.4 更有效地处理只读查询 (Processing Read-Only Queries More Efficiently)：
- 为读取绕过Raft日志很有吸引力 (避免磁盘写入)，但如果领导者过时/分区，则可能读取到陈旧数据。
- 线性一致性读取 (无时钟) (Linearizable Reads (without clocks))：
  1. 领导者确保它已提交其当前任期的一个条目 (例如，任期开始时的空操作条目)。这会将其commitIndex更新到当前状态。
  2. 领导者将其当前commitIndex保存为readIndex。
  3. 领导者与集群多数节点交换心跳 (确认它仍然是领导者并且没有更新的领导者取代它)。
  4. 领导者等待其状态机应用条目直到readIndex。
  5. 领导者查询其状态机并回复客户端。
- 可以将心跳的成本分摊到多个只读查询上。
- 跟随者可以通过向领导者请求当前readIndex来服务读取。
- 6.4.1 使用时钟减少只读查询的消息传递 (租约机制) (Using Clocks to Reduce Messaging (Lease Mechanism))： (图6.3)
  - 领导者维护一个租约 (例如，在多数节点确认心跳后的 electionTimeout / clockDriftBound 时间内)。
  - 在租约期间，领导者无需额外通信即可回复读取。
  - *假设时钟漂移有界。*如果违反，可能返回陈旧信息。
  - 为实现顺序一致性 (即使存在时钟问题，客户端也能单调读取)：服务器在回复中包含日志索引。客户端在请求中发送最后看到的索引。如果服务器状态较旧，则不回复。
6.5 结论： 线性一致性和只读查询优化在正确性和性能方面都非常微妙但至关重要。

第7章：Raft用户研究 (Raft User Study) (评估Raft的可理解性)

目标： 与Paxos相比，客观评估Raft的可理解性。
方法：
- 参与者：高年级本科生/研究生 (斯坦福, 加州大学伯克利分校)。
- 材料：Raft和Paxos的录制视频讲座 (由J. Ousterhout主讲)，测验。
- 过程：观看视频1，参加测验1，观看视频2，参加测验2。顺序是平衡的。
- Raft讲座：Raft基础算法，联合共识成员变更。
- Paxos讲座：单提案Paxos, Multi-Paxos, 成员变更, 优化。
结果：
- 测验分数：Raft平均分25.7，Paxos平均分21.0 (满分60)。Raft高22.6%。
  - 线性回归模型：对于没有Paxos经验的学生，预测Raft分数比Paxos高12.5分。
- 调查：41人中有33人认为Raft更容易实现/解释。
7.1 研究问题和假设：
1. Raft是否比Paxos更容易理解？(预测Raft测验分数更高)。
2. Raft最难理解的方面？(预测是提交和成员变更)。
3. 交叉学习效应？(预测第二次测验分数更高)。
4. 对Raft的偏好？(预测偏好Raft)。
7.2 方法讨论：
- 7.2.1 参与者： 激励措施不同 (斯坦福：课程学分，伯克利：学习机会)。表7.1参与情况。
- 7.2.2 教学： 为保证一致性和时间采用讲座。J. Ousterhout主讲两者。Paxos变体来自D. Mazières，成员变更采用Lamport的α方法。录制视频。(表7.2讲座时长)。
- 7.2.3 测试理解： 采用测验而非实现。开放式简答题。平衡难度/分数。有意设置较难。(附录A为测验内容)。
- 7.2.4 评分： 两轮评分，有评分标准。允许部分给分。
- 7.2.5 调查： 简短，李克特量表，开放式反馈。
- 7.2.6 试点研究： 两次试点研究以完善材料。
7.4 结果详情：
- 7.4.1 测验：
  - 图7.2：测验分数的CDF。
  - 图7.3, 7.4：散点图 (Raft vs Paxos分数，按顺序/先前经验分组)。43人中有33人在Raft上得分更高。
  - 图7.5：分数差异的CDF。Raft中位数得分比Paxos高6.5分 (31.7%)。
  - 图7.6：顺序效应。先学Paxos可能略微拉低了Raft分数。
  - 表7.3, 7.4：线性回归模型。学校因素不显著。顺序对Raft测验显著。
  - 图7.7：按难度/顺序划分的分数。大部分差异在简单/中等难度。
  - 图7.8：按单个问题划分的分数。
- 7.4.2 调查：
  - 图7.9：先前Paxos经验。
  - 图7.10：公平性调查 (讲座质量，测验难度)。一些人感觉有偏见。
  - 图7.11：偏好调查。绝大多数人偏好Raft的实现/解释。
7.5 关于实验方法的讨论：
- 用户研究提供了经验证据，但并非所有系统评审员都完全接受。
- 对偏见、讲座内容、测验问题的担忧。
- 与机器实验相比，用户研究成本高、风险大、迭代困难。
7.6 结论： 研究表明，在学习1小时后，学生对Raft的理解优于Paxos。这是客观评估的重要第一步。

第8章：正确性 (Correctness)

目标： 建立Raft的正确性，并使其他人能够构建正确的系统。
务实方法：基于理解/直觉的基础，然后应用形式化方法。
8.1 Raft基础算法的形式化规约和证明：
- 完整规约和证明在附录B (TLA+)。约450行。
- 定义状态、初始状态(Init)、转换(Next)。模拟异步系统。
- 比第3章略微通用 (消息传递 vs RPC，更小的原子区域)。
- 证明验证了状态机安全特性。使用历史变量。证明约3500词。
8.2 先前验证尝试的讨论：
1. Murphi模型检查器：发现一个bug，错过另一个 (由于模型大小受限)。
2. TLA模型检查器：可伸缩性问题。
3. TLA证明系统：机械证明了领导者完整性 (依赖未经证明的不变性)。对于完整证明过于繁琐。TLA是无类型的。
- 模型检查比证明更容易，但受规模限制。证明耗时约6周。机器检查的证明最理想，但依赖工具。
8.3 构建正确的实现：
- 最安全：从已证明的Raft规约自动生成 (对Multi-Paxos [101] 可行)。
- 减少bug的设计：
  - Howard的ocaml-raft [37, 36]：状态转换在一个模块中，断言，单进程模拟以检查不变性。
- 测试：
  - Jepsen & Knossos [45]：在Raft只读处理中发现bug。Jepsen (分区，数据丢失)，Knossos (线性一致性)。
  - 鼓励罕见事件：低选举超时，频繁快照，随机重启，成员变更，资源竞争，网络操纵 (丢包，延迟，分区)。
  - 长时间运行，多台机器/进程。
8.4 结论： Raft的正确性与基于Paxos的系统相当。基础Raft的形式化规约几乎是完整的。未来工作：成员变更、压缩、客户端交互、活性的证明。

第9章：领导者选举评估总结 (Leader Election Evaluation Summary)

分析Raft领导者选举的性能。
预期主要发现：
- 无选票分裂：选举快速完成 (例如，选举超时范围的1/3)。
- 在足够宽的超时范围内 (例如，单向网络延迟的10-20倍)，选票分裂罕见。
- 预期选举轮数遵循几何分布。
- 在局域网和广域网 (模拟) 中表现良好。
- 日志差异影响较小。
- 预投票扩展可以防止重新加入的服务器造成干扰。
讨论实验设置 (真实局域网，用于广域网的AvailSim)。
分析固定与可变延迟、故障数量、集群大小对选票分裂概率和选举时间的影响。
(图9.1-9.10将详细说明这些时间线、CDF和参数扫描)。

第10章：实现与性能总结 (Implementation and Performance Summary)

10.1 实现：
- LogCabin：Raft的C++实现，约2000行代码。
- 数十个第三方开源实现 (actor模型，事件驱动)。
- 公司部署 (例如，Facebook HydraBase)。
- 10.1.1 线程化架构 (LogCabin)： (图10.1) 带锁的监视器式共享状态。对等线程、服务线程、状态机线程、定时器线程、日志同步线程。
10.2 性能考虑：
- 正常操作与Multi-Paxos相似 (领导者复制条目)。
- 图10.2：请求处理流水线 (未优化 vs. 优化，其中领导者磁盘写入并行化)。
- 10.2.1 领导者磁盘并行写入。
- 10.2.2 批处理和流水线化 (Batching and Pipelining)： Raft两者都支持。讨论了权衡。
10.3 初步性能结果 (LogCabin)： (表10.1设置，图10.3图表)
- 吞吐量：约19,500次1KB写入/秒 (3服务器)。
- 延迟：1KB写入约0.7ms (单服务器)，约1.0ms (2-5服务器)。
10.4 结论： 性能目标是在提高可理解性的同时匹配Multi-Paxos。初步结果合理。列出了未来的分析领域。

第11章：相关工作总结 (Related Work Summary)

将Raft与其他共识算法 (Paxos, Viewstamped Replication, Zab) 及特定机制进行比较。
11.1 概述： Paxos (Google, Microsoft, Ceph, Cassandra, Riak), Viewstamped Replication (Harp), Zab (ZooKeeper)。Raft机制更少。
11.2 领导者选举： 检测故障、中和被罢免的领导者、选择新领导者、确保新领导者拥有所有已提交条目。Raft使用更简单的机制。
11.3 日志复制和提交： Raft按顺序追加/提交。Paxos允许乱序。Raft的两阶段提交规则与其他算法的对比。
11.4 集群成员变更： 基于α的方法 (Paxos/SMART), VRR/Mazières (在领导者选举期间), Zab (最接近Raft的联合共识)。
11.5 日志压缩： 快照 (Chubby, VRR, ZooKeeper的模糊快照)。
11.6 RSMs vs. 主副本方法 (Primary Copy Approach) (VR, ZooKeeper)。
11.7 性能： 优化 (减少领导者瓶颈、见证者、避免持久存储写入)。
11.8 正确性： 证明方法的比较。
11.9 可理解性： HCI研究，NetComplex度量。

第12章：结论 (Conclusion)

目标达成： Raft提供了更易于理解和实践的基础。
Raft的可理解性设计： 不同的分解方式、强领导者、简单的选举、受限的日志复制。
Raft的实用性： 足够详细、解决主要问题、高效。解决了日志复制、成员变更、日志压缩、客户端交互。
评估总结： 用户研究 (可理解性)、证明 (正确性)、随机化选举 (性能)、LogCabin (吞吐量/延迟)。
工业界采纳： 表明其成功。
12.1 经验教训：
- 关于复杂性 (Raft对此的不容忍)。
- 关于连接理论与实践 (学术界的作用)。
- 关于寻找研究问题 (构建一些东西，优化一个指标)。
12.2 最后评论： 希望Raft能为教学共识和构建未来系统奠定良好基础。