易理解的raft共识算法

共识算法（Consensus Alogrithm）是允许分布式系统在忍受部分机器可以宕机的前提下实现一致可靠的算法。Paxos是共识算法鼻祖，基本上后续的算法都是Paxos的变种，本质上（先到先得原则、大多数原则、两阶段提交）都一样。但是Paxos作者只是提出理论，没有给出工程化的实现细节，并且理论描述也晦涩难懂。因此Raft作为一种更易理解的共识算法被提出，而且还给出算法实现的诸多细节，其目标让算法满足安全、高效、易理解的性质，可以显著减少开发者的初期设计工作量。本文是在阅读了Raft论文之后，将其关键点记录下来，并附上自己的一些理解。

复制状态机

复制状态机（Replicated state machines）是实现分布式系统中容错服务的一种方法。从字面上理解，就是将状态机复制到系统中的每一台机器上，如果是确定状态机，则多个相同状态机的拷贝，从同样的“初始”状态开始，经历了相同的输入序列后，会达到同样的状态，并且输出同样的结果。其实现一般采用复制日志的方式，如下图所示：

客户端发送一系列命令，集群中的每台机器都会用日志顺序记录这些命令，通过一致性模块保证每台机器的日志保持一致，日志一致表示命令的执行顺序和数目都一样。然后每台机器会顺序执行日志中的命令，客户端从状态机中读取最新的结果。raft算法就是用来保证日志复制的一致性，一条日志记录称为log entry，记录了客户端命令。

Raft

raft的起始流程为选主（leader election），通过选择一个leader机器，其他机器则成为follower机器，后续的流程由leader主导，客户端只与leader进行交互，日志数据从leader流向follower，当一个leader宕机或与其他机器失联时，会重新进行选主。这种设计简化了日志的复制过程。raft和paxos一样，也是基于大多数原则进行共识的，所以只要多半机器正常，那么系统仍然可以正常提供服务，比如集群有5台机器，可以忍受2台机器宕机。

Raft基本概念

Term(任期)

term类似paxos中的proposal number(提议号)，用连续自增的自然数表示，这些连续的数本质上是表示时序性，区分提议的时序先后。但paxos中的proposal number是全局唯一的，不仅标识时序性，还标识单个提议，而raft中是将时间切分成段落，一个term表示一段时间，而具体的提议（日志复制）是通过lastLogIndex（最新的日志索引）表示的。在一个term中，最多只能有一个leader，所以新的term开始时会进行选主流程。每台机器会存储当前属于哪一个term，在机器之间通信时附带term，如果发现大于自身的term，则更新自身的term；如果发现小于自身的term，则拒绝对方的请求。

机器状态机

raft的机器共有3种状态，leader、follower、candidate。状态机转换如下图所示：

系统启动时，默认都是follower状态，初始化时会随机赋予一个时间（下面会描述原因），当超时时会转换为candidate状态，发起一轮投票，candidate是选主过程中的中间状态，只有大多数follower投票通过时，才会转换为leader。如果candidate选主超时，则会新发起一轮选主过程（当前自身term自增）。如果candidate收到leader发来的信息时，会转换为follower。cadidate和leader在发现更大的term时，会转换为follower。所以term其实是专门为leader设计的，保证当前term内leader的合法性，并在leader异常时通过超时机制重新在新的term内选择新的leader。

请求类型

raft协调一致性的请求有两类:RequestVote和AppendEntries。RequestVote表示candidate发起选主投票。AppendEntries表示leader发起日志同步请求（将最新的log entry复制到大多数follower机器上）以及心跳（leader续约，防止频繁的选主）。

Raft性质

raft算法包括以下5种性质，确保了算法的安全性：

• 选主安全（Election Safty）:给定一个term，最多只有一个leader可以被选举。
• leader仅追加（Leader Append-Only）:leader绝不覆盖或删除自身的log entries，只能追加日志。
• 日志匹配（Log Matching）:如果两份日志包含一个具有相同index和term的日志记录（log entry）,那么index之前的所有日志记录都是相同的。
• leader完备性（Leader Completeness）：如果一个log entry在特定的term被提交，那么这个entry会出现所有更大term的leaders的日志中。
• 状态机安全性（State Machine Safety）:如果一台机器应用了某个index的log entry至其状态机中，那么没有其他机器会在同一index应用不同的log entry。

选主(Leader election)

系统启动是都是follower状态，等待超时时会将自身term自增并转换成candidate开始向集群中所有机器发起选主投票（RequestVote），当收到大多数投票时，转换成leader状态，此时发送心跳（AppendEntries）给其他机器及时制止新的选举流程。

如何确保选主安全？

有两个原则可以确保选主安全。一个是先到先得原则，每台机器在当前term中只能投票给一台candidate；另一个是大多数原则，必然有一个公共的机器，这台机器只能投票给一台candidate，这样就只可能有一台candidate会成为leader。

如何避免无限选举？

