Raft算法
前言
Raft算法是解决分布式系统共识的问题的算法，Raft是基于Multi-Paxos的基础上做了简化和限制。不同于Paxos的难以理解，Raft设计的首要目的就是可理解性，一个易于理解、实现简单的分布式一致性协议。
Raft 将一致性算法分解成了几个关键模块，例如领导人选举、日志复制和安全性，本文将主要基于raft论文简单分析raft算法。
领导选举
Raft是强领导(Strong leader)模型，一切以leader为主，比如日志只能由leader复制到其他服务器。所以leader的选举是非常重要的一部分。
首先介绍raft算法的三个服务状态：
- Leader：处理客户端请求、向集群其他服务发送心跳、日志复制管理。
- Follower：接受leader的信息，当于leader心跳超时，转换为候选者(candidate)。
- Candidate：候选人将向其他节点发送请求投票消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。
任意时间集群中只能由一个leader存在。
Raft使用心跳机制实现leader选举。在服务启动的时候，处于follower角色，需要注意的是每个服务于leader的心跳超时的时间是随机的(150-300 毫秒)。
服务启动
如上图，集群中有三个几点A、B、C，超时时间分别为150ms、200ms、300ms刚启动时任期编号都是0，都处于follower角色。节点A与leader的心跳超时时间最短，最先从follower状态转为candidate，并增加自己的任期编号，先给自己投上一张选票，并向集群中其他节点发送投票信息，当B、C节点接受到A的投票请求之后，在任期为1的这个阶段没有给其他节点投过票，便接受A的投票请求。此时节点A接受到了集群中超过一半的节点的投票，便成为任期为1的leader。
上诉是最简单的选举流程，里面有很多概念都需要解释，比如为什么超时时间不一样？任期编号是什么？投票比较的规则又是什么？
1. 任期编号
每个leader在当选期间都有一个自己的任期编号，它是全局单调递增的数字。每个节点都存储这当前的leader的任期编号，当处于candidate阶段的时候，发起投票的时候会把当前任期编号加一。
而且当一个节点接受到比自己任期高的请求时，会将自己的任期编号更新为高的任期编号，如果当前角色是leader，会从leader转换为follower角色。当接受到任期编号比自己小的请求时，节点会直接拒绝这个请求。
2. 投票比较规则
a. 先到先服务：一个节点在一个任期只能投一票，如果A、B节点都请求C节点投票，C节点如果先投给A之后、就会拒绝B的投票请求。
b.日志完整性：一个节点接受的投票信息如果它的日志比自身小，将会拒绝该投票请求。
c.过半策略：当某节点接受到了集群中超过一半的节点投票之后，成为该次任期的leader，向其他节点发送leader心跳。
d. 在等待投票期间，candidate 可能会收到另一个声称自己是 leader 的服务器节点发来的 AppendEntries RPC 。如果这个 leader 的任期号（包含在RPC中）不小于 candidate 当前的任期号，那么 candidate 会承认该 leader 的合法地位并回到 follower 状态。
3.随机超时
前面提高过，每个几点与leader的心跳超时时间是不同的，这样的好处在于避免瓜分票数的情况存在，能快速的进行leader选举。如果各个节点的超时时间都是一样的，就容易出现瓜分票数的情况存在，每个节点都没有获得超过一半的投票，就会开启下一轮的选举，选举时间就会很长。使用随机超时机制，正常情况下，一个时间段里只有一个节点发起投票请求。
下图是整个集群中服务角色变化的流程图。
状态转换
日志复制
Leader选举出来之后为客户端提供服务，将接受到的指令作为一个新的日志项追加到日志中去，然后并行的发起 AppendEntries RPC 给其他的服务器，让它们复制该日志项。当该日志项被安全地复制（过半的节点已复制完成），leader 会应用该日志项到它的状态机中（状态机执行该指令）然后把执行的结果返回给客户端。如果 follower 崩溃或者运行缓慢，或者网络丢包，领导人会不断地重试 AppendEntries RPC（即使已经回复了客户端）直到所有的 follower 最终都存储了所有的日志。
什么是日志
日志
上图展示了日志的格式，一个日志项包含三部分
- 索引(index)：日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码。
- 指令：一条由客户端请求指定的、状态机需要执行的指令。
- 任期编号：创建这条日志项的领导者的任期编号。
复制
Leader通过 AppendEntries RPC 将日志复制到其他节点。
AppendEntries RPC：
| 参数 | 解释 |
|---|---|
| term | 领导人的任期号 |
| leaderId | 领导人的 Id，以便于跟随者重定向请求 |
| prevLogIndex | 新的日志条目紧随之前的索引值 |
| prevLogTerm | prevLogIndex 条目的任期号 |
| entries[] | 准备存储的日志条目（表示心跳时为空；一次性发送多个是为了提高效率） |
| leaderCommit | 领导人已经提交的日志的索引值 |
| 返回值 | 解释 |
|---|---|
| term | 前的任期号，用于领导人去更新自己 |
| success | 跟随者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志时为真 |
接收者实现：
- 如果 term < currentTerm 就返回 false
- 如果日志在 prevLogIndex 位置处的日志条目的任期号和 prevLogTerm 不匹配，则返回 false
- 如果已经存在的日志条目和新的产生冲突（索引值相同但是任期号不同），删除这一条和之后所有的
- 附加日志中尚未存在的任何新条目
- 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志条目索引值中较小的一个
上诉是AppendEntries RPC的参数的接受流程。term与leaderId不用介绍很简单，而prevLogIndex、prevLogTerm的作用是日志的一致性检测，如果 follower 在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝该新的日志条目。一致性检查就像一个归纳步骤：一开始空的日志状态肯定是满足 Log Matching Property（日志匹配特性） 的，然后一致性检查保证了日志扩展时的日志匹配特性。因此，每当 AppendEntries RPC 返回成功时，leader 就知道 follower 的日志一定和自己相同（从第一个日志条目到最新条目）。
正常操作期间，leader 和 follower 的日志保持一致，所以 AppendEntries RPC 的一致性检查从来不会失败。然而，leader 崩溃的情况会使日志处于不一致的状态（老的 leader 可能还没有完全复制它日志里的所有条目）。如下情况：
image.png
在 Raft 算法中，leader 通过强制 follower 复制它的日志来解决不一致的问题。这意味着 follower 中跟 leader 冲突的日志条目会被 leader 的日志条目覆盖。
Leader 针对每一个 follower 都维护了一个 nextIndex ，表示 leader 要发送给 follower 的下一个日志条目的索引。当选出一个新 leader 时，该 leader 将所有 nextIndex 的值都初始化为自己最后一个日志条目的 index 加1。如果 follower 的日志和 leader 的不一致，那么下一次 AppendEntries RPC 中的一致性检查就会失败。在被 follower 拒绝之后，leaer 就会减小 nextIndex 值并重试 AppendEntries RPC 。最终 nextIndex 会在某个位置使得 leader 和 follower 的日志达成一致。此时，AppendEntries RPC 就会成功，将 follower 中跟 leader 冲突的日志条目全部删除然后追加 leader 中的日志条目（如果有需要追加的日志条目的话）。一旦 AppendEntries RPC 成功，follower 的日志就和 leader 一致，并且在该任期接下来的时间里保持一致。
总结
本机简单介绍了raft 的leader选举和日志复制，当然raft还有其他的特性本文并没有介绍，推荐去看raft的论文，完整的了解raft。
我之前ZAB协议的文章分析了zookeeper的zab协议，这里对比一下两者的异同。
- 两者都是强领导模型，由领导接受处理请求、复制日志。
- leader选举，两者都需要获取过半节点的投票才能选举出leader，raft采用随机超时和先到先服务的策略，相比zab协议会尽快选举出leader。
- 日志复制，在服务正常运行期间两者的日志复制没什么区别，都是由leader复制和过半节点确认提交日志。但是从leader崩溃到选举出新的leader，zab需要经过DISCOVERY和SYNCHRONIZATION两个阶段，来确认自己的leader地位和保持其他节点与leader的日志一致，才能对外提供服务。而raft选举完成之后就能对外提供服务，通过心跳和日志复制来完成leader的确认和日志的一致性。
最后https://raft.github.io这个网址详细介绍了raft协议。
参考
https://time.geekbang.org/column/intro/279
https://raft.github.io/
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
