Raft 算法笔记

Posted by cwen 2017-07-23
 分布式  Raft  一致性

花了一个周末仔细读了 Raft 论文，此处只是做个简单的笔记，方便以后查看回顾...

Introduction

Raft 使用用来保证复杂日志一致性的算法，相比paxos 算法，更加简单容易理解。

Features

  • Strong leader： Raft 约束，日志只能从 leader 复制到 follower
  • Leader election: Raft 采用随机定时器来选主，简单的方法避免了冲突的问题。
  • Membership change：Raft 引用一个中间态( joint consensus) ，来做成员变更

Replicated State Machine

一致性算法产生的背景，在这种方法中，一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。例如，大规模的系统中通常都有一个集群领导者，像 GFS、HDFS 和 RAMCloud，典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。
复制状态机

图1: 复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令，所以产生的结果也是相同的

每台机器上都有一系列的日志，每条日志就是一条 command ，已经确认的日志会被状态机按顺序执行。一致性算法主要用来保证每台机器上 的已经确认的日志是一样到，因此内存中的状态机也是一致的，输出也是一致的。一致性协议模块从客户端接收到一条命令，并添加到日志中，然后和其他机器的一致性模块通信，来保证日志最终都是一样的。一旦一条日志被确认了，那么，少数派的机器宕机并不会影响对外服务。整个系统看起来就像是一个高可用的状态机。

一致性协议又如下特点:

  • 保证safety：不管网络延迟或者分区，网络包丢失、重复或者乱序，都要保证一致性。
  • 可用性：只要多数派机器在线，就应该能提供服务。
  • 不依赖时钟来保证正确性：时钟出错或者网络消息延迟过大只是会导致可用性，并不会导致一致性错误。
  • 通常，一次网路来回的事件就可以对一个command确认。

Overview

Raft首先选主，然后leader全权负责同步日志。有了leader极大地简化了日志复制：leader可以单方面决定日志写在什么位置上；日志流只能是从leader到follower。
通过领导人的方式，Raft 将一致性问题分解成了三个相对独立的子问题，这些问题会在接下来的子章节中进行讨论：

Leader election

一个新的领导人需要被选举出来，当现存的领导人宕机的时候

Log replication

领导人必须从客户端接收日志然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同。

状态：

状态 所有服务器上持久存在的
currentTerm 服务器最后一次知道的任期号（初始化为 0，持续递增）
votedFor 在当前获得选票的候选人的 Id
log[] 日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的任期号
状态 所有服务器上经常变的
commitIndex 已知的最大的已经被提交的日志条目的索引值
lastApplied 最后被应用到状态机的日志条目索引值（初始化为 0，持续递增）
状态 在领导人里经常改变的 （选举后重新初始化）
nextIndex[] 对于每一个服务器，需要发送给他的下一个日志条目的索引值（初始化为领导人最后索引值加一）
matchIndex[] 对于每一个服务器，已经复制给他的日志的最高索引值

附加日志 RPC：

由领导人负责调用来复制日志指令；也会用作heartbeat

参数 解释
term 领导人的任期号
leaderId 领导人的 Id，以便于跟随者重定向请求
prevLogIndex 新的日志条目紧随之前的索引值
prevLogTerm prevLogIndex 条目的任期号
entries[] 准备存储的日志条目（表示心跳时为空；一次性发送多个是为了提高效率）
leaderCommit 领导人已经提交的日志的索引值
返回值 解释
term 当前的任期号，用于领导人去更新自己
success 跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真

接收者实现：

  1. 如果 term < currentTerm 就返回 false
  2. 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false
  3. 如果已经存在的日志条目和新的产生冲突（索引值相同但是任期号不同），删除这一条和之后所有的
  4. 附加任何在已有的日志中不存在的条目
  5. 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个

请求投票 RPC：

由候选人负责调用用来征集选票

参数 解释
term 候选人的任期号
candidateId 请求选票的候选人的 Id
lastLogIndex 候选人的最后日志条目的索引值
lastLogTerm 候选人最后日志条目的任期号
返回值 解释
term 当前任期号，以便于候选人去更新自己的任期号
voteGranted 候选人赢得了此张选票时为真

