分布式学习笔记1-分布式算法Raft
简介
Raft是当今比较流行的一个分布式选举算法。在它出来之前，业界只有Paxos一种算法。但是Paxos是非常难以理解，更不用说有统一的算法方案。Raft的出现，就是为了提供一个通俗易懂，容易实现的分布式方案。研究论文和相关源码已久，写下此文笔记，希望能对你也有一些启发。
基本原理
Server状态
集群的每个机器可以有3种角色状态
Leader 每个集群只能有一个，处理所有client的请求，日志复制。
Follower 普通的Server，完全被动的，只会对收到的消息进行回应。
Candidate 候选人，当进入新一轮选举的时候，所有的候选人都会发起投票。重新选出一个新leader
三者之间的关系，可以互相转换，如果下图
最开始，所有的Server都是Follower。
如果Follower没有收到心跳，就会变成Candidate
Candidate 开始进行新一轮的选举，其中一个成为新的Leader,其余的成为Follower。
Leader如果收到更大的Term（任期）消息，就降级为普通的Follower。
Term
时间划分为不同的Term（任期）。每次导致新的选举发生，Term就会改变+1.一个Term包括两个阶段：选举和正常阶段。每个服务器都会保存当前的任期Current Term。用于发送和接受RPC消息时验证比较。
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。
当前Term 增加1。
状态由Follower变成Candidate。
给自己投票。
发送投票信息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的。
举个例子
选举最合适的Leader
当一个Log被committed时，它一定是被复制到大多数（大于1半）的server。如果要重新选举一个Leader，我们希望Candidate带上最多的committed entries。
上面RequeustVote RPC 介绍过，要么Term比较大，要么log index比较大
if(lastTermVote>lastTermC||
(lastTermVote==lastTermC)&&lastIndexVote>lastIndexC))
服务器节点更新
通常情况下，集群里面的服务器数量是固定的。但在实际生产中，经常需要扩容，缩容，所以服务器可能不断变化。我们来看下Raft是如何解决的
服务器的配置信息无法直接从旧配置转换为新配置。我们要解决的问题，就是变更期间，同一个任期不能有两个Leader选举胜出。为了保证安全，配置变更采用两阶段的办法。
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这边的集群不能单边决策
当进入join consensus之后，Leader会再提交一个新的C-new Log，其他Follower收到这个Log，就可以使用新的配置了。当C-new这个Log被committed，C-old就没有用了，不在C-new的节点可以关闭。基于这套流程，在任何时刻，C-old和C-new不会出现单边投票的情况。
三个问题
新机器初始化的时候可能没有任何存储日志。如果以这样的状态加入集群，需要花费很长时间才能赶上集群中的其他机器，这个期间机器是不能提交新日志。为了避免不可用的间隙，Raft在配置变更前引入一个新的阶段，类似Learner的角色，不参与投票，只复制日志。
leader可能不是新配置的机器。这种情况下，leader在提交新配置后就降级成Follower
最后一步删除不在新配置的机器，这些机器可能干扰中断集群。它们收不到心跳，会发起新的选举，导致当前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节点的状态信息数据，还需要通过一些额外的操作：
Leader节点必须有关于已经提交日志的最新信息。Leader在任期开始时，会提交一条空白的log，这样确保上一个term的所有log都会被提交。此时Leader拥有所有已经被committed的log
Leader会记录只读请求对应的编号readIndex，当Leader提交的位置committedIndex达到或者超过该位置后，即可响应只读请求
Leader在处理只读请求之前必须检查集群中是否有新的Leader。在处理只读请求之前，让Leader节点可以和半数以上的节点交换一次心跳。如果成功，Leader依然是最新的，readerIndex值也是整个集群中所有节点能看到的最大提交位置commitIndex。
随着日志记录不断提交，Leader节点的提交位置commitIndex最终会超过上述readIndex，此时Leader就可以响应client的只读请求了。
开源项目
BRaft 百度开源的c/c++实现的raft框架
JRaft 蚂蚁金服开源的Java实现的raft框架，参考了BRaft
Etcd 内部采用raft协议作为一致性算法，基于Go语言实现。
参考资料
《Raft论文》 （我的这篇笔记其实只是这篇伟大论文的拙劣复述）
《Raft User Study》 （简洁易懂）
《JRaft 官方文档》。（里面的原理讲得很好，后续我将写点源码笔记）
《etc技术内幕》
后记
哪里有恐惧，哪里就有爱。--《霍乱时期的爱情》2020.2.29
如果觉得有用，可以加个关注：showcodes。后续会持续更新。