易于理解的一致性算法研究（Raft）论文翻译总结

2016-11-24

× 文章目录

1. In Search of an Understandable Consensus Algorithm

In Search of an Understandable Consensus Algorithm

Diego Ongaro and John Ousterhout
Stanford University

1.简介

在设计Raft时，我们采用一些特定的技术来提高其理解性，包括：分解（decomposition）（Raft将领导人选举、日志复制、安全性分离），状态空间减少（state space reduction）（相较于Paxos，Raft减少了非确定性的程度和服务器能彼此不一致的方式）。

Raft在很多方面都和现存的一致性算法相似，但它有几个新奇的特征：
- 强领导者（Strong leader）：Raft使用比其他一致性算法更强的领导形式。例如，日志条目只从领导流向其他服务器。这简化了复制日志的管理，使得Raft更容易理解。
- 领导者选举（Leader election）：Raft使用随机化的计时器选出领导人。这只需添加少量机制到（任何一致性算法早已需要的）心跳（heartbeats）中，却能简单且快速地解决冲突。
- 成员变更(Membership changes)：Raft改变集群中的服务器集合的机制使用新的联合一致性方法，其中两个不同配置（configurations）的大部分在转换期间重叠。这允许集群在配置更改（configuration changes）期间继续正常运行。
Raft算法更简洁且易于理解；它描述的足够完整来满足实际系统的需要；它有几个开源实现，并被几家公司使用；它的安全性已正式规定和验证；它的效率与其他算法相当。

2.复制状态机（Replicated state machines）

一致性算法通常出现在复制状态机的上下文中。复制状态机用于解决分布式系统中的各种容错问题。例如，具有单个集群领导者的大规模系统，例如GFS，HDFS和RAMCloud，通常使用单独的复制状态机来管理领导者选举和存储在领导者崩溃下必须保持的配置信息。复制状态机的示例包括Chubby和ZooKeeper。
复制状态机使用复制日志实现，如图1所示。每个服务器存储包含一系列命令的日志，其状态机按顺序执行。每个日志按相同的顺序包含相同的命令，因此每个状态机处理相同的命令序列。状态机是确定性的，因此每个状态机计算相同的状态和相同的输出序列。
保持复制日志的一致性是一致性算法的工作。 服务器上的一致性模块接收来自客户端的命令，并将它们添加到日志中，它与其他服务器上的一致性模块通信，以确保每个日志最终以相同的顺序包含相同的请求，即使一些服务器失败。一旦命令被正确复制，每个服务器的状态机按日志顺序处理它们，并将输出返回给客户端。作为结果，整个服务器组看起来是一个高度可靠的状态机。
实际系统的一致性算法通常具有以下属性：
- 它们确保在所有non-Byzantine条件下的安全性（不返回不正确的结果），包括网络延迟，分区和数据包丢失，复制和重新排序。
- 它们是完全功能的（可用的），只要任何大多数服务器是可操作的并且可以与彼此以及客户端通信。因此，五个服务器的典型集群可以容忍任何两个服务器的故障。假设服务器通过停止导致失败，它们可以稍后在稳定存储上从状态恢复并重新加入群集。
- 它们不依赖于时序来确保日志的一致性：但在最坏的情况下，错误的时钟和极端消息延迟可能导致可用性问题。
- 在通常情况下，只要集群的大部分已经响应了单轮远程过程调用，命令就可以完成；少数慢服务器不影响整体系统性能。

3.Paxos有什么问题

Paxos的第一个缺点是特别难以理解
Paxos的第二个问题是它不能为构建实际的实现提供良好的基础。

4.可理解性设计

略

5.Raft一致性算法

Raft通过首先选举一位领导者，然后让领导者完全负责管理复制日志来实现一致性。领导者从客户端接受日志条目，复制日志条目到其他服务器，并告诉服务器何时安全地将日志条目应用到其状态机。
拥有领导者可简化复制日志的管理。例如，领导者可以决定将新条目放在日志中的哪个位置，而无需咨询其他服务器，并且数据以简单的方式从领导者流向其他服务器。领导者可能失败或变得与其他服务器断开连接，在这种情况下需要选择新的领导者。
领导者方法，Raft将一致性问题分解为三个相对独立的子问题，这些问题将在下面的小节中讨论：
- 领导者选举（Leader election）：一个新的领导者必须在已存在的领导者失败后被选择。
- 日志复制（Log replication）：领导者必须接受来自客户端的日志条目，并在集群中复制它们，来迫使其他日志同意自己的日志条目。
- 安全（Safety）：Raft的关键安全属性是图3中的状态机安全属性：如果任何服务器已经将特定日志条目应用于其状态机，其他服务器便不能对相同的日志索引应用不同的命令。

