raft

共识算法：Raft https://www.jianshu.com/p/8e4bbe7e276c
Raft动画： http://thesecretlivesofdata.com/raft/

• 如何选主？
  Node有3个status，分别为Follower, Candidate和Leader。每个Node都有定时器，在Follower成为Candidate的这个阶段，定时器的间隔设为election timeout，当Follower经过election timeout后就会成为Candidate，成为Candidate后就会向其他所有Node发送选举的信息。如果一个Candidate收到超过半数的投票(包括自己的投票)就会成为Leader。成为Candidate后就会向所有的Node发送heartbeat，Follower的定时器还在不断运行，每收到一次heartbeat定时器就会重置一次，所以只要保证Follower定期收到heartbeat，Follower就不会变为Candidate。

• Leader出现故障怎么办?
  当一个Leader出现故障后，就会停止向Follower发送heartbeat。因此Follower定时器超时后就会成为Candidate，向其他Follower发送election message，最后成为新Leader。每个Node都会记录当前是第几轮选举(Term)，当之前的Leader(Term 1)从故障中恢复后，发现有Term 2的Leader就会自动降级成为Follower。

• 多个Candidate如何选主的情况
  当Follower中有多个Follower同时timeout就会出现多个Candidate的情况，Candidate会向所有的Node发送投票请求，Follower接收到来自Candidate的election message后，如果还没有为其他Candidate投票就会向这个Candidate发送确认选举的消息，如果已经为其他Candidate投票就对这个Candidate发送vote denied的消息。如果在一轮中没有选出leader就会进行下一轮的选举。

• Log Replication
  当client对Leader发送append entries的请求时，Leader会将entry写入本地(uncommitted)，然后向Follower发送append entries的消息，当Follower收到消息并将entry写入本地(uncommitted)后就会向Leader发送ok的确认消息。当Leader收到了超过半数的ok消息(包括Leader)，就向客户端返回确认消息，然后将本地中entry的状态设置为committed，向所有Follower发送append entries的消息，Follower将本地中的entry的状态设置为committed。

• Network partition时的Log Replication
  Network partition是指网络出现故障，从而出现不同组之间无法通信的情况。因此每个组之间都会选举出一个Leader，如果组内的成员不超过半数，那么entry会一直在uncommited的状态。最终uncommitted的entry会被置换成committed的entry，从而保证一致性。如果都时uncommitted，那么向客户端返回失败。