raft的特性是易于理解， raft主要做了2方面的事情

1. 问题分解： 把共识算法分为三个子问题，分别是领导者选举(leader election), 日志复制(log replication), 安全性
2. 状态简化: 对算法做出一些限制，减少状态数量和可能产生的变动

复制状态机

相同的初始状态 + 相同的输入 = 相同的结束状态
共识算法就是为了实现复制状态机

状态简化

在任何时刻，每一个服务器节点都处于leader， follower或candidate这三个状态之一
raft把时间分割成任意长度的任期(term), 任期用连续的整数表示
raft算法中服务器节点之间使用rpc进行通信，并且raft中只有两种主要的rpc:

• RequestVote RPC
• AppendEntries RPC
• 服务器之间通信的时候会交换当前任期号，如果一个服务器上的当前任期号比其他的小，该服务器会将自己的任期更新为较大的那个值
• 如果一个candidate或者leader发现自己的任期号过期了，它会立即回到follower状态
• 如果一个节点接收到一个包含过期任期号的请求，他会直接拒绝这个请求

领导者选举

• Raft内部有一种心跳机制，如果存在leader, 那么它就会周期性的向所有follower发送心跳，来维持自己的地位。如果follower一段时间没有收到心跳，那么他就会认为系统中没有可用的leader了，然后开始进行选举
• 开始一个选举过程后，follower先增加自己的当前任期号，并转换到candidate状态。然后投票给自己。并且并行地向集群中的其他服务器节点发送投票请求(RequestVote RPC)
• candidate发起选举最终有3个结果
  1. 它获得超过半数选票赢得了选举 -> 成为leader并开始发送心跳
  2. 其他节点赢得了选举 -> 收到新leader的心跳后，如果新leader的任期号不小于自己当前的任期号，那么久从candidate回到follower状态
  3. 一段时间之后没有任何获胜者(比如多个candidate同时发起投票，选票过于分散) -> 每个candidate都在一个自己随机选举超时时间后增加任期开始新一轮投票；每个candidate等待随机选举超时时间之后，默认进入下一轮选举
• Raft 通过随机选举定时器来阻止选举分裂的发生，即使选举分裂发生也可以很快的被解决。选举超时将在 [150,300]ms 之间随机生成

RequestVote RPC

image.png

日志复制

• leader收到客户端的指令后，会把指令做为一个新的条目追加到日志中
• 一条日志包含3个信息
  1. 状态机指令
  2. leader的任期号
  3. 日志号(日志索引)
• leader并行发送AppendEntries RPC给follower，让他们复制该条目。当该条目被超过半数的follower复制后，leader久可以在本地执行该指令并把结果返回客户端
• 我们把本地执行指令，也就是leader应用日志到状态机这一步，称作commit
• 在此过程中，leader或follower随时都有崩溃或缓慢的可能性。 Raft必须要在有宕机的情况下继续支持日志复制。并且保证每个副本的日志顺序一致。具体为重试+一致性检查:
  1. 如果follower因为某些原因没有给leader响应，那么leader会不断的重复发送AppendEntries RPC, 哪怕leader已经回复了客户端
  2. 如果follower崩溃后恢复，这时AppendEntries RPC一致性检查生效，保证follower能按顺序回复崩溃后缺失的日志。
     raft的一致性检查： leader在每一个发往follower的AppendEntries RPC中，会放入前一个日志条目的索引位置和任期号，如果follower在它的日志中找不到前一个日志，那么它就会拒绝此日志，leader收到follower的拒绝后，会发送前一个日志条目，从二逐渐向前定位到follower第一个缺失的日志
  3. leader崩溃，那么崩溃的leader可能已经复制了日志到部分follower但还没提交，而被选出的leader又有可能不具备这些日志，这样就有部分follower中的日志和新leader的日志不相同
     raft在这种情况下，leader通过强制follower复制它的日志来解决不一致的问题，这意味着follower中跟leader冲突的日志条目会被新leader的日志条目覆盖(因为没有commit，所以不违背外部一致性，已经commit的日志，需要后边1条选主的限制来解决)
