1、简介
raft一致性算法基于Pasox算法，但是更容易理解和实现。
raft集群一般要有几个节点实例：通常是5个节点实例，因为这样可以允许2个节点故障而不影响可用性（因为选举算法需要N/2 + 1个同意票才可以选举成功）。
2、Paxos的问题
- 难以理解
大家对Paxos论都感到很疑惑，基于自己的理解各执一词，那这样的话大家就无法进行统一和制定标准（感觉这也是一个分布式问题啊，这得出现一个Paxos Leader角色，一言堂搞定所有人的说辞，但是你懂的总有不服你的）。 - 难以实现
Paxos协议我没有读过，只能复制“Diego Ongaro and John Ousterhout”两神的说法： its architecture requires complex changes to support practical systems.
3、raft
raft算法分为三个步骤：
- Leader选举
- 日志复制
- 安全性
4、特性
-
强大的Leader
日志节点只能从Leader分发到其他成员服务器，这样做的目的简化了管理和更容易理解。 -
Leader选举
raft使用了随机时间的定时器来选举领导者。 -
成员变更
raft使用共同共识方法来处理成员变更问题，这样在选举期间依然可以对外提供服务。
5、Leader选举
集群中每个节点的状态有三种，分别为Leader、Follwer和Candidate。
5.1、领导人状态：Leader
集群中只有一个节点为Leader，剩余节点都为Follower。Leader处理所有的客户端请求。如果有客户端连接了Follower，那么Follower会将客户端重定向到Leader。
5.2、跟随者状态：Follower
Follower是被动的：他们一般都是被动响应Leader或者Candidate的请求。
5.3、候选人状态：Candidate
Candidate只有在选举Leader时才会出现。一般集群初始化时没有Leader需要选举处一个Leader，或当前Leader故障时才会转换到此状态。
5.4、三种状态转换（论文版本）
5.5、三种状态转换（手画版本）
5.6、状态转换说明
所有的raft节点启动的时候，所有节点都是Follower状态，那么这些所有的Follower状态的节点都在等待Leader的消息，在等了一个超时时间内没有收到Leader消息，说明集群中还没有Leader或者集群中的Leader故障了。
没有收到Leader消息的Follower将状态转换为Candidate并开始选举。
5.6.1、Follower
-
集群中所有节点启动，默认为Follower状态；
在集群节点启动的时候，新启动的节点处于Follower状态，新节点会等待一个固定超时时间的Leader消息，如果在这个固定超时时间内没有等到Leader消息，那么新节点就发起一次选举，并将自己的状态转换为Candidate状态。 -
Follower状态等待Leader心跳消息，等待Leader消息超时就开始选举并进入Candidite状态；
5.6.2、Candidate
- Candidate等待投票消息超时再次发起新一轮的选举；
- Candidate获得了大多数服务节点的票数（N/2+1，其中N为集群节点数）后转换为Leader；
- Candidate收到了Leader消息或者新任期时转换为Follower等待Leader消息；
5.6.3、Leader
- Leader状态在收到了任期大节点的消息后转换为Follower状态；
5.7、 日志复制
Leader从客户端接收日志然后复制到集群中的Follower节点，并且强制要求Follower节点的日志保持和自己的相同。
5.7.1、复制状态机
先附上论文状态机模型图：
现在可以看到的Server是Leader角色，Server下面的是Followers。
图中1、2、3和4步骤如下：
- 客户端请求Leader服务器，请求信息就是一系列的指令；
- Leader在收到请求以后，将操作同步到所有的Follower服务器中（包括自己）；
- Leader和Follower服务器收到同步的指令以后，就将请求应用到状态机中；
- 最后响应结果给客户端。
5.7.2、顺序
Leader按照客户端的指令顺序来同步到所有的Follower中，同步中不能打乱顺序也不能丢失请求，否则状态机的状态会不一致。
5.7.3、ZAB协议中的同步
Zookeeper在同步状态时使用类似于两阶段提交方式，Leader先向Follower提交决议，所有Follower通过ACK回复决议结果，Leader根据决议结果执行Commit，流程如下图：
5.8、安全性
分布式中选举安全性是指经过几轮选举以后一定可以选出一个Leader，并且选出来的Leader一定是活的没有故障的节点。raft协议安全性还要求已经应用到集群中的状态不能丢失，raft保证状态不丢弃的方式是候选人的状态日志必须是最新的。
raft协议满足非拜占庭条件下的安全，包括网络延迟、分区、丢包、重复和重排序。
5.8.1、选举限制
raft的选举机制保证被选举出来的Leader包含所有提交的日志节点。
如果一个Candidate相对于其他所有Candidate的日志节点是最新的，那么就认为这个Candidate节点拥有所有已提交的日志节点。
raft通过投票RPC中包含Candidate的日志信息来拒绝投票给其他日志少的Candidate票。
5.8.2、日志覆盖
raft保证Leader只能提交当前任期的日志，不能提交之前任期的日志。
来看张图（提交之前任期的日志导致日志被覆盖）：
有5个服务节点S1-S5,abcde为时序:a<b<c<d&e
- 在时序a，节点S1是Leader，在S1服务期间接收了请求2并将其传播到S2后崩溃；
- 在时序b，节点S5当选了Leader并且处理了请求3并将3放到日志节点2的位置后崩溃；
- 在时序c，节点S1再次当选为Leader，然后继续复制日志节点2到其他大部分服务器但未提交，然后崩溃；
- 在时序d，节点S5再次当选为Leader，然后使用日志节点2的数据项3覆盖了所有的节点；
- 在时序e，如果S1将日志节点2的数据项2复制到了大部分服务节点并进行了提交，那么S5就不会当选为Leader。