分布式教程1-分布式算法Raft入门

简介

Raft是今比较流行的一个分布式选举算法。在它出来之前，业界只有Paxos一种算法。但是Paxos是非常难以理解，更不用说有统一的算法方案。Raft的出现，就是为了提供一个通俗易懂，容易实现的分布式方案。研究论文和相关源码已久，写下此文笔记，希望能对你也有一些启发。

基本原理

Server状态

集群的每个机器可以有3种角色状态

• Leader 每个集群只能有一个，处理所有client的请求，日志复制。
• Follower 普通的Server，完全被动的，只会对收到的消息进行回应。
• Candidate 候选人，当进入新一轮选举的时候，所有的候选人都会发起投票。重新选出一个新leader

三者之间的关系，可以互相转换，如果下图

raft1.png

1. 最开始，所有的Server都是Follower。
2. 如果Follower没有收到心跳，就会变成Candidate
3. Candidate 开始进行新一轮的选举，其中一个成为新的Leader,其余的成为Follower。
4. Leader如果收到更大的Term（任期）消息，就降级为普通的Follower。

Term

时间划分为不同的Term（任期）。每次导致新的选举发生，Term就会改变+1.一个Term包括两个阶段：选举和正常阶段。每个服务器都会保存当前的任期Current Term。用于发送和接受RPC消息时验证比较。

raft2.png

Log Entry

每一个client操作，对于Leader来说，都是增加一个Log Entry，然后复制同步到其他的Server。包括以下数据：

• term Leader收到log时的term
• index log下标。log存储结构是一个List
• command 操作指令

Persistent State 持久化状态

每个server都会在本地存储一些持久化状态，每次在相应rpc时先持久化

• currentTerm 当前Term，启动的时候是0
• voteFor 当前term收到的投票
• log[] 日志数据

选举过程

当一个Follower没有收到Leader的心跳时，就会投票开始新一轮的选举。所以当Leader出现故障时，可能有多个Follower变成Candidate开始投票。这里有个细节，就是开始的时间是不同的，是一个随机100-500ms，这样可以更快速产生新的Leader。

1. 当前Term 增加1。
2. 状态有Follower变成Candidate。
3. 给自己投票。
4. 发送投票信息RequeustVote给所有的Server，一直重试，直到以下情况之一发生才停止：
   • 收到大多数(>=n/2+1)的Server投票给自己，然后变成新一轮的Leader，开始发送心跳AppendEntry给其他的Server。
   • 收到新Leader的RPC，状态变成Follower
   • 没有人选举成功。增加Term，开始新一轮的选举。

RequeustVote RPC

参数

• candidateId 投票的candidate
• term candidate当前的term
• lastLogIndex 上一个Log的index
• lastLogTerm 上一个Log的term

返回值

• term 当前term
• voteGranted 如果是true表示赞同投票

实现过程

1. if (term>currentTerm){
    currentTerm = term;
    //如果是（Leader or Candidate） -> Follwer
}
2. if（term==currentTerm）{
    //本轮还没收到过其他的投票
    if（voteFor==null||voteFor==candidateId）{
        if（candidateLog >=本地的log）{
            赞同本次选举
            自己不再进行本轮主动投票
        }
    }
    
}

日志复制

当前Term如果处于正常状态，那么就可以接受client的请求。

• client向Leader发送command
• Leader 将command增加到log[]
• Leader 向所有的Follower发送AppendEntry RPC
• 如果有大多数（大于一半）的请求有响应，Leader将command提交到自己的状态机，然后返回消息给client。
• Follower 也将command提交到自己的状态机。
• 如果Follower crash或者很慢响应，那么Leader会继续重试直到成功

AppendEntries RPC

参数

• term Leader的当前Term
• leaderId Follower可以重新和新Leader交互
• preLogIndex 倒数第二个Log Index
• preLogTerm 倒数第二个Log的Term
• entries[] 存储的log entry
• commitIndex 即将commit的的entry

返回值

• term 当前term，用于Leader更新自己的（如果Leader发现自己的是旧的，就会退回Follower）
• succes 是否成功，如果preLogIndex和preLogTerm在本地能找到

实现过程

//太旧的Term，说明这个Leader已经失效了
if(term<currentTerm){
    return false
}
if（term>currentTerm）{
    currentTerm = term
}
//如果是candidater or leader，重新变成Follower
//如果找不到一个log，同时匹配preLogIndex和preLogTerm，return false
//删除冲突的entry
//添加新的entry
//更新本地的状态机

异常情况

Log一致性

• 如果在不同的Server 有相同的index和term那么表明：
  • 他们存储相同的Command
  • 在这个log之前的所有entry也是相等的
• 如果一个指定的entry被committed，那么在它之前的所有entry也是committed

基于上面的论证，每次AppendEntries RPC都会带上当前entry的前一个log信息，包括index和term，如果Follower找不到，就说明两者的log不一致了，需要删除冲突的，填上新加的，然后再提交本次需要committed的。

举个例子

raft3.png

选举最合适的Leader

当一个Log被committed时，它一定是被复制到大多数（大于1半）的server。如果要重新选举一个Leader，我们希望Candidate带上最多的committed entries。

上面RequeustVote RPC 介绍过，要么Term比较大，要么log index比较大

if(lastTermVote>lastTermC||
(lastTermVote==lastTermC)&&lastIndexVote>lastIndexC))

服务器节点变更

通常情况下，集群里面的服务器数量是固定的。但在实际生产中，经常需要扩容，缩容，所以服务器可能不断变化。我们来看下Raft是如何解决的