当系统开始时，如果所有机器同时发起选主流程，可能所有流程都不满足大多数原则，这个时候只能等待candidate超时重新发起一轮选主，此时仍然会不满足大多数原则，这样系统就一直处于选主过程中，造成系统不可用。为了避免无限选举，raft采用了随机选举超时（randomized election timeouts）的方法，让机器的选举超时时间进行随机初始化，避免选主流程在同一时间段发生，同时leader会定时发送心跳到follower进行续约。

选举超时时间如何设定？

raft采用随机选举超时策略错开选举时间，尽量避免并发选举，但是超时时间的设定同样很重要，影响到系统的可用性。为此raft给出了如下公式用来确定选举超时时间：

broadcastTime « electionTimeout « MTBF

broadcastTime是广播RPC请求的平均响应时间，MTBF是单台机器平均宕机时间间隔。broadcastTime需要远小于electionTimeout，用来确保leader到follower的心跳是可靠的，而electionTimeout需要远小于MTBF，保证系统可以正常运行，否则leader崩溃之后，需要等很久才会发起新一轮选举，这期间系统处于不可用状态。broadcastTime一般会在20ms以内，MTBF一般几天甚至几个月，所以electionTimeout可以在（150ms, 300ms）内随机选择。

leader完备性的保证

是不是所有发起选主的候选candidate都可以成为leader？答案是否定的，因为这破坏了leader完备性，如果一个不包含所有已经提交的log entries的candidate成为leader的话，且没有额外的操作来从其他机器复制最新的log entries，就会丢失数据。需要强调是这里的已提交日志指的是大多数机器已经持有该日志的副本并且可以安全的应用到状态机中，但是大多数机器已经持有该日志的副本并不表示该日志是已提交的，是属于两种状态。如下图所示是日志的组织方式：

raft为了简单和易理解，保证了日志流只能从leader流向follower，所有新选举出来的leader必须包含所有已经提交的log entries，这个就是leader完备性。为了拒绝过期的candidate，follower会查看RequestVote请求中的lastLogIndex和lastLogTerm，和自身的日志进行比较，如果相同或更新（up-to-date），则同意选举，否则拒绝。up-to-date定义如下：

两份日志如果最新的log entry有不同的term，则term大的更up-to-date，如果term相同，则日志更长（index大）的更up-to-date

所以，整个RequestVote过程如下图所示：

日志复制(Log Replication)

leader可以决定一个log entry何时可以被提交，就是当log entry被大多数机器复制的时候。由于Log Macthing机制，当一个log entry已提交，那么其index之前的所有entries也是已提交的。所有机器自身都会维护一个commitIndex来标志哪些entry是已提交的，那些已提交的log entries是可以安全的被应用到状态机中。leader将自身的commitIndex同步到follower中。

日志不一致如何处理？

leader和follower是可能会出现日志不一致的情形，follower中的日志可能缺失、增多、或者两者都有。如下图所示：

图中follower(f)在term为2时成为leader，收到客户端请求，并追加了若干entries，在提交日志前宕机，快速恢复之后在term为3时又成为leader并追加了若干entries，随后再次崩溃宕机。最终与term为8的leader日志产生了不一致。

前面讲过，leader的日志是不能覆盖和删除的（Leader Append-Only），而且日志流仅从leader流向follower，follwer的日志可以被覆盖和删除。如果leader与follower的日志不一致，说明follower存在未提交的日志，这种情况一般都是leader换届造成的。为了让follower与leader一致，可以强制让follower复制leader的日志。为此，leader维护了所有follower的nextIndex变量，表示下一个需要发送到follower的日志索引，并且发送了上个日志索引prevLogIndex和上个日志所属任期prevLogTerm，供follower判断是否在prevLogIndex和leader保持一致，否则leader循环往上查找直到找到与follower一致的index。在上图中，leader和follower(f)的index为3时保持一致，那么(f)将删除其后的所有entries，leader会将index大于3后的entry都复制到(f)中。日志复制的请求如下图所示：

什么时候提交日志？

leader只有在entry被大多数机器复制成功才会提交entry索引，但是如果leader在提交日志前宕机，新的leader是不能立马知晓之前term的entry是否已经提交过。虽然entry已经被大多数机器复制了，但仍然可能被覆盖。raft的做法是从不计算副本数目进行之前term的日志提交，而是只有在当前term的时候才会通过计算副本数进行日志提交，由于Log Macthing机制，当一个log entry已提交，那么其index之前的所有entries也是已提交的。这样的做法不会改变entry所属的term，便于理解。

集群成员变更(Cluster membership changes)

之前所述的选主和日志复制流程都是在集群成员固定的情形下，但有时候需要上线或下线机器，可以通过暂停服务然后更改集群配置后再重启系统，这降低了系统的可用性。我们可以利用raft算法在不影响客户端请求的前提下让配置更新自动化。

