Raft
Raft 是斯坦福的Diego Ongaro 、John Ousterhout 两个人以易懂（Understandability）为目标设计的一致性算法，在2013 年发布了论文： 《In Search of an Understandable Consensus Algorithm》 。Paxos 一致性算法从90 年提出，但是其流程太过于繁杂实现起来也比较复杂；而Raft 一致性算法就是比Paxos 简单又能实现Paxos 所解决的问题的一致性算法，从2013 年发布，两年多时间内就有了十多种语言的Raft 算法实现框架，较为出名的有etcd ，Google 的Kubernetes 也是用了etcd 作为他的服务发现框架。
Raft 是一个用于日志复制，同步的一致性算法，它提供了和Paxos 一样的功能和性能，只要保证 n/2+1 节点正常就能够提供服务；但是不同于Paxos 算法直接从分布式一致性问题出发推导出来，Raft 算法则是从多副本状态机的角度提出，用于管理多副本状态机的日志复制。为了强调可理解性，Raft 将一致性算法分解为几个关键流程（模块） ：Leader 选举（Leader election） 、日志同步（Log replication） 、安全性（Safety） 、日志压缩（Log compaction） 、成员变更（Membership change）等，通过将分布式一致性这个复杂的问题转化为一系列的小问题进而各个击破的方式来解决问题。同时它通过实施一个更强的一致性来减少一些不必要的状态，进一步降低了复杂性。Raft 还允许线上进行动态的集群扩容，利用有交集的大多数机制来保证安全性。
Raft 的主要流程包含以下步骤：
Raft 开始时在集群中选举出Leader 负责日志复制的管理；Leader 接受来自客户端的事务请求（日志） ，并将它们复制给集群的其他节点，然后负责通知集群中其他节点提交日志，Leader 负责保证其他节点与他的日志同步；当Leader 宕掉后集群其他节点会发起选举选出新的Leader ；
系统角色
Raft 将系统中的角色分为领导者（Leader） 、跟从者（Follower）和候选人（Candidate） ：
Leader：接受客户端请求，并向Follower 同步请求日志，当日志同步到大多数节点上后告诉Follower 提交日志。
Follower：接受并持久化Leader 同步的日志，在Leader 告之日志可以提交之后，提交日志。
Candidate：Leader 选举过程中的临时角色。
Raft 要求系统在任意时刻最多只有一个Leader ，正常工作期间只有Leader 和Followers ；算法将时间分为一个个的任期（term） ，每一个term 的开始都是Leader 选举。Raft 算法角色状态转换如下：
Follower 只响应其他服务器的请求。如果Follower 超时没有收到Leader 的消息，它会成为一个Candidate 并且开始一次Leader 选举。收到大多数服务器投票的Candidate 会成为新的Leader 。Leader 在宕机之前会一直保持Leader 的状态。
在成功选举Leader 之后，Leader 会在整个term 内管理整个集群。如果Leader 选举失败，该term 就会因为没有Leader 而结束。Splite Vote 是因为如果同时有两个候选人向大家邀票，这时通过类似加时赛来解决，两个候选者在一段timeout 比如300ms 互相不服气的等待以后，因为双方得到的票数是一样的，一半对一半，那么在300ms 以后，再由这两个候选者发出邀票，这时同时的概率大大降低，那么首先发出邀票的的候选者得到了大多数同意，成为领导者Leader ，而另外一个候选者后来发出邀票时，那些Follower 选民已经投票给第一个候选者，不能再投票给它，它就成为落选者了，最后这个落选者也成为普通Follower 一员了。
Raft 与Multi-Paxos 对比Raft 与Multi-Paxos 有着千丝万缕的关系，下面总结了Raft 与Multi-Paxos 的异同。Raft 与Multi-Paxos 中相似的概念：
Raft 的Leader 即Multi-Paxos 的Proposer 。Raft 的Term 与Multi-Paxos 的Proposal ID 本质上是同一个东西。Raft 的Log Entry 即Multi-Paxos 的Proposal 。Raft 的Log Index 即Multi-Paxos 的Instance ID 。Raft 的Leader 选举跟Multi-Paxos 的Prepare 阶段本质上是相同的。Raft 的日志复制即Multi-Paxos 的Accept 阶段。
Raft 与Multi-Paxos 的不同：
Raft 假设系统在任意时刻最多只有一个Leader ，提议只能由Leader 发出（强Leader ） ，否则会影响正确性；而Multi-Paxos 虽然也选举Leader ，但只是为了提高效率，并不限制提议只能由Leader 发出（弱Leader ） 。强Leader 在工程中一般使用Leader Lease 和Leader Stickiness 来保证：
Leader Lease：上一任Leader 的Lease 过期后，随机等待一段时间再发起Leader 选举，保证新旧Leader 的Lease 不重叠。
Leader Stickiness：Leader Lease 未过期的Follower 拒绝新的Leader 选举请求。
Raft 限制具有最新已提交的日志的节点才有资格成为Leader ，Multi-Paxos 无此限制。Raft 在确认一条日志之前会检查日志连续性，若检查到日志不连续会拒绝此日志，保证日志连续性，Multi-Paxos 不做此检查，允许日志中有空洞。Raft 在AppendEntries 中携带Leader 的commit index ，一旦日志形成多数派，Leader 更新本地的commit index 即完成提交，下一条AppendEntries 会携带新的commit index 通知其它节点；Multi-Paxos 没有日志连接性假设，需要额外的commit 消息通知其它节点。
Links
