raft是管理复制日志的一致性算法，功能与paxos一样，但相比paxos，raft更加好理解，在真实系统中具备更佳实践性。这篇论文主要介绍了复制状态机的问题(一致性算法的典型应用)、paxos的一些短板、raft的一致性算法和这项算法的评估。

raft算法跟很多一致性算法类似(Viewstamped Replication)，但是它有几个自己的特性：

1. 强leader：与其它一致性算法不同，raft采用强leader形式。例如日志只从leader流向follower，而不可以相反。这种方式简化了raft的日志管理，使得raft更容易理解。
2. leader选举：raft采用随机化的时间来选举，增加少量的心跳交流来简单地解决冲突，避免无限的split(下文将会描述)。
3. 成员变更：使用joint consensus的方式，使得集群在进行变更时可以正常运行。

论文的作者认为无论在教学方面还是实践系统方面raft都优于paxos和其它算法。

复制状态机

在分布式系统中，复制状态机用于解决容错问题。GFS、HDFS和RAMCloud都使用了独立的复制状态机来实现管理leader的选举和存储配置信息。复制状态机的例子有Chubby和ZooKeeper。
复制状态机典型的实现是使用复制日志，保持复制日志的一致性需要使用一致性算法。

实践系统中的一致性算法一般有以下属性：

1. 确保安全。不能返回不正确的结果，即便在网络延迟、分区、丢包、冗余和乱序的情况下。
2. available。在大多数server运行正常并可以彼此交流时，系统是可用的。因此，一个五个server的集群可以容忍两台server宕机。
3. 不依赖时间来保证一致性：时钟错误和极端的消息延迟在最坏的情况下才可引起不可用问题。
4. 一般情况下，在大多数server回应一轮rpc调用后完成。少数较慢的server不影响整个系统的性能。

paxos的问题

这一小节主要讲述paxos存在的问题，虽然paxos已经成为一致性算法的代名词，也被证明了正确性，通常情况下也很高效。但是它很难理解，并且难以在真实系统中实现。lamport的大多数解释是对于single paxos，而对于multi-paxos并没有很多细节。

paxos使用从许多日志条目中选出日志融合到有序的序列中和将点对点作为核心(最终也提出了弱leader模式来提升性能)都增加了复杂度。在实际系统中的实现都与paxos相差很大，下面这条来自Chubby实现的评价很好的说明了这个问题：
paxos算法的理论描述与真是系统的实现存在巨大鸿沟，最终系统的实现往往是建立在没有被证明算法的基础之上。

raft一致性算法

raft将一致性问题解剖为三个子问题：

1. leader选举
2. 日志复制
3. safety

raft基础

通常一个raft集群含有5个server，最多容忍2个server失败。每个server可以有三种状态：leader，follower和candidate。leader响应客户端的请求，follower将请求路由到leader。

raft将时间段划分为term，每个term开始于一次选举，term号是连续递增的。给定的term，最多只有一个leader。term在raft中类似逻辑时钟。每个server保存当前的term，server交流中如果发现本地的term较小则更新为较大值。如果leader或者candidate发现自己的term过期了，则转为follower。如果server接收到一个比自己小的term请求，则拒绝这个请求。

raft server间的交流使用RPC，基础的一致性算法只需要两种RPC。RequestVote RPC用于在选举阶段候选人的投票，AppendEntries RPC用于leader复制日志和提供心跳，后面有介绍第三种RPC用于snapshot的传输。一段时间内如果server没有接收到rpc将会重试，server以并行的方式发送来提高性能。

leader选举

raft以心跳的机制触发leader的选举。最初所有的server都以follower的形式开始，leader会不断发送心跳到follower，如果follower在一段时间内没有接收到心跳(election timeout)将会发起一次选举。将自己变为candidate，将投票自己为leader的请求并行的发送给其它server，持续这种状态直到三件事情发生：

1. 它赢得了选举
2. 另外一个server公布它成为了leader
3. 一段时间没有winner

一旦候选人赢得了选举，它会发送心跳到所有server宣告并阻止新的选举。

在等待投票结果时，候选人可能会接收到称为leader的server发送的AppendEntry请求，如果leader包括rpc的term大于等于自己的term，则候选人认为它是leader并将自己的状态转为follower。否则，拒绝这个请求。

第三种结果是产生了投票分裂，如果同一时间多个follower成为了候选人并投票自己为leader，就会使得票数分裂无法形成多数派。这种情况发生时，每个候选人会超时并开启一次新的选举，但是下一次也会出现同样的状况。

raft采用随机的超时限制(elect timeout,eg150-200ms)来使得split vote成为小概率事件并且可以快速被解决。

日志复制

leader响应客户端的请求，将命令追加到日志中并行的发送给每一个server，当日志被成功的复制，leader将这条日志应用到自己的状态机中并回应客户端。如果follower宕机、运行缓慢或者网络丢包，leader会无限的重试append请求直到所有的server都保存了这个日志条目。

leader决定日志条目什么时候可以被应用(committed)，raft保证committed条目已经持久化并最终会应用到状态机的所有可用节点。leader保存它知道的最大的已提交的index，并将其写入Append RPC中(包括心跳)，其它server知道这个日志条目被committed之后会将相应的条目应用到本地的状态机。

raft维护两个特性，也构成了日志匹配的原则：

1. 如果不同log中的两个条目有相同的index和term，那么它们保存了同样的命令。
2. 如果不同log中的两个条目有相同的index和term，那么它们之前的条目都是一样的。

