状态转化

Raft协议已经广泛应用于Etcd、Consul、Tikv等各种主流产品，今天开始我们就仔细了解下Raft协议。

重点

AppendEntry和RequestVote 两个结构体字段非常重要，对理解leader选举、日志复制逻辑非常重要。

随机化：每个节点的election timeout会从一个固定的区间（如150-300ms间）随机选择，降低了竞选活锁的概率

• 每个Candidate在开始一次选举的时候会重置一个随机的选举超时时间，然后一直等待直到选举超时。

投票的3个检查点

1. 日志索引(LastLogIndex)：RequestVote请求中的LastLogIndex 小于 自身LastLogIndex，则拒绝投票
2. 任期号(LastLogTerm)：RequestVote请求中LastLogTerm 小于 自身的Term，则拒绝投票
3. 投票状态：自身未投票

两个超时限制【etcd的默认值，和raft无关】：

1. HeartBeat-interval : 100ms
2. Election Timeout : 1000ms， 每个节点等待发起选举的时间点不一致，避免竞选活锁

这两个超时配置影响什么？

1. HeartBeat-interval 影响心跳探测，最好根据节点间网络质量进行调整，如果是跨可用区，这个配置就需要特别注意。etcd官方建议是节点往返时长的0.5-1.5倍左右，

2. Election timeout 影响 Leader异常后等待多久重新发起选举，也就是意味着 集群不可用时长。etcd官方建议是节点往返时长的10倍，上限是50s

动态图：http://kailing.pub/raft/index.html

• 说明：关于网络分区中的错误：5节点集群，2节点分区的集群因无法实现leader选取(永远不可能获得半数以上票数)，故不会正常运行，也就无法处理请求

如果帮到你，辛苦点赞鼓励下吧！

Raft两个核心rpc结构体

Raft算法中服务器节点间使用RPC通信，并且基本的一致性算法只需要两种类型的RPC，请求投票(RequestVote，由Candidate发起)和追加条目(AppendEntry, 由Leader发起)
AppendEntry：由leader节点发出，携带收到的最新命令，同时还用作心跳消息。当Follower收到此消息时，将重置选举计时器。

type AppendEntryArgs struct {
  Term      int    // current term of the leader, very IMPORTANT
  LeaderId     int    // id of the leader, 0 to N-1 where N = total servers
  Entries      []Entry // new data to sync
  PrevLogIndex  int    // important metadata for log correctness
  PrevLogTerm    int    // important metadata for log correctness
  LeaderCommit  int   // what index have been received by the majority
}

type AppendEntryReply struct {
  Term       int   // current term of the receiving node
  Success      bool  // AppendEntry declined or accepted
  ConflictIndex  int    // if declined, specifying the conflicting index
  ConflictTerm  int    // if declined, specifying the conflicting term
}

RequestVote：当Follower的选举计时器超时(长时间没有收到AppendEntry， 约300ms)，成为Candidate并调用所有其他节点为自己投票。

type RequestVoteArgs struct {
  Term       int      // current term of the candidate, very IMPORTANT
  CandidateId   int      // id of the candidate, 0 -  N-1 where N = total servers
  LastLogIndex   int      // important metadata for election correctness
  LastLogTerm   int      // important metadata for election correctness, explain later
}

type RequestVoteReply struct {
  Term       int      // current term of the receiving node
  VoteGranted   bool    // yes or no
}

leader选举

节点状态和选举过程

状态与选举

节点共有3种状态：Leader、Candidate、Follower， 各角色的规则：
All Server ：

1. 如果commitIndex>lastApplied：增加lastApplied，应用日志(lastApplied)到状态机；
2. 如果rpc请求或响应中的Term T > currentTerm; 则currentTerm = T，转换为follower

Follower:

1. 响应candidates 和 leaders的rpc请求；
2. 如果没有接收到（或超时）leader 的AppendEntry或Candidate的requestVote请求，转换为Candidate

Candidate:

1. 一旦转换为Candidate，开启选举：
   • 增加currentTerm
   • 为自己投票
   • 重置选举计时器
   • 发送RequestVote 给其他所有servers
2. 如果收到超半数投票：成为leader
3. 如果收到新leader的AppendEntry rpc消息：转换为follower
4. 如果选举超时：开启新一轮选举

Leader:

1. 定期向每个服务器发送初始的空 AppendEntries RPC（心跳）：在空闲期间重复以防止选举超时
2. 接收客户端请求：追加日志条目到本地日志，在条目应用于状态机后响应
3. 如果最新日志索引 大于等于 follower的nextIndex：发送AppendEntry rpc，日志条目从nextIndex开始：
   • 如果成功：更新follower的nextIndex和matchIndex
   • 如果因为日志不一致而失败：缩小nextIndex并且重试
4. 如果存在一个 N 使得 N > commitIndex，大多数 matchIndex[i] ≥ N，并且 log[N].term == currentTerm：设置 commitIndex = N

