• raft-extended论文精读
  • 可复制状态机
  • Paxos的弊端与Raft对应的优势
  • Raft算法
    • Leader选举
    • Log复制
    • Safety
      • 数据最新的candidate才能赢
      • 处理前一任期遗留的未提交数据？
    • Joint Consensus
    • Log 瘦身
  • 客户端API
• MIT-Lab2
  • 2A:LeaderElection&Heartbeat
  • 2B:LogReplication
  • 2C:Persistance&Recovery
• 参考文献

分布式环境中，对于有状态的服务的高可用性保证，常常采用加备机的方式处理；主备的方式，需要处理failover的问题；并且备机只是不断的同步数据；在决策中，没有主动权；在主挂机时，也不会主动切换。相对地，共识算法是在一群机器中，确保大家行为一致，而不是一个节点处理所有问题。

我这里对一组需要达成一致的机器称为共识组，共识组内使用Paxos或者Raft等共识算法保证一致性。本文主要介绍Raft算法。

raft-extended论文精读

相对于Paxos算法的难以理解，Raft是一个相对容易理解的共识算法；其将算法分为多个模块，并减少了状态空间的复杂度，这样减少了整体的不确定程度，使其更容易理解与实现。Raft有如下特点：

• StrongLeader：logentries只能从leader向follower流动；
• LeaderElection：在共识组中，按照随机时间触发Leader选举，这在原来的hearbeat中只添加了很少的额外工作。
• MembershipChange：基于joint consensus过程，向共识组中添加新的成员；在过渡过程中，保证共识组仍能正常工作。

可复制状态机

拜占庭将军问题 : 在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的，或不存在本问题。

对于系统设计中的单点问题，如果是一个无状态的服务，那么可以无脑的分成多个节点，前端加一个负载均衡。而一个有状态的服务可以认为是一个状态机，要保证的状态机的可用性，除了主备的方式，就是采用共识算法，将状态机进行复制，并保证各个节点的信息始终一致。

生产中可用的共识算法，需要有如下特性：

• 在非拜占庭情况下（包括网络延迟、网络分割、丢包、重复发送、信息乱序），保证信息的安全，即不会返回一个错误的结果。

• 在多数节点可用时，保证系统的可用性。
• 不依赖时间来保证日志的一致性，因为如果时钟有错，或者信息延迟很长时间，那么会造成系统长时间不可用。
• 多数节点完成了一个指令后，那么就应该对client进行响应；不应因为少数节点，影响整体性能。

Paxos的弊端与Raft对应的优势

Paxos首先定义了一个BasicPaxos，对单个logentry进行共识决策；然后结合多个BasicPaxos，实现一个MultiPaxos，对多个logentry进行决策；其可用性和正确性都被证实过，但是有两个显著的弊端：

1. 难以理解
2. 没有leader的对等架构，实现起来比较复杂，导致最终实现区别比较大。

针对Paxos的弊端，Raft设计出来了；主要解决的问题就是更容易被人理解，进而更加容易使用；

首先Raft将需要解决的问题进行分解，分解为：leaderelection、logreplication、safety、membershipchange。然后，减少需要维护的状态，进而减少系统可能的不确定性，比如，日志中不能有空洞。

Raft算法

Raft首先在共识组中选出一个leader，然后由leader全权处理LOG的复制；leader首先从client处得到logentry，然后将该logentry请求复制转发到其他server中；在该logentry标记commited后，leader再通知其他server进行apply。这样由leader来统一处理，简化了日志的复制管理。由此，Raft算法可分为以下几个部分：

• Leader Election：当leader失效后，需要选举处一个新的leader。
• Log Replication：leader收到新log entry时，需要及时复制给其他server，并确保其他log与自己本地log达成一致。
• Safety：当某个server将某个log index处的log进行了apply后，那么在整个集群内，该log index处都应该apply同一条log。
• membership change：增加或删除共识组内的节点。

在Raft共识组中，任何时间只有三种角色：Leader/Follower/Candidate。大部分时间为一个leader和多个follower；candidate用在新leader选举中。follower是一个被动节点，只是响应leader和candidate的请求；如果client连接到了follower上，也是会被转发到leader上处理。共识组中的信息交互通过rpc，主要有三种：