5.1 Raft basics

Raft集群包含多个服务器，在任何给定时间，每个服务器处于三种状态之一：领导者(leader)，追随者(follower)或 候选者(candidate)。在正常操作中，只有一个领导者，而其他服务器都是追随者。
- 追随者是被动的：他们不会自己发出请求，而只是响应领导者和候选人的请求。
- 领导者处理所有客户端请求（如果客户端联系追随者，则追随者将其重定向到领导者）。
- 候选者用于选择一个新的领导者。
Raft将时间分为任意长度的terms，terms用连续整数编号。
1. 每个term从选举(election)开始，一个或多个候选人试图成为领导者。
2. 如果候选人赢得选举，那么它在该term的剩余时间担任领导者。
3. 在某些情况下，选举将导致分裂投票。在这种情况下，该term将以没有领导者结束; 在选举结束后，新的term（伴随新的选举）将会开始。
4. Raft确保在给定term中最多有一个领导者。
不同的服务器可能在不同时间观察term的转换，并且在一些情况下，服务器可能不观察选举或甚至不观察整个term。terms在Raft中作为逻辑时钟(logical clock)，服务器可以用它们来检测过时的信息，例如陈旧的领导者。
- 每个服务器存储当前term编号，其随时间单调增加。
- 当服务器通信时，如果一个服务器的当前term小于另一个服务器的当前term，则它将其当前term更新为较大的那个。
- 如果候选者或领导者发现其term已过期，则会立即返回到追随者状态。
- 如果服务器接收到具有陈旧term编号的请求，则它会拒绝该请求。
Raft服务器使用远程过程调用（remote procedure calls）（RPCs）进行通信，基本一致性算法仅需要两种类型的RPC。
- RequestVote RPCs由候选人在选举期间启动（第5.2节），
- AppendEntries RPCs由领导者启动以复制日志条目并提供心跳（heartbeat）形式（第5.3节）。
- 第7节添加了第三个RPC，用于在服务器之间传输快照。
- 如果RPC没有及时收到响应，服务器将重试RPC，并且它们并行的发出RPC以获得最佳性能。

5.2 Leader election

Raft使用心跳机制(heartbeat mechanism)来触发领导者选举。
- 所有服务器都作为追随者开始，并启动选举定时器。
- 只要服务器从领导者或候选者那里接收到有效的RPC，服务器就保持在追随者状态。
- 领导者定期向所有追随者发送心跳（AppendEntries RPC，不携带日志条目）以保持其权限，重置选举定时器。
- 如果追随者的选举定时器超时而没有接收到通信，则其假定没有领导者并发起选举。
为了开始选举，追随者递增其当前term并转换到候选者状态。然后它投票自己并且向集群中的其他服务器并行地发出RequestVote RPC。候选人将持续处于这种状态，直到发生以下三种情况之一：（a）赢得选举，（b）另一个服务器建立自己作为领导者，（c）一段时间没有胜利者。
- 如果候选者从同一term的完整集群中的大多数服务器接收到投票，则其选举胜出。
  1. 每个服务器将按照 先到先得 的原则在给定term内投票最多一个候选人。
  2. 多数规则确保至多一个候选人可以赢得特定term的选举。
  3. 一旦候选人赢得选举，它就成为领导者。然后，它向所有其他服务器发送心跳消息以建立其权限并阻止新的选举。
- 在等待投票时，候选人可以从声称是领导者的另一服务器接收AppendEntries RPC。
  1. 如果领导者的term（包含在其RPC中）至少与候选者的当前term一样大，则候选者识别出领导者是合法的并且返回到追随者状态。
  2. 如果RPC中的term小于候选者的当前term，则候选者拒绝RPC并且继续处于候选者状态。
- 第三个可能的结果是候选人 既不赢得也不失去选举 ：如果许多追随者同时成为候选人，则可以分裂选票，导致没有候选人获得多数票。当这种情况发生时，每个候选人将超时并通过增加其term和发起另一轮RequestVote RPC开始新的选举。然而，没有额外的措施，分割票可以无限期重复。
Raft使用 随机选择的 选举超时机制（election timeouts）以确保分割投票是罕见的：每个候选者在选举开始时重置其选举超时（随机值），并且在开始下一选举之前等待该超时结束; 这减少了在新选举中再次分裂投票的可能性。

