【分布式】一致性算法 Raft

总述

Raft 算法是 2013 年在《In Search of an Understandable Consensus Algorithm》这篇论文里提出的（PDF 链接：https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf），主要作为 Paxos 的替代算法。文章有一万多个字，对算法的主要内容进行了整理，加上了对关键问题的消化和理解，希望对大家学习 Raft 算法能提供一些帮助。

解决的问题

Raft 算法是共识算法（也叫一致性算法）的一种，用来解决分布式一致性问题。

分布式一致性问题指的是：对于提供特定服务的集群，给定一组操作，需要保证集群中各台服务器达成的结果一致。

关于集群，集群是由单台服务器衍生过来的，因为单台服务器无法满足业务要求，而增加服务器，形成一个集群。集群里的所有服务器运行一样的程序，对外就好像是一台服务器在提供服务。集群不同于分布式系统。分布式系统是一个完整的系统，其中会包含多个集群，一个集群只负责一项子服务，比如缓存、数据库。各个集群之间使用通信协议，比如 RPC，进行交互。所有集群在一起，共同构成一个功能完备的分布式系统。

基本思想

按上面所说，共识算法要保证在一个集群内，所有服务器的最终状态一致。要实现这一目标的基本手段是 —— 复制状态机 —— 让所有服务器按同样的顺序执行同样的操作（一步一步做，操作顺序相同、操作内容相同、不多做也不少做），如果所有服务器的初始状态是相同的，那么服务器的状态就会一直保持一致，互为副本。Raft 算法就是以复制状态机为基础的。

算法结构

Raft 算法主要包括了 选主、日志复制、安全性 三个子问题。

关于选主，对于一个集群，必须要考虑的是集群是否需要一个 leader。Raft 算法的选择是，有 leader 。集群的 leader 是随机选举出来的，本质上就是集群中一台普通的服务器。Raft 算法要解决的问题是什么时候选举新的 leader、怎么选举一个 leader 以及选出新 leader 后如何继续保持日志一致性。

关于日志复制，为了能“让所有服务器按同样的顺序执行同样的操作”，Raft 让每一个服务器都存储一个包含一系列指令的日志，每个日志都按照相同的顺序包含相同的指令，每一个服务器按照日志中指令的顺序执行指令序列。这样，每一个服务器执行的指令序列就完全相同。保证集群内各台服务器状态的一致性 也就转换为 保证复制日志的一致性。日志格式如下图所示（论文图 6），每一个日志条目中（一个小方格）都包含 leader 的任期（任期的概念在后面说明）和状态机要执行的指令。

论文图 6

关于安全性，主要考虑的是在 leader 宕机、重新选举等情况下如何继续保持日志复制的一致性，以及 Raft 主要特性的证明。

关键特性

Raft 算法有几个关键的特性，列举如下。这些特性在后面的内容中都会涉及、都会有更详细的叙述。这些特性对理解算法至关重要。因为有这些特性的存在，使得集群在遭遇各种“意外”的情况下仍能保证日志复制的一致性。

• Election Safety：在一个任期内最多只能选举出一个领导者（与 5.2 节相关）
• leader Append-Only：一个领导者永远不会覆写或者删除日志中的条目，它只会追加新的日志条目（与论文 5.3 节相关）
• Log Matching：如果两份日志包含一个具有相同索引和任期的条目，那么两份日志在这个条目之前的所有日志条目都是相同的。（与 5.3 节相关）
• Leader Completeness：如果一个日志条目在某一个任期中被提交了，那么这个条目会出现在所有更高任期的领导者的日志中（与 5.4 节相关）
• State Machine Safety：如果一台服务器已经把一个日志条目应用到它的状态机，则不会有其它的服务器再以相同的索引应用不同内容的日志条目到状态机（与 5.4.3 节相关）

选主（论文 5.2 节）