• RequestVote：Candidate发起投票请求；
• AppendEntries：Leader复制log entry，以及发送hearbeat。
• TransferSnapshot：传输快照信息

Raft确保共识组运行中，始终满足以下五个特性：

1. Election Safety：每个term中最多只有一个leader；见Leader选举章节
2. Leader Append-Only：Leader对于自己的日志只会追加，不修改和删除；见Log复制章节
3. Log Matching：如果两个日志包含一个logindex和term都相同的entry，那么该Entry之前的日志都相同；见Log复制章节
4. Leader Completeness：如果一个log entry在某个term中已经提交了，那么之后的term换了leader，该commited的entry仍然在日志中。见Safety章节。
5. State Machine Satety：如果状态机已经应用了某条日志，那么在该logindex处，不能apply其他entry。见Safety章节。

Leader选举

Raft以任期（term）的方式划分时间，每个任期开始的时候，进行一次选举；在每次选举中，可能有一个或多个candidate；term是一个单调递增的序列，在每个server中，存储了一个current term，并且会和其他server进行交换，如果发现自己的term比别人的小，那么就更新为大的term（如果自己的角色不是follower，那么就降级为follower）。

RequestVote：

当离leader的最后一条信息的时间超过election timeout，超时后follower变成candidate，递增自己的term，并发调用RequestVote，向其他server请求投票；在任一任期内，收到RequestVote请求的server，只能给一个candidate投票。

如果candidate收到一个leader的AppendEntries请求，如果该请求的term值比自己的term值大，那么自己在该term内成为follower，否则拒绝该请求，继续选举。

另外，有可能在某个任期内，很多follower同时变成candidate，那么可能由于分票，导致选举失败；Raft采用随机设置election timeout的方式（每个follower的超时时间的随机的[150ms, 300ms]），减少多个follower同时选举的情况，来减少这个问题。

这里除了采用随机超时的方式解决外，还可以考虑了给各个server一个优先级排序；但是在实际情况中，不如随机超时效果好。

Log复制

Log中每个Entry包含一个logindex和一个termid，用来保证每个logindex的内容都是唯一的；并且有如下保证：

• 在共识组的两个不同log中，如果logentry有相同的logindex和term，那么其中的内容是相同的；由于leader在每个index处，只创建一个logentry，并且follower不会更改logentry的位置，那么可确保该项成立。

• 在共识组的两个不同log中，如果logentry有相同的logindex和term，那么之前的logentry都是相同的；leader在AppendEntries请求中，会带上new logentry前一个logentry的logindex和term，如果follower在本地日志中没有找到该项logentry，就拒绝这个new logentry，直到follower响应了AppendEntries请求， 那么leader就知道follower已经同步到的该位置，如下图：

  

当新leader初始化时，对于每个follower初始化一个nextIndex（等于leader当前的index），然后通过多次AppendEntries，将nextIndex向前推进到正确的位置中。

后续leader发送的new entry，当follower发现new logentry和follower本地的相同index处的logentry不同时，用new logentry覆盖

这里可能会覆盖已经commit的日志，那么存在问题，下一章针对该问题进行讨论如何避免，其实这就是保证Leader Completeness。

综上，发现只要有大多数节点活着，大部分情况下，一次rpc就能提交，那么我们可以得出一次提交的过程如下：

1. client请求leader
2. leader将client的command封装成logentry，记在本地log中
3. leader通过AppendEntries将变更发送给follower；
4. follower收到logentry将其写到本地log中，该logentry状态为uncommited；
5. leader收到大多数follower的ack，那么该变更标记为commited；对于没有收到ack的follower继续重试。
6. leader将commited的logentry应用到state machine中，leader给client返回成功；在leader的AppendEntries请求中会包含最大的commited的logindex，这样follower都知道当前可提交的logentry。

脑裂

当发生脑裂时，如果老leader在少节点的部分，那么发过来的请求，一直不能提交，从而在网络恢复时，收到新leader的请求，然后被新的logentry覆盖；

在不存在leader的部分，这些节点会不断的进行选举，但是总是选举失败，那么termid会递增，最终在网络恢复的时候termid比实际的leader的termid大；当实际的leader发来AppendEntries请求时，就会拒绝该请求，并把自己的termid发给leader，那么leader的任期就更新为更大的term了，下次AppendEntries，就会把这个candidate收编了。

Safety