接收者实现：

  1. 如果term < currentTerm返回 false
  2. 如果 votedFor 为空或者就是 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他

所有服务器需遵守的规则：

所有服务器：

  • 如果commitIndex > lastApplied，那么就 lastApplied 加一，并把log[lastApplied]应用到状态机中
  • 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，那么就令 currentTerm 等于 T，并切换状态为跟随者

跟随者：

  • 响应来自候选人和领导者的请求
  • 如果在超过选举超时时间的情况之前都没有收到领导人的心跳，或者是候选人请求投票的，就自己变成候选人

候选人 ：

  • 在转变成候选人后就立即开始选举过程
    • 自增当前的任期号（currentTerm）
    • 给自己投票
    • 重置选举超时计时器
    • 发送请求投票的 RPC 给其他所有服务器
  • 如果接收到大多数服务器的选票，那么就变成领导人
  • 如果接收到来自新的领导人的附加日志 RPC，转变成跟随者
  • 如果选举过程超时，再次发起一轮选举

领导人：

  • 一旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以阻止跟随者超时
  • 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端
  • 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex，那么：发送从 nextIndex 开始的所有日志条目：
    • 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
    • 如果因为日志不一致而失败，减少 nextIndex 重试
  • 如果存在一个满足N > commitIndex的 N，并且大多数的matchIndex[i] ≥ N成立，并且log[N].term == currentTerm成立，那么令 commitIndex 等于这个 N
特性 解释
选举安全特性 对于一个给定的任期号，最多只会有一个领导人被选举出来
领导人只附加原则 领导人绝对不会删除或者覆盖自己的日志，只会增加
日志匹配原则 如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同
领导人完全特性 如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中
状态机安全特性 如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志

Safty

如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令。

Raft Basic

Raft中的server只有三种状态：Leader / Follower / Candidate。通常情况下（无主备切换时），一个leader其他是follower。Follower处于被动的状态，它不能发起任何请求，只能回应leader和candidate的请求。Leader处理客户端的请求，如果客户端请求发到了follower，follower负责将请求重定向到leader。Candidate是选主过程中用于选出新主。状态转移图如下：

状态转移图

Raft 将时间话费为不同的 Term, Term 可以是任意长的时间，但是在每个 Term 时间内最多只能有又一个 Leader, Term有一个连续递增的id。每个term以选主开始，选主过程中，若干candidate尝试成为leader。选主过程成功之后进度normal operation的阶段，leader开始服务。选主可能因为选票分裂而失败，此时当前term没有leader，在下一个term继续选主。

Term

Term是需要持久化保存的。因为是分布式环境，所以不同的机器维护的term可能不一样，term是一个逻辑时钟，因此，当一台机器在与其他机器通信时发现自己的term比较小，应该推进本地的term。如果一台机器发现请求方的term比较小，则要拒绝请求。如果一个candidate发现自己的term落后了，就要退回到follower。
机器之间使用RPC通信，Raft中只有两种RPC：RequstVote 和 AppendEntries。RequstVote RPC 用于candidate在选主期间拉票。AppendEntries RPC 用于 leader 复制日志到 follower，同时也作为主备之间的心跳 RPC。RPC 请求收不到任何结果时，要定时重试。为了优化性能，RPC可以并发发起。

Leader Election

