在大数据的学习过程中，学到了分布式一致性算法Raft，因此写下本文记录学习过程。
算法背景
一致性算法允许一组机器像一个整体一样工作，即使其中一些机器出现故障也能够继续工作下去。正因为如此，一致性算法在构建可信赖的大规模软件系统中扮演着重要的角色。在过去的 10 年里，Paxos 算法统治着一致性算法这一领域：绝大多数的实现都是基于 Paxos 或者受其影响。同时 Paxos 也成为了教学领域里讲解一致性问题时的示例。
但是不幸的是，尽管有很多工作都在尝试降低它的复杂性，但是 Paxos 算法依然十分难以理解。并且，Paxos 自身的算法结构需要进行大幅的修改才能够应用到实际的系统中。这些都导致了工业界和学术界都对 Paxos 算法感到十分头疼。
由此更加容易理解的Raft算法出现了。Raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。为了达到易于理解的目标，raft做了很多努力，其中最主要是两件事情：问题分解、状态简化。问题分解是将”复制集中节点一致性”这个复杂的问题划分为数个可以被独立解释、理解、解决的子问题。状态简化则是对算法做出一些限制，减少需要考虑的状态数，使得算法更加清晰，更少的不确定性。
raft工作时会先选举出leader，leader完全负责日志复制的管理。leader负责接受所有客户端更新请求，然后复制到follower节点，并在“安全”的时候执行这些请求。如果leader故障，followers会重新选举出新的leader。
核心机制：领导人选举
基本概念
raft协议中，一个节点任一时刻处于以下三个状态之一：
- leader（领导人）
- follower（跟随人）
- candidate（候选人）
下面的状态转移图能很直观的直到这三个状态的区别
可以看出所有节点启动时都是follower状态；在一段时间内如果没有收到来自leader的心跳，就从follower切换到candidate，发起选举；如果收到大多数的选票（含自己的一票）则切换到leader状态；如果发现其他节点比自己更新，则主动切换到follower。
总之，系统中最多只有一个leader，如果在一段时间里发现没有leader，则大家通过选举-投票选出leader。leader会不停的给follower发心跳消息，表明自己的存活状态。如果leader故障，那么follower会转换成candidate，重新选出leader。
选举方式
从先前内容可以看出，哪个节点做leader是大家投票选举出来的，每个leader工作一段时间，然后选出新的leader继续负责。这跟民主社会的选举很像，每一届新的履职期称之为一届任期，在raft协议中，也是这样的，对应的术语叫term。
term（任期）以选举（election）开始，然后就是一段或长或短的稳定工作期（normal Operation）。从上图可以看到，任期是递增的，这就充当了逻辑时钟的作用；另外，term 3展示了一种情况，就是说没有选举出leader就结束了，然后会发起新的选举，后面会解释这种split vote的情况。
选举过程
发起选举：
- 增加节点本地的 current term ，切换到candidate状态
- 投自己一票
- 并行给其他节点发送 RequestVote RPCs
- 等待其他节点的回复
选举结果：
- 收到大多数投票（含自己的一票），则赢得选举，成为leader，此时立刻给所有节点发消息，避免其余节点触发新的选举。
- 被告知别人已当选，那么自行切换到follower
- 一段时间内没有收到majority投票，则保持candidate状态，重新发出选举
投票规则：
- 在任一任期内，单个节点最多只能投一票
- 候选人知道的信息不能比自己的少
- first-come-first-served 先来先得
日志复制
基本概念
当有了leader，系统应该进入对外工作期了。客户端的一切请求来发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。
由于相同的初始状态和相同的输入一定能带来相同的结束状态，所以对于这种状态的迁移我们可以用状态机来进行表示。复制状态机的图如下所示：
在raft中，leader将客户端请求封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用（apply）log entry中的command，则状态肯定是一致的。
案例分析
不难看到，日志由顺序编号的log entry组成 ，每个log entry除了包含请求，还包含产生该log entry时的leader term。从上图可以看到，五个节点的日志并不完全一致，raft算法为了保证高可用，并不是强一致性，而是最终一致性，leader会不断尝试给follower发log entries，直到所有节点的log entries都相同。
在上面的流程中，leader只需要日志被复制到大多数节点即可向客户端返回，一旦向客户端返回成功消息，那么系统就必须保证log（其实是log所包含的请求）在任何异常的情况下都不会发生回滚。这里有两个词：commit（committed），apply(applied)，前者是指日志被复制到了大多数节点后日志的状态；而后者则是节点将日志应用到状态机，真正影响到节点状态。
安全性
选举安全性
即任一任期内最多一个leader被选出。这一点非常重要，在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个leader，被称之为分裂（ split），这是非常严重的问题，会导致数据的覆盖丢失。在raft中，两点保证了这个属性：
- 一个节点某一任期内最多只能投一票；
- 只有获得majority投票的节点才会成为leader。
日志匹配性
如果两个节点上的某个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 entry在某个任期被提交（committed），那么这条日志一定会出现在所有更高term的leader的日志里面。
- 一个日志被复制到majority节点才算committed
- 一个节点得到majority的投票才能成为leader，而节点A给节点B投票的其中一个前提是，B的日志不能比A的日志旧。
- raft与其他协议不同，raft始终保证leader包含最新的已提交的日志，因此leader不会从follower catchup日志，这也大大简化了系统的复杂度。
状态机安全性
如果节点将某一位置的log entry应用到了状态机，那么其他节点在同一位置不能应用不同的日志。简单点来说，所有节点在同一位置（index in log entries）应该应用同样的日志。
错误处理
node crash
leader、follower都可能crash，那么follower维护的日志与leader相比可能出现以下情况：
1. 比leader日志少，如左图中的ab
2. 比leader日志多，如左图中的cd
3. 某些位置比leader多，某些日志比leader少，如ef（多少是针对某一任期而言）
对于比leader日志少的情况比较容易理解，可能是出于网络故障，节点没有收到leader发出的appendEntry的消息；对于比leader多的情况，可能是由于该节点曾经当选过leader，但是它还没有来得及把自己收到的命令发布出去，就已经挂了，所以只有它自己保存了这些消息；对于ef的情况，可能是在term 2和term 3中，节点曾经当选，并收到一些命令，但是还没有来得及发出appendEntry的消息，它就down了，然后一直down到term 8，才重新加入。
当出现了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, 跳转到step2. 否则
- 同步nextIndex[x]后的所有log entries。（如果有超出的log，全部删除）
state machine safety
上图是一个较为复杂的状态机出现混乱的情况。在时刻(a), s1是leader，在term2提交的日志只复制到了s1 s2两个节点就crash了。在时刻（b), s5成为了term 3的leader，日志只复制到了s5，然后crash。然后在(c)时刻，s1又成为了term 4的leader，开始复制日志，于是把term 2的日志复制到了s3，此刻，可以看出term 2对应的日志已经被复制到了majority，因此是committed，可以被状态机应用。不幸的是，接下来（d）时刻，s1又crash了，s5重新当选，然后将term 3的日志复制到所有节点，这就出现了一种奇怪的现象：被复制到大多数节点（或者说可能已经应用）的日志被回滚。
究其根本，是因为term 4时的leader s1在（c）时刻提交了之前term 2任期的日志。如何理解呢？如果S1不是只提交2，而是连同最新的日志4一起提交了，这样的话，有三个节点的日志到达了term 4，那么接下来S5就不会当选，也不会出现日志回滚的情况。
因此，为了杜绝这种情况的发生，Raft的设计为：
某个leader选举成功之后，不会直接提交前任leader时期的日志，而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了。那么问题来了，如果leader被选举后没有收到客户端的请求呢，论文中有提到，在任期开始的时候发立即尝试复制，提交一条空的log。
因此，在上图中，不会出现（c）时刻的情况，即term4任期的leader s1不会复制term2的日志到s3。而是如同(e)描述的情况，通过复制-提交 term4的日志顺便提交term2的日志。如果term 4的日志提交成功，那么term 2的日志也一定提交成功，此时即使s1 crash，s5也不会当选。
leader crash
follower的crash处理方式相对简单，leader只要不停的给follower发消息即可。而当leader crash的时候，事情就会变得复杂。以上是一个更新请求的流程图。数据的流向只能从 Leader 节点向 Follower 节点转移。当 Client 向集群 Leader 节点提交数据后，Leader 节点接收到的数据处于未提交状态（Uncommitted），接着 Leader 节点会并发向所有 Follower 节点复制数据并等待接收响应，确保至少集群中超过半数节点已接收到数据后再向 Client 确认数据已接收。一旦向 Client 发出数据接收 Ack 响应后，表明此时数据状态进入已提交（Committed），Leader 节点再向 Follower 节点发通知告知该数据状态已提交。
但是，Leader节点在上述过程的任一时刻都有可能挂掉，因此需要分情况讨论：
1. 数据到达 Leader 节点前
这个阶段 Leader 挂掉不影响一致性。
2. 数据到达 Leader 节点，但未复制到 Follower 节点
这个阶段 Leader 挂掉，数据属于未提交状态，Client 不会收到 Ack 会认为超时失败可安全发起重试。Follower 节点上没有该数据，重新选主后 Client 重试重新提交可成功。原来的 Leader 节点恢复后作为 Follower 加入集群重新从当前任期的新 Leader 处同步数据，强制保持和 Leader 数据一致。
3. 数据到达 Leader 节点，成功复制到 Follower 所有节点，但还未向 Leader 响应接收
这个阶段 Leader 挂掉，虽然数据在 Follower 节点处于未提交状态（Uncommitted）但保持一致，重新选出 Leader 后可完成数据提交，此时 Client 由于不知到底提交成功没有，可重试提交。针对这种情况 Raft 要求 RPC 请求实现幂等性，也就是要实现内部去重机制。
4. 数据到达 Leader 节点，成功复制到 Follower 部分节点，但还未向 Leader 响应接收
这个阶段 Leader 挂掉，数据在 Follower 节点处于未提交状态（Uncommitted）且不一致，Raft 协议要求投票只能投给拥有最新数据的节点。所以拥有最新数据的节点会被选为 Leader 再强制同步数据到 Follower，数据不会丢失并最终一致。
5. 数据到达 Leader 节点，成功复制到 Follower 所有或多数节点，数据在 Leader 处于已提交状态，但在 Follower 处于未提交状态
这个阶段 Leader 挂掉，重新选出新 Leader 后的处理流程和阶段 3 一样。
6. 数据到达 Leader 节点，成功复制到 Follower 所有或多数节点，数据在所有节点都处于已提交状态，但还未响应 Client
这个阶段 Leader 挂掉，Cluster 内部数据其实已经是一致的，Client 重复重试基于幂等策略对一致性无影响。
7. 网络分区导致的脑裂情况，出现双 Leader
网络分区将原先的 Leader 节点和 Follower 节点分隔开，Follower 收不到 Leader 的心跳将发起选举产生新的 Leader。这时就产生了双 Leader，原先的 Leader 独自在一个区，向它提交数据不可能复制到多数节点所以永远提交不成功。向新的 Leader 提交数据可以提交成功，网络恢复后旧的 Leader 发现集群中有更新任期（Term）的新 Leader 则自动降级为 Follower 并从新 Leader 处同步数据达成集群数据一致。
上面穷举分析了最小集群（3 节点）面临的所有情况，可以看出 Raft 协议都能很好的应对一致性问题，并且很容易理解。
