Raft 共识算法 _生活百科

转载请注明出处：https://www.cnblogs.com/morningli/p/16745294.html
【Raft 共识算法】raft是一种管理复制日志的算法，raft可以分解成三个相对独立的子问题:

选主（Leader election）：原有的leader故障后需要选举一个新的leader 。
复制（Log replication）： leader必须接受client发送的记录（log entries）然后复制到集群中其他节点，并强制要求其他节点的日志和自己保持一致。
安全（Safety）：raft安全的关键是状态机安全：如果存在server将一个特定的记录应用到状态机中，不存在另外一个server在相同的日志索引上应用的是不同的命令。

算法组成状态

所有server上的持久性状态（在回应PRC之前更新到稳定存储（stable storage））
- currentTerm：已知的最新的任期（term）（初始化为0，单调递增）
- votedFor：当前任期内接受投票的candidateId（如果没有为null）
- log[]：记录（log entries）；每个记录包含应用到状态机的命令以及leader接收该记录时的任期
所有server上的易变的状态
- commitIndex：已知已经提交的最高的记录索引（初始化为0，单调递增）
- lastApplied：已经应用到状态机的最高的记录索引（初始化为0，单调递增）
leader上的易变的状态（选举后重新初始化）
- nextIndex[]：对于每个server，需要发送到这个server的下一条记录的索引（初始化为leader的最新的记录索引+1）
- matchIndex[]：对于每个server，已知已经复制到这个server的最高的记录索引（初始化为0，单调递增）

AppendEntries RPC（leader调用来复制日志，也会被用作心跳）

参数
- term：leader的任期
- leaderId：follower用来重定向客户端
- prevLogIndex：新记录前一个记录的索引
- prevLogTerm：prevLogIndex记录的任期
- entries[]：需要存储的记录（心跳传空，为了提高效率可能会发送多个）
- leaderCommit：leader的commitIndex
返回
- term：currentTerm，给leader更新自己的任期
- success：如果follower包含匹配prevLogIndex和prevLogTerm的记录返回true
接收者实现
1. term < currentTerm 返回false
2. prevLogTerm匹配但是找不到匹配prevLogIndex的记录返回false
3. 如果已经存在的记录与其中一个新记录（index相同但是term不同）冲突，删除存在的这条记录以及后面的所有记录
4. 添加不存在的新的记录到后面
5. 如果leaderCommit > commitIndex，设置commitIndex = min(leaderCommit, 最新的记录索引)

RequestVote RPC（被candidate调用来收集选票）

参数
- term：candidate的任期
- candidateId：请求投票的candidate
- lastLogIndex：candidate最新的记录索引
- lastLogTerm：candidate最新的记录任期
返回
- term：currentTerm，给candidate更新自己的任期
- voteGranted：true表示candidate收到投票
接收者实现
1. term < currentTerm 返回 false
2. 如果votedFor是null或者candidateId，并且candidate的日志至少和自己一样新，那么就投票给他

server 需遵守的规则