声明

本文是对文献^[1]和文献^[2]的阅读笔记，非本人原创。本博客仅发表在博客园上，作者LightningStar，其他平台均为转载。

摘要

本文主要介绍了raft共识算法，值得强调的是共识（consensus）算法和一致性（consistency）算法是完全不同的两类算法，其所解决的问题是不同的。读者应当明确共识算法与一致性算法的区别。

Raft是一种用于管理复制日志的共识算法。它产生的结果相当于(multi-)Paxos，与Paxos一样高效，但结构不同;这使得Raft比Paxos更容易理解，也为构建实用系统提供了更好的基础。为了增强可理解性，Raft分离了共识的关键元素，如领导人选举、日志复制和安全，并强制执行更强的一致性，以减少必须考虑的状态数量。

Raft与其他共识算法类似，但是也具有一些特性：

• strong leader
  raft的使用了更强形式的leadership，例如，日志条目只从主服务器流向其他服务器。这简化了对复制日志的管理，并使Raft更易于理解。
• leader election
  Raft使用随机的始终选举leader。这只是在共识算法原有的心跳检测的基础上增加了少量的特殊机制，使得冲突解决变得更加简单快速。
• membership changes
  Raft通过一种新的joint consensus的方法来实现服务器集合的改变，其中两个不同配置下的majority在过渡阶段会发生重合。这能让集群在配置改变时也能正常运行。

复制状态机 replicated state machine

共识算法是在复制状态机的背景下提出来的。在这个方法中，一组服务器上的状态机对同一个状态计算产生多个完全相同的副本，这使得即使其中一些服务器崩溃了，这组服务器也还可以继续正常执行。复制状态机通常用于解决分布式系统中容错相关的一系列问题。复制状态机的典型例子包括chubby和zookeeper。

如上图所示，复制状态机通常使用replicated log实现。每个服务器都保存一个记录了状态机执行顺序和执行指令的日志。每个日志以相同的顺序包含相同的命令，因此每个状态机处理相同的命令序列。由于状态机是确定性的，所以每个状态机都计算相同的状态和相同的输出序列。

共识算法的任务是保持复制日志的一致性。服务器上的共识模块接收来自客户端的命令并将它们添加到日志中。它与其他服务器上的共识模块通信，以确保每个日志最终以相同的顺序包含相同的请求，即使一些服务器出现故障。一旦正确地复制了命令，每个服务器的状态机将按照日志顺序处理它们，并将输出返回给客户机。因此，服务器似乎形成了一个单一的、高度可靠的状态机。

一般共识算法具有以下几点特征：

• safety of non-Byzantine conditions（非拜占庭问题下的安全性）
  它们确保在所有非拜占庭条件下(包括网络延迟、分区和包丢失、复制和重新排序)的安全性(永远不会返回不正确的结果)。
• high available 高可靠性
  只要大多数服务器都是可操作的，并且可以相互通信，也可以与客户机通信，它们就是完全可用的。因此，一个典型的由5台服务器组成的集群可以容忍任意两个服务器的故障。服务器被假定通过停止而失败;它们稍后可能会从稳定存储上的状态恢复并重新加入集群。
• time-independent
  它们不依赖于时间来确保日志的一致性:错误的时钟和极端的消息延迟在最坏的情况下会导致可用性问题。
• majority is all
  在一般情况下，只要集群的大多数成员响应了一轮远程过程调用，命令就可以完成;少数速度较慢的服务器不需要影响整体系统性能。

Raft共识算法

Raft实现共识的方式是，首先选举一位杰出的领导人，然后赋予该领导人管理复制日志的完全责任。leader接受来自客户机的日志条目，在其他服务器上复制它们，并告诉服务器何时将日志条目应用到它们的状态机是安全的。使用leader可以简化复制日志的管理。例如，领导者可以决定在日志中放置新条目的位置，而不需要咨询其他服务器，数据以一种简单的方式从领导者流向其他服务器。leader可能会失败或与其他服务器断开连接，在这种情况下，会选出一个新的leader。

Raft将共识问题分解为三个相对独立的子问题：

• leader election 领导者选举
• log replication 日志复制
  一个leader必须接受来自客户端的日志条目并将日志赋值给集群中的其他服务器，并强制其他服务器的日志与leader相同
• safety 安全性
  如果任何服务器将特定的日志条目应用到其状态机，那么其他服务器就不能对相同的日志索引应用不同的命令

Raft basics

Raft集群包含多个服务器。在任何给定的时间，每个服务器都处于三种状态之一:领导者（leader）、追随者（follower）或候选人（candidate）。