Raft 算法给集群中的服务器设定了三种角色：follower（跟随者）、candidate（候选者）、leader（领导者）。正常情况下，集群中只包含一个 leader ，其余服务器都是 follower 。三种角色的状态转换关系（论文图 4）如下：

论文图 4

跟随者（Raft 的三种 RPC）

当系统启动时，所有服务器都是作为 follower。如果一个 follower 收到来自 leader 或者 candidate 的有效的 RPC 请求（Raft 里主要有 AppendEntries、RequestVote、InstallSnapshot 三种 RPC；第一种是由 leader 发给 follower 用来追加日志条目，也做心跳用；第二种由 candidate 发起用来获取选票；第三种由 leader 发送用来将快照传递给远远落后的 follower），就会保持在 follower 的状态。如果一个 follower 的选举定时器超时的都还没有收到任何请求，就会假设整个集群没有可用的 leader 或者 candidate，而发起新的选举（先给自己投票，再给集群中的其他机器发送 RequestVote RPCs），转换到 candidate 的状态。

候选者

在一个时间段内，可能会有多个 follower 转换为 candidate 状态，发起新的投票。如果其中有一个 candidate 接收到集群中大多数机器的投票，就将胜出成为 leader。一旦 candidate 胜出成为 leader ，就会给集群的其他机器发送心跳宣誓自己胜出，阻止其他候选人的选举。如果同一时间段内，有其他在等待选票的 candidate，收到新 leader 的心跳后就会转变回 follower 状态。

follower 投票的原则是，在一个任期（任期的概念在后面说明）只能投票给一个 candidate，按照先到先服务的原则，先收到谁发起的投票就投票给谁。当集群中有多个 candidate 在同一时间发起选举，可能没有一个 candidate 可以获得半数以上选票，即发生“选举分裂”。当选举分裂发生时，所有 candidate 的选举定时器会超时，增加本地存储的任期后启动新一轮的选举。Raft 通过随机选举定时器来降低选举分裂发生的可能性：选举超时时间在 [150, 300] ms 之间随机生成，大概率保证集群中会有一个机器先超时，而不是所有机器同时超时，先超时的那个服务器首先转变为 candidate，并大概率选举胜出成为 leader。

领导者

leader 负责处理所有的客户端请求，即使一个客户端的请求连接到了 follower，follower 也会把请求重定向到 leader。leader 会一直保持自己的身份，直到自己崩溃。

任期

任期是对时间的抽象划分，每一个任期的开始都是 leader 选举。在成功选举之后，一个 leader 会在任期内管理整个集群。如果选举失败，该任期就会因为没有 leader 而结束。

论文图 5

日志复制（论文 5.3 节）

leader 收到客户端的请求后，将请求中的指令追加到自己的日志文件中，并发送 AppendEntries RPC 给 follower 进行日志复制。当日志被复制到集群中的大多数机器后，leader 将日志应用到自己的状态机并将结果返回给客户端。

正常情况下只需要一轮 RPC 就可以将日志记录复制到集群的大多数。如果集群中有 follower 宕机、处理速度慢或者出现网络丢包的情况，leader 将不断重试 AppendEntries RPC 请求。因为只需要把日志复制到半数以上机器，leader 就可以将日志应用到自己的状态机并将结果返回给客户端，所以只要集群有半数以上机器存活，Raft 就可以接受、复制和应用新的日志记录；单个速度慢的 follower 也不会影响整个集群的性能。

日志提交

一条日志成功地复制到集群地大多数机器、应用到 leader 的状态机后，日志变为已提交状态。如果当前日志记录已提交，那么由前任 leader 或者当前 leader 创建的前继日志记录都会被提交。

当 leader 把日志记录提交后，并不会专门发送 RPC 给 follower，而是会维护一个即将被提交的日志记录的索引，并把这个索引放在未来的 AppendEntries RPC 请求中，通过后面的 AppendEntries RPCs 顺带把提交日志的消息传达给 follower。当 follower 从请求获知已提交的索引后，会将本地该索引及之前的日志应用自己的到状态机。