• 总结
  1. 通过这种机制，leader在当选之后久不需要任何特殊的操作来使日志恢复到一致状态
  2. leader只需要进行正常的操作，然后日志就能在回复AppendEntries一致性检查失败的时候自动趋于一致
  3. leader从来不会覆盖或者删除自己的日志条目
  4. 这样党日志复制机制，就可以保证一致性特性
  5. 只要过半的服务器能正常运行，Raft就能够接受、复制并应用新的日志条目
  6. 在正常情况下，新的日志条目可以在一个rpc来回中被复制给集群中的过半机器
  7. 单个运行缓慢的follower不会影响整体的性能

Logs

leader重选之后的日志不一致

AppendEntries RPC

安全性

• 领导者选举和日志复制两个子问题实际上已经涵盖了共识算法的全程，但这两点还不能完全保证每一个状态机会按照相同的顺序执行相同的命令
• 所以raft通过几个补充规则完善整个算法，使算法可以在各类宕机问题下都不出错
• 这些规则包括：
  1. leader宕机处理： 选举限制
  2. leader宕机处理： 新leader是否提交之前任期内的日志条目
  3. follower和candidate宕机处理
  4. 时间与可用性限制

leader宕机处理： 选举限制

• 如果一个follower落后了leader若干条日志(但没有漏一整个任期), 那么下次选中，按照领导者选举的规则，它依旧有可能当选leader。它在当选新leader后就永远也无法补上之前缺失的那部分日志，从而造成状态机之间的不一致
• 所以需要对领导者选举增加一个限制: 保证被选出来的leader一定包含了之前各任期的所有被提交的日志条目(留意提交的概念)
• RequestVote RPC执行了这样的限制: RPC中包含了candidate的日志信息，如果投票者自己的日志比candidate的还新，它会拒绝掉该投票请求
• raft通过比较两份日中中最后一条日志条目的索引值和任期号来定义谁的日志比较新
• 如果两份日志最后条目的任期号不同，那么任期号大的日志更“新”
• 如果两份日志的最后条目的任期号相同，那么日志较长的那个更“新”

leader宕机处理： 新leader是否提交之前任期内的日志条目

• 一旦当前任期内的某个日志条目已经存储到过半的服务器节点上，leader就知道该日志条目可以被提交了
• follower的提交出发: 下一个AppendEntries RPC，心跳or新日志
• raft的commit表示单点commit，无明确的机群commit
• 如果某个leader在提交某个日志条目之前崩溃了，以后的leader会试图完成该日志条目的入职
• 复制而非提交，不能通过心跳提交老日志
• Raft永远不会通过计算副本数目的方式来提交之前任期内的日志条目
• 只有leader当前任期内的日志条目才通过计算副本的方式来提交
• 一旦当前任期的某个日志条目以这种方式被提交，那么犹豫日志匹配特性，之前的所有日志条目都会被间接提交(相当于用一个新任期内的日志把旧日志保护起来了)

leader不能根据复制日志确定之前任期的日志是否可提交

follower和candidate宕机处理

• follower和candidate奔溃后的处理方式比leader崩溃要简单的多，并且两者的处理方式是相同的
• 如果follower或candidate崩溃了，那么后续发送给他们的RequestVote和AppendEntries RPCs都会失败
• Raft通过无限的重试来处理这种失败，如果崩溃的机器重启了，那么这些rpc就会成功地完成
• 如果一个服务器在完成了一个RPC，但是还没有响应的时候崩溃了，那么它重启之后就会再次收到同样的请求(Raft的RPC都是幂等的)

时间与可用性限制

• raft算法整体不依赖客观时间，也就是说，哪怕因为网络或其他因素，造成后发的RPC先到，也不会影响raft的正确性
• 只要整个系统满足下面的要求，Raft就可以选举出并维持一个稳定的leader
• 广播时间(BroadcastTime) << 选举超时时间(electionTimeout) << 平均故障时间(MTBF)
• 广播时间和平静故障时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft的RPC需要接受并将信息落盘，所以广播时间大约0.5ms到20ms，取决于存储到技术。因此，选举超时时间可能需要在10ms到500ms之间。大多数服务器的平均故障时间都在几个月甚至更长。

集群成员变更

问题

• 在需要改变集群配置的时候，raft可以进行配置变更自动化
• 自动化配置变更机制的最大难点是保证转换过程中不会出现同一任期的两个leader，因为转换期间整个集群可能划分为两个独立的大多数

