Raft学习笔记

概念

Raft是一种协议，用于协调分布式环境下的多个节点，使它们到达最终一致性状态，比如用于MongoDB集群的数据复制。

Raft协议下的节点有三种状态，任何一个节点必定处于其中一种状态：

• Leader
  
  • 处理客户端的读写请求
• Follower
  
  • 处理客户端的读请求
  • 当收到客户端的写请求时，重定向给Leader处理
  • redo从Leader节点同步过来的op log（Leader主动向Followers推送op log）
• Candidate
  
  • 候选人

术语

• term：任期

  ​ 每一次成功或失败的选举都会增加term的序号，初始值为0，第一次选举时，Candidate节点将其增至1，第二次选举时，Candidate节点将其增至2，以此类推。

  

  ​ 如上图所示，一共进行了4次选举，其中term 1, term 2, term 4都成功选举出了一位Leader, term 3那次选举由于各种原因（比如平票）失败了。

选举规则

• 同一任期内，只能给一个选举者投票，可以投赞同，也可以投反对
• 一个任期内，得到大多数赞成票的Candidate节点成为Leader，这样就保证了同一个任期内最多只有一个节点成为Leader（也有可能没有，比如出现平票时）
• 可以为更高的term投票，不能为更低或相同的term投票
• 只有当候选人的op logs至少和投票节点一样或更加新时，才能投赞同票

选举时机

• Follower在一段时间内（选举超时election timeout）收不到Leader发送的心跳消息

• Leader在一段时间内（心跳超时heartbeat timeout）联系不上大多数的Follower

  注意这里有两个超时器：

  1. election timeout，这是Follower的定时器，超时之后会进入Candidate开始新一轮选举，当收到Leader发送的心跳消息时，会重置定时器。另外，为了避免多个Follower同时超时发起选举而平票的可能性，这个超时时间会加上150-300ms的随机值。
  2. heartbeat timeout，这是Leader的定时器，用于周期性的通知Followers。

阶段

• 选举阶段
• 日志复制阶段
  
  1. 客户端发送写请求到Leader
  2. Leader写append log，并在下一个heartbeat timeout时发送消息给所有的Followers
  3. 如果大多数Followers响应成功，则Leader将数据真正写入内存或磁盘，此log被提交（committed）
  4. 返回响应给客户端

状态机

状态转换过程：

1. 所有节点启动后处于Follower

2. 因为启动之后没有Leader，因此收不到Leader发送的心跳消息，所以选举超时器（election timeout）会超时，最先超时的Follower进入Candidate，开始一次新的选举，并为自己投上一票

3. 处于Candidate的节点如果收到大多数的赞同票，则成为Leader；当极端情况下出现平票时，保持Candidate状态并在一段超时时间后（election timeout）重新开始一轮新的选举；如果此时发现了新的Leader，则恢复成Follower

4. 如果一个Candidate或者Leader发现自己的term过期了，那么他会恢复成Follower

   ​

改进

• Followers chain

  Raft原本的方式是由Leader向所有Followers推送op log，这种方式在Followers较多时会影响Leader的性能，使用Followers chain方式，Follower使用tailing query向Leader拉取最新的op logs，并向链条一样一级一级往上拉取。

• Leader选举时支持优先级

  ​

参考资料

Raft论文

Raft动画演示

MongoDB 中的Raft 一致性协议