为了保证安全性，必须保证任意任期都只有一个leader，然而任何一种直接从旧配置转换成新配置的方法都是不安全的。raft的做法是先转换成联合配置（旧配置+新配置），然后再转换成新配置。集群配置作为一个特殊的log entry追加到机器的日志中，日志复制采用raft两阶段提交，当机器复制完配置后，立马采用新配置进行决策而不管日志是否已经被提交。整个过程如下图所示：

• 第一阶段，提交Cold,new配置，一旦Cold,new配置已提交，则只有Cold,new配置中的机器可以被选为leader;
• 第二阶段，提交Cnew配置，整个集群转换为Cnew中的机器作决策。

这样就不存在时间点可以让Cold和Cnew同时独立作决策。除此之外，有以下3个问题需要考虑：

• 新机器没有存储任何日志，会消耗大量时间进行日志同步。为此，Raft新增一个阶段，新机器不作为投票机器，只从leader同步日志，等差不多时才开始做配置变更。

• leader不在新配置中。为此，原来的leader在提交（计算日志副本个数时不包含自己））了Cnew配置后，转成follower状态。

• 移除的机器可能会干扰新的集群，因为移除的机器在选举超时后会发起新一轮选举。为此，如果一台机器接收到RequestVote的时间和收到leader心跳的时间间隔不超过最小的electionTimeout，则会拒绝掉此次选举。

日志压缩(Log compaction)

随着时间的推移，集群中机器的日志会越来越多，占用大量磁盘空间，日志重放会非常耗时，最终影响整个系统的可用性。所以需要做日志压缩，快照（Snapshot）技术是最简单的解决方案。LSM和Log cleaning也可以用来做日志压缩，但是会带来额外的复杂性。raft采用快照技术做日志压缩的机制如下图所示：

集群中所有机器独立的进行快照过程，将所有已经committed的entries做一个snapshot，并包含状态机的当前状态，以及当前最新的index和term用来进行选住过程和日志复制过程中的一致性校验，还有当前的集群配置以支持集群成员变更操作。当完成了snapshot操作之后，可以删除之前的所有entries以及snapshot。

虽然每台机器是独立进行快照的，但是也会存在一些慢follower或者是新加入的机器需要leader将完整的快照发送过去。raft使用InstallSnapshot请求进行快照的复制，follower会在根据本地日志情况作出不同的操作：

• 本地包含所有快照中的日志时，删除快照之前的日志，保留快照之后的日志。

• 本地不包含快照中的日志时，删除本地所有日志，保存快照数据，重置状态机以及集群配置。

两个性能问题

什么时候进行快照？快照的频率会影响系统性能，太快影响带宽，太慢会有磁盘爆满风险以及增加日志重放时间。一个简单的策略是当日志达到一定阈值时开始进行快照。

如何解决写快照耗时太长影响正常请求？这个可以通过写时复制（Copy-on-write）技术来优化写快照。

客户端交互

客户端与集群交互时需要满足线性化（linearizable）语义（所有操作都是瞬时仅执行一次）。客户端只将请求发送给leader， 客户端与集群交互方式如下：

1. 客户端随机选择集群中的一台机器，如果是leader，则直接发送请求
2. 如果选择的机器不是leader，则机器会拒绝客户端请求并返回其最近接受心跳的leader地址给客户端
3. 如果leader宕机，客户端请求会超时，重复步骤1

幂等性如何保证？

由于raft需要满足线性化语义，意味着客户端的请求只能执行一次，由于网络问题，客户端可能会同一个请求发送多次，所以需要保证幂等性。解决方案是客户端为每次请求附加一个唯一连续id，机器的状态机维护每一个客户端最新的请求id及回复，如果发现已经成功执行过，则直接回复成功不用再次执行。

如何防止返回过期数据？

在leader换届时，客户端可能会连接到过时的leader，因而读到过期数据。要满足线性读则必须返回最新的数据。为此，Raft添加了两个额外操作保证：

• 由于leader完备性，leader总是包含所有已提交数据。正如之前说过，新的leader是不能立马知晓之前term的entry是否已经提交过。为了让leader知道哪些被提交了，需要在其term内commit一个entry，可以让leader在任期开始时发送一个什么都不做的no-op的entry。

• leader在执行只读请求时需要校验自己是否被罢免，自身的数据可能已经过期。通过让leader在回复客户端只读请求前和大多数的机器交换heartbeat消息来确定自己还是leader，否则直接拒绝客户端请求。

总结

Raft和Paxos本质上其实是一样的，先到先得原则、大多数原则、两阶段提交。不同之处在于Raft是基于leader的算法，将选主和一致性算法结合起来，使得算法更易于理解。另外raft中的日志是连续的，日志流向只从leader流向follower，强化了leader的地位，简化了一致性过程。有时间准备自己实现一下raft，毕竟实践出真知。

• 上一篇 Paxos如何直觉性推导？
• 下一篇 Netty设计思想之Reactor