follower是被动的：他们不发送任何请求，只是响应来自leader和candidate的请求。leader来处理所有来自客户端的请（如果一个客户端与follower进行通信，follower会将请求信息转发给leader）。candidate是用来选取新的领导人的。图-4 阐述了这些状态及它们之间的转换。

Raft将时间分为不同任期（term），如图5所示。任期（term）用连续的整数编号。每一届任期都以leader选举开始，一名或多名候选人竞选领导人。如果一个候选人赢得了选举，那么他将在余下的任期内担任领导人。在某些情况下，投票分裂会导致选举失败，那么这一届任期就没有leader，新的任期会随机开始，Raft保证一个任期至多有一个leader。

Raft服务器使用远程过程调用进行通信，基本共识算法只需要两种类型的RPC。RequestVote RPC由候选人在选举期间发起；而AppendEntries RPC由leader发起，以复制日志条目并提供一种心跳形式。第三种RPC是在服务器之间传输快照，如果服务器没有及时收到响应，则重试RPC。

leader选举

服务器刚启动时会进入follower状态，如果该服务器能一直收到来自leader或者candidate的RPC请求，那么将会一直保持follower状态。leader会一直发送周期性的心跳，保证自己的leader地位。如果follower在一定时间（election timeout）之内一直收不到心跳，那么就认为当前没有合法的leader，并开始进行选举。

开始选举时，follower首先递增自身的任期并将状态切换为candidate。然后标识voteFor为自己，并发送Request Vote RPCs到集群中所有其它的服务器。candidate会一直保持自身状态，直到一下三种情况任何一种发生：赢得选举，成为leader；其它candidate赢得选举；选举超时，未能成功选出leader。

如果一个候选人在同一任期内从整个集群中的大多数服务器获得选票，那么他就赢得了选举。每个服务器将在给定的任期内以先到先得的方式投票给最多一个候选人。多数决定原则确保最多只有一位候选人能在特定任期内赢得选举。一旦候选人赢得选举，他就成为领袖。然后它向所有其他服务器发送心跳信息，以建立其权威并阻止新的选举。

candidate选举期间，会不断收到其它候选人发送 Request Vote RPCs，如果接收到的请求中的任期号大于等于candidate的当前任期号，则candidate认可当前投票，并将自身转换为follower状态。如果接收到的请求中的任期号小于candidate当前的任期号，则candidate拒绝此次请求，并继续保持candidate状态。

第三种可能的结果，即选举失败：同一时间，过多follower成为candidate，启动选举时，投票被过分的分割，将没有candidate能够获得“大多数”投票。当这一情况发生，所有的选举都将进入选举超时状态，候选人又会重新发起新一轮选举。然而，如果不采取额外的措施，投票分裂（split votes）将会无限的重复发生。

Raft使用随机的选举超时时间来确保split votes很少发生，或者即使发生了，也能很快解决。为了在一开始就避免split votes 发生，Raft将选举超时设定为150~300ms之间的一个随机值。这就使得服务器能够很好的分散开来，大多数情况下，同一时间，只会有一个服务器发生选举超时。当一个服务器赢得选举，它能够在其它服务器选举超时之前向他们发送心跳信息。每一个candidate在选举开始时，重置一个随机的选举超时时间，然后等待超时时间到来后，重新启动下一轮选举。这就大大减少了下一次选举时split votes现象的发生。

日志复制 log replication

一旦选出了领导者，它就开始服务客户的请求。每个客户机请求都包含要由复制的状态机执行的命令。leader将命令作为新条目附加到其日志中，然后并行地向每个其他服务器发出AppendEntries rpc以复制该条目。当条目被安全地复制(如下所述)时，leader将该条目应用到它的状态机，并将执行结果返回给客户机。如果跟随者崩溃或运行缓慢，或者网络数据包丢失，leader将无限期地重试AppendEntries rpc(即使在它响应客户机之后)，直到所有跟随者最终存储所有日志条目。

日志的组织如下图6所示。当leader接收到条目时，每个日志条目存储一个状态机命令和term（任期）号。日志条目中的term编号用于检测日志之间的不一致性，

leader决定什么时候让状态机执行日志条目是安全的，而这一日志条目称之为commited。Raft保障所有commited都是持久的，并且最终都会被集群中所有的状态机所执行。当一个日志条目被集群的众大多数服务器成功复制后，它就会被leader commited，这一过程同时也会将此条目之前的所有日志条目一并commited，包括之前任期leader创建的条目。leader 会一直跟踪最新commited的日志条目索引，并将它包含在随后的Append Entries RPCs（包括心跳）中，以便其它服务器识别，并应用到自身状态机。

