更容易理解的一致性算法Raft
副本状态机模型
如下图，集群中多台服务器保存一份Log副本及内部状态机。所谓一致性协议就是保证每个状态机的Log是一样的。
image.png
服务器状态
首先是服务器状态，在任意时刻，集群中的服务器只能处于下面三种情况之一：Leader、Follower、Candidate。正常情况下，只有一个Leader状态的服务器来充当领导者，由其来负责响应客户端的请求，而其它服务器作为Follower被动接受Leader的RPC消息，来同步Leader的Log。Candidate是Follower变换成Leader之前的状态，处于这个状态的服务器会向其它服务器请求投票，如果收到的票数最多，则转换为Leader。三者的转换关系如下图所示：
服务器状态
Term
image.png
Raft将整个系统执行时间划分为若干个时间片段，每个时间片段称为一个Term。在每个Term的开始是选举期间，在这段时间内，若干个Candidate服务器会请求投票，选票最多的那个赢得选举。如果没有Candidate赢得选举（Candidate的票数一样多），则重新开启一轮投票。
领导者选举
Raft采用心跳机制来触发选举，当Follower长时间收不到Leader发来的心跳包，则将自身状态转换为Candidate，同时增加Term编号。然后向其它服务器发起投票请求（RequestVote RPC）。
其结果可分为三种情况：
-
赢得选举
如果Candidate收到了大多数服务器的投票，则成为新的Leader，同时周期性的发送心跳RPC以维持自己的地位。
对于多个Term相同的Candidate，投票者只能给一个服务器投票。 -
另一个服务器宣称自己为Leader
如果那个服务器的Term编号大于等于Candidate自身的Term编号，则转换为Follower，承认对方的地位。否则认为对方是无效的，继续收集选票。 -
没有人赢得选举
重新开启一轮投票，为了防止再次出现这个情况。每个Candidate重启投票的延迟时间是随机的。
一致性日志同步
当Leader被选出来以后，所有的客户端请求都将转发给Leader统一处理。Leader收到请求后，写入到自己的Log中，并且向其它服务器发送AppendEntries RPC消息，使得其它服务器复制Leader的Log。当所有服务器都返回成功的结果后，Leader向客户端返回成功提示。
其过程如下图所示：
image.png
Raft通过两个保证措施来实现一致性的同步
一条Log记录包含具体的命令和Term编号。(Log类似于数组，索引编号就是下标)
1. 对于任意服务器的Log，如果有两个记录的索引编号和Term编号都相同，则其内容一定相同。
2. 对于任意服务器的Log，如果有两个记录的索引编号和Term编号都相同，则他们前面的记录一定也相同。
安全原则
为了处理一些特殊情况，Raft协议还有两个约束来增强安全性
1. 只有包含了所有Log的服务器才能被选举为Leader
有可能一个Follower恰好崩溃，然后在重启后被选为Leader，但是他缺少了崩溃期间的Log，导致其他服务器的Log被其同步覆盖，所以这个约束就是防止它被选举为Leader。
2. 对于新的领导者来说，只有它自己已经提交过当前Term的操作命令才被认为是真正的提交。
动画演示
http://thesecretlivesofdata.com/raft/
参考
- 大数据日知录：架构与算法
- In Search of an Understandable Consensus Algorithm