一致性保证

Raft 提供了下面两个性质的保证：

1. 如果两个日志文件中的两条日志记录有相同的索引和任期，那么这两条日志记录中的命令一定也是相同的 —— 在一个给定的任期，leader 创建的日志索引是不断递增的，不会重复，而且日志记录一旦被创建后，索引不会改变。
2. 如果两个日志文件中的两条日志记录有相同的索引和任期，那么这两个日志文件中前继的日志记录也是相同的 —— leader 发送的所有 AppendEntries RPCs 中，都会包含当前正在复制的日志记录的直接前继的任期和索引，如果 follower 在自己的日志中没有发现有相同 任期和索引的日志记录，它将直接拒绝请求（也即每次追加日志的时候都会进行日志一致性检测，leader 接收到返回成功的 AppendEntries RPCs 请求，就表明 follower 与自己的日志是相同的）。

这两个性质共同组成了 Raft 的日志匹配特性（Log Matching Property）：如果两个日志文件中存在相同索引和任期的日志记录，那么这两个日志文件在这个索引之前的所有日志记录都相同。

正常情况下，leader 和 follower 的日志都是相同的，但是如果服务器崩溃，尤其是 leader 崩溃，就可能会导致日志不一致。Raft 是通过强制 follower 只能复制 leader 的日志来解决不一致的问题，当 follower 的日志和 leader 的日志发生冲突的时候，follower 的日志将会被重写或者删除：

leader 为每个 follower 维护了一个索引 nextIndex，这个索引记录的是 leader 将复制给该 follower 的日志的索引。当一个 leader 选举生效（新被选举出来）后，它将初始化 nextIndex 为它自己日志文件中最后一条日志记录的索引。如果进行 AppendEntries RPCs 请求时，发现一致性检测失败，leader 将会减少 nextIndex 并重试 AppendEntries RPCs，经过多次重试，leader 会确定 follower 和自己一致的最后一条日志记录。然后让 follower 删除这条日志后面的日志，再把后面的日志复制给 follower。

安全性（论文 5.4 节）

选举约束

Raft 添加了额外的选举约束，这个约束保证当选的 leader 必须包含所有之前提交的日志。这样的约束带来的好处是集群中的数据流向只能是从 leader 到 follower，leader 永远仅需要追加即可。在其他没有这条约束的同样是基于 leader 的一致性算法中，在选举过程中或者选举胜出后，需要通过额外的机制确定缺失的日志，然后传给新的 leader，增加了额外的复杂度。

这个约束通过 RequestVote RPC 请求来实现：RequestVote RPC 请求中包含了 leader 的日志信息，如果投票者（follower）的日志比 candidate 的日志更新，那么它就拒绝投票。如果候选者的日志如果比集群中其它任意一台机器的日志都要新，就意味者包含所有已提交的日志。

关于日志的新旧，两个日志文件谁的日志更新是通过比较日志中最后一条日志记录的任期和索引：如果两个日志文件的最后一条日志的任期不相同，谁的任期更大谁的日志就更新；如果两条日志记录的任期相同，那么谁的索引更大，谁的日志就更新。

提交上一个任期的日志

在 Raft 算法中，禁止 leader 直接提交之前任期的日志。直接指的是只要判断一条日志已经复制到大多数机器上，就提交日志，让用户可见。原因是，如果允许 leader 提交上一个任期的日志，可能会破坏一致性。在论文中图 8 的 (a)~(d)，说明了一个例子：

论文图 8

图上部的数字是日志索引，方框中的数字是任期。在 (a) 中，S1 是 leader，follower S2 复制了任期为 2、索引为 2 的日志记录；在 (b) 中，S1 崩溃了，然后 S5 通过 S3、S4 和自己的选票赢得选举，从客户端接收了一条不一样的日志记录放在了索引 2 处、任期为 3；