Raft使用了心跳机制来触发选主。Server刚启动时，状态处于follower，只要follewer一直收到leader或者candidate发来的rpc，就保持为follower。Leader周期性地向follower发送心跳（用的是AppendEntries RPC，里面不带日志内容）来保持leader的权限。如果一个follower在election timeout时间内没有收到leader的心跳，follower就认为没有leader了，就会开始选主。
开始选主时，follower先递增本地term（要持久化），然后主机状态切换为candidate。然后主机向其他发送拉票请求，同时也给自己投票。Candidate在这个状态等待，直到如下三种情况发生：

  • a) 该candidate赢得了选主
  • b) 其他机器成为了leader
  • c) 超时间内未能选主成功
    一个candidate赢得选主的判定：在相同的term内，收到了多数派的投票。在给定的term内，每台机器都只能按照先来先服务的规则投一个candidate（要持久化）。收到多数派才可能成为leader，可以避免出现双主。选主成功之后，新主向其他主机发送心跳AppendEntries RPC，宣告自己当选了。
    在选主时间内， candidate如果收到了其他主机宣告当选的心跳AppendEntries RPC且RPC中携带的term比本机维护的term更大或相等，本机就自动退为follower。
    超时时间未能内选主成功，可能是发生了选票分裂。同时有若干参与者拉票，选票分流，没有candidate能够拉倒多数派的选票。选主失败时，所有candidate递增term开始下一轮。为了减少选票分裂出现的概率，选举超时时间使用随机化的方法避开多个candidate同时拉票。
    Raft的选主方案的进化。一开始Raft使用的是ranking system，每个candidate都分配一个唯一的rank，低rank的主机收到高rank的主机的拉票请求，就把自己转为follower，这样rank高的就能尽快被选出来（可能在下一轮选主中）。这个方案有些微妙的可用性问题：如果高rank的主机宕机了，低rank的主机还要等超时才有机会转为candidate。这个方案调整了几次，每次调整都引入新的corner case。最后才选择了这个随机化方案。
    Raft的选主方案还要加上一些约束，以支持log replication实现。

Log replication

Leader被选出来之后，就开始服务客户端的请求。Leader收到客户端请求之后，将命令记入日志并同步到follower。当这条日志被确认之后，就把日志对应的命令应用到状态机。如果某个follower没有收到AppendEntries RPC，leader会不停地重试，确保follower最终有全部的日志。
日志组织方式如图，
日志

日志由有序序号标记的条目组成。每个条目都包含创建时的任期号（图中框中的数字），和一个状态机需要执行的指令。一个条目当可以安全的被应用到状态机中去的时候，就认为是可以提交了。

每条日志都记录了term值，这个值是提交这条日志的leader当时的term值。这个term值可以用以检测不一致性。
当leader将日志复制到多数派的时候，这条日志就commit了。Raft保证任何commit的日志最终都会被副本的状态机执行。
Raft约束日志是连续commit的，leader维护最大已经commit的日志id，并将这个信息附加到AppendEntries告知follower，follower了解到之后即可将本机已有的且已经commit的日志应用到本地的状态机。
Raft维护了更高级别的不同主机之间的日志的一致性，简化了系统的行为、使得系统行为更加可预测、更容易保证safety。
Raft保证了如下的约束（Log Matching Safety）：
不同主机上日志文件中，相同term和相同log id的日志内容一定相同。
这条相同的日志之前的日志文件内容也一定相同。
实现这两点也很简单。第一点，只要保证leader给每一条log id只分配一条日志即可。第二点，由AppendEntries RPC保证，AppendEntries RPC在消息中携带term和前一条log id。如果follower发现自己本地的日志并不匹配这个AppendEntries RPC中的log id时，会拒绝这条日志。因此按照归纳法，就可以证明只要某条日志被接收了，那么前面的日志都被接收了，前面的日志文件内容都是一致的。
正常运行时，主备之间通常都是一致的，AppendEntries RPC也一直成功。但是如果有leader宕机了，就会有不一致。例如如图。
冲突

当一个领导人成功当选时，跟随者可能是任何情况（a-f）。每一个盒子表示是一个日志条目；里面的数字表示任期号。跟随者可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f）。例如，场景 f 可能这样发生，那个服务器在任期 2 的时候是领导人，附加了一些日志条目到自己的日志中，在提交之前就崩溃了；很快这个机器就重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在这些任期 2 和任期 3 重点日志被提交之前，这个服务器又宕机了，然后的几个任期里一直处于宕机状态。

主备不一致可能有如下几种情况：少了一些日志（term可能相同或者少了）；多了一些未commit的日志（term可能多了也可能少了）；某些term多了一些日志且某些term少了一些日志。
Raft中如何解决这些不一致呢？leader强制让follower的日志文件复制leader的日志文件，即follower上不一致的日志文件内容被覆写。新主上任之后，在和某个follower同步日志时，先确定和这个follower最后一条相同的日志，然后用leader上的内容覆盖之后不相同的部分。当然，为了避免已经commit的日志被覆盖，选主时需要特别注意，后面会讨论这个问题。
Leader确定与follower不一致点的方法：leader维护一个log id，初始为leader本地最大的log id，然后发送AppendEntries RPC到follower，follower在收到AppendEntries之后，检查RPC中携带的term和log id（leader上被追加的这条日志的前面一条日志的term和log id），如果follower本地没有这条日志，就拒绝此次AppendEntries RPC，leader就能知道follower的同步点更靠前，逐渐就能知道同步点的位置。当然，实际实现时，会使用更有效率的方法。
通过这种方法，leader上任后，并不需要做特殊的操作，只用AppendEntries就可以逐渐使follower上的日志文件保持一致。Leader从不覆写自己的日志文件，即Leader Append-Only Property。