服务器的配置信息无法直接从旧配置转换为新配置。我们要解决的问题，就是变更期间，同一个任期不能有两个Leader选举胜出。为了保证安全，配置变更采用两阶段的办法。

rafe4.png

Raft引入了一个过渡状态-joint consensus。节点成员的变更，Leader会将C-old和C-new都放在joint consensus（也就是下图的C-old-new）,然后作为一个Log发送给其他的Follower。其他Follower收到后，可以马上使用最新的节点数据，不需要等待log被committed。注意，此时只有C-old里面的集群可以进行选举。如果此时Leader down，新选出 的Leader在C-old or C-old-new。 C-new这边的集群不能单边决策

rafe5.png

当进入join consensus之后，Leader会再提交一个新的C-new Log，其他Follower收到这个Log，就可以使用新的配置了。当C-new这个Log被committed，C-old就没有用了，不在C-new的节点可以关闭。基于这套流程，在任何时刻，C-old和C-new不会出现单边投票的情况。

三个问题

1. 新机器初始化的时候可能没有任何存储日志。如果以这样的状态加入集群，需要花费很长时间才能赶上集群中的其他机器，这个期间机器是不能提交新日志。为了避免不可用的间隙，Raft在配置变更前引入一个新的阶段，类似Learner的角色，不参与投票，只复制日志。
2. leader可能不是新配置的机器。这种情况下，leader在提交新配置后就降级成Follower
3. 最后一步删除不在新配置的机器，这些机器可能干扰中断集群。它们收不到心跳，会发起新的选举，导致当前leader回退到Follower。新的leader被选举出来，但是旧机器将会再次超时。这个过程不断重复。为了避免这个问题，servers在确定leader存在的情况下将不理会RequestVote。如果一个机器在最小超时时间下收到当前term的vote，他将不更新自己的term，也不参与本次选举。这样做并不会影响正常的选举。

日志压缩

随着集群的运行，机器的日志将会不断增长。为了保证集群的可用性，需要额外的机制来删除日志中过期的日志。快照是最简单的压缩方法。

每个机器独立进行快照，快照只需要覆盖已经提交的日志。更多的工作是状态机将自己的当前状态写入快照中。Raft中包含了少量的metadata在快照中：

• last included index 日志中最后一条被快照取代的日志的索引（也是状态机应用的上一条日志的索引）
• last included term 这条日志对应的Term

这些被持久化用来支持AppendEntries的日志一致性检测，如前面提过，日志的一致性检测需要前一条日志的Term和索引。为了支持集群成员变更，快照也包含了最后一条被快照取代的日志所使用的配置。一旦机器完成快照，它将可以删除last included index 之前的所有日志，也包括之前的快照。

正常情况下，机器都是单独的进行快照。但是在某些情况下，leader也会发送快照到那些落后的机器上。发送快照可以是分段发送的，带上偏移量。具体的过程如下所示。

InstallSnapshot RPC

参数

• term Leader的当前Term
• leaderId Follower可以重定向到Leader
• lastIncludedIndex 快照替换的最后一条日志记录的索引
• lastIncludedTerm 快照替换的最后一条日志记录的索引的Term
• offset 快照中的字节偏移量
• data[] 数据块，从偏移量开始存储
• done 是否最后一个块文件

返回值

• term 当前term，用于Leader更新自己

实现过程

//太旧的Term，说明这个Leader已经失效了
if(term<currentTerm){
    return false
}
if（偏移量==0）{
    创建新的快照文件
}
在快照文件的指定偏移量写入数据
if（！done）{
    return 响应 等待更多的块数据
}
保存快照文件，删除快照之前的日志
如果存在快照点之后的日志文件，保留这些日志并重放
删除整个日志文件
使用快照的状态来重置状态机，并加载快照中的配置

线性读

我们之前讲过，client的每个操作，leader都要封装成一个log，复制到所有的节点。如果只是读操作，我们其实是可以提高性能，不进行日志复制的。但是要避免返回脏数据的风险。因为Leader节点响应client请求时可能已经故障（或者是发送了网络分区），集群中已经选出了新的Leader，但是此时旧Leader自己还不知道。

Raft在处理只读请求，除了直接读取Leader节点的状态信息数据，还需要通过一些额外的操作：

1. Leader节点必须有关于已经提交日志的最新信息。Leader在任期开始时，会提交一条空白的log，这样确保上一个term的所有log都会被提交。此时Leader拥有所有已经被committed的log
2. Leader会记录只读请求对应的编号readIndex，当Leader提交的位置committedIndex达到或者超过该位置后，即可响应只读请求
3. Leader在处理只读请求之前必须检查集群中是否有新的Leader。在处理只读请求之前，让Leader节点可以和半数以上的节点交换一次心跳。如果成功，Leader依然是最新的，readerIndex值也是整个集群中所有节点能看到的最大提交位置commitIndex。
4. 随着日志记录不断提交，Leader节点的提交位置commitIndex最终会超过上述readIndex，此时Leader就可以响应client的只读请求了。

开源项目

1. BRaft 百度开源的c/c++实现的raft框架
2. JRaft 蚂蚁金服开源的Java实现的raft框架，参考了BRaft
3. Etcd 内部采用raft协议作为一致性算法，基于Go语言实现。

参考资料

1. 《Raft论文》 （我的这篇笔记其实只是这篇伟大论文的拙劣复述）
2. 《Raft User Study》 （简洁易懂）
3. 《JRaft 官方文档》。（里面的原理讲得很好，后续我将写点源码笔记）
4. 《etc技术内幕》

后记

哪里有恐惧，哪里就有爱。--《霍乱时期的爱情》2020.2.29