在 (c) 中，S5 又崩溃了，S1 重新启动，并且赢得选举，任期为 4，开始复制日志。当领导人复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号。在这时，索引为 2、任期为 2 的日志记录已经被复制到了集群中的大多数机器上，但是还没有被提交。如果允许提交之前任期的日志，那么 索引为 2、任期为 2 的日志就会被提交，让用户可见。如果在 (d) 中，S1 还没有来得及把任期为 4，索引为 3 的日志条目复制到大多数机器，就又崩溃了，S5 可以重新被选举成为 leader（大多数机器还认为当前最大任期为 3），然后用索引为 2、任期为 3 的日志记录覆盖 follower 在索引 2、任期为 2 的日志。这样就破坏了数据的一致性，一条用户可见的数据没了。其实从这里就可以得出，leader 不能直接提交之前任期的日志，即使日志已经被复制到了多数机器上。

除非，有当前任期的日志记录被提交了，那么之前的日志记录可以被间接地提交。像 (e) 中那样，如果 S1在 crash 前，以当前任期 4 成功提交了一条索引为 3 的日志，那么索引为 2、任期为 2 的日志也会被间接提交（在前面“日志提交”小节已经有说明）。此时即使 S1 挂了。S5 的任期为 3，不满足选主条件，也就没法覆盖索引为 2，任期为 2 的日志了。

注：(d) 和 (e) 实际描述的是在 (c) 之后可能发生的两种情况，一种是任期为 4，索引为 3 的日志条目还没有来得及被复制到大多数机器，另一种是已经复制到大多数机器。两者是并列的或的关系，而不是时间上先后的关系。

安全性讨论

论文专门用一小节（5.4.3 节）证明了 leader Completeness 性质（如果一个日志条目在一个任期被提交了，那么这个条目会出现在所有更高任期的 leader 的日志中）和 State Machine Safety 性质（如果一台机器已经应用一个给定索引的日志条目到状态机，其他机器就不会应用一条具有相同索引但是内容不同的日志到状态机）。

证明 leader Completeness 性质用的是反证法 —— 首先假设 leader Completeness 性质不成立，然后推导出一个矛盾 —— 假设是任期 T 的领导者leader_{T}提交了一条日志，但是这条日志并没有被复制到未来某个任期的领导者的日志中，考虑是大于 T 的最小任期 U 的领导者leader_{U}没有存储这条日志，那么：

1. 这条已提交的日志在leader_{U}进行选举的时候一定不在它的日志中（因为领导者不会删除或者覆写日志条目）。
2. 根据假设，可知leader_{T}已经将日志条目复制到了集群大多数机器（日志已提交），同时leader_{U}也接收到了集群大多数机器的选票（赢得选举）。那么，至少存在一台服务器（一个投票者）既接收到了leader_{T}复制的日志，也投票给了leader_{U}，如图 9 中所示的 S3。这个投票者是推出矛盾的关键。

论文图 9

1. 这个投票者在投票给leader_{U}之前，一定先接受了来自leader_{T}的这条已提交的日志条目；否则它将拒绝leader_{T}的 AppendEntries 请求（因为它获知的最新的任期已经是 U，是大于 T 的）。
2. 并且，在这个投票者投票给leader_{U}的时候，仍然存储着这条日志（因为按照假设，T 和 U 任期之间的领导者都会包含这条日志，而且领导者不会删除日志条目，跟随者也只会在和领导者冲突的时候才删除日志）。
3. 再根据选举约束，可知投票者将自己的票投给了leader_{U}，那么leader_{U}的日志至少和投票者的一样新。至少一样新有两种情况：
4. 第一种，投票者和leader_{U}的最后一条日志记录相同，那么leader_{U}的日志至少和投票者的日志一样长，leader_{U}的日志中会包含所有投票者的日志条目。由上面的推导过程可知投票者已经包含了leader_{T}已提交的那条日志，那么leader_{U}也应该要包含leader_{T}已经提交的那条日志。但是这和我们假设的leader_{U}没有这条日志互相矛盾。
5. 第二种，投票者和leader_{U}的最后一条日志记录不同，那么leader_{U}的最后一条日志必须大于投票者。进一步，也会大于任期 T，因为投票者最后一条日志的任期至少是 T（它存储了来自任期 T 的已提交的日志）。按照假设，创建leader_{U}的最后一条日志的 leader，一定包含这条已提交的日志。那么，根据 Log Matching 性质，leader_{U}也一定包含这条已提交的日志，和假设矛盾。
6. 这里完成了矛盾的证明。所以，所有任期大于 T 的领导者一定包含在任期 T 提交的所有日志。
7. 另外，Log Matching 性质保证未来的 leader 也会包含被间接提交的日志，比如图 8(d) 中索引为 2 的日志条目。

