阅读论文 Chain Replication，参考 note。

概述

链式复制是一种容错复制方式，可以保证高性能、高可用和强一致性（可线性化）。客户端的请求都以原子的方式执行，查询请求直接发送到 tail，更新请求发送到 head，然后沿着链传递到 tail。在没有故障的情况下，可线性化保证源于以下两点：只有 tail 会响应客户端的请求，以及更新操作只会在 head 计算一次，从而可以避免冗余计算和非确定性操作带来的一致性问题。

实现

基本概念

对象由 \(objID\) 唯一标识，\(Hist_{objID}\) 表示该对象上已执行的请求，\(Pending_{objID}\) 表示该对象上待执行的请求。对于链式复制来说，客户端视图中的 \(Hist_{objID}\) 被定义为 tail 存储的 \(Hist_{objID}\)，\(Pending_{objID}\) 被定义为任何服务器接收到的、没有被 tail 执行的客户端请求。注意，这两个状态都是对象的客户端视图，而不是实际存储在服务器中的数据。此外，论文只是为方便论证才将对象状态描述为 \(Hist_{objID}\)，实际的状态应该是对象的当前值。

故障检测和恢复

链式复制使用额外的服务来检测故障，重新配置链，通知客户端链头和链尾对应的服务器。论文称该服务为 master，使用复制进行容错，使用 Paxos 维持多个 master 副本之间的一致性。可以将其视为类似 ZooKeeper 的协调服务。虽然论文没有提及，不过检测故障通常是使用定时心跳。

链头故障

master 直接将 head 的下一个节点作为新的 head，然后通知客户端。所有旧 head 接收而未转发给后继的请求最终都会超时，然后客户端会重试。该过程相当于执行 T2 转移。

链尾故障

master 直接将 tail 的上一个节点作为新的 tail，然后通知客户端。因为更新是从前往后传播的，所以上一个节点的视图至少和旧 tail 的视图一样新，不会影响一致性。该过程相当于执行 T3 转移。

中间故障

master 会修改故障节点的前驱和后继的指针，从而将故障节点从链中删除。但是，如果前驱转发更新请求到故障节点，而故障节点没有将其转发至后继，那么前驱需要一种机制识别这部分请求，然后重新将其转发至后继。

每个服务器维护一个更新请求的已转发列表 \(Sent\)，当服务器将请求转发到后继时，会将该请求添加到列表中。当更新请求 \(r\) 转发到尾节点，并被尾节点处理时，尾节点会向前驱发送确认信息 \(ack( r)\)。收到 \(ack( r)\) 的服务器会将 \(r\) 从 \(Sent\) 列表中删除，同时将 \(ack( r)\) 转发到前驱。

当中间节点 \(S\) 故障，master 向后继 \(S^{+}\) 发送其新的前驱 \(S^{-}\)，\(S^{+}\) 会响应 master 确认消息，其中包含 \(S^{+}\) 收到的最后一个更新请求的序列号。然后 master 向前驱 \(S^{-}\) 发送其新的后继 \(S^{+}\) 和序列号，\(S^{-}\) 会将在 \(Sent_{S^{-}}\) 中且在序列号之后的请求转发到 \(S+\)，这部分请求就是故障节点 \(S\) 未转发至 \(S^{+}\) 的请求。该机制的关键在于保留已发送请求的列表，\(ack\) 的作用只是回收空间。

恢复冗余

发生故障的服务器会从链中删除，需要恢复冗余以保证容错。理论上，可以将新服务器添加到链中的任意位置。实践中，添加到链尾比较简单。master 会要求当前链尾 \(T\) 转发对象已执行的请求队列 \(Hist_{objID}^{T}\) 到新的链尾 \(T^{+}\)，在转发完成之前，依然是当前链尾 \(T\) 执行查询请求和前驱传来的更新请求，以及响应客户端。该过程中执行的更新请求同时会被添加到 \(Sent_{T}\)，该操作与 \(Sent_{T}\) 的定义不一致，之后会处理。当 \(Hist_{objID}^{T}=Hist_{objID}^{T^{+}}\oplus Sent_{T}\) 成立时，也就是转发开始时的 \(Hist_{objID}^{T}\) 都转发到 \(T^{+}\) 时，\(T^{+}\) 可以成为链尾。

