Raft算法

相比与Paxos算法,Raft更容易理解。首先推荐个动画视频 (注意这个动画真的基于raft算法,所以每次选举出的节点都是不同的,我观看某些章节时候甚至出现过3次选举过程),然后是raft论文中文版raft主页,基本结合这3个网站就能理解raft了。

在Raft算法中,有3种角色:

  • Leader
  • Follower
  • Candidate

大体分为2个过程:

  1. 选举(Leader Election)
  2. 日志同步(Log Replication)

选举

选举和现实社会中的民主选举制度很像,当Follower超过选举超时时间(election timeout)没收到来自Leader的心跳报文,则成为Candidate,增加任期(Term)并向其他节点发起新的选举请求。接收到请求的节点如果还没投票则投票给该节点,并重置自己的超时时间。如果获取到了超过一半的赞同票,则成为新的Leader。每隔一定时间向Follower发送心跳报文来维持自己的"统治"地位。

那么,万一有多个节点获得了同样的投票怎么办呢?

此时则等待各自的超时时间后,增加Term后再次发起投票。解决这个问题的关键在于 每个节点的election timeout 是不同的。

日志同步

当选举完成后,客户端进行的操作都要通过Leader来进行。首先Leader接受到客户端发来的操作请求后记录到日志中,此时为uncommitted状态。然后在下一个心跳报文中通知所有Follower,当大多数Follower响应后,Leader响应客户端,进入committed阶段,并向Follower发送通知应用(apply)操作。

脑裂

如果由于网络分区(network partition)造成同时有多个Leader,这种情况下某些Leader由于获取不到大多数的投票,所以数据永远不会提交成功。当网络故障恢复后,旧的Leader发现有Term更新的Leader存在,则自动降级为Follower并从最新的Leader同步数据达成集群一致。

思考

如果在日志同步阶段,Leader响应客户端后进入committed阶段,但没来得及向Follower发送通知就挂掉了,重新选举后这次修改会不会丢失?

答案是不会丢失。具体解释可以参考这里


最后再推荐一个文章,里面关于什么时候Leader挂掉的图解很清晰。