证明了 leader Completeness 性质，我们就可以证明 State Machine Safety 性质：考虑一个最小任期，在这个任期里所有服务器都应用了某一个索引的日志条目；而 follower 将一个日志条目应用到自己的状态机的前提条件是「到这个日志条目为止 follower 与 leader 的日志完全相同」并且「这个日志条目已经被提交」；也就意味着，这条被所有服务器应用到状态机的日志在各个服务器上必定是相同的；又 Log Completeness 性质保证了所有更高任期的 leader 都会包含这个被所有服务器提交了的日志条目；所以服务器在后面的任期里应用的这个索引的日志将会有相同的值。所以，State Machine Safety 性质成立。

Raft 要求集群服务器按照日志索引的顺序将日志条目应用到状态机。再和 State Machine Safety 性质结合起来，就意味着所有的服务器会以相同的顺序将相同的日志条目集合应用到状态机。

跟随者和候选者宕机（论文 5.5 节）

如果跟随者或者候选者不可用，那么发送给他们的 RequestVote 和 AppendEntries RPCs 将会失败，然后 Raft 会进行重试。Raft 请求是可重入的，重试是没有危害的。

时间和可用性（论文 5.6 节）

Raft 可以进行选举和保持一个稳定的 leader，对于选举超时时间的设定有一定要求，需要满足下面的不等式：

broadcastTime << electionTimeout << MTBF

这个不等式中 broadcastTime 是一个服务器并行发送 RPCs 到每个机器并收到它们回应的平均时间，electionTimeout 是选举超时时间，MTBF 是单台机器的平均故障间隔时间。broadcastTime 和 MTBF 都是系统的固有特性

关于不等式中的两个远小于。broadcastTime 的数量级必须远小于 electionTimeout，这样 leader 才可以通过发送心跳来有效地阻止 follower 启动新的选举。electionTimeout 在数量级上也应该远小于 MTBF，这样系统才能稳定地运行 —— 当 leader 宕机，系统最长不可用时间不会超过选举超时时间；如果选举超时时间远小于机器平均故障时间间隔，那么不可用的时间就只会占整个运行时间极小的一部分。

Raft 的 RPCs 请求往往需要接受者将信息持久化到稳定存储介质，所以 broadcastTime 的实际值一般在 0.5ms 到 20ms 之间，典型的 MTBF 往往是数月或者更久，则选举超时时间应该设在 [10ms, 500ms] 的区间内（在保证系统稳定运行的条件下，超时时间设置得尽可能短）。

集群成员变更（论文 6 节）

在工程实践中，有时需要更换服务器。尽管可以通过让整个集群下线、更新配置文件、重启集群来完成，但是这会导致集群在成员变更期间不可用。而且，任何手动操作的步骤，都会引入操作错误的风险。为了避免这些问题，Raft 算法中加入了自动执行配置更改的部分：

