Raft算法

Raft

Paxos和Raft都是为了实现Consensus一致性这个目标，这个过程如同选举一样，参选者需要说服大多数选民(服务器)投票给他，一旦选定后就跟随其操作。Paxos和Raft的区别在于选举的具体过程不同。

在Raft中，任何时候一个服务器可以扮演下面角色之一：

• Leader: 处理所有客户端交互，日志复制等，一般一次只有一个Leader.
• Follower: 类似选民，完全被动
• Candidate候选人: 类似Proposer律师，可以被选为一个新的领导人。
  Raft阶段分为两个，首先是选举过程，然后在选举出来的领导人带领进行正常操作，比如日志复制等。下面用图示展示这个过程：

1. 任何一个服务器都可以成为一个候选者Candidate，它向其他服务器Follower发出要求选举自己的请求：

   
   

2. 其他服务器同意了，发出OK。

   
   
   

   注意如果在这个过程中，有一个Follower当机，没有收到请求选举的要求，因此候选者可以自己选自己，只要达到N/2 + 1 的大多数票，候选人还是可以成为Leader的。
   3.这样这个候选者就成为了Leader领导人，它可以向选民也就是Follower们发出指令，比如进行日志复制。

   
   

3. 以后通过心跳进行日志复制的通知

   
   

4. 如果一旦这个Leader当机崩溃了，那么Follower中有一个成为候选者，发出邀票选举。

   
   

5. Follower同意后，其成为Leader，继续承担日志复制等指导工作：

   
   
   

   值得注意的是，整个选举过程是有一个时间限制的，如下图：

   
   
   Splite Vote是因为如果同时有两个候选人向大家邀票，这时通过类似加时赛来解决，两个候选者在一段timeout比如300ms互相不服气的等待以后，因为双方得到的票数是一样的，一半对一半，那么在300ms以后，再由这两个候选者发出邀票，这时同时的概率大大降低，那么首先发出邀票的的候选者得到了大多数同意，成为领导者Leader，而另外一个候选者后来发出邀票时，那些Follower选民已经投票给第一个候选者，不能再投票给它，它就成为落选者了，最后这个落选者也成为普通Follower一员了。

英文动画演示Raft

CAP定理

分布式Paxos算法

ZooKeeper在服务发现中应用

分布式事务