Safety

Election restriction

如果不对选主加约束，那么，可能一个落后的follower被选为主，落后的那些日志可能已经commit了，要保证log matching property，就必然要有从旧主或者其他不落后的follower上拉取这些已经commit的日志。
Raft使用的方案是：确保包含所有commit日志的candidate才能有机会被选为leader。因为一条日志commit，必然在任意一个多数派中，至少有一台主机包含了这条日志。选举时，candidate要和至少多数派的主机通信，通信时带上自己本地的日志信息（本地最后一条的term和log id），接收消息的主机发现发送消息的candidate的日志并不比我本地更新，就拒绝投票。也就是说，candidate至少是某个多数派中拥有最新日志的主机，才能被选为leader。

Commit entries from previous terms

领导人知道一条当前任期内的日志记录是可以被提交的，只要它被存储到了大多数的服务器上。如果一个领导人在提交日志条目之前崩溃了，未来后续的领导人会继续尝试复制这条日志记录。然而，一个领导人不能断定一个之前任期里的日志条目被保存到大多数服务器上的时候就一定已经提交了。图 8 展示了一种情况，一条已经被存储到大多数节点上的老日志条目，也依然有可能会被未来的领导人覆盖掉。

考虑如下场景：

如图的时间序列展示了为什么领导人无法通过老的日志的任期号来判断其提交状态。在 (a) 中，S1 是领导者，部分的复制了索引位置 2 的日志条目。在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。但是，在崩溃之前，如果 S1 在自己的任期里复制了日志条目到大多数机器上，如 (e) 中，然后这个条目就会被提交（S5 就不可能选举成功）。 在这个时候，之前的所有日志就会被正常提交处理。

出现这个问题的根本原因是S1在时序(c) 的任期4内提交了一个之前任期2的log，这样S1提交的日志中最大的term仅仅是2，那么一些日志比较旧的server，比如S5(它最日志的term为 3)，就有机会成为leader，并覆盖S1提交的日志。解决办法就是S1在时序(c)的任期term4提交term2的旧日志时，旧日志必须附带在当前term 4的日志下一起提交。这样就把S1日志的最大term提高到了4，让那些日志比较旧的S5没有机会竞选成为Leader，也就不会用旧的日志覆盖已经提交的日志了。

简单点说，Leader如果要提交之前term的旧日志，那么必须要提交一条当前term的日志。提交一条当前term的日志相当于为那些旧的日志加了一把安全锁，让那些日志比较旧的server失去得到Leader的机会，从而不会修改那些之前term的旧日志。

Safety argument

在给定了完整的 Raft 算法之后，我们现在可以更加精确的讨论领导人完整性特性（这一讨论基于 9.2 节的安全性证明）。我们假设领导人完全性特性是不存在的，然后我们推出矛盾来。假设任期 T 的领导人（领导人 T）在任期内提交了一条日志条目，但是这条日志条目没有被存储到该领导人未来某个任期的日志中。设大于 T 的最小任期 U 的领导人 U 没有这条日志条目。

安全性论证