过程如下：如果 master 收到上述不变式成立的通知，master 会通知 \(T\) 其不是链尾，之后 \(T\) 会将收到的查询请求转发到 \(T^{+}\)。然后 \(Sent_{T}\) 中的更新请求也会被转发到 \(T^{+}\)，转发完成之后，就符合 \(Sent_{T}\) 的定义，\(T\) 会通知 master 将 \(T^{+}\) 作为新的链尾。然后，master 会通知客户端新的链尾。PS：注意，此时 \(Sent^{T}\) 中的请求已经响应客户端。

对比主从复制

链式复制可以视为特殊的主从复制，头节点和尾节点共同充当主节点，其他节点作为从节点。相比传统的主从复制（指的是强一致性的主从复制）：

• 链式复制的查询，由链尾的服务器处理，不会被链中其他服务器的活动延迟。而主从复制的查询，主节点需要等待之前的更新被从节点确认，才能执行查询。PS：个人理解，指的应该是多客户端之间的更新和查询，单客户端是同步的，只有接收到上一个请求的响应才会发送下一个请求，否则链式复制是无法保证客户端的 FIFO 执行顺序。
• 链式复制串行传播更新，主从复制并行传播更新，所以链式复制的更新延迟更高，而且和链的长度成正比。

测试

根据论文中的模拟实验可以发现，链式复制比主从复制具有更高的读取性能，但是强一致性保证使得读写性能不能随着机器的数量线性扩展，不像 ZooKeeper。比较令人惊讶的是，在更新请求至少占总请求数的 15% 时，弱一致性保证的读取方案反而会降低系统的总吞吐量，因为在头节点的查询和更新会产生竞争。主从复制的吞吐量不会受复制因子的影响，而链式复制的更新是串行传播的，似乎吞吐量会随着链的长度增加而减少。但是，只要有足够多的更新请求，那么通过一个预热时间启动流水线，吞吐量可以恢复正常水平。

问题

Q：更新请求不是幂等的，如果响应丢失，客户端重试更新请求怎么办？

A：目前讨论的系统：GFS 的 primary chunkserver 重试会导致重复追加，我猜客户端重试大致也是如此；VM-FT 请求是否幂等取决于虚拟机中的应用程序；Raft 要求请求包含唯一标识，在状态机层去重；尽管 ZooKeeper 的事务是幂等的，但是请求不是幂等的，没有讨论如何处理；链式复制论文提到可以在重试之前，进行查询判断更新是否已经执行。总的来说，是否要求幂等是根据系统的实际使用场景而定的，课程中也提到，ZooKeeper 和链式复制也可以使用和 Raft 类似的方法去重，从而实现幂等。

Q：更新请求的延迟和链的长度成正比，那么超时时间会更长，如果请求丢失似乎需要更多等待？

Q：如果链头 \(S\) 和 master 发生网络分区故障，那么 \(S^{+}\) 会成为新链头，而此时 \(S^{+}\) 依然会收到旧链头 \(S\) 的转发。节点必然需要一种机制判断是否应该忽略请求，这可以通过简单的判断请求的来源是否是其前驱来实现。

Q：客户端在连接到服务器时，以及链头或链尾被改变时，master 需要通知客户端，如果客户端很多会有什么问题？

总结

课程提到，复制状态机有两种主要的实现方式，一种是使用共识算法复制所有操作，另一种是使用配置服务 + 主从复制，配置服务中的共识算法仅复制元数据，其他操作不需要使用共识算法复制。链式复制使用的是第二种方式，它需要利用额外的配置服务进行故障恢复，同时避免脑裂。链式复制概念简单，只有中间故障和恢复冗余稍微复杂一点。和共识算法不同，只要有一个服务器故障，就可能会导致读请求或写请求的短暂中断。论文在模拟实验中提到多链和对象放置策略，我认为论文的描述很模糊，所以没介绍。

阅读论文 ZooKeeper，参考 FAQ，note，官方文档，另一个课程的 note。

概述

ZooKeeper 是一个协调服务，用于协调分布式应用程序。它没有实现特定的协调原语（例如：配置、选举、锁），而是提供 API 供应用程序开发者使用，让开发者根据实际需要实现协调原语。ZooKeeper API 具有无等待特性，提供事件驱动机制。ZooKeeper 使用流水线（pipeline）架构处理请求，流水线自动支持客户端请求的 FIFO 执行顺序，从而允许客户端异步发送请求。ZooKeeper 没有实现可线性化一致性模型，它仅保证写操作的异步可线性化，以及读操作的写后读和单调读一致性（术语取自 DDIA），适合读多写少的工作负载。