因为不同的服务器切换配置的时间不完全一致，所以如果直接从旧配置切换到新配置，可能会导致在某一个时间点，有两台服务器被选举为同一个任期的 leader，即出现脑裂现象。比如论文里的图 10，一台服务器依照旧配置的 majorities 被选举为 leader（Server 1 和 Server 2 的选票），又有另一台服务器按照新配置的 majorities 被选举为 leader（Server 3、4、5 的选票）。

论文图 10

为了确保安全，配置更改用的两阶段方法。集群首先切换到被称为“联合共识”的过渡配置；集群配置通过特殊的日志条目进行存储和交流，一旦保存过渡配置的日志条目被提交，系统就转换到新配置。过渡配置同时结合了旧配置和新配置。当集群处于过渡配置时：

• 日志条目会被复制到所有新配置、旧配置中包含的服务器
• 新旧两种配置中的服务器都可以被选举为领导者
• 对于选举胜出和判断日志条目是否可以提交，既要满足旧配置的majority，又要满足新配置的 majority

除了确保安全性，联合共识也让集群在整个配置变更期间继续为客户端请求提供服务。

论文图 11 阐述了配置变更的过程。当 leader 接收到将配置从 C_{old}变更为 C_{new}的请求后，将过渡配置（图中的C_{old,new}）存储为一个日志条目。这个日志条目在存储、提交的机制上和前面描述的普通日志条目没有任何差别。一旦一个服务器将包含新配置的日志条目应用到它的日志，它将该配置用于所有未来的决策（服务器始终在其日志中使用最新配置，而不管该条目是否已提交）。这意味着当C_{old,new}被提交之后，leader 就会用C_{old,new}配置来进行决策。如果 leader 崩溃了，新的 leader 可能在C_{old}或者C_{old,new}规则之下被选出，取决于获胜的候选人是否已收到C_{old,new}。无论如何，C_{new}在这个阶段不能单方面做出决定。

一旦C_{old,new}被提交了，在没有得到另一方同意的情况下，C_{old}和C_{new}都不可以进行决策，并且 Leader Completeness 性质保证了只有包含C_{old,new}日志条目的服务器可以被选举为leader。现在创建一条描述C_{new}的日志条目、并把这个条目复制到集群就是安全的。同样，这个配置被复制到服务器以后就会立即生效。当新的配置在新的规则C_{new}下被提交，旧配置就变得无关紧要，未包含在新配置中的服务器也可以关机了。像在论文图 11 中展示的那样，没有一个时刻C_{old}和C_{new}都可以独立进行决策，这保证了安全性。

论文图 11

关于重新配置，还有三个问题需要解决：

第一个问题是新服务器最初可能不会存储任何日志条目。如果是在这种状态下将它们添加到集群中，它们可能需要很长时间才能赶上。在这段时间里，可能也无法提交新的日志条目。为了避免出现可用性缺口，Raft 在配置更改之前引入了一个附加阶段。在这个附加阶段里，leader 只是把日志条目复制给新加入集群的服务器，但是在统计日志复制到服务器的数量、决定是否提交日志的时候，不会把这些新服务器算进去；如果进行选举，这些新加入的服务器也有投票权。当新服务器赶上了集群的其他机器，再启用上面描述的两阶段方法。

第二个问题是群集领导者可能不是新配置的一部分。在这种情况下，一旦C_{new}日志条目被提交，leader 就会下台，回到 follower 的状态。这意味着，也许会有一段时间 leader 是在管理一个不包含它自己的集群（领导者提交C_{new}日志条目的时候）；它复制日志，但是不把自己计入包含日志的大多数机器里。当C_{new}被提交，leader 发生转换，因为这是新配置可以独立运行的第一个点（从C_{new}选择一位领导总是可以的）。在这一点之前，可能只有C_{old}中的服务器才能当选为领导人。

