前言
先后拜读了Paxos made simple和Raft两篇大作，作为一个学数学出身的人，深感Paxos作者Leslie Lamport逻辑之严密，通过层层递进不断加强保证的方式推导出Paxos的神级算法，论文虽不长但要彻彻底底明白作者的心思逻辑，还得细细品味一番。笔者也深以为论文正应如此，逻辑严密不差丝毫。然而，在拜读Raft大作之后，笔者却有一种读小说后如沐春风之感。Raft作者没有任何头脑风暴，清清楚楚用及其通俗的语言阐述了一个工业级的通俗易懂的一致性协议。
Paxos在1990年就已经被提出来了，Raft协议直到2013年才以论文的形式面世，但短短几年Raft的各种开源和工业级应用却在以指数级增长，像开源实现etcd就是基于Raft协议实现的。下面我们来详细了解下Raft协议的真面目。
Raft一致性协议
为了形成多数派，Raft集群一般都是由奇数个server构成。Raft集群中的server总共有三种状态：
- Leader
- follower
- candidate
一般情况下leader只有一个，其它全部都是follower。leader负责接收并处理所有client的请求，follower是被动的，它只能接收leader的请求但从不主动发出任何请求。第三个状态candidate负责选举leader，一旦server身份确定则自动转换到leader或follower状态。下图展示了不同状态之间转换的条件：
Raft协议中另外一个非常重要的术语就是term（任期），Raft把时间轴按从左到右划分成任意长度的任期。每个term都是从一次选举开始，当某个candidate被选举为leader后，它便成为整个term的leader，选举结束后开始处理client的请求。
Leader选举
与Paxos选举算法相比，Raft协议选举算法显得相当的简单。从以上的状态转换图可以看出来，只有当server处于candidate状态时才能够进行选举流程。开始选举之前server首先增加它当前的term，然后才会转换到candidate状态。
- A启动后处于follower状态，当follower在timer时间内没有收到leader的心跳请求，会转换到candidate状态并触发选举流程。Raft协议使用多数派来保证leader的唯一性，当收到全部或者多数节点的同意后，candidate认为自己可以成为leader。一旦leader确定身份后，它会发送心跳信息给其它的server，以此来宣告它的统治时代到来。
- 如下图所示，当A发出投票后进入等待状态，此时由于集群中已经存在leader，A收到B的请求告知B已经是leader。这时如果B的term大于或者等于A当前的term，则A自动转换成follower，如果A当前的term大于B的term，则A维持在candidate状态继续等待其它请求。在Raft协议中所有的请求有一个共同的原则，就是如果请求中的term大于本地当前的term，server会自动转换成follower状态。
- 还有一种情况就是所有的server都处于candidate状态，发出自己的投票，大家的投票比较分散，所以没有server拿到大多数的投票，也就不能产生所谓的leader，这就是通常所说的split vote。那这种情况下怎么办呢？Raft为了避免这种情况发生的概率，采取了随机超时的机制，也就是说当某个server发起一次投票之前，他会随机设置超时时间，以此来减小不同server同时发出投票造成split vote的概率。
日志复制
Raft集群中每个server都维护自己的有限状态机，日志复制就是用来保证集群中有限状态机的一致性。一般过程如图所示，
client向leader发出请求，leader首先在本地的log中增加一条记录，同时发出append请求给其它所有的follower，follower收到请求后在自己的log中追加一条记录并回复leader，当leader确定有超过一半的server记录该操作后，就会把本次操作提交到状态机。
来看一下Raft日志的组成形式，log由一串连续的记录组成，每条记录是一个三元组（index，term，command）。其中，index是指记录在日志中的位置，term是该条记录在追加时的任期，command是每一次具体的操作信息。
当日志发生不一致的时候，leader和follower之间就需要进行日志比较，为了快速完成这样的操作，Raft定义了日志匹配特性可以达到此目的，
- 如果不同日志中的两个记录有相同的index和term，则它们存储的操作是相同的；
- 如果不同日志中的两条记录有相同的index和term，则所有以前的条目中的记录都是相同的。
对于一般正常的操作，leader和follower的日志会一直保持一致，但是每台机器都不是100%高可用的，leader宕机的情况下leader和follower的日志就及其容易造成不一致。
安全性
为了保证Raft算法的安全性，还需要两个特殊的限制，接下来我们就来看看这两个限制是什么?
选举限制
任何leader-based一致性算法中leader必须保存所有的提交的日志记录，一些一致性算法像VR，Zookeeper等在server中不包含所有committed日志的情况下依然可以被选择为leader。事物都有其两面性，这样看似优雅的处理让协议的实现变得复杂困难。相反，Raft使用简单的策略保证被选举的leader包含所有已经提交的日志。策略就是，选举leader的时候总是选择拥有最新日志的server作为leader。比较方法就是利用上面提到的日志匹配特性：
- 当term不同时，term更大的log更新
- 当term相同时，选择拥有更大index的
日志提交限制
当有半数以上的server保存了日志，leader可以安全的提交。有一种情况就是leader崩溃前并没有提交日志，未来的leader会继续未完成的使命。然而，新的leader并不知道日志记录是否已经同步到半数以上的server，况且，即便半数以上的server已经同步过了，依然有可能被覆盖掉。为了避免这种情况的发生，Raft要求leader永远不通过统计副本数量的方式提交先前term的日志，统计副本的方式只适用于当前term日志。当新的term有日志提交后，先前term的日志间接也会被提交，这就保证了同样index的日志不会被提交两次。
总结
相比较于Paxos协议，Raft在设计之初就本着简单易用的宗旨，才成就了这样一个可理解的，易于实现的，对于人类思维毫无违和感的协议。
参考
[1]. Leslie Lamport. Paxos Made Simple. 2001
[2]. Diego Ongaro and John Ousterhout. Raft Paper. 2013
[3]. Raft Website. The Raft Consensus Algorithm
[4]. Raft Demo. Raft Animate Demo