数据最新的candidate才能赢

在Raft的vote过程中，只有包含所有commited的entry的candidate才会赢得选举；candidate在发起RequestVote请求中，会包含自己的log信息；follower收到请求后，会判断自己的log是否比candidate的log更新（如何比较日志更新？见下文），follower只会响应比自己新的candidate的请求；那么，只有上一个term的多数派中的其中一个follower，才有可能成为新的leader，因此，新的leader永远包含所有commited的数据，而之后只是接着向后写，不会更改自己的log（满足了Leader Completeness，只要满足了Leader Completeness，State Machine Completeness也就能够保证了）。

如何比较日志更新？

if my_termid > can_termid:
  return "I am later"
elif my_termid == can_termid and my_logindex > can_logindex:
  return "I am later"
else:
  return "he is laster"

处理前一任期遗留的未提交数据？

一个新的leader中，可能有一些之前没有标记commited的entry；对于这些日志，不能简单的采用多数派的方式来提交，考虑以下情况：

在c时间点处，S5挂了，S1作为新leader；S1将之前term=2的日志复制到S3中，这时满足了多数派；如果，就这样提交了前任期的日志，那么如果此时S1挂了，S5起来了，S5同样复制自己的遗留entry，这时就会把已经提交的日志覆盖了，这就有问题了。

解决办法就是，新的leader只负责复制遗留的entry，然后通过多数派的方式提交当前term的日志，如果提交了当前term的日志，由于Log Matching机制，那么之前的也间接提交了。那么，按照这种方式，即使在d处S5成为新的leader，其覆盖的数据也只是没有提交的数据，不会影响正确性。

由于只有包含最新commited的logentry的candidate才会赢得选举，所以一旦在e处S1提交了新entry，那么，S5就不会被选举成功了

对于Follower和Candidate的失效，leader会不断的重试；即使follower在完成了rpc请求后，挂了，由于Raft的Rpc请求是幂等的，重启后，再次重复也没事。

Raft的Safety需要保证不和时间相关，即不会因为某个事件发生的过快或过慢影响整个共识算法的Safety。这里需要确定election timeout时间，即保证 broadcastTime << electionTimeout << MTBF

• broadcastTime是一个server并发给其他server发送RPC，并得到响应的时间，一般rpc要求接受者落盘，那么这个时间一般在0.5ms到20ms之间（取决于使用的存储技术）。
• electionTimeout是何时发起新的选举，一般就是10ms到500ms。
• MTBF是单个server失效的平均间隔时间（一般是以月为量度）

Joint Consensus

在集群配置变更的过程中，无法保证所有节点同时变更；因此，在变动过程中，由于同一时刻存在两种配置，会对majority的认识不一致（如上图）；那么为了保证配置变更时的集群安全，Raft采用两阶段的方式，如下图。

相比于其他两阶段的方式，Raft的两阶段不会阻塞客户请求，其添加了一个过渡期（称为joint consensus，见上图红色部分），过渡期是RaftLog是[C_old_new,C_new)的日志段，这段日志可以理解为在C_old和C_new两个共识组中进行双写，因此，就算在joint consensus中Leader挂了，然后回滚到C_old配置，数据也不会丢失；

注意上图的虚线分别只对应两个日志记录，在虚线内不会有其他记录提交，也不会存在虚线内到底按照什么配置决策的问题。

joint consensus有以下三个特点：

• 过渡期收到的log entry，会按照C_old和C_new，复制到所有的server上。
• 不管是采用新配置还是老配置的server，都可能成为leader。
• 一致性的达成（选举或者logentry提交）需要得到C_new的majority和C_old的majority，而不是只得到一个majority。

那么，配置变更的流程总结如下：

1. 当leader收到了配置变更的请求后，将C_old和C_new结合，生成一个特殊的logentry——C_old_new，将其复制到其他所有新老server中；

2. 当前Leader请求提交C_old_new；

3. 当follower收到C_old_new记录后，就可以使用C_old_new的配置了，以后该server的任何决策都基于这个配置，比如说当前leader挂了，这个follower成为新leader，那么其会按照C_old_new的方式决策（注意这个C_old_new在follower的生效不会等待commit，而是收到后立马生效）

   C_old为{1,2,3}，C_new为{2,3,4,5,6}；leader发起一个投票，如果2/3号节点投票了，那么C_old.majority++，C_new.majority++；

