Raft协议

Paxos算法不容易实现，Raft算法是对Paxos算法的简化和改进。

Raft算法将一致性问题分解为两个的子问题，Leader选举（Leader election）和日志复制（Log Replication）。

Raft协议的节点有三种状态：Leader、Follower、Candidate。

Leader：所有对系统的修改都会先经过leader。每个修改操作都会写一条日志，然后将日志复制到所有Follower节点，多数Follower节点响应时才提交日志，然后通知Follower节点提交日志，这个过程叫做Log Replication。

Follower：所有节点都以follower的状态开始，如果没收到Leader的心跳则会变成Candidate状态。

Candidate：发起投票，如果得到多数节点的选票则成为Leader，这个过程叫做Leader election。等待超时会重新发起投票，竞选失败（收到了Leader的心跳）则会变成Follower状态。

Raft官网

Raft论文

Raft动画演示

Leader 选举

何时选举

集群开始时，所有服务器都是follower，当服务器在指定的时间之内没有收到leader或者candidate的消息时会发起选举。这个指定的时间被称为选举超时（election timeout），并且是一个150~300ms之间的随机数（为了避免选举冲突）。这里，leader的消息是指心跳消息，以心跳超时（heartbeat timeout）指定的时间间隔发送，candidate的消息是指投票消息。要求（heartbeat timeout）<< min(election timeout)，避免Follower发起无谓的投票。

投票过程

1. Follower在选举超时时间内没有收到来自Leader的请求后会将当前维护的Term值加1

2. 将自身状态变成Candidate

3. 投票给自己

4. 向集群的其他节点发送投票请求（RequestVote）

5. 可能会有如下几种可能：

   1. 收到多数节点的选票，节点状态从Candidate变为Leader，并立刻向其他服务器发送心跳消息，之后按照心跳间隔发送心跳消息。收到投票消息的节点，会立刻重置自己的选举超时时间，它在这个Term下没有投票过，才能为其投票，其他Candidate节点已经在这个Term下已经投票给自己，所以不能为其投票。
   2. 收到了Leader节点的心跳消息并且这个Leader节点的Term不小于自己的Term，状态转为follower，否则丢弃消息。
   3. 没有节点赢得选举，可能是由于网络超时或者服务器原因没有leader被选举，这种情况比较简单，超时之后重试。有一种情况被称为split votes，比如一个有三个服务器的集群中所有服务器同时发起选举，那么就不可能有leader被选举出来，此时如果超时之后重试很可能所有服务器又同时发起选举，这样永远不可能有leader被选举出来。raft处理这种情况是采用上文提到过的随机 election timeout，随机超时保证了split votes发生的几率很小。

何时同意

如果发起的投票请求包含的term大于等于当前term，并且日志信息不新于candidate的日志信息（保证选出最新log的server为leader），那么会同意。

比较日志是否新于Candidate：比较两个log中最后的entry的index和term，更大term的更加新，如果term一样，那么index更大的更加新。

Term更新

所有请求和响应的接收方在接收到更大的term时都必须更新自己的term，这保证了投票最终能够选出一个leader。

日志复制

流程如下：

1. 客户端发起请求（SET 5）给Leader
2. Leader接收到请求后，写入到本地日志中，Leader上这条记录的状态是uncommitted
3. Leader通过心跳发送AppendEntries消息将日志复制给其他节点
4. 其他节点收到AppendEntries消息后，会写入日志（状态是uncommitted），如果写入成功则给Leader发出响应
5. Leader接收到大部分节点写入成功的响应后，会将Leader上这条记录更新为Committed状态，并且值更新为5。
6. Leader通知其他节点提交日志
7. 其他节点收到提交日志的消息后，将日志状态更新为Committed状态，并且值更新为5。
8. 此时集群状态完全一致

AppendEntries消息

Leader发送AppendEntries消息时，需要携带日志信息Log1和前一个日志Log2的term和index。

1. 如果在follower节点的日志中找到Log2，那么follower的日志中这条log之后的信息全部丢弃，然后写入Leader发来的Log1。
2. 如果没有找到Log2，follower将拒绝此消息，那么leader端对应follower的nextIndex会减一然后再对此follower进行AppendEntries操作（既发送Log2和前一个日志Log3的term和index）。如果再次失败那么再进行自减并执行AppendEntries操作。循环直到成功。

Append Log并行化

日志复制中的步骤2、步骤3可以并行执行，为什么？

1. 如果Leader没有Crash，那么和顺序的处理结果一致。
2. 如果Leader Crash了，那么如果大于n/2+1的follower收到了这个消息并Append成功，那么这个Raft Log就一定会被Commit，新选举出来的Leader会响应客户端；否则这个Raft Log就不会被Commit，客户端就会超时/错误/或重试后的结果（看实现方式）。

网络分区

在发生网络分区的时候，Raft一样能保持一致性。

假设发生了网络分区：节点A和B在一个网络分区，节点C、D和E在另一个网络分区，如下图所示，且节点B和节点C分别是两个网络分区中的Leader节点：

客户端给节点B发送请求（SET 3），由于网络分区的原因，这个值不能被另一个网络分区中的Leader即节点C拿到，它最多只能被两个节点（节点B和C）感知到，所以它的状态是uncomitted（红色）。

此时另一个客户端给节点C发送请求（SET 8），由于可以被同一个分区下总计三个节点（节点C、D和E）感知到，3个节点已经符合大多数节点的条件。所以，这个值的状态就是committed。

然后修复网络分区，节点B能感知到C节点这个Leader的存在，它就会从Leader状态退回到Follower状态，并且节点A和B会回滚之前没有提交的日志（SET 3产生的uncommitted日志）。同时，节点A和B会从新的Leader节点即C节点获取最新的日志（SET 8产生的日志），从而将它们的值更新为8。如此以来，整个集群的5个节点数据完全一致了。

优缺点

优点

1. 相比Paxos更容易理解和工程化实现

缺点

1. Raft有一个很强的假设是主（leader）和备（follower）都按顺序投票，存在并发瓶颈，可参考OceanBase的一致性协议为什么选择 paxos而不是raft?，不过也可以参考TiDB使用multi raft，或者是PolarFS使用的ParallelRaft。
   1. Elasticell-Multi-Raft实现
2. 网络分区会导致脑裂，可能会导致stale read，可以通过ReadIndex Read和Lease Read的方法来解决。
   1. TiDB如何确认 leader 在处理这次 read 的时候一定是 leader