如果 S1 （任期 T 的领导者）提交了一条新的日志在它的任期里，然后 S5 在之后的任期 U 里被选举为领导人，然后至少会有一个机器，如 S3，既拥有来自 S1 的日志，也给 S5 投票了。

  1. 在领导人 U 选举的时候一定没有那条被提交的日志条目（领导人从不会删除或者覆盖任何条目）。
  2. 领导人 T 复制这条日志条目给集群中的大多数节点，同时，领导人U 从集群中的大多数节点赢得了选票。因此，至少有一个节点（投票者、选民）同时接受了来自领导人T 的日志条目，并且给领导人U 投票了，如图 9。这个投票者是产生这个矛盾的关键。
  3. 这个投票者必须在给领导人 U 投票之前先接受了从领导人 T 发来的已经被提交的日志条目；否则他就会拒绝来自领导人 T 的附加日志请求（因为此时他的任期号会比 T 大）。
  4. 投票者在给领导人 U 投票时依然保有这条日志条目，因为任何中间的领导人都包含该日志条目（根据上述的假设），领导人从不会删除条目，并且跟随者只有和领导人冲突的时候才会删除条目。
  5. 投票者把自己选票投给领导人 U 时，领导人 U 的日志必须和投票者自己一样新。这就导致了两者矛盾之一。
  6. 首先，如果投票者和领导人 U 的最后一条日志的任期号相同，那么领导人 U 的日志至少和投票者一样长，所以领导人 U 的日志一定包含所有投票者的日志。这是另一处矛盾，因为投票者包含了那条已经被提交的日志条目，但是在上述的假设里，领导人 U 是不包含的。
  7. 除此之外，领导人 U 的最后一条日志的任期号就必须比投票人大了。此外，他也比 T 大，因为投票人的最后一条日志的任期号至少和 T 一样大（他包含了来自任期 T 的已提交的日志）。创建了领导人 U 最后一条日志的之前领导人一定已经包含了那条被提交的日志（根据上述假设，领导人 U 是第一个不包含该日志条目的领导人）。所以，根据日志匹配特性，领导人 U 一定也包含那条被提交当然日志，这里产生矛盾。
  8. 这里完成了矛盾。因此，所有比 T 大的领导人一定包含了所有来自 T 的已经被提交的日志。
  9. 日志匹配原则保证了未来的领导人也同时会包含被间接提交的条目，例如图 8 (d) 中的索引 2。

通过领导人完全特性，我们就能证明图 3 中的状态机安全特性，即如果已经服务器已经在某个给定的索引值应用了日志条目到自己的状态机里，那么其他的服务器不会应用一个不一样的日志到同一个索引值上。在一个服务器应用一条日志条目到他自己的状态机中时，他的日志必须和领导人的日志，在该条目和之前的条目上相同，并且已经被提交。现在我们来考虑在任何一个服务器应用一个指定索引位置的日志的最小任期；日志完全特性保证拥有更高任期号的领导人会存储相同的日志条目，所以之后的任期里应用某个索引位置的日志条目也会是相同的值。因此，状态机安全特性是成立的。

最后，Raft 要求服务器按照日志中索引位置顺序应用日志条目。和状态机安全特性结合起来看，这就意味着所有的服务器会应用相同的日志序列集到自己的状态机中，并且是按照相同的顺序。

Follower and candidate crash

到目前为止，我们都只关注了领导人崩溃的情况。跟随者和候选人崩溃后的处理方式比领导人要简单的多，并且他们的处理方式是相同的。如果跟随者或者候选人崩溃了，那么后续发送给他们的 RPCs 都会失败。Raft 中处理这种失败就是简单的通过无限的重试；如果崩溃的机器重启了，那么这些 RPC 就会完整的成功。如果一个服务器在完成了一个 RPC，但是还没有响应的时候崩溃了，那么在他重新启动之后就会再次收到同样的请求。Raft 的 RPCs 都是幂等的，所以这样重试不会造成任何问题。例如一个跟随者如果收到附加日志请求但是他已经包含了这一日志，那么他就会直接忽略这个新的请求。

Timing and availability

Raft 的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。但是，可用性（系统可以及时的响应客户端）不可避免的要依赖于时间。例如，如果消息交换在服务器崩溃时花费更多的时间，候选人将不会等待太长的时间来赢得选举；没有一个稳定的领导人，Raft 将无法工作。

领导人选举是 Raft 中对时间要求最为关键的方面。Raft 可以选举出并维持一个稳定的领导人除非整个系统满足下面的时间要求：

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

在这个不等式中，广播时间指的是从一个服务器并行的发送 RPCs 给集群中的其他服务器并接收响应的平均时间；选举超时时间就是在 5.2 节中介绍的选举的超时时间限制；然后平均故障间隔时间就是对于一台服务器而言，两次故障之间的平均时间。广播时间必须比选举超时时间小一个量级，这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态；通过随机化选举超时时间的方法，这个不等式也使得选票瓜分的情况变得不可能。选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行。当领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用；我们希望这种情况在整个系统上是很小的情况。