5.3 Log replication

一旦领导者被选举出来，它便开始为客户端请求所服务。
1. 每个客户端向领导者发送一个要由复制状态机执行的命令。
2. 领导者将命令作为新条目附加到其日志中，然后并行地向每个其他服务器发出AppendEntries RPC以复制该条目。
3. 当条目已被安全复制（如下所述）时，领导者将该条目应用于其状态机，并将该执行的结果返回给客户端。
4. 如果追随者崩溃或运行缓慢，或者网络数据包丢失，领导者将无限期地重试AppendEntries RPC（即使在响应客户端之后），直到所有追随者最终存储所有日志条目。
日志组织如下图。每个日志条目存储状态机命令，以及领导者接收条目时的term编号，还具有标识其在日志中的位置的整数索引。日志条目中的term编号用于检测日志之间的不一致。
领导者决定何时安全地向状态机应用(apply)日志条目；这样的条目称为 已提交(committed)。 Raft确保提交的条目是持久的，并且最终将由所有可用的状态机执行。
- 一旦创建该条目的领导者复制了该条目到大多数服务器（例如，上图中的条目7），则提交该日志条目以及领导者的日志中的所有先前条目，包括由先前领导创建的条目。
- 领导者在AppendEntries RPC（包括心跳）中包括要提交的最高索引，以便其他服务器最终找到。
- 一旦追随者获知日志条目被提交，它将该条目应用于其本地状态机（以日志顺序）。
Raft维护以下属性，它们一起构成Figure3中的日志匹配属性(Log Matching Property)：
- 如果不同日志中的两个条目具有相同的索引和term，则 它们存储相同的命令。原因:领导者在给定term中创建具有给定日志索引的至多一个条目，并且日志条目从不改变它们在日志中的位置。
- 如果不同日志中的两个条目具有相同的索引和term，则 所有先前条目中的日志相同。原因：当发送AppendEntries RPC时，领导者在其日志中包括紧接在新条目之前的条目的索引和term。如果追随者在其日志中没有找到具有相同索引和项的条目，则拒绝新条目。一致性检查用作归纳步骤：日志的初始空状态满足日志匹配属性，并且每当日志扩展时，一致性检查保留日志匹配属性。因此，每当AppendEntries成功返回时，领导者知道追随者的日志与通过新条目的自己的日志相同。
领导崩溃可能会使日志不一致（旧领导可能没有完全复制其日志中的所有条目），进而造成一系列领导和追随者崩溃。 Figure7示出了追随者的日志可能与新领导者的日志不同的方式。追随者可能缺少存在于领导者上的条目，具有不存在于领导者上的额外条目。日志中缺失和无关的条目可能跨多个term。

在Raft中，领导者通过 强制追随者复制自己的日志 来处理不一致。这意味着，追随者日志中的冲突条目将被来自领导者日志的条目覆盖。
- 领导者为每个追随者维护一个nextIndex，这是领导者将发送给该追随者的下一个日志条目的索引。
- 当领导者首次上台时，它会将所有nextIndex值初始化为其日志中的最后一个索引的下一个（Figure7中的11）。
- 如果追随者的日志与领导者的日志不一致，AppendEntries一致性检查将在下一个AppendEntries RPC中失败。
- 追随者拒绝后，领导者递减nextIndex并重试AppendEntries RPC。
- 最终nextIndex将达到领导者和追随者日志匹配的点，AppendEntries将成功，它删除追随者日志中的所有冲突条目，并附加领导者日志中的条目（如果有的话）。
- 一旦AppendEntries成功，追随者的日志与领导者的日志是一致的。
优化协议以 减少被拒绝的AppendEntries RPC的数量 。例如，当拒绝AppendEntries请求时，追随者可以包括冲突条目的term和它为该term存储的第一个索引。利用这个信息，领导者可以递减nextIndex以绕过该term中的所有冲突条目；每个具有冲突条目的term需要一个AppendEntries RPC，而不是每个条目一个RPC。

5.4 Safety

5.4.1 Election restriction