第三个问题是那些不在C_{new}中的被移除的服务器可能会破坏集群可用性。这些被移除的服务器将不会接收心跳，所以它们会超时并且开始新的选举。它们会用新的任期发送 RequestVote RPCs，并且这会导致现在的领导者回到 follower 状态。新的领导者最后会被选举出来，但是被移除的服务器会再一次超时然后重复上面的这个过程，导致非常差的可用性。为了避免这个问题，当服务器相信当前存在领导者的时候将无视 RequestVote RPCs。具体一点说，如果服务器在收到当前领导者消息的最小选举超时内收到 RequestVote RPC，不会更新自身任期或进行投票。这不会影响正常选举，即每个服务器在开始选举之前至少等待一个最小选举超时时间。但是，这有助于避免被移除的服务器造成的中断：如果一个领导者能够将心跳发送到其集群，那么它就不会被更大的任期所取代。

日志压缩（论文 7 节）

为了存储不断到来的客户端请求，在系统运行期间，Raft 的日志会持续地增长。不断增长的日志会占用越来越多的空间，对于新加入集群的服务器，也需要更多的时间复制历史日志以达到最新状态。在实际系统中，日志的增长不能没有限制。如果没有一种机制来丢弃日志中大量累积的过时的信息，最终会影响系统的可用性。

快照是最简单的压缩日志的方法。在快照机制中，将整个系统当前的状态写入稳定存储介质上的快照文件，然后丢弃到该点的之前的所有日志。

论文图 12 展示了在 Raft 中进行快照的基本思想。每个服务器都独立地拍摄快照，快照只覆盖其日志中已提交的条目。大部分工作包括状态机将其当前状态写入快照。Raft 还包括快照中的少量元数据：last included index 是快照替换的日志中最后一个条目的索引（状态机应用的最后一个条目），last included term 是此条目的任期。保留这些条目是为了支持快照后第一个日志条目的 AppendEntries 一致性检查，这个日志条目需要以前的日志索引和任期。要启用群集成员变更（第六节），快照还需要包括日志中截至上次包含索引的最新配置。一旦服务器完成快照的写入，它可能会删除快照包含的最后的索引之前的所有日志条目，以及之前的所有快照。

论文图 12

虽然服务器通常独立拍摄快照，但 leader 必须偶尔向落后的跟随者发送快照。当领导者已经放弃了需要发送给跟随者的下一个日志条目时，就会发生这种情况。幸运的是，这种情况在正常运行中不太可能出现：跟在领导者的跟随者可能已经有了这个条目。但是，异常缓慢的跟随者或加入集群的新服务器不会。让这样的跟随者带到最新情况的状态是由领导者通过网络向其发送快照。

如在“选主 - 跟随者”一节中提到的，leader 向 follower 发送快照是通过 InstallSnapshot RPC。当 follower 通过这个 RPC 收到快照时，如果快照中包含 follower 的日志中不包含的新日志（通常情况），follower 就会丢弃自己的整个日志，完全被快照取代；相反，如果 follower 接收到的是一个描述其日志前缀的快照，那么快照中包含的日志也还是会被删除，但是快照之后后面的日志条目仍然会被保留下来。

领导者使用名为 InstallSnapshot 的新 RPC（见论文图13）将快照发送给远远落后的追随者；当跟随者通过这个 RPC 接收快照时，它必须决定如何处理其现有日志项。通常，快照将包含接收者日志中尚未包含的新信息。在这种情况下，跟随者丢弃其整个日志；它全部被快照取代，并且可能有与快照冲突的未提交的日志条目。相反，如果跟随者接收到一个描述其日志前缀的快照（由于重新传输或错误），则快照包含的日志条目将被删除，但快照后面的条目仍然有效，必须保留。