广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。

Cluster Membership changes

之前的讨论都是假设成员组是不变的。这一节描述Raft的成员变更方案。
要保证成员变更过程中的safety，就要保证在任何时候，都不会出现双主。
如果一次成员变更中，将成员组立刻切换为新的成员组，那么就会因为各个成员之间不能同时生效而导致双主，如图。

双主的情况

从(S1,S2,S3)变为(S1,S2,S3,S4,S5)的变更中，因为各个成员上变更生效时间不同，可能导致在中间某个时刻，出现两个disjoint majorities，两个多数派能够分别选主并服务客户端，导致一致性无法保证。
为了保证safety，常规的解法是使用两个阶段。例如，在Viewstamped Replication协议里，成员变更先停止旧的成员组，然后启用新的成员组，但是这样导致中间会有停服务的问题。
Raft里采用的两阶段方案是，集群先进入一个称之为Joint Consensus的过渡状态，等过渡状态commit了，再只使用新的成员组。在Joint Consensus中，不管是日志复制（客户端提交的普通日志）还是选主，都要在新旧两个成员组C_old、C_new内分别形成多数派。
成员变更命令通过成员变更日志作为载体复制到其他副本。一个副本只要收到了成员变更日志，之后的日志就立刻使用新的成员组开始工作，不管这条成员变更是不是commit了。也就是说，leader要用两个多数派C_old,new同时满足来commit这条成员变更日志。
因为有Joint Consensus，所以在C_old,new commit之前，C_new无法单方面确认任何事情。那么，在C_old,new commit之前如果leader宕机了呢？这种情况下，C_old或者C_old,new可能选出新的leader（取决于新主上是否有C_old,new这条日志）。同样，C_new仍然无法单方面确认任何事情。
一旦C_old,new commit了，那么即使leader宕机，选出来的新leader也一定有C_old,new这条日志了（选主的约束：Leader拥有全部commit的日志）。此时，leader发起一个成员变更，将状态转为只使用C_new的状态（这条日志也记为C_new）。直到C_new被commit了，C_old便不再被需要。成员变更的两个阶段就完成了。
这个过程如图示：

中间态

成员变更保证safety，要遵循的原则是：在任何时候都不允许C_old和C_new同时可以单方面做决定。例如图中上半部分，C_old和C_new分别可以单方面做决定的时间段是没有重叠的，中间使用C_old,new过渡。
成员变更还有三个延伸的问题：

  • 问题1：新加入的主机上可能没有任何日志，在实际执行成员变更前，我们希望这台主机先作为观察者基本追上leader的日志，再做成员变更。否则加入的这台空机器在追上之前，几乎起不到高可用的目的。
  • 问题2：如果leader并不是C_new的一员，那么leader要卸任。因为C_new的commit是这个leader主导的，因此在C_new commit之后，leader要卸任。
  • 问题3：如果是机器下线的变更，被下线的机器因为不会再收到C_new中的leader的心跳而超时触发选主了。C_new中的leader因为term比下线机器的term小，因此会卸任，又因为C_new中的副本拥有最多的日志，选主约束仍会从C_new中选出一个leader。同样，下线的机器会再次超时，又触发选主，周而复始，虽然不会有safety问题，但是可用性却因为leader反复卸任再上任而降低。Raft的方法也很简单：如果一台主机认为还有leader，那么就不会给其他人投票。这是一个非常有效的补丁（是补丁），这个补丁完美躲避了对选举核心机制的修改，我真是不知道说什么好了。

Raft在Joint Consensus之后，引入了一阶段成员变更：在一次只变更一个成员组的情况下，成员变更可以直接从C_old变为C_new，接收到C_new的成员立刻使用新的成员组。
因为每次只变更一个成员，所以新旧多数派必有交集（可以按照奇偶加减成员四种情况穷举推算）。 那么，即使没有过渡阶段，也不会出现新旧成员组同时能够单方面做决定的情况。

日志压缩

