Raft算法
source link: https://www.hi-roy.com/posts/raft%E7%AE%97%E6%B3%95/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Raft算法
相比与Paxos算法，Raft更容易理解。首先推荐个动画视频 (注意这个动画真的基于raft算法，所以每次选举出的节点都是不同的，我观看某些章节时候甚至出现过3次选举过程)，然后是raft论文中文版和raft主页，基本结合这3个网站就能理解raft了。
在Raft算法中，有3种角色：
- Leader
- Follower
- Candidate
大体分为2个过程：
- 选举(Leader Election)
- 日志同步(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挂掉的图解很清晰。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK