Paxos 一直是分布式协议的标准，但是 Paxos 难于理解，更难以实现，例如 Google 的分布式锁系统 Chubby 在实现 Paxos 协议时就遇到很多坑。
来自 Stanford 的新的分布式协议研究称为 RAFT，它是一个为真实世界应用建立的协议，主要注重协议的落地性和可理解性。
简介
RAFT 算法在许多方面和现有的一致性算法都很相似，其独有的特性如下：
- 强领导者，日志只从领导者发送给其它从服务器，简化了对日志复制的管理。
- 领导选举，在所有一致性算法的心跳机制上增加了一个随机计时器来选举领导者，从而可以更加简单快捷地解决冲突。
- 日志一致，简单来说就是通过 Term 和 Index 保证所有的日志及其顺序全局唯一，同时不允许存在空洞 (Paxos允许)。
- 成员变更，使用一种共同一致的方法来处理集群成员变换的问题，在变更过程中集群依然可以继续工作。
复制状态机
一致性算法实际上是基于这一模型的，需要保证复制日志相同，简单来说就是初始状态相同，以相同的顺序处理指令，那么各个节点会产生相同的状态以及状态序列。目前使用比较多的是基于日志的复制方式，这一复制过程也被称为原子广播。
实际系统中使用的一致性算法通常含有以下特性：
- 安全性 safty，也就是在非拜占庭错误情况下，包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。
- 可用性 livness，集群中只要多数机器、客户端可以相互通讯，那么集群就是可用的，如果机器异常崩溃，大部分场景可以从持久化中恢复。
- 非时序依赖，通常不会因为物理时钟、消息延迟导致可用性问题。
拜占庭问题
这一问题实际上是 Lamport 老爷子在 《The Byzantine Generals Problem》中提出的，这实际上是一个虚构的故事，准确来说是研究分布式系统容错性的时候编出的一个故事。
不同的版本可能会略有出入，简单如下。
假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。
拜占庭将军问题更像是一个错误模型，简单地说，Byzantine Generals Problem 是针对所谓的 Byzantine Failure 来说的，而 Byzantine Failure 是指分布式系统中的某一恶意节点允许做任意事情去干扰系统的正常运行 (包括选择性不传递消息、选择性伪造消息等)，如何保证在这一场景下确保整个系统不会异常。
简单来说，就是在缺少可信的中央节点和可信任的通道的情况下，分布在网络中的各个节点如何达成共识的问题。
Practical Byzantine Fault Tolerance, PBFT
经典的 PBFT 的解决方案是需要所有节点均交换数据，有明显的扩展性问题。
Proof of Work, POW
在出现比特币之前，解决分布式系统一致性问题主要是 PAXOS 及其衍生算法，仅适用于中心化的分布式系统，这样的系统的没有不诚实的节点，也就是不会发送虚假错误消息，但允许出现网络不通或宕机出现的消息延迟。
在区块链的实现中通过 POW 来解决这一问题。
RAFT 算法
算法中的大部分工作是为了消除不确定性，例如不允许日志有空洞。为了方便理解，将算法分成了几个模块，包括了领导选举、日志复制、安全性、成员变更。
日志管理主要是通过 Leader 负责，从客户端接收日志，并将日志复制到其它从服务器上，同时通知其它从服务器什么时候将日志应用到状态机上，通过这一机制大大简化了对复制日志的管理。
Leader 会直接决定日志存放的位置，而不需要和其它服务器进行协商，当 Leader 宕机后，会从其它服务器上重新选举出来。
关于 Term
也就是一个任期，此时的 Leader 不变，每次都会通过发送的消息进行同步更新，如果当前服务器保存的 term 较小，那么就会更新到更大的值。
其中 term 的标识从 1 开始单调递增，而且总是以选举开始，总的时间不定，可能无限长，也可能只有选举时间。而且因为网络的延迟，各个节点看到相同term的时间点不同，极端情况下可能会有丢失某个 term 的情况。
Term 相当于不依赖墙上时钟的逻辑时间，同样可以用来做一些常规的判断，例如判断是否是一个过期的 Leader、如果收到了一个过期的请求则直接丢弃。
如果 Candidate 和 Leader 发现自己的 term 过期，那么会自动切换到 Follower 状态。
选主逻辑
基础的 RAFT 协议主要包含了如下几个角色：
Leader处理客户端请求，并将写日志同步到Follower节点。Candidate参与选主逻辑。Follower复制Leader发送的日志、转发客户请求。
RAFT 维护了单调递增的 Term 信息，值越大优先级越高，某个 Term 内最多只存在一个主节点，每个节点会通过 log::set_term() 持久化已知的 Term 信息；发送消息会附带该节点的 Term 信息，当节点接收到更大 Term 时会转换为 Follower 角色。
Leader 在任期内会周期性的发送心跳，如果 Follower 一直没收到心跳，那就认为原 Leader 失效，则转为 Candidate 开始重新发起选举，选举信息会带上日志信息 (TODO 应该是已经提交的信)。
日志复制
RAFT 的日志包含了 (Term, Index, Command)，其中 Command 的值协议本身并不关心，只有主节点可以收到写请求，从主节点来看大致会经历如下步骤：
- 通过
log::append()写入本地日志，当非Leader节点收到请求时会转发到Leader节点； - 并行地向各个
Follower发送Message::Append日志； - 等待多数
Follower节点的响应； - 应用到状态机，返回给客户端；
- 通知其它节点应用日志。
集群会保证提交的日志应用到状态机，不会发生回滚，注意，未提交的日志可能被覆盖。
安全性
所有基于领导者的一致性算法中，领导者都必须包含所有已提交的日志，有些算法需要额外机制识别并复制到主节点，而 RAFT 则通过选主阶段的限制来达到这一目的，简单来说，就是只对比当前节点新的 Candidate 投票，可确保至少一个节点有最新提交数据。
Multi RAFT
原始的 RAFT 协议主节点会处理所有请求，而且每个保存了所有数据，这样单节点会很容易成为系统瓶颈，常规的解决方案是 Sharding 数据，也就是 MultiRaft 实现。
线性一致性
RAFT 只提供了基础的共识机制，考虑到复制延迟、分区、主备切换等场景，是无法通过直接读取单节点数据来达成目标的，包括 Follower、Leader 等节点，所以，为了实现线性一致性还需要其它额外的机制来保证，
最简单的是将线性读采用类似写的逻辑，走一遍完整的日志复制提交流程，也被称为 LogRead，这种方式满足要求但是性能会很差，常规的优化方法有 ReadIndex 和 LeaseRead 两种。
ReadIndex
在 Leader 中读取，执行流程如下：
- 记录当前的
CommitIndex保存为本地的ReadIndex变量； - 向其它节点发起心跳，如果多数节点响应，那就能确定当前节点现在仍为
Leader角色； - 等待状态机至少应用到
ReadIndex日志，就可以安全读取了； - 执行读请求，将结果返回给客户端。
其中关键的是第三步中的 至少，在 ReadIndex 以及之后都可以满足要求，通过心跳确保当前仍然为主，省去了日志复制流程，而心跳开销较小，相比来说效率要好很多。
注意，当某个节点被选举为主时，此时的 CommitIndex 并非最新，需要节点完成 Noop 日志后再提供服务。
LeaseRead
上述方式仍然存在 Heartbeat 交互。
性能优化
整个 RAFT 的处理流程如下：
- Leader 接收 Client 发送的请求；
- Leader 将日志 Append 到本地；
- Leader 将日志并发送给其它节点；
- Leader 等待 Follower 结果，当多数节点提交成功则 Apply 到状态机；
- Leader 将结果返回给 Client 节点；
其它
FAQ
RAFT 根 2PC 的区别和相同点是什么？
严格来说两者的使用场景是不同的，RAFT 是共识算法，目的是为了保证各个节点的数据一致性，虽然在日志应用过程中分成了日志同步+日志应用两个阶段，但是其目的是保证该日志不同节点一致性。而 2PC 是为了处理分布式事务，其协调的是两个本地事务和全局事务的一致性。
为什么会有 Noop 日志？
这里的 Noop 日志是在节点当选 Leader 之后同步的日志，在作者毕业论文的 3.6.2 章节中有详细的介绍，为了保证日志的安全，节点当选后不会同步前任期的日志，而客户端何时提交数据又不确定，同时为了通过 Log Matching Property 保证各个节点数据一致性，那么就有了 Noop 日志。
Apply 失败如何处理？
RAFT 负责将请求同步到多个节点，并保证提交的数据不丢失以及不同节点的数据一致性，但是，对于应用数据结果是没有要求的，那么实际处理时会将报错信息返回给客户端，同时将 AppliedIndex 前移。
也可以对错误进行分类，如果是业务上的报错那么如上处理，如果是内部异常，例如 Bug、OOM 等，那么最好是直接崩溃退出。
为什么不持久化 Applied 和 Commit 的 Index 信息？
其中前者保存在状态机中，由其决定已经应用了多少日志；而后者则在主节点的选举过程中获得。
TODO
- Zookeeper 支持 Hierarchical Quorum 选主优化。
参考
- 核心内容包括了 官网地址、Paper(Extended Version)、Thesis 。