会话

客户端在连接到服务器时建立一个会话（session），同时获得一个会话 ID。只要会话 ID 有效，应用程序就可以通过客户端调用 ZooKeeper API。客户端会定期向服务器发送心跳，如果服务器在超时时间内没有收到心跳，则服务器会结束会话。如果客户端当前连接的服务器故障，则客户端在会话 ID 过期之前自动尝试连接到另一台服务器。

PS：创建会话类似写操作，需要经过多数服务器同意，会话的状态也会使用日志持久化，它是一个全局会话。这也可以解释，为什么客户端可以使用同一个会话 ID 透明地切换到另一台服务器。由于开销较大，ZooKeeper 在之后的版本添加了本地会话功能，本地会话只能执行全局会话操作的子集，状态只在本地服务器维护。

数据模型和监视

ZooKeeper 以类似文件系统的树形结构在内存中存储协调数据（应用程序元数据），树中的数据节点被称为 znode，由路径名唯一标识。不同的应用程序在各自的子树中组织数据，存储在节点中的数据以原子的方式被读写。节点会维护一个统计结构，包含版本号、时间戳和事务 ID（zxid）等元数据。节点分为常规（Regular）和临时（Ephemeral）两种类型，客户端可以显示创建和删除节点。特别的，临时节点如果没有被显示删除，则在创建它们的会话终止时被自动删除，以及临时节点不能有子节点。

创建节点时，客户端可以设置顺序（sequential）标志，从而将一个计数值附加到该节点的路径末尾，同一父节点的子节点的计数值根据创建顺序单调递增。客户端可以为节点设置一次性监视（watch）标志，该标志在客户端连接的服务器本地维护。当监视触发时，服务器会向客户端发送一个监视事件，同时取消监视。有两种监视类型，监视数据和监视子节点。有四种监视事件，创建、删除、数据变化、子节点变化（不包含子节点的数据变化）。监视和会话相关，当会话结束时，监视也会被取消。ZooKeeper 保证设置监视的客户端在看到变化之前，会收到服务器的通知。会话事件也会触发监视，以便客户端知道监视事件可能延迟。

原语示例

客户端可以使用 ZooKeeper API 实现更强的原语，示例如下。更多示例（双重屏障、2PC、选举）可以查看官方文档。

配置管理

ZooKeeper 可用于分布式应用程序的配置管理，可以将配置存储在 znode 中。客户端从 znode 读取配置，同时设置监视标志。如果配置被更新，则客户端会收到通知，然后再次从该 znode 读取配置和设置监视标志。

群组成员

客户端可以创建一个 znode 表示一个群组，当进程以该群组的成员身份启动时，它会在该 znode 下创建一个临时子 znode。如果每个进程有一个唯一的名称，则将该标识作为子 znode 的名称，否则可以使用顺序标志，使其获得唯一的名称。进程可以将其元数据存储在该子 znode 中，例如地址和端口。如果进程终止，则临时节点会被自动删除。可以通过在 znode 上设置监视标志，从而监视群组成员的变化。

简单锁

可以将一个指定路径的 znode 作为锁，客户端可以创建临时 znode 来获取锁，其他客户端通过判断 znode 是否存在来判断是否能够获取锁，同时设置监视标志。当临时 znode 被显示或自动删除，则表示锁被释放。此时，等待锁的客户端将收到通知。但是该实现存在羊群效应（herd effect）：在锁被释放时，许多客户端会争抢同一个锁。

无羊群效应的简单锁

直觉上来说，将获取锁的请求按照 FIFO 的顺序排队处理，那么就可以避免羊群效应。可以使用顺序标志在指定父 znode 下创建临时子 znode，客户端通过判断其创建的临时 znode 是否是序号最小的，来判断它是否已获取锁。当客户端需要释放锁时，只需删除其创建的临时 znode。个人认为，有无羊群效应的简单锁，有点像是 notify_all 和 notify_one 的区别。

