本篇讲解分布式系统共识算法 raft 的基本姿势，相关论文可点击这里。
注：此篇尚未整理完成，虽然代码已经完成，但因一些变故，日后再继续整理
简介
Paxos 作为一套可以解决分布式场景下高容错（半数以内的机器挂掉）的共识算法被广泛接受，然而由于其难以被理解所以少有直接的实现。Raft 的本质其实是对 Paxos 协议加强后的一种实现方式，对诸多细节进行了定义，使得这套系统变得易于实现。（个人认为，其实不得不承认的是，这样的代价是降低了效率）。
Raft 类似于其他的共识算法，但它有几个独有的特征———
- 强 leader：Raft 的 leader 相比其他算法要更强，例如 log entry（理解为一条记录）只允许从 leader 通知给其他服务器，这使得 log entry 的分发变得简单易于理解；
- leader 选举：Raft 中每个服务器都有自己不同的（随机）竞选周期。这一对心跳机制的独特改进有效解决了可能出现的选举冲突问题；
- 成员变更：Raft 在变更服务器集群成员时使用了新的联合共识方法，切换期间两个不同配置的大多数服务器保持重叠。
看不懂没关系，往下看。
基本概念
首先讲一讲共识算法的一些基本概念（不仅仅是 raft 协议）。
可复制状态机
共识算法基本讲的都是基于可复制状态机的共识算法，服务器集合中的所有状态机都可以通过相同的日志拷贝计算得到相同的状态，即使一些（不超过半数）服务器出现异常也一样能保持一致。可复制状态机是众多大型分布式系统的基础。例如包括 GFS、HDFS、RAMCloud 等通常使用分布式的可复制状态机管理 leader 选举和保存配置信息。常见的可复制状态机的例子包括 Chubby 和 ZooKeeper。
可复制状态机通常通过可复制 log 实现。每台服务器保存了相同的所有历史 command 的 log，状态机依次执行这些 command 可以得到相同的状态和输出。（类比 git）
角色
在共识协议中通常节点服务器有三种状态——leader、candidate 和 follower。
- leader：通常由 leader 决定确认 command 的写入，或者在数据不一致时决定使用的内容，或者由 leader 负责分发内容。
- candidate：candidate 是候选人，candidate 并不总是存在。当 leader 节点出现异常或某些情况下，follower 会成为 candidate 并通过获得多数确认成为 leader。
- follower：follower 作为分布式的执行机，接收执行来自 leader 的执行等。
服务器节点的角色会在三种状态间根据规则切换。
行为
- 心跳检测：所有 follower 和 leader 间会通过心跳保证连接正常。当 follower 长时间无法收到 leader 的心跳时或心跳回复时判定 leader 挂掉（真实情况下也可能是自己网络挂了）
- leader 选举：当目前的 leader 无法正常工作或连接到时，需要进行 leader 选举选出新的 leader，一些 follower 会成为 candidate，并在获得半数赞同投票时成为新的 leader
- 投票：当收到竞选请求时决定是否选举 candidate 为 leader
- log 分发：leader 会接受来自客户端的 log，然后将其分发复制给整个集群，同时强制要求其他节点与自己一致
raft 基础
在 raft 中，follower 是完全被动的：follower 不主动发送任何请求，只对 leader 和 candidate 的请求做回应。（如果客户端向 follower 发送了 command，follower 将其重定向到 leader）只有 leader 拥有 log 的写入权限，所有的 command 由 leader 先接受，然后分发给所有 follower，不一致时可覆盖 follower 内容。下图简要展示了各角色切换的条件。
raft 采用任期制，任期用递增的整数表示。leader 由选举选出，在竞选时会有一到多个 candidate 尝试成为 leader，当 candidate 赢得竞选后，它会转变为该任期的 leader 直到新的任期。在某些情况下，投票可能无法产生大多数同意的情况（比如 3 个 candidate 每人获得了总数 1/3 节点的支持），那么很快新的任期（新的选举）会再次开始以打破局面。由此可以看出，raft 保证了每一任期至多有一个 leader。
然而作为分布式系统，不同的节点可能并不总是同时能观察到任期的更迭，甚至某些情况下某个节点可能会错过整个选举甚至整个任期，所以对于每个节点而言，都会存有一份当前任期和当前 leader。所有的节点间通信都会带上任期信息以校验传来的或自己节点的数据是否过期，并更新或通知更新。当 candidate 发现自己的 term 已经过旧则立刻回归 follower 状态。对于过旧的请求服务器直接拒绝执行。
raft 节点间通过 RPC 通信。具体的 RPC 格式在下文解释。
raft 实现
状态
持久状态
这些状态信息需要在每次响应 RPC 前更新到静态存储
- currentTerm：节点观察到的最新任期（初始化为 0，递增）
- votedFor：当前任期选举环节投给的 candidate 节点 ID
- log[]：log 条目数组，每个条目都包含一条状态机 command 和收到该指令时的任期（首条下标为 1）
所有服务的易失状态
- commitIndex 已知最高日志条目的下标（初始化为 0，单调增加）
- lastApplied 应用于状态机的最高日志条目的下标（初始化为 0，单调增加）
leader 的易失状态
选举后重新初始化
- nextIndex[] 对于每个服务器，要发送到该服务器的下一个日志条目的下标（初始化为领导者最后日志下标+1）
- matchIndex[] 对于每个服务器，已知在服务器上复制的最高日志条目的下标（初始化为 0，单调增加）
AppendEntries RPC
由 leader 调用以复制日志条目; 也用作心跳。