在Raft节点刚启动的时候，所有节点都是Follower状态

1. 因为此时没有Leader，所有的Follower都无法收到leader的心跳(AppendEntry)，所以每个Follower在每个随机超时后(150-300ms)后，进入Candidate状态
2. 假设B进入Candidate会立即发起选举，自增任期号(Term+1)，选票给自己，并向其他节点发起竞选Leader投票消息
3. C收到B的竞选Leader消息后，有2种处理情况：

• C也恰好发起Leader竞选，并投票给自己，此时不会投票给B。这时谁也无法获取大多数支持，只能等待Election Timeout再发起选举。（Raft做引入随机数，每个节点等待发起选举时间点不一致，规避了潜在竞选活锁），返回：

RequestVoteReply { 
  Term: 当前自身Term；如果该term大于candidate发起的term，则candidate转化为follower
  VoteGranted: no
}

• C判断B的数据至少和自己一样新、B-term大于C-term、且C未投票给其他候选者，则投票给B，B获取大数据支持称为Leader，返回：

RequestVoteReply {
    Term: Candidate发送的Term
    VoteGranted: yes
}

自测

https://segmentfault.com/a/1190000022398199
https://towardsdatascience.com/raft-algorithm-explained-a7c856529f40

以上两篇文章对于Candidate、Follower、Leader安全性、多Leader等问题在选举中各种情况做了分析，但是基本也是围绕“投票的3个检查点”展开，所以自己也可以根据检查点做分析。

Raft Log复制 & 安全性

重点

关键特性：
Election Safety：最多一个leader
Leader Append-Only： leader不会覆盖、删除日志条目，只会追加新条目
Log Matching：如果两个日志包含具有相同索引和任期的条目，则日志通过给定索引的所有条目都是相同的
Leader Completeness：如果在给定任期内提交了日志条目，则该日志条目将出现在所有较高任期的Leader日志中
state Machine Safety：如果服务器已经将给定索引出的日志条目应用到其状态机，则没有其他服务器回味同一个索引引用不同的日志条目
通过以上5个特性，推导出：

• 如果不同日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令
• 如果不同日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也都相同。

Leader什么时候把日志条目应用到状态机？
这种条目被称为 已提交 的；Raft算法保证所有已提交的日志条目都是持久化且最终会被所有可用的状态机执行。一旦创建该日志条目的 leader 将它复制到过半的服务器上，该日志条目就会被提交（例如在图 6 中的条目 7）。Leader 将追踪会被提交的日志条目的最大索引LeaderCommit，未来的所有 AppendEntries RPC 都会包含该索引，这样其他的服务器才能最终知道哪些日志条目需要被提交。Follower 一旦知道某个日志条目已经被提交就会将该日志条目应用到自己的本地状态机中（按照日志的顺序）。

• 思考： leader和follower的日志保存阶段：follower接受AppendEntry请求，如果接受日志条目，返回sussuce给leader。leader获取半数以上接受状态后，应用该条目到本地状态机，并更新lastApplied条目，在下一条AE中LeaderCommit和LastApplied一致，follower在收到下一个AE，对比自身的LastApplied和LeaderCommit，决定将哪些条目应用到本地状态机 【自己猜测，还没看源码核对】

  
  图6
  

  对图6的格式说明：命令(x←3), Term(1),在logs中的序号，及log index； 索引7因为半数以上提交，所以7已经被应用到状态机

复制逻辑

Raft中各server维护的状态说明：

所有server维护的状态	leader维护的状态
commitIndex：被提交的最新日志条目索引	nextIndex：为每个server维护 即将发送给该server的日志条目索引
lastApplied：被应用到状态机的最新日志条目索引	matchIndex：为每个server维护 在该server已复制的最新日志条目的索引

在节点成为leader后，leader需要保证集群所有日志条目一致，在接受新日志服请求的同时，需要将历史日志同步给follower，当一个新leader出现时，该leader将所有nextIndex的值初始化为自己最后一个日志条目的index+1，在下一次AppendEntry rpc请求中，可能有2种场景：

第一： follower-1 的日志条目和leader持平；

leader 发出的新的AppendEntry rpc请求会携带Entries、PrevLogIndex、PrevLogTerm和leaderCommit， follower-1会对比rpc请求的PrevLogIndex和PrevLogTerm是否和自己日志索引一致，如果一直则接受本次Entries条目

第二： follower-2的日志条目相对leader落后较多；

follower-2 对比PrevLogTerm和prevlogIndex，此时判断失败，此时会将冲突的信息(ConflictIndex 和 ConflictTerm)返回给leader，在被follower-2拒绝后，leader就会减少nextIndex值，并重试AppendEntry RPC，最终nextIndex会在某个位置使得leader和follower-2日志达成一致。此时AppendEntry rpc就会成功，将follower-2中跟leader冲突的日志条目全部删除，然后追加leader的日志条目。