特别的，在代码实现时有一个陷阱，ZooKeeper 没有提供监视来通知当前 znode 的序号是否最小。在创建 znode 之后， 我们首先需要获取子 znode 列表，判断当前是否是最小的。如果不是，则可以在前一个节点上设置监视。但是，该监视触发并不意味着当前客户端已获取锁，因为有可能只是前一个客户端提前结束会话，此时仍存在更小的序号。

读写锁

实现细节

ZooKeeper 使用复制提供容错，使用原子广播协议（ZAB）保证多个副本之间的一致性。客户端仅连接到一个服务器发送请求，写请求会被转发给领导者，读请求读取本地数据库而不需要通过领导者。本地处理读请求使得读取性能可以随着服务器的数量增加而增加，而不会受限于单个领导者。复制数据库是一个内存数据库，当日志持久化到磁盘时，才会将日志应用到内存数据库，同时会定期为数据库生成快照。PS：类似 Raft，内存数据库实际上就是一个状态机。

ZooKeeper 使用 ZAB 保证写操作的可线性化，同时保证异步请求按照客户端 FIFO 的顺序执行，从而实现写操作的异步可线性化（A-linearizability）。当领导者收到写请求时，如果请求包含的版本号和目标 znode 的未来版本号匹配，就会将请求转换为事务。之所以要和未来版本号匹配，是因为可能存在尚未应用到数据库的事务。如果事务未提交（复制到大多数），则无法应用到数据库。ZooKeeper 保证事务是幂等的，〈transactionType, path, value, new-version〉。

ZooKeeper 使用的是模糊快照（fuzzy snapshot），因为允许在创建快照的过程中更改状态机，而且也不像 Raft 使用写时复制，所以快照不对应某个时刻的状态，故称为模糊快照。不过，由于事务的幂等性，重放相同的日志也没有关系。从日志的角度看，模糊快照并不对应一个连续的日志范围，可能是断断续续的。

客户端向服务器发送读写请求和心跳消息，得到的响应中会包含服务器的 zxid。如果客户端连接到新服务器，会检查客户端的 zxid 和新服务器的 zxid，确保新服务器满足客户端的单调读一致性。如果新服务器的视图更旧，客户端可以连接另一台服务器。

问题

Q：无等待（wait-free）是什么意思？

A：论文 Wait-Free Synchronization 进行了介绍，并发数据对象的无等待实现可以保证，任何进程都能在有限步中完成任何操作，而不论其他进程的执行速度如何。个人认为这个定义有点抽象，无等待还有一个层次结构和共识数。类似的术语还有无锁、无障碍、无阻塞。FAQ 提供了一个简单的解释，为什么 ZooKeeper 是无等待的，因为客户端调用 API 不会被其他客户端阻塞，ZooKeeper 没有使用锁来阻塞调用。

Q：为何流水线自动支持客户端请求的 FIFO 执行顺序？异步请求为何能提高性能？

A：我的理解是 TCP 可以保证客户端请求的 FIFO 到达顺序。流水线将一个处理过程分解为多个组件，能够充分利用系统的资源。但流水线依然是一个顺序的处理过程，一般就是按照到达顺序处理的，所以能够自动支持 FIFO 执行顺序。异步请求能提高性能是流水线的特性，如果同步发送请求，流水线中的很多组件会处于空闲状态。

FAQ 中有问到 ZooKeeper 如何实现异步请求的 FIFO 执行顺序，按照论文的逻辑，这个问题就不对。论文首先说流水线支持 FIFO 执行顺序，然后推出客户端可以发送异步请求。从而我觉得，FAQ 的答案也不对。FAQ 对流水线的解释也有问题，他把流水线解释为批处理。

Q：如何实现读操作的写后读和单调读一致性？

A：写后读一致性可以由客户端的 FIFO 执行顺序保证，而单调读一致性通过检查客户端和服务器的 zxid 保证。

Q：ZooKeeper 如何实现监视（watch）？

A：FAQ 有解释，客户端通常会注册一个回调函数，该函数在监视触发时调用。Go 使用通道（channel）来实现，当监视触发时，服务器会向通道发送一个事件，然后应用程序可以从通道中获取该事件。但是有个疑问，Go 的通道能跨网络传输数据么。

Q：为什么请求不幂等，而事务幂等？

A：假设有一个带顺序标志的创建节点的请求，那么多次发送请求会创建不同的节点。事务是请求的幂等形式，论文中提到形如 〈transactionType, path, value, new-version〉。