Raft 的日志在正常操作中不断的增长，但是在实际的系统中，日志不能无限制的增长。随着日志不断增长，他会占用越来越多的空间，花费越来越多的时间来重置。如果没有一定的机制去清除日志里积累的陈旧的信息，那么会带来可用性问题。

快照是最简单的压缩方法。在快照系统中，整个系统的状态都以快照的形式写入到稳定的持久化存储中，然后到那个时间点之前的日志全部丢弃。快照技术被使用在 Chubby 和 ZooKeeper 中，接下来的章节会介绍 Raft 中的快照技术。

增量压缩的方法，例如日志清理或者日志结构合并树，都是可行的。这些方法每次只对一小部分数据进行操作，这样就分散了压缩的负载压力。首先，他们先选择一个已经积累的大量已经被删除或者被覆盖对象的区域，然后重写那个区域还活跃的对象，之后释放那个区域。和简单操作整个数据集合的快照相比，需要增加复杂的机制来实现。状态机可以实现 LSM tree 使用和快照相同的接口，但是日志清除方法就需要修改 Raft 了。

snapshap

一个服务器用新的快照替换了从 1 到 5 的条目，快照值存储了当前的状态。快照中包含了最后的索引位置和任期号。

展示了 Raft 中快照的基础思想。每个服务器独立的创建快照，只包括已经被提交的日志。主要的工作包括将状态机的状态写入到快照中。Raft 也包含一些少量的元数据到快照中：最后被包含索引指的是被快照取代的最后的条目在日志中的索引值（状态机最后应用的日志），最后被包含的任期指的是该条目的任期号。保留这些数据是为了支持快照前的第一个条目的附加日志请求时的一致性检查，因为这个条目需要最后的索引值和任期号。为了支持集群成员更新（第 6 节），快照中也将最后的一次配置作为最后一个条目存下来。一旦服务器完成一次快照，他就可以删除最后索引位置之前的所有日志和快照了。

尽管通常服务器都是独立的创建快照，但是领导人必须偶尔的发送快照给一些落后的跟随者。这通常发生在当领导人已经丢弃了下一条需要发送给跟随者的日志条目的时候。幸运的是这种情况不是常规操作：一个与领导人保持同步的跟随者通常都会有这个条目。然而一个运行非常缓慢的跟随者或者新加入集群的服务器（第 6 节）将不会有这个条目。这时让这个跟随者更新到最新的状态的方式就是通过网络把快照发送给他们。

安装快照 RPC：

在领导人发送快照给跟随者时使用到。领导人总是按顺序发送。

参数 解释
term 领导人的任期号
leaderId 领导人的 Id，以便于跟随者重定向请求
lastIncludedIndex 快照中包含的最后日志条目的索引值
lastIncludedTerm 快照中包含的最后日志条目的任期号
offset 分块在快照中的偏移量
data[] 原始数据
done 如果这是最后一个分块则为 true
结果 解释
term 当前任期号，便于领导人更新自己

接收者实现：

  1. 如果term < currentTerm就立即回复
  2. 如果是第一个分块（offset 为 0）就创建一个新的快照
  3. 在指定偏移量写入数据
  4. 如果 done 是 false，则继续等待更多的数据
  5. 保存快照文件，丢弃索引值小于快照的日志
  6. 如果现存的日志拥有相同的最后任期号和索引值，则后面的数据继续保持
  7. 丢弃整个日志
  8. 使用快照重置状态机

一个关于安装快照的简要概述。为了便于传输，快照都是被分成分块的；每个分块都给了跟随者生命的迹象，所以跟随者可以重置选举超时计时器。

在这种情况下领导人使用一种叫做安装快照的新的 RPC 来发送快照给太落后的跟随者；见图 13。当跟随者通过这种 RPC 接收到快照时，他必须自己决定对于已经存在的日志该如何处理。通常快照会包含没有在接收者日志中存在的信息。在这种情况下，跟随者直接丢弃他所有的日志；这些会被快照所取代，但是可能会和没有提交的日志产生冲突。如果接收到的快照是自己日志的前面部分（由于网络重传或者错误），那么被快照包含的条目将会被全部删除，但是快照之后的条目必须正确和保留。