给定的log index和term，leader最多只创建一个条目，不会更改其位置，并且leader从来不会修改或者删除日志。

一致性检查：follower在接收Append 请求时会检查rpc中携带的上一次committed log index和term，如果follower没有发现对应的日志条目则拒绝这次请求。

在异常情况下，follower可能会出现缺失日志、多余日志或者两者皆有这三种情况。leader通过强制使follower复制自己的日志来处理不一致，有矛盾的日志将会被重写，多余的日志会被删除。在异常情况下，follower的一致性检查将会失败，leader收到失败后会减小index并再次发送rpc到follower，最终会到达一个一致的点。这种方式可以优化，例如当一致性检查失败时，follower可以反馈冲突term的最早的index信息给leader，这样最多每个term会有一次rpc。

safety

这部分增加了leader选举的限制来完善raft算法。有了这一限制，可以保证每个任期的leader都拥有之前任期leader的所有日志条目，符合leader completeness原则，最后提出了简单的证明和如何修正状态机。

选举限制

参与选举的leader必须含有之前任期leader的所有日志条目。leader从来不需要重写已存在的日志，日志的流向始终为单向的。voter将会拒绝比它更小的term的投票。

提交之前任期的日志条目

raft不可以通过在大多数上存储的日志条目来确定提交的日志，只有leader上的日志条目可以。一旦日志条目以这种方式提交，那么它之前的日志条目都被间接提交了。其它一致性算法在新leader需要复制之前任期的日志时必须使用新的任期号，而raft使用同样的任期号。

安全性论证

假设不能保证leader completeness，将会有哪些矛盾点，不详述了。

follower和candidate crash

相比leader crash更加简单，通过重试append rpc请求，raft请求是幂等的，即便是重试了相同的请求，也是安全的。

timing and availability

raft的安全性不依赖于时间，但系统的可用性(响应时间)依赖于时间。选举是对时间要求的关键操作。
在满足以下条件时，raft可以选出稳定的leader:
broadcastTime << electionTimeout << MTBF

• broadcastTime: 并行发送请求到每个server以及接收回应的平均时间(0.5ms ~ 20ms)
• electionTimeout: 选举超时时间(10ms ~ 500 ms)
• MTBF: server不可用的平均时间间隔(几个月)

一般情况下，上述公式很好满足。

集群成员变更

在现实系统中，会需要更改配置。如何在集群转变过程中不影响正常的服务请求是很重要的。raft实现了自动配置变更并将其加入一致性算法中。
为了确保集群变更过程中的安全性，不能同时有两个leader存在。使用两阶段协议，有多种使用两阶段协议的方式，在raft中，先使集群切换到一个过渡的配置阶段，叫作join consensus，是新旧配置的组合：

1. 日志条目被复制到新旧配置中的所有server
2. 任意配置中的任何一个server都可以成为leader
3. 选举和commitment需要新旧配置都达成多数派

一旦join consensus提交了，集群就变更为新集群。join consensus使得在变更过程中系统依然可以对外提供服务。
对于配置变更提出了三个问题：

1. 新加入的server是空白的，需要追赶日志。所以增加新的阶段，server不作为投票的一员，只复制日志直到追赶上集群中的其它server。
2. leader可能不是Cnew中的一员，在提交Cnew之后退回follower状态，这意味着有一段时间(committing)leader管理着集群但不包括它自己。在Cnew提交时，发生leader过渡。
3. 移除不在Cnew中的server会使得它们收不到心跳，从而引起不断的选举，使可用性大大降低。为了避免这个问题，server在确认有主存在时忽略投票请求。特别地，如果server接收到一个最小超时选举时间的投票，它会忽略它，这不会影响正常的选举，只是在每次选举时等待一个最小超时时间，但它很好的避免了被移除server的扰乱。

日志合并

这一章节提出snapshot的方式来解决不断增长的日志size导致的空间膨胀和性能问题。snapshot方式也被用于chubby和zookeeper中。

日志的清理和merge采用LSM-Tree的方式，一种渐进式的compaction，避免了每次操作整个数据集。每个server可以独立的创建快照，快照之前的日志可以丢弃，当leader丢弃了需要发送给落后follower的日志条目时也需要传输快照给follower，这就是前文提到的第三种类型的rpc，InstallSnapshot RPC。

两个问题需要注意：

1. 何时去做snapshot
   一般是限定log size的大小
2. 做snapshot时不应该影响正常的操作，性能相关
   使用copy-on-write机制

客户端交互

客户端随机选择一个server发送请求，如果server是follower则会拒绝这个请求并返回leader的相关信息，如果leader crash了，则请求超时，再次重试发送给随机的serever。客户端对于同一个请求分配一个独一无二的number，对于重试了相同的请求的情况，raft对于相同的请求的处理是幂等的。
读不可以返回过期的数据，在没有额外的处理方式时，leader可能会返回被新leader废弃掉的数据，而它自己并不知道。raft增加两个额外的措施来保证不会返回过期的数据：

1. leader可能不知道哪些数据已经被提交，leader完全原则保证了新leader拥有之前leader所有日志条目，但是它最开始并不知道它们是哪些。解决方式：
   leader在任期开始时提交一个空白log来解决
2. leader检查自己是否已经不是leader了，解决方式：
   在回应client之前，与多数server进行心跳交流

其它

剩余几章讲述了raft的实现、评估、正确性和不同elect timeout下的性能测试。不详述，具体见论文。

参考In Search of an Understandable Consensus Algorithm论文