Q：ZooKeeper 服务器、客户端和应用程序的关系？

A：个人理解，服务器提供低级原语，客户端使用 API 实现更高级的原语，应用程序使用客户端提供的高级原语。

Q：ZooKeeper 中的 zxid 和版本号有什么关系？

A：ZooKeeper 的每次状态更改（写操作）都会递增 zxid，而版本号则是 znode 的属性。个人认为，zxid 是 ZAB 层面的，版本号是数据库（状态机）层面的。

Q：可线性化和可串行化的区别？

A：可以看下 Linearizability versus Serializability，很清晰。

总结

刚开始看这篇论文，涉及很多没见过的术语，看着比较折磨。如果深入细节的话，会花费很多时间。我确实一开始没有抓住重点，陷入如何在代码层面使用 ZooKeeper，无等待和通用对象是什么意思之类的。但是，如果从更高的层面来看，ZooKeeper 可以理解为 ZAB + 数据库（状态机），就是使用数据树结构提供一个通用的 API。

在查找资料的过程中发现很多不一致的地方，例如：API 文档中描述异步请求会排队等待发送，但按照论文的描述应该不是这样的，不然怎么提高性能；一致性保证中提到单一系统映像，定义首先说保证看到相同的视图，然后又说不会看到旧视图，但这完全不是一个意思；FAQ 中对异步请求如何实现客户端 FIFO 执行顺序的讨论，我认为论文和另一份笔记都证明 FAQ 的错误。

在阅读论文和资料的过程中，经常会看到某个描述，感觉模糊不清，只能凭自己的猜测去理解。实际上确实有很多模糊的地方，没有描述具体的实现方式，但有些问题其实论文中也给出了回答。所以，在读论文的过程中还是要仔细一点，遇到不懂的不要随便猜测，先记下问题，因为很可能是一个错误的猜测，还会干扰之后的理解。总之，论文只是提供一个简要的说明，深入理解还需要实际使用 ZooKeeper，以及阅读源码。

阅读论文 Raft，参考 FAQ1，note1，FAQ2，note2。

概述

MapReduce 的 master、GFS 的 master 和 VM FT 的共享磁盘都存在单点故障（即使 GFS 的 master 存在副本，其依然是单点故障，因为故障时系统会停止），从而可以很简单的避免脑裂。脑裂会发生的根本原因在于，无法区分机器故障和网络分区故障。共识算法使用多数原则（仲裁协议，quorum），可以在复制的同时避免脑裂。如果集群中有 \(2f+1\) 个服务器，则共识算法可以容忍 \(f\) 个服务器故障。共识算法通常使用状态机复制，以复制日志的方式实现。客户端、服务器以及共识算法和状态机的关系见下图。

Raft 的主要设计目标是可理解性，通过分解问题和减少状态来实现。问题被分解为多个子集，例如：领导者选举、日志复制、安全性和成员变更。使用随机化超时时间、限制选举保证日志单向流动等方式，来减少状态。

实现

基础知识

服务器有三种状态：leader、follower、candidate，服务器初始时都是 follower。正常情况下，只有一个 leader 和多个 follower。只有 leader 会处理客户端的请求，如果客户端将请求发送给 follower，该 follower 会将其重定向到 leader。服务器之间使用远程过程调用（RPC）进行通信，基本的 Raft 算法使用两种 RPC，candidate 在选举时会发起 RequestVote RPC，leader 在复制日志和发送心跳时会发起 AppendEntries RPC（心跳消息是没有日志条目的 AppendEntries RPC）。Raft 保证 RPC 是幂等的。

时间被划分为任期（term），使用单调递增的连续整数表示。每个服务器都会持久存储当前任期，不同服务器的任期可能不同（由于故障）。服务器之间进行通信时会交换任期，处于旧任期的服务器会更新其任期。如果 leader 或 candidate 发现自己包含旧任期，它会成为 follower。如果服务器收到具有旧任期的请求，它会拒绝该请求。

领导者选举

如果一个 follower 在超时时间（该时间被称为选举超时，election timeout）内没有收到来自 leader 或 candidate 的有效 RPC（何为有效，参考图 2），它将递增其任期成为 candidate，开始选举新的 leader。它为自己投票，然后向集群中的其它服务器发送 RequestVote RPC。