这种快照方法背离了 Raft 的强领导者原则，因为 follower 可以在 leader 不知情的情况下拍摄快照。但是，Raft 认为这种背离是合理的。虽然有一位领导者有助于避免在达成共识时出现决策冲突，但在拍摄快照时已经达成共识，因此没有决策冲突。数据仍然只能从 leader 流向follower，只是 follower 现在可以重新组织他们的数据。如果采用的是只让 leader 创建快照，然后将快照发送给每个 follower 的方案，会带来两个问题。第一，将快照发送给每个 follower 会浪费网络带宽并减慢快照过程；每个follower 已经拥有生成自己的快照所需的信息，服务器从其本地状态生成快照通常比通过网络发送和接收一个快照方便得多。第二，领导者的实现将变得更加复杂；比如，leader 需要向 follower 发送快照，同时向 follower 复制新的日志条目，以避免阻止新的客户端请求。

还有两个问题会影响快照性能。首先，服务器必须决定何时进行快照。如果服务器快照太频繁，则会浪费磁盘带宽和能量；如果快照频率太低，则可能会耗尽其存储容量，并会增加重新启动期间重放日志所需的时间。一个简单的策略是在日志达到固定大小（以字节为单位）时拍摄快照。如果此大小设置为远大于快照的预期大小，则快照的磁盘带宽开销将很小。

第二个性能问题是，编写快照可能需要大量时间，延迟正常的操作。解决这个问题的方案是使用写时复制技术，以便在不影响正在编写的快照的情况下接受新的更新。操作系统的写时拷贝支持（比如 Linux 上的 fork）可用于创建整个状态机的内存快照（我们的实现使用这种方法）。

客户端交互（论文 8 节）

在论文的第八节里，讲述了客户机如何与 Raft 集群进行交互，包括客户机如何找到集群的 leader 以及 Raft 如何支持线性化语义（线性化语义指的是在调用和响应之间的某个点上，每个操作似乎都会立即执行一次）。这些问题适用于所有基于共识的系统，并且 Raft 的解决方案也与其他系统类似。

Raft 的客户将其所有请求发送给集群 leader。当客户端首次启动时，它会随机选择一个集群中服务器进行连接。如果客户的第一选择不是 leader，则服务器将拒绝客户的请求，并提供其最近听到的领导者的信息（AppendEntries 请求包括领导者的网络地址）。如果 leader 崩溃，客户端请求将超时；然后客户端会再次随机选择一个服务器，进行重试。

注：leader、follower 都只是 Raft 算法中的逻辑概念，物理上都是只是普通的服务器

Raft 的目标是实现线性化语义（在调用和响应之间，每个操作看起来都会立即执行，而且只执行一次）。但是，如前文所说的，Raft 可能会执行一条命令多次：比如 leader 在提交日志条目之后、响应客户机之前崩溃了，那么新的 leader 会被选举出来，客户机会针对新的 leader 重试命令，导致命令的二次执行。解决冲突的方案是让客户端为每个命令分配唯一的序列号，并让状态机跟踪为每个客户机处理的最新请求的序列号以及相关响应；如果它接收到的序列号是已经执行过的命令，它将立即响应，而不重新执行请求。

对于只读操作，可以在不向日志写入任何内容的情况下就处理掉。线性化读取一定不能返回旧数据，但是在不使用日志的条件下，如果没有其他措施，会有返回过时数据的风险，因为响应请求的 leader 可能已经被其他新的 leader 取代了而不自知。为了保证线性化读取，Raft 设置了两个额外的预防措施：

首先，leader 必须拥有提交条目的最新信息。Leader Completeness 性质保证了当选的领导者拥有所有已提交的日志条目，但在任期开始时，它可能不知道哪些条目是已提交的。要清楚这一点，leader 需要在它的任期中提交一个条目 —— Raft 让每个 leader 在任期开始时向日志中提交一个空白的不包含具体操作的条目，这样 leader 就可以确定哪些条目已经被提交了。

其次，leader 必须在处理只读请求之前检查自己是不是已经被废黜（如果最近有 leader 当选，自己的信息可能是过时的）。为了解决这个问题，Raft 让 leader 在响应只读请求之前与集群的大多数成员交换心跳，来确保自己还没有被废黜。

参考

中文翻译链接：https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md

可视化链接：Raft