Raft是一种共识算法（consensus algorithm），旨在替代Paxos。 它通过逻辑分离比Paxos更容易理解，但它也被正式证明是安全的，并提供了一些额外的功能。所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币（比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集（replication）。
1. 拜占庭将军问题
拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军必需达成 一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序，在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员不可靠的情况下，其余忠诚的将军在不受叛徒或间谍的影响下如何达成一致的协议，拜占庭问题就此形成。
这就是拜占庭将军的「问题」：只能依靠通信相互交流，又不知道谁是叛徒，怎么能不受叛徒们的影响，让这些忠诚的将军快速的达到一致的作战计划呢？
很显然，将这一场景套用到计算机系统中也是非常适用的：在一个分布式系统中，针对每个运算，每台独立的机器也需要最终达成一致的结果。但每台计算机之间也只能依靠网络通信（显然它们无法聚在一起开会），每台计算机都有出错的可能（被攻击，或故障），从而变成「叛徒」干扰正常的计算机达成一致。
2. Raft算法
2.1 Raft算法简介
Raft 是一个非拜占庭的一致性算法，即所有通信是正确的而非伪造的。N 个结点的情况下（N为奇数）可以最多容忍 (N−1)/2个结点故障。
Raft算法主要可以分为两个子问题：领导人选举和日志复制问题。
2.2 领导人选举
2.2.1 选举简介
Raft算法中的服务器主要扮演三类角色：
- Follower（追随者）
- Leader（领导者）
- Candidate（候选人）
下面给出的状态转移图能很直观的理解这三个状态的区别
正常情况下只存在一个 Leader，其他均为 Follower，所有客户端都与 Leader 进行交互。Leader负责管理集群中的日志复制，在大多数时候Candidate这个状态是不存在的，只有当集群中没有 Leader（可能由于 Leader宕机之类的原因）的时候才会产生Candidate，然后Candidate会要求其他节点进行投票，获得大多数票数的节点就变为新的Leader，其他所有节点的状态变为Follower。
在算法刚开始时，所有结点都是 Follower，每个结点都会维护一个Term值与一个定时器。
Term值：为了记录节点处于第几个任期，为了后面日志纠错而设定。
定时器：每次收到来自 Leader 的信息就会更新该定时器，定时器会随机给一个TIMEOUT值，一般在150ms到300ms之间。【下图是用最外圈圆圈的周长表示定时器的时间，当周长越小说明剩余时间越小。为了解决冲突，每个定时器给出的时间一般而言不是等长的。】
当TIMEOUT值到达后，还没有收到领导者的心跳检测【也就是定时器超时】，说明一段时间内没有收到 Leader 的消息，那么就可以认为 Leader 已宕机或不存在，那么该结点就会转变成 Candidate，意思为准备竞争成为 Leader。
成为 Candidate 后结点会向所有其他结点发送请求投票的请求（RequestVote），其他结点在收到请求后会判断是否可以投给他并返回结果。Candidate 如果收到了半数以上的投票就可以成为 Leader，成为之后会立即并在任期内定期发送一个心跳信息通知其他所有结点新的 Leader 信息，并用来重置定时器，避免其他结点再次成为 Candidate。
如果 Candidate 在一定时间内没有获得足够的投票，那么就会进行一轮新的选举，直到其成为 Leader，或者其他结点成为了新的 Leader，自己变成 Follower。
2.2.2 再次选举
再次选举会在两种情况下发生：
- 第一种情况是 Leader 下线，此时所有其他结点的计时器不会被重置，直到一个结点成为了 Candidate，和上述一样开始一轮新的选举选出一个新的 Leader。
- 第二种情况是某一 Follower 结点与 Leader 间通信发生问题，导致发生了分区，这时没有 Leader 的那个分区就会进行一次选举。这种情况下，因为要求获得多数的投票才可以成为 Leader，因此只有拥有多数结点的分区可以正常工作。而对于少数结点的分区，即使仍存在 Leader，但由于写入日志的结点数量不可能超过半数因此不可能提交操作。这解释了为何 Raft 至多容忍
(N−1)/2个结点故障。
2.2.3 定时器
定时器时间的设定实际上也会影响到算法性能甚至是正确性。
试想一下这样一个场景，Leader 下线，有两个结点同时成为 Candidate，然后由于网络结构等原因，每个结点都获得了一半的投票，因此无人成为 Leader 进入了下一轮。然而在下一轮由于这两个结点同时结束，又同时成为了 Candidate，再次重复了之前的这一流程，那么算法就无法正常工作。
为了解决这一问题，Raft 采用了一个十分“艺术”的解决方法，随机定时器长短（例如 150-300ms）。通过这一方法避免了两个结点同时成为 Candidate，即使发生了也能快速恢复。这一长短必须长于 Leader 的心跳间隔，否则在正常情况下也会有 Candidate 出现导致算法无法正常工作。
2.2.3 Term
Leader 的选举引出了一个新的概念——任期（Term）。
每一个任期以一次选举作为起点，所以当一个结点成为 Candidate 并向其他结点请求投票时，会将自己的 Term 加 1，表明新一轮的开始以及旧 Leader 的任期结束。所有结点在收到比自己更新的 Term 之后就会更新自己的 Term 并转成 Follower，而收到过时的消息则拒绝该请求。
在一次成功选举完成后，Leader 会负责管理所有结点直至任期结束。如果没有产生新的 Leader 就会开始一轮新的 Term。任期在 Raft 起到了类似时钟的功能，用于检测信息是否过期。
2.2.4 投票限制
在投票时候，所有服务器采用先来先得的原则，在一个任期内只可以投票给一个结点，得到超过半数的投票才可成为 Leader，从而保证了一个任期内只会有一个 Leader 产生（Election Safety）。
在 Raft 中日志只有从 Leader 到 Follower 这一流向，所以需要保证 Leader 的日志必须正确，即必须拥有所有已在多数节点上存在的日志，这一步骤由投票来限制。
投票由一个称为 RequestVote 的 RPC 调用进行，请求中除了有 Candidate 自己的 term 和 id 之外，还要带有自己最后一个日志条目的 index 和 term。接收者收到后首先会判断请求的 term 是否更大，不是则说明是旧消息，拒绝该请求。如果任期更大则开始判断日志是否更加新。日志 Term 越大则越新，相同那么 index 较大的认为是更加新的日志。接收者只会投票给拥有相同或者更加新的日志的 Candidate。
由于只有日志在被多数结点复制之后才会被提交并返回，所以如果一个 Candidate 并不拥有最新的已被复制的日志，那么他不可能获得多数票，从而保证了 Leader 一定具有所有已被多数拥有的日志（Leader Completeness），在后续同步时会将其同步给所有结点。
2.3 日志复制
所有操作采用类似两阶段提交的方式：
- Leader 在收到来自客户端的请求后并不会执行，只是将其写入自己的日志列表中，然后将该操作发送给所有的 Follower。
- Follower 在收到请求后也只是写入自己的日志列表中然后回复 Leader，当有超过半数的结点写入后 Leader 才会提交该操作并返回给客户端，同时通知所有其他结点提交该操作。
通过这一流程保证了只要提交过后的操作一定在多数结点上留有记录（在日志列表中），从而保证了该数据不会丢失。
Raft 保证了如下几点：
- Leader 绝不会覆盖或删除自己的日志，只会追加 （Leader Append-Only）
- 如果两个日志的 index 和 term 相同，那么这两个日志相同 （Log Matching）
- 如果两个日志相同，那么他们之前的日志均相同
2.3.1 Leader Append-Only
因为选举时的限制，根据 Leader Completeness，成为 Leader 的结点里的日志一定拥有所有已被多数节点拥有的日志条目，所以先前的日志条目很可能已经被提交，因此不可以删除之前的日志。
2.3.2 Log Matching
log匹配特性， 就是说如果两个节点上的某个log entry的log index相同且term相同，那么在该index之前的所有log entry应该都是相同的。如何做到的？依赖于以下两点
- leader在某一term的任一位置只会创建一个log entry，且log entry是append-only。
- consistency check：leader在AppendEntries中包含最新log entry之前的一个log 的term和index，如果follower在对应的term index找不到日志，那么就会告知leader不一致。
在没有异常的情况下，log matching是很容易满足的，但如果出现了node crash，情况就会变得复杂。比如下图
注意：上图的a-f不是6个follower，而是某个follower可能存在的六个状态
leader、follower都可能crash，那么follower维护的日志与leader相比可能出现以下情况
- 比leader日志少，如上图中的ab
- 比leader日志多，如上图中的cd
- 某些位置比leader多，某些日志比leader少，如ef（多少是针对某一任期而言）
当出现了leader与follower不一致的情况，leader强制follower复制自己的log
leader会维护一个nextIndex[]数组，记录了leader可以发送每一个follower的log index，初始化为leader最后一个log index加1， 前面也提到，leader选举成功之后会立即给所有follower发送AppendEntries RPC（不包含任何log entry， 也充当心跳消息），那么流程总结为：
- leader 初始化nextIndex[x]为 leader最后一个log index + 1
- AppendEntries里prevLogTerm prevLogIndex来自 logs[nextIndex[x] - 1]
- 如果follower判断prevLogIndex位置的log term不等于prevLogTerm，那么返回 False，否则返回True
- leader收到follower的回复，如果返回值是False，则nextIndex[x] -= 1, 跳转到s2. 否则
- 同步nextIndex[x]后的所有log entries
2.3.3 State Machine Safety
State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.
简单点说就是：所有节点在同一位置（index in log entries）应该应用同样的日志。
只要日志在多数结点上存在，那么 Leader 就可以提交该操作。但是 Raft 额外限制了 Leader 只对自己任期内的日志条目适用该规则，先前任期的条目只能由当前任期的提交而间接被提交。但是似乎有某些情况会违背这个原则。
corner case：上图是一个较为复杂的情况。在时刻(a): s1是leader，在term2提交的日志只赋值到了s1 s2两个节点就crash了。在时刻(b):s5成为了term 3的leader，日志只赋值到了s5，然后crash。然后在时刻(c)，s1又成为了term 4的leader，开始赋值日志，于是把term2的日志复制到了s3，此刻，可以看出term2对应的日志已经被复制到了majority，因此是committed，可以被状态机应用。不幸的是，接下来时刻d:s1又crash了，s5重新当选，然后将term3的日志复制到所有节点，这就出现了一种奇怪的现象：被复制到大多数节点（或者说可能已经应用）的日志被回滚。
究其根本，是因为term4时的leader s1在时刻C提交了之前term2任期的日志。
为了杜绝这种情况的发生：
- 某个leader选举成功之后，不会直接提交前任leader时期的日志，而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了，具体怎么实现了，在log matching部分有详细介绍。那么问题来了，如果leader被选举后没有收到客户端的请求呢，论文中有提到，在任期开始的时候发立即尝试复制、提交一条空的log。
因此，在上图中，不会出现（C）时刻的情况，即term4任期的leader s1不会复制term2的日志到s3。而是如同(e)描述的情况，通过复制-提交 term4的日志顺便提交term2的日志。如果term4的日志提交成功，那么term2的日志也一定提交成功，此时即使s1 crash，s5也不会重新当选。
参考链接：