4. 当前leader收到C_old中的majority和C_new中的majority后，C_old_new就可以提交了，之后就进入了joint consensus状态。

5. 在joint consensus中，仍然可以接受客户端请求；只是共识方式，需要old和new都同意。此时，相当于数据在两个配置中进行双写，那么就可以考虑摆脱C_old了。

6. 之后，leader自己产生一个C_new的记录，请求在C_new中commit；注意这之后，当前的Leader就只需要C_new的majority同意即可。

7. 此时，收到C_new记录的follower，就开始按照C_new配置进行后续操作了，就不认识不在C_old中的节点了。

   NOTE：此时如果当前Leader挂掉，如果C_new已经复制给新配置中的多数节点，那么选出的新Leader可能是C_new状态(完成配置变更)；否则，还是C_old_new状态。

8. 最后，C_new提交，那么集群就完成了配置变更；这时不在C_new中的follower可以直接关闭了。

   NOTE：最后C_new提交的时候，可能leader不在C_new配置中；leader在C_new提交的时候判断自己是否在C_new中，如果不在，自己降级为follower。此时相当于C_new配置的起点，所有server都是follower，然后发起一次选举，选出新的leader 。

对于不在C_new中的，被删除的节点A，由于自己不在集群中了，但是处于C_old_new状态，超时没有收到heartbeat，会自己向C_old和C_new发起RequestVote请求，这样会将C_new的当前leader变成follower，然后在C_new中，选出一个新leader，但是新leader还是不会给A发送hearbeat，那么这个A还会继续骚扰新leader，周次往复；为了避免这个问题，如果节点的election timeout尚未超时，那么本节点认为leader存在，不会理会这个RequestVote请求。

另外，新加入的节点可能需要很久才能追上数据，Raft在配置变更之前，会等待这些新节点先把数据追上，在追数据的过程中，这些节点不作为majority的投票者。

Log 瘦身

在实际环境中，日志不可能永远保留着；在数据库中，我们在日志中会定义一个检查点（Checkpoint），检查点之前的日志可以删除；在Raft中，定义了一个Snapshot，其描述了当前状态机的状态，对于该Snapshot状态之前的日志可以删除。在共识组中的所有server都可以创建自己的Snapshot。

如果只允许Leader才能创建Snapshot，那么Leader的实现逻辑就会变得很复杂，即在传输Snapshot的过程中，还要保证Client的响应正常；并且，创建Snapshot的信息在每个server都有，那么每个Follower产生自己的Snapshot是很容易的，没有必要限制只在Leader才可以。

对于请求snapshot之前的记录的follower，leader直接通过InstallSnapshot调用，将Snapshot发送给Follower。

Follower可以不知道Leader是谁的情况下，而获取Snapshot，这和Raft的Strong Leader原则有点出入。但是Snapshot中的数据都是已经达成一致的数据，因此不会存在冲突的问题。而获取Snapshot之后，Follower还是只从Leader处拉数据。

另外，SnapShot的产生是一个代价较大的操作；为了不影响正常流程，我们应该考虑做Snapshot的间隔（以时间为计量，或者以日志大小为计量），并且可以采用操作系统的Copy-on-Write策略，在内存中创建一个Snapshot。

客户端API

Client在连接共识组的时候，首先会随机找一个server；如果是Leader那么OK，不是的话，就会返回上次AppendEntries的Leader。那么Client就会连接这个Leader，而这个Leader如果也挂了；那么Client就会超时重试上述流程；

当Leader在提交某个entry后到返回Client提交成功之前挂了，那么客户端重试时，会重复执行；解决方式就是加一个唯一ID，在执行前检查该请求是否被处理过了。

在Leader刚启动的时候，自己并不知道目前日志提交到什么位置了；只有在自己的term内，提交了一个日志后，那么才知道这个最后提交点；那么，在Leader刚启动的时候会写一个no-op的logentry。

lease，Leader确认自己的租约

Leader对于收到的Read-Only请求，在回复前，回向集群的majority发送hearbeat，确认现在我的lease还有效，即没有新主产生。

MIT-Lab2

//TODO

2A:LeaderElection&Heartbeat

2B:LogReplication

2C:Persistance&Recovery

参考文献

raft extend

joint consensus

commit previous entry