在任何基于领导者的一致性算法中，领导者最终必须存储所有提交的日志条目。Raft使用一种更简单的方法，它保证来自先前terms的所有已提交条目（从领导者选举的时刻起）已经存在于每个新领导者中。这意味着 日志条目只从领导者到跟随者，领导者从不覆盖其日志中的现有条目 。
只有当候选人的日志包含所有已提交的条目才能赢得选举。候选人必须联系群集的大多数(majority)以便被选举，这意味着每个已提交的条目必须存在于至少一个服务器中。如果候选者的日志至少与majority中的任何一个服务器中的日志一样是最新的（其中“最新”在下面被精确定义），则它将包含所有已提交的条目。RequestVote RPC包括关于候选人的日志的信息，如果选举人的日志比候选人的日志更新，则选举人拒绝投票。
Raft通过比较日志中的最后条目的索引和term来确定两个日志中的哪一个是最新的。
- 如果日志具有包含不同term的最后条目，则具有较后term的日志更新。
- 如果日志以相同的term结束，则日志较长的日志是最新的。

5.4.2 Committing entries from previous terms

领导者不能立即判断先前term的条目被提交（一旦该条目被存储到大多数服务器中）。Figure8展示了一种情况，旧日志条目存储在大多数服务器上，但仍然可以被未来的领导者覆盖。
为了消除类似Figure8中的问题，Raft从不通过计数副本提交先前term的日志条目。计数副本只用来提交来自领导者当前term的日志条目；一旦来自当前term的条目已经以这种方式提交，则由于日志匹配属性(Log Matching Property)，所有先前的条目都间接地提交了。
为了使得更容易推理日志条目：当领导者复制来自先前term的条目时，日志条目保留其原始term编号。

5.4.3 Safety argument（不懂、、、）

给定领导者完整性属性（Leader Completeness Property），我们可以证明状态机安全属性(State Machine Safety Property)：如果服务器已经在其状态机上给定索引处应用了日志条目，则对于相同的索引没有其他服务器会应用不同的日志条目。当服务器将日志条目应用于其状态机时，其日志必须与领导者通过该条目的日志相同，并且必须提交该条目。现在考虑任何服务器应用给定日志索引的最低term; 日志完整性属性保证所有更高级term的领导者将存储相同的日志条目，因此在后面的term应用该索引的服务器将应用相同的值。因此，状态机安全属性得证。
Raft要求服务器以日志索引顺序应用条目。结合状态机安全属性，这意味着所有服务器将以相同的顺序应用完全相同的一组日志条目到它们的状态机。

5.5 Follower and candidate crashes

如果一个追随者或候选者崩溃(crash)，那么未来发送给它的RequestVote和AppendEntries RPC将失败。Raft通过 无限期重试 来处理这些故障；如果崩溃的服务器重新启动，则RPC将成功完成。
如果服务器在完成RPC之后但在响应之前崩溃，则它将在重新启动后再次接收相同的RPC。
Raft的RPC是幂等的（幂等是指可以使用相同参数重复执行，并能获得相同结果的函数。这些函数不会影响系统状态，也不用担心重复执行会对系统造成改变。）。例如，如果跟随者接收到包括已经在其日志中存在的日志条目的AppendEntries请求，则它忽略新请求中的那些条目。

5.6 Timing and availability

只要系统满足以下时间要求，Raft将能够选择和维持稳定的领导者：

broadcastTime ≪ electionTimeout ≪ MTBF
- broadcastTime是服务器并行地向集群中的每个服务器发送RPC并接收它们响应所花费的平均时间。
- electionTimeout是第5.2节中描述的选举超时。
- MTBF是单个服务器的平均故障间隔时间。
broadcastTime应该比electionTimeout少一个数量级，以便领导者可以可靠地发送使得追随者不能开始选举所需的心跳消息；electionTimeout应该比MTBF少几个数量级，使系统稳定的运行。

6.集群成员变更