• 下图中的直接切换可能导致2个leader

  
  
  变更配置直接切换可能导致脑裂

联合一致

• 配置变更采用了一种两阶段的方法
• 集群先切换到一个过渡到配置，成为联合一致(joint consensus)
• 第一阶段，leader发起C_old,new, 使整个集群进入联合一致状态。这时，所有RPC都要在新旧两个配置中都达到大多数才算成功
• 第二阶段，leader发起C_new, 使这个集群进入新配置的状态。这时，所有RPC只要在新配置下能达到大多数就算成功

配置生效

• 配置信息座位一个日志体包装为一个普通的AppendEntries RPC，发给所有的followers
• 一旦某个服务器将该新配置日志条目增加到自己的日志中，他就会用该配置来做出未来所有的决策(服务器总是使用它日志中最新的配置, 无论该配置日志是否已经被提交)
• 这意味着leader不用等待C_old,new和C_new返回，就会直接使用其中的新规则来做出决策

配置变更的时间线

leader在C_old,new未提交时宕机

• 已经同步到C_old,new的节点使用C_old发起选举, 已经同步的使用C_old,new联合一致规则发起选举，无论哪种节点，都需要C_old配置的大多数选票才能当选leader，所以不会出现多个leader。
• 新当选的节点，如果没有C_old,new，那么配置变更信息丢失，变更失败
• 如果新当选的leader由C_old,new，按照日志复制的规则，raft不会直接提交之前任期的log，即新leader不会直接提交C_old,new。
  留意正常流程是C_old,new commit之后发器C_new，但这个特殊场景下可以继续发起C_new,只是提交规则不明确，某些设计中强制要求按照联合一致规则提交，如果leader满足不了条件，自动退位。

leader在C_old,new已提交但C_new未发起时宕机

• 这时候选举限制安全性规则决定了选出的新leader一定具有C_old,new，也不会有多个leader
• 留意联合一致状态下，也是可以正常执行命令的，但也需要在两个配置集群中都达到大多数才能提交
• C_old,new提交后，leader就会发器C_new

leader在C_new已发起时宕机

• C_new先后同步到各个节点
• 此时因为C_old,new已经复制到新旧配置两个集群的大多数节点，所有选出的leader已不可能是C_old。后续的选举出来的leader，要么是C_old,new，要求满足新旧两个配置集群的大多数选票，要么是C_new, 要求满足新集群的大多数选票。两种可能性要求满足新配置的大多数选票，所有不会出现多个leader
• 留意缩减节点的情况下，即将remove的节点不会复制C_new, 这些节点在C_new commit之后无法当选为leader，因为无法得到新集群的多数选票

补充规则

1. 新增节点时，需要等新增的节点完成日志同步再开始集群成员变更
   这点是防止集群新增节点还未同步日志时就进入联合一致状态或新配置状态，影响正常命令日志提交
2. 缩减节点时，leader本身可能就是要缩减的节点，这时它会在完成C_new后自动退位
   在发起C_new后，要退出集群的leader就会处在操作一个不包含它本身的raft集群的状态下。这时他可以发送C_new日志，但是日志计数时不计自身。
3. 为了避免下线的节点超时选举而影响集群运行，服务器会在它却心集群中有leader存在时拒绝RequestVote RPC

• 因为C_new的新leader不会再发送心跳给要退出的节点。如果这些节点没有及时下线，它们会超时增加任期号后发送RquestVote RPC。虽然它们不可能当选leader，但会导致raft集群进入投票选举阶段，影响集群的正常运行
• 为了解决这个问题， Raft在RequestVote RPC上补充了一个规则：一个节点如果在最小超时时间之内收到RequestVote RPC，那么它会拒绝此RPC
• 这样，只要follower连续收到leader的心跳，那么退出集群节点的RequestVote RPC就不会影响raft集群的正常运行了

单节点成员变更

• 每次只增减一个节点，相比于多节点变更，最大的差异时新旧配置集群的大多数，是一定会有重合的。比如3节点扩展为4节点，旧集群需要至少2个节点满足大多数，剩下的2个节点点无法满足新集群的大多数
• 连续的两次变更，第一步变更的过程中如果出现了切主，那么紧跟着的下一次变更可能错误。 解决方法时新leader通过no-op日志把之前的配置覆盖掉

参考

https://raft.github.io/