Raft确保日志的以下特性：

• 如果两个日志中的日志条目的任期号和索引都相同，则他们存储的command也相同；
• 如果两个日志中的日志条目的任期号和索引都相同，则之前的所有条目也都相同。

第一个特性说明，leader在一个日志索引位置至多只会创建一个日志条目，并且日志中的条目位置都是固定的。第二个特性是由Append Entries执行一个简单的一致性检查来保障的。在发送Append Entries RPCs时，leader会将要发送的最新条目之前的条目索引（preLogIndex）及任期号（preLogTerm）包含进去，如果follower在其日志中找不到匹配preLogIndex及preLogTerm的日志条目，则拒绝接受发送的新的日志条目。一致性检查是一个递归过程：初始时日志为空，这满足Log Matching属性，当日志扩增时，一致性检查都会确保符合Log Matching属性。因此，leader能够通过Append Entries RPC返回的成功结果，判定所有的follower的当前及后续日志都会和自己的日志保持一致。

如下图7所示，当leader宕机时，会引发日志的不一致。Raft协议中，leader通过强制follower复制自己的日志来处理日志的不一致问题。follower中不一致的条目将会被leader中的条目覆盖。为了使follower的日志和自己保持一致，leader首先需要找到和follower日志中能够保持一致的最新的日志条目索引，然后，删除follower中此索引之后的所有条目并发送leader中此条目之后的所有条目到follower。

safety

前文所述的机制不足以保证每个状态机都以完全相同的顺序执行完全相同的命令。例如：当一个follower不可达时，其日志条目将与leader不一致，这样当该follower被选举为leader时，将用新的条目覆盖原leader的条目。此时不同的状态机将会执行不同的命令序列。

选举限制

Raft控制选举过程，只有当candidate的日志包含所有已提交的日志条目时，它才能够被选举为leader。参与选举期间，candidate需要与大多数服务器进行通信，同时，我们知道，集群大多数原则，每一个日志条目必须存在于大多数的服务器中至少一个服务器上。这样，当一个candidate满足自己的日志至少比大多数服务器中任何一个服务器的日志新时，它就存储了集群中所有已提交的日志条目。Request Vote RPCs实现了这种限制：请求中包含candidate的日志信息，如果投票服务器的日志条目比candidate的日志新，则会拒绝此次投票。

Raft通过比较两个服务器上日志的最后一个日志条目的任期和索引来决定谁的日志时最新的。任期不同，则任期大的日志新。任期相同，则索引大的日志新。

leader知道任期内的日志条目一旦被大多数服务器复制存储，就被提交了。如果一个leader在提交一个日志条目前宕机了，将来的leader会继续尝试完成这一日志条目的复制，提交。然而，一个leader并不能立马识别一个被大多数服务器存储的日志条目，是否已被之前的leader提交了。

为了消除这种问题，Raft从来不会通过计算备份数来决定是否提交上一个任期的日志条目。只有leader当期的日志条目需要通过计算备份数来决定提交。一旦当前任期内的一个日志条目以这种方式被提交了，那么根据 Log Matching Property 限制，所有之前日志条目也就间接的被提交了。当然也存在某些情景，leader能够立即识别是否一个旧的日志条目被提交了（日志条目被所有的服务器复制存储了），但是Raft为了简洁，选择了使用更加保守的方法。Raft之所以会有这种问题是因为leader在复制之前leader日志条目时任然保留着原始的任期号。Raft的这种方式，使得其能够更好的对相关日志条目进行推断。另外，Raft复制的之前的日志条目也相对较少。

follower和candidate宕机

如果follower或者candidate崩溃，那么以后发送给它的RequestVote PRC和AppendEntries RPC都将失败。Raft通过无限期的重新尝试来处理这些失败;如果崩溃的服务器重新启动，则RPC将成功完成。如果服务器在完成RPC之后但在响应之前崩溃，那么它将在重启后再次收到相同的RPC。

Timing和availability

我们对Raft的要求之一是安全不能依赖于时间:系统不能仅仅因为某个事件比预期发生得更快或更慢而产生错误的结果。然而，可用性(系统及时响应客户端的能力)必然依赖于时间。Raft的领导人选举是时机最关键的方面。Raft将能够选出并保持一个稳定的领导者，只要系统满足以下时间要求:

broadcastTime代表一个服务器并行的向所有的其它服务器发送RPCs并收到回复的平均时间；electionTimeout代表选举超时时间；MTBF代表单个服务器的故障发生间隔。

broadcastTime应该比electricTimeout小一个数量级，这样leader就能可能的发送心跳信息到follower以阻止新的领导选举。通过随机的 electionTimeout 使用，使得split votes更加不可能出现。 electionTimeout应该比MTBF小几个数量级，这样系统就能够正常运行。当leader宕机时，系统会在 electionTimeout 内变的不可用。我们希望这种情景出现的尽量少.

集群成员改变

到目前为止，我们都假定集群的配置（参与一致性算法的服务器）是固定的。但是，在实际应用中，配置时常也需要做相应的变动。

为了保障配置变更机制的安全，在配置转换期间，不能存在同一任期内选举出现两个leader的现象。不幸的是，没有任何方法能够使得集群能够安全的实现配置转换。自动的转换全部的服务器是不可能的，所有集群在转换期间极有可能出现裂脑现象。如下图10所示。

为了确保安全，配置变更必须采用两阶段法。有很多种方法来实现这种算法。Raft中，集群首先切换到过渡配置状态，我们称之为 joint consensus ，一旦 joint consensus 被提交，系统切换到新的配置状态。联合一致性状态既包括旧的配置，也包括新的配置：

• 日志条目在集群中被复制到两种配置下所有的服务器。
• 新旧配置中的服务器都有可能选举成为leader
• 关于选举和日志条目的提交的协定同时需要新旧配置中的大多数服务器原则要求。

joint consensus允许单个服务器在不影响安全性的基础上，在不同的特定时刻进行不同配置的转换。此外， joint consensus允许集群在配置转换期间继续处理客户端的请求。

集群配置是通过特殊的日志条目通过日志复制进行存储和传输通讯的，下图11展示了配置的转换过程。当leader收到配置从 \(C_{old}\) 到 \(C_{new}\)变更的的请求时，它首先将配置作为日志条目存储为 \(C_{old,new}\) 并复制到其它服务器，一旦某个服务器将收到的 \(C_{old,new}\) 配置日志条目添加到自身的日志，那么之后其所有的决策都将以此配置 \(C_{old,new}\) 为依据（服务器总是以日志中最新的配置为依据进行决策，无论配置条目是否已提交）。这就意味着，leader将使用 \(C_{old,new}\) 配置，来决定配置条目 \(C_{old,new}\) 什么时候提交。当leader宕机时，新的leader将在旧配置 \(C_{old}\)或者联合配置 \(C_{old,new}\) 的机器中选举出来。这取决于获得选举的candidate是否已经收到联合配置 \(C_{old,new}\) 。任何情况下，具有新配置 \(C_{new}\) 的服务器在这段时间内都不能做出片面的决定。

一旦 \(C_{old,new}\)被提交后，具有\(C_{old}\)或者\(C_{new}\)的服务器将不能再没有其它服务器允许的情况下做出任何决策， Leader Completeness Property确保了只有具有\(C_{old,new}\)的服务器才能当选为leader。此时，leader将能够安全的创建\(C_{new}\)的配置条目并将其复制到集群其它服务器。同样，当复制的服务器收到配置条目后就开始使用它。当新的配置被提交后，拥有旧配置的服务器将可以被关闭。

Log compaction

Raft日志会伴随着系统的日常运行持续增长。快照是压缩的最简单的方式，通过快照将某一时刻系统的当前状态写入快照文件，保存到磁盘，然后将这一时刻之前的所有日志丢弃。

图12展示了快照的基本思想。各个服务器独立的对已提交的日志条目进行日志快照。主要的工作是由状态机将它当前的状态写入快照文件来完成。Raft也保留了一些元数据在快照中，例如，last included index代表状态机最后应用的日志条目索引。last included term则是指这一条目的任期。因为日志条目需要包含preLogIndex和preLogTerm这两个属性以应对AppendEntries的一致性检查。为了支持集群配置变更，快照文件也在last included index之前包含了最新的配置条目。一旦某个服务器完成快照写入，他就会将last include index之前的所有日志条目都删除掉。
虽然，正常情况下，各个服务器各自完成各自的快照。但是，偶尔也需要leader向落后的follower发送自身的快照。这一情况通常发生在leader丢弃掉了需要发送到follower的日志条目的时候。当然，这种情况很少发生。和leader保持同步的follower拥有leader的所有日志，但是，落后比较大的follower或者刚加入集群的服务器却并非如此。处理此类follower的机制就是leader发送日志快照来进行同步。

参考文献