这种快照的方式背离了 Raft 的强领导人原则，因为跟随者可以在不知道领导人情况下创建快照。但是我们认为这种背离是值得的。领导人的存在，是为了解决在达成一致性的时候的冲突，但是在创建快照的时候，一致性已经达成，这时不存在冲突了，所以没有领导人也是可以的。数据依然是从领导人传给跟随者，只是跟随者可以重新组织他们的数据了。

我们考虑过一种替代的基于领导人的快照方案，即只有领导人创建快照，然后发送给所有的跟随者。但是这样做有两个缺点。第一，发送快照会浪费网络带宽并且延缓了快照处理的时间。每个跟随者都已经拥有了所有产生快照需要的信息，而且很显然，自己从本地的状态中创建快照比通过网络接收别人发来的要经济。第二，领导人的实现会更加复杂。例如，领导人需要发送快照的同时并行的将新的日志条目发送给跟随者，这样才不会阻塞新的客户端请求。

还有两个问题影响了快照的性能。首先，服务器必须决定什么时候应该创建快照。如果快照创建的过于频繁，那么就会浪费大量的磁盘带宽和其他资源；如果创建快照频率太低，他就要承受耗尽存储容量的风险，同时也增加了从日志重建的时间。一个简单的策略就是当日志大小达到一个固定大小的时候就创建一次快照。如果这个阈值设置的显著大于期望的快照的大小，那么快照对磁盘压力的影响就会很小了。

第二个影响性能的问题就是写入快照需要花费显著的一段时间，并且我们还不希望影响到正常操作。解决方案是通过写时复制的技术，这样新的更新就可以被接收而不影响到快照。例如，具有函数式数据结构的状态机天然支持这样的功能。另外，操作系统的写时复制技术的支持（如 Linux 上的 fork）可以被用来创建完整的状态机的内存快照（我们的实现就是这样的）。

客户端交互

这一节将介绍客户端是如何和 Raft 进行交互的，包括客户端如何发现领导人和 Raft 是如何支持线性化语义的。这些问题对于所有基于一致性的系统都存在，并且 Raft 的解决方案和其他的也差不多。

Raft 中的客户端发送所有请求给领导人。当客户端启动的时候，他会随机挑选一个服务器进行通信。如果客户端第一次挑选的服务器不是领导人，那么那个服务器会拒绝客户端的请求并且提供他最近接收到的领导人的信息（附加条目请求包含了领导人的网络地址）。如果领导人已经崩溃了，那么客户端的请求就会超时；客户端之后会再次重试随机挑选服务器的过程。

我们 Raft 的目标是要实现线性化语义（每一次操作立即执行，只执行一次，在他调用和收到回复之间）。但是，如上述，Raft 是可以执行同一条命令多次的：例如，如果领导人在提交了这条日志之后，但是在响应客户端之前崩溃了，那么客户端会和新的领导人重试这条指令，导致这条命令就被再次执行了。解决方案就是客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。

只读的操作可以直接处理而不需要记录日志。但是，在不增加任何限制的情况下，这么做可能会冒着返回脏数据的风险，因为领导人响应客户端请求时可能已经被新的领导人作废了，但是他还不知道。线性化的读操作必须不能返回脏数据，Raft 需要使用两个额外的措施在不使用日志的情况下保证这一点。首先，领导人必须有关于被提交日志的最新信息。领导人完全特性保证了领导人一定拥有所有已经被提交的日志条目，但是在他任期开始的时候，他可能不知道那些是已经被提交的。为了知道这些信息，他需要在他的任期里提交一条日志条目。Raft 中通过领导人在任期开始的时候提交一个空白的没有任何操作的日志条目到日志中去来实现。第二，领导人在处理只读的请求之前必须检查自己是否已经被废黜了（他自己的信息已经变脏了如果一个更新的领导人被选举出来）。Raft 中通过让领导人在响应只读请求之前，先和集群中的大多数节点交换一次心跳信息来处理这个问题。可选的，领导人可以依赖心跳机制来实现一种租约的机制，但是这种方法依赖时间来保证安全性（假设时间误差是有界的）。

参考

  1. In Search of an Understandable Consensus Algorithm
  2. Raft 论文中文翻译
  3. Raft论文解读 | LoopJump's Blog
  4. raft理解