Raft算法将采用自动化更改集群配置。
失败的尝试：由于不可能一次性原子的切换所有服务器，集群在转换期间可能会拆分成两个独立的majorities。
为了确保安全，配置更改必须使用两阶段方法。在raft中，集群首先切换到过渡配置，我们称为联合一致性(joint consensus)；一旦提交了联合一致性，系统就转换到新的配置。联合一致性结合了旧的和新的配置：
- 日志条目将复制到两个配置中的所有服务器。
- 两个配置中的任一服务器都可能成为领导者。
- （选举和条目提交的）协议需要在旧的和新的配置都分出majority。
当领导者接收到将配置从$C{old}$更改为$C{new}$的请求时，它将联合一致性的配置（图中的$C{old,new}$）存储为日志条目，并使用先前描述的机制来复制该条目。一旦给定的服务器将新的配置条目添加到其日志中，所有后续的决策它都将使用该配置（无论该条目是否已提交）。这意味着领导者将使用$C{old,new}$的规则来确定何时提交$C{old,new}$的日志条目。一旦$C{old,new}$提交了，领导完整性属性（Leader Completeness Property）确保只有具有$C{old,new}$日志条目的服务器可以被选为领导者。最后再使用相同策略提交$C{new}$。如图11所示，$C{old},C{new}$都不可以做出单方面的决定；这保证了安全性。
重新配置还有三个问题要解决：
- 新服务器可能最初不存储任何日志条目。如果在此状态下将它们添加到集群，则可能需要相当长的时间才能赶上，在此期间可能无法提交新的日志条目。Raft在配置更改之前引入了一个附加阶段，其中新服务器作为无投票资格成员加入群集（领导者将日志条目复制到它们，但不将它们考虑为majority）。
- 集群领导者可能不是新配置的成员。在这种情况下，领导者一旦提交了$C{new}$日志条目，就会降级（返回追随者状态）。这意味着将有一段时间（当它正在提交$C{new}$时）,领导者管理着集群但不包括它自己，它复制日志条目，但不把自己算在majority。领导者转换发生在$C_{new}$被提交时，因为这是新配置可以独立操作的第一点。
- 删除的服务器（不在$C_{new}$中）可能会中断群集。这些服务器将不会收到心跳，超时并开始新的选举。然后，他们将发送具有新的term编号的RequestVote RPC，这将导致当前领导恢复到从状态。为了防止此问题，如果服务器在当前领导者的最小选举超时(election timeout)时间内接收到RequestVote RPC，则它认为当前领导存在,不更新它的term或投票。

7.日志压缩

随着日志增长更长，它占用更多的空间，需要更多的时间来重放，这最终将导致可用性问题。
快照(Snapshot)是最简单的压缩方法。在快照中，整个当前系统状态将写入稳定存储上的快照，然后丢弃该点的整个日志。
图12显示了Raft中快照的基本概念。每个服务器独立地拍摄快照，仅覆盖其日志中的已提交条目。大多数工作包括状态机将其当前状态写入快照。
- Raft在快照中还包含少量元数据：最后包含的索引 是快照替换的最后一个条目（状态机应用的最后一个条目）的索引，最后包含的term 是此条目的term。保留这些值以支持对快照后的第一个日志条目的AppendEntries一致性检查，因为该条目需要以前的日志索引和项。
- 要启用群集成员资格更改（第6节），快照还包括日志中最后包含的索引的最新配置。
- 一旦服务器完成写入快照，它可以删除除最后包括的索引以外的所有日志条目，以及任何先前的快照。

领导者必须偶尔向一个异常缓慢的追随者或一个新加入集群的服务器发送快照，使用一个名为InstallSnapshot的新RPC。
两个影响快照性能的问题。
- 服务器必须决定何时创建快照。 一个简单的策略是当日志达到固定大小（以字节为单位）时拍摄快照。
- 写快照可能需要大量的时间，我们不希望这会延迟正常操作。 解决方案是使用 写时复制技术(copy-on-write techniques) ，以便可以接受新的更新，而不影响正在写入的快照。

客户端交互

本节描述客户端如何与Raft交互，包括客户端如何找到集群领导者，以及Raft如何支持线性化语义(linearizable semantics)。
- Raft的客户端将他们所有的请求发送给领导者。
- 当客户端首次启动时，它连接到随机选择的服务器。如果客户端的首选不是领导者，那么服务器将拒绝客户端的请求并提供它听到的最近的关于领导者的信息（AppendEntries请求包括领导者的网络地址）。
- 如果领导崩溃，客户端请求将超时，客户端再次随机选择服务器。
- 如果领导者在提交日志条目之后但在响应客户端之前崩溃，则客户端将使用新的领导者重试该命令，使得其被执行第二次，这违背了线性化语义。解决方案 是客户端为每个命令分配唯一的序列号，状态机跟踪每个客户端处理的最新序列号以及相关联的响应，如果它接收到其序列号已经被执行的命令，则它立即响应而不重新执行该请求。