• 如果 candidate 收到大多数服务器的投票，它会成为新的 leader，同时向其他服务器发送心跳消息，以建立其权威防止新的选举。每个服务器在给定的任期内，只能投票给一个 candidate。服务器是否投票给某个 candidate 存在限制，将在安全性中讨论。
• 如果在等待投票时，candidate 收到 leader 的 AppendEntries RPC，且 leader 的任期大于等于 candidate 的任期，那么 candidate 会成为 follower。如果 leader 的任期更小，则 candidate 会拒绝该 RPC。或者收到其他 candidate 的 RequestVote RPC，且其任期大于当前 candidate 的任期，当前 candidate 同样会成为 follower。
• 如果存在多个 candidate 使选票分裂，使得没有 candidate 可以得到大多数服务器的投票，则每个 candidate 都会超时，继续递增任期，重新开始选举。Raft 使用随机 election timeout 来确保选票分裂很少发生（避免同时超时），election timeout 是从一个固定间隔中随机选择的（例如 [150, 300] 毫秒），每个候选人在开始选举时会重新随机化 election timeout。

如果 follower 在执行完成 AppendEntries RPC 之后，回复之前发生崩溃，则 leader 会重试 RPC。如果 follower 重新上线，它会忽略重复请求中的日志条目。如果 candidate 在发送 RequestVote RPC 之后崩溃，重启之后它会重新发送 RPC，follower 会持久存储其投票的 candidate，避免在同一任期内多次投票。

为了保证系统的可用性，election timeout 存在如下要求：

其中 \(broadcastTime\) 是发送 RPC 的平均往返时间，\(electionTimeout\) 是 follower 的超时时间，\(MTBF\) 是单个服务器的平均故障间隔时间。broadcast time 应该比 election timeout 小一个数量级，防止 follower 开始不必要的选举。election timeout 应该比 MTBF 小几个数量级，这样在 leader 真正发生故障时客户端不会等待太久。

日志复制

客户端会向 leader 发送请求，请求包含由复制状态机执行的命令，leader 会将当前任期和命令作为一个条目（entry）追加到日志中（只读命令可以不记录日志，但有额外的限制，在可线性化中描述），由日志索引标识其位置。然后 leader 向其他服务器并行发送 AppendEntries RPC 以复制该条目，当大多数服务器确认复制该条目时，leader 将条目应用到其状态机（即状态机执行条目中的命令），并将执行结果返回给客户端，之后 leader 通过不断地失败重试保证剩余服务器会复制该条目。

只要创建日志条目的 leader 将其复制到大多数服务器上，该日志条目就是已提交的（committed）。注意，是创建日志条目的 leader，而不是之后的 leader，这将在安全性中讨论。Raft 保证已提交的条目是持久的，并且最终会被所有可用的状态机执行。leader 提交其创建的日志条目时，也会提交 leader 日志中在该日志条目之前的所有日志条目，包含由之前 leader 创建的条目（会在安全性中解释原因）。leader 会跟踪其已提交日志条目的最高索引，并且在之后的 AppendEntries RPC 中包含该索引，以通知 follower 哪些日志条目已提交，之后 follower 会应用已提交的日志条目到本地状态机（按照日志顺序）。

Raft 的日志匹配（Log Matching）属性保证不同服务器之间日志的一致性：如果两个日志在同一索引位置的条目具有相同任期，则两个日志中所有小于等于该索引位置的条目都相同。如何实现该属性？leader 在给定任期只会对自己的日志进行追加，而不会覆盖。当 leader 向 follower 发送 AppendEntries RPC 时，会进行一致性检查。请求中会包含上一个条目的索引和任期，如果 follower 中对应索引的任期不同，则 follower 会拒绝该请求，回复 leader 匹配失败。如果系统正常运行，那么所有服务器上的日志都会相同。

但是当发生故障时，服务器之间的日志会产生不一致。如何处理不一致？leader 会为每个 follower 维护一个 nextIndex，表示 leader 下次向 follower 发送该索引位置的日志条目，如果 follower 拒绝 leader 的 AppendEntries RPC，则 leader 会将该 follower 对应的 nextIndex 递减，然后重试 RPC 直到 follower 和 leader 的日志完全相同（冲突条目将被删除）。整个过程表现为，递减 follower 的 nextIndex 到和 leader 日志最长相等前缀之后的一个位置，然后追加条目到 follower 直到其 nextIndex 和 leader 日志的尾后索引相等。

可以对上述算法进行优化，不是将 nextIndex 每次递减 1，而是递减整个任期，这通过在 follower 回复的信息中包含冲突条目的任期以及该任期在其日志中的第一个索引位置来实现。从而，每个冲突的任期都需要一个 AppendEntries RPC，而不是每个冲突的条目一个 RPC。为什么直接返回第一个索引位置，论文并没有描述之后该如何处理。我的理解是，其实并不是从该索引位置开始重传日志条目，因为这样可能会导致不必要的重传已提交的日志条目。在 leader 接收到冲突的任期和第一个索引之后，应该会递增该索引直到任期不同为止（之所以可以这样，是因为日志匹配属性），然后再传递该位置的日志条目。这样关于课程中提出的问题，为什么需要返回任期，而不是只返回第一个索引，也可以得到解答。

安全性

选举限制

即使日志一致，两个状态机也可能执行不同的命令序列。例如，leader 提交日志时，某个 follower 可能发生故障，如果它成为 leader，它将覆盖旧 leader 中的条目，而这些条目可能已经应用于旧 leader 的状态机上。为此 Raft 的领导者完整性（Leader Completeness）属性保证在某个任期被提交的日志条目必定会出现在更高任期的 leader 日志中，从而可以保证所有状态机执行相同的命令序列。

如何实现该属性？candidate 在发送 RequestVote RPC 时，会包含其日志信息，如果投票者的日志比 candidate 的日志更（读第四声）新，则投票者会拒绝投票。更新的定义如下：如果两个日志的最后一个条目具有不同任期，则更大任期的日志更新；否则，更长的日志更新。上述限制使得，只有包含所有已提交日志条目的 candidate 才有可能当选 leader，日志只会从 leader 流向 follower。

提交之前任期的条目

在日志复制中提到，创建日志条目的 leader 将其复制到大多数服务器上，则该日志条目就是已提交的。之所这样定义，是因为即使 leader 将之前任期的条目（不是由当前 leader 创建）复制到大多数服务器上，依然可能会被之后的 leader 覆盖（根据之前描述的日志匹配属性）。如果将其视为已提交，则会违反领导者完整性属性，导致状态机不一致。那么之前任期的条目何时视为已提交？当前任期的一个日志条目被提交时，由于日志匹配属性，之前任期的条目将会间接提交。

日志压缩

日志可能会变得很大，导致崩溃恢复需要花费很多时间重放所有日志，以及日志占用大量空间，Raft 通过使用快照来压缩日志。每个服务器会定期创建快照（通常是当日志达到固定大小时），快照中包含状态机的状态、状态对应的最后一个日志条目的索引和任期（以支持 AppendEntries PRC 的一致性检查）、当时的配置信息（用于集群成员变更）。当服务器将快照持久化之后，可以删除该快照之前的日志和之前的快照（剩余日志的索引并不会重置为从 1 开始，或许会新开一个数组从 1 开始存储，但是对外来说索引总是会加上某个偏移量）。

如果有一个严重滞后或新加入集群的 follower，它需要的日志可能已经被 leader 删除，此时 leader 需要使用 InstallSnapshot RPC 向滞后的 follower 发送快照。通常快照会比 follower 的日志更新，follower 会丢弃整个日志，使用快照替代。但是，由于重传或错误，follower 可能会收到描述其日志前缀的快照，此时仅会删除快照覆盖的日志，快照之后的日志将被保留。

为了避免在创建快照时停止操作，可以使用写时复制技术。状态机可以通过实现某种数据结构支持写时复制，或者使用操作系统的写时复制支持（例如，Linux 的 fork）来创建状态机的内存快照（作者使用该实现方式）。具体来说，Linux 的 fork 创建的子进程会共享和父进程相同的内存页面，如果父进程更新页面，则操作系统会对该页面执行写时复制。

可线性化

什么是可线性化？每个操作似乎在其调用和响应之间的某个时刻以原子的方式执行。Raft 如何实现可线性化语义？如果 leader 在执行命令之后回复客户端之前崩溃，然后客户端在新的 leader 重试请求，将会多次执行同一个命令。如果客户端向新 leader 发送读请求，由于旧 leader 在回复客户端之后发送下一个 AppendEntries RPC 之前崩溃，新 leader 可能并没有将某些已提交的命令应用到状态机，此时客户端可能会从新 leader 读取到旧数据。如果出现网络分区故障，旧 leader 可能不知道它已经被新 leader 取代，此时客户端可能从旧 leader 读取到旧数据。

首先，客户端需要为每个命令分配唯一的序列号，状态机会跟踪为每个客户端处理的最后的序列号以及相关响应。如果状态机收到已被执行的命令，它不会执行该命令而是直接返回响应。注意，日志中依然包含重复命令的日志条目。其次，每个 leader 在任期开始时会提交一个无操作日志条目，从而确定哪些日志条目已被提交并将其应用到状态机。能否通过心跳消息确定哪些日志条目已提交，个人认为不能，就是之前提到的旧任期日志条目不能通过计数判断是否已提交。最后，leader 在回复读请求之前，需要和集群中的大多数交换心跳消息，以确保它仍然是 leader（或者可以使用租约，论文中没有详细介绍，不过课程笔记中有提到具体方式）。

问题

Q：Raft 集群是部署在一个数据中心，还是多个数据中心？

A：通常是一个数据中心，这样可以避免 leader 跨数据中心向多个 follower 发送 RPC（网络延迟）。

Q：客户端如何知道谁是新的 leader？

A：客户端包含所有 server 的地址，它可以随机发送请求，follower 会将请求重定向到它认为的 leader。

Q：为什么日志的索引从 1 开始？

A：可以将其视为从 0 开始，索引 0 包含任期为 0 的空日志条目，以方便 AppendEntries RPC 在初始时的一致性检查。个人认为，类似于求数组的前缀和时从索引 1 开始。

Q：Raft 何时将其状态（currentTerm、votedFor、log）持久化到磁盘？

A：在内存中修改状态的同时刷盘，只有持久化之后 leader 才能向 follower 发送 RPC，follower 才能回复 leader，leader 才能将命令应用到状态机。否则，如果服务器发生崩溃，Raft 的各种属性将无法得到保证。

Q：图 2 中的 lastApplied 为何不需要持久化？如果发生崩溃，服务器如何知道日志条目是否应用于状态机？

A：论文作者在会话中对该问题以及下一个问题进行了解释（推荐阅读）。实际上 lastApplied 是否被持久化取决于状态机是否被持久化。如果状态机不被持久化，那么崩溃恢复之后需要重放所有日志，所以 lastApplied 会被初始化为 0。否则，只需重放 lastApplied 之后的日志。按我的理解，由于快照的存在，以及更新状态机的同时持久化产生的随机 I/O 开销较大，所以状态机一般不会实时持久化。如果存在快照，lastApplied 会被赋值为快照中包含的索引。

Q：图 2 中的 matchIndex 有什么作用？

A：matchIndex 表示 follower 和 leader 匹配的最高日志条目的索引（可能会小于实际值），只要大多数 follower 的 matchIndex 超过 leader 的 commitIndex，并且 log[matchIndex] 条目的任期是当前 leader 的任期（参见提交的定义），则 leader 可以增加 commitIndex。

Q：图 7 的 leader 崩溃之后，谁有可能成为新的 leader？

A：服务器 acd 都有可能成为新的 leader。首先日志 9 是最后一个提交的日志条目，根据领导者完整性属性，只能从 acd 中选择 leader。同时，acd 都有可能得到大多数服务器的投票，对于 a 来说是 abef，对于 c 来说是 abcef，对于 d 来说是 abcdef。有一点需要注意，服务器最后一个日志条目的任期可能并不是其当前任期。

总结

Raft 共识算法实现可线性化一致性模型，核心内容包括领导者选举、日志复制和安全性。论文中还提到 Raft 的集群成员变更机制，我并没有做介绍。然后日志压缩可以看作是 Raft 的额外补充。如课程中所述，论文中也有很多细节没有介绍，单个机制可以有多种不同的实现方式。课程视频、问答和笔记是对论文很好的补充，其中还提到一篇文章 Raft does not Guarantee Liveness in the face of Network Faults，讲述 Raft 在特定情况下无法建立稳定的领导者，除非使用 PreVote 和 CheckQuorum 技术。可见这篇论文介绍的仅仅是 Raft 的基本实现，现实中面临各种复杂场景，或许需要添加很多额外的机制。

附录