一致性算法

Paxos

Raft几位研究员花了近一年的时间搞懂 Paxos。所以,不要死磕 Paxos。

Raft

Raft is a consensus algorithm for managing a replicated log.

raft是一个一致性算法(consensus algorithm),用于管理日志复制。一致性算法允许一个计算机集群中死掉一部分成员。

Raft

In Search of an Understandable Consensus Algorithm

1. 引言

Our approach was unusual in that our primary goal was understandability

首要目标就是可理解性

主要是两件事:

  • 分解(Raft分解了leader选举,日志复制、安全性、成员变更)
  • decomposition (Raft separates leader election, log replication, and safety)
  • 简化状态空间(Raft相对于Paxos减少了不确定性和服务器相互矛盾的方式,使用随机化简化了Raft领袖选举算法。)
  • state space reduction (relative to Paxos, Raft reduces the degree of nondeterminism and the ways servers can be inconsistent with each other. We used randomization to simplify the Raft leader election algorithm.)

2. 复制状态机

Consensus algorithms typically arise in the context of replicated state machines [37]. In this approach, state machines on a collection of servers compute identical copies of the same state and can continue operating even if some of the servers are down. Replicated state machines are used to solve a variety of fault tolerance problems in distributed systems.

一致性算法通常发生在状态机的上下文。这种策略下,集群中的状态机计算相同的状态副本,即使有几台挂了,整个集群依然能够正常运行。状态机的复制用于解决一系列分布式系统的故障容错问题。

If two identical, deterministic processes begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.

状态机:相同的初始状态 + 相同的有序输入 = 相同的结束状态

Replicated state machines are typically implemented using a replicated log

复制状态机通常使用复制日志来实现

img

Keeping the replicated log consistent is the job of the consensus algorithm.

一致性算法的主要工作是保证日志的一致性。

一致性算法通常具有以下属性:

  • 他们在非拜占庭条件包括网络延迟,分区,数据丢包,复制,重新排序下保证安全性(绝不返回错误的结果)
  • 他们只要大部分服务器是可用的并和彼此通信以及和客户端通信就是实用的(可用的)。
  • 他们不以时间为日志一致性的标准:时钟故障和极度的消息延迟,最坏的情况下可能导致可用性问题。
  • 通常情况下,一个命令可以在集群中的多数响应了单轮远程调用结束,少数慢的服务器不影响系统整体的性能。

一般地,把出现故障( crash 或 fail-stop,即不响应)但不会伪造信息的情况称为“非拜占庭错误”( non-byzantine fault)或“故障错误”( Crash Fault);伪造信息恶意响应的情况称为“拜占庭错误”( Byzantine Fault)

  • 非拜占庭错误的算法:paxos、raft

  • 拜占庭错误算法:pbft、pow

3. What’s wrong with Paxos?

Paxos已经成为共识,大多数一致性实现以它为起点。但它有两个明显缺点:

  • Paxos非常难以理解
  • Paxos没有为构建实际实现提供良好的基础

4. 设计可理解性

  • 提供完整、实用的基础,减少程序员的工作量
  • 在任何条件下安全,在典型操作条件下可用
  • 可理解性 、可扩展性

5. Raft一致性算法

Raft 通过选举 Leader,然后完全授权Leader管理复制日志。Leader 接受客户端的日志,在其它服务器上复制它们,并告诉服务器何时可以安全地应用日志到它们的状态机。Leader 可以简化复制日志的管理。Leader 可以在不咨询其它服务器的情况下,决定新条目在日志的位置,数据流以简单方式从Leader 到其它服务器。Leader 失败或与其它服务断开连接时,新的 Leader 会被选举出来。

Raft将一致性问题分解为三个相对独立的子问题:

  • Leader election
  • Log replication
  • Safety

5.1 Raft 基础

一个 Raft 集群包含若干个服务器节点;通常是 5 个,这样的系统可以容忍 2 个节点的失效。在任何时刻,每一个服务器节点都处于这三个状态之一:leader、follower 或者 candidate 。在正常情况下,集群中只有一个 leader 并且其他的节点全部都是 follower 。Follower 都是被动的:他们不会发送任何请求,只是简单的响应来自 leader 和 candidate 的请求。Leader 处理所有的客户端请求(如果一个客户端和 follower 通信,follower 会将请求重定向给 leader)。第三种状态,candidate ,是用来选举一个新的 leader(章节 5.2)

img

Raft 把时间分割成任意长度的任期(term)。任期用连续的整数标记。每一段任期从一次选举开始,一个或者多个 candidate 尝试成为 leader 。如果一个 candidate 赢得选举,然后他就在该任期剩下的时间里充当 leader 。在某些情况下,一次选举无法选出 leader 。在这种情况下,这一任期会以没有 leader 结束;一个新的任期(包含一次新的选举)会很快重新开始。Raft 保证了在任意一个任期内,最多只有一个 leader 。

img

5.2 Leader 选举

Raft 使用一种心跳机制来触发 leader 选举。当服务器程序启动时,他们都是 follower 。一个服务器节点只要能从 leader 或 candidate 处接收到有效的 RPC 就一直保持 follower 状态。Leader 周期性地向所有 follower 发送心跳(不包含日志条目的 AppendEntries RPC)来维持自己的地位。如果一个 follower 在一段选举超时时间内没有接收到任何消息,它就假设系统中没有可用的 leader ,然后开始进行选举以选出新的leader

要开始一次选举过程,follower 先增加自己的当前任期号并且转换到 candidate 状态。然后投票给自己并且并行地向集群中的其他服务器节点发送 RequestVote RPC(让其他服务器节点投票给它)。Candidate 会一直保持当前状态直到以下三件事情之一发生:(a) 它自己赢得了这次的选举(收到过半的投票),(b) 其他的服务器节点成为 leader ,(c) 一段时间之后没有任何获胜者。这些结果会在下面的章节里分别讨论。

当一个 candidate 获得集群中过半服务器节点针对同一个任期的投票,它就赢得了这次选举并成为 leader 。对于同一个任期,每个服务器节点只会投给一个 candidate ,按照先来先服务(first-come-first-served)的原则(注意:5.4 节在投票上增加了额外的限制)。要求获得过半投票的规则确保了最多只有一个 candidate 赢得此次选举(图 3 中的选举安全性)。一旦 candidate 赢得选举,就立即成为 leader 。然后它会向其他的服务器节点发送心跳消息来确定自己的地位并阻止新的选举。

在等待投票期间,candidate 可能会收到另一个声称自己是 leader 的服务器节点发来的 AppendEntries RPC 。如果这个 leader 的任期号(包含在RPC中)不小于 candidate 当前的任期号,那么 candidate 会承认该 leader 的合法地位并回到 follower 状态。 如果 RPC 中的任期号比自己的小,那么 candidate 就会拒绝这次的 RPC 并且继续保持 candidate 状态。

第三种可能的结果是 candidate 既没有赢得选举也没有输:如果有多个 follower 同时成为 candidate ,那么选票可能会被瓜分以至于没有 candidate 赢得过半的投票。当这种情况发生时,每一个 Candidate 都会超时,然后通过增加当前任期号来开始一轮新的选举。然而,如果没有其他机制的话,该情况可能会无限重复。

Raft 算法使用随机选举超时时间的方法来确保很少发生选票瓜分的情况,就算发生也能很快地解决。为了阻止选票一开始就被瓜分,选举超时时间是从一个固定的区间(例如 150-300 毫秒)随机选择。这样可以把服务器都分散开以至于在大多数情况下只有一个服务器会选举超时;然后该服务器赢得选举并在其他服务器超时之前发送心跳。同样的机制被用来解决选票被瓜分的情况。每个 candidate 在开始一次选举的时候会重置一个随机的选举超时时间,然后一直等待直到选举超时;这样减小了在新的选举中再次发生选票瓜分情况的可能性。9.3 节展示了该方案能够快速地选出一个 leader 。

5.3 日志复制

Leader 一旦被选举出来,就开始为客户端请求提供服务。客户端的每一个请求都包含一条将被复制状态机执行的指令。Leader 把该指令作为一个新的条目追加到日志中去,然后并行的发起 AppendEntries RPC 给其他的服务器,让它们复制该条目。当该条目被安全地复制(下面会介绍),leader 会应用该条目到它的状态机中(状态机执行该指令)然后把执行的结果返回给客户端。如果 follower 崩溃或者运行缓慢,或者网络丢包, Leader 会不断地重试 AppendEntries RPC(即使已经回复了客户端)直到所有的 follower 最终都存储了所有的日志条目。

img

Leader 决定什么时候把日志条目应用到状态机中是安全的;这种日志条目被称为已提交的。Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行。一旦创建该日志条目的 leader 将它复制到过半的服务器上,该日志条目就会被提交

Raft 的日志机制来维持不同服务器之间日志高层次的一致性。

  • 如果不同日志中的两个条目拥有相同的索引和任期号,那么他们存储了相同的指令。
  • 如果不同日志中的两个条目拥有相同的索引和任期号,那么他们之前的所有日志条目也都相同。

leader 崩溃的情况会使日志处于不一致的状态(老的 leader 可能还没有完全复制它日志里的所有条目)。这种不一致会在一系列的 leader 和 follower 崩溃的情况下加剧。

img

follower 可能是(a-f)中的任何情况。每一个盒子表示一个日志条目;里面的数字表示任期号。

  • Follower 可能会缺少一些日志条目(a-b),
  • 可能会有一些未被提交的日志条目(c-d),
  • 或者两种情况都存在(e-f)。

例如,场景 f 可能这样发生,f 对应的服务器在任期 2 的时候是 leader ,追加了一些日志条目到自己的日志中,一条都还没提交(commit)就崩溃了;该服务器很快重启,在任期 3 重新被选为 leader,又追加了一些日志条目到自己的日志中;在这些任期 2 和任期 3 中的日志都还没被提交之前,该服务器又宕机了,并且在接下来的几个任期里一直处于宕机状态。

在 Raft 算法中,leader 通过强制 follower 复制它的日志来解决不一致的问题。这意味着 follower 中跟 leader 冲突的日志条目会被 leader 的日志条目覆盖。

要使得 follower 的日志跟自己一致,leader 必须找到两者达成一致的最大的日志条目(索引最大),删除 follower 日志中从那个点之后的所有日志条目,并且将自己从那个点之后的所有日志条目发送给 follower 。所有的这些操作都发生在对 AppendEntries RPCs 中一致性检查的回复中。Leader 针对每一个 follower 都维护了一个 nextIndex ,表示 leader 要发送给 follower 的下一个日志条目的索引。当选出一个新 leader 时,该 leader 将所有 nextIndex 的值都初始化为自己最后一个日志条目的 index 加1(图 7 中的 11)。如果 follower 的日志和 leader 的不一致,那么下一次 AppendEntries RPC 中的一致性检查就会失败。在被 follower 拒绝之后,leaer 就会减小 nextIndex 值并重试 AppendEntries RPC 。最终 nextIndex 会在某个位置使得 leader 和 follower 的日志达成一致。此时,AppendEntries RPC 就会成功,将 follower 中跟 leader 冲突的日志条目全部删除然后追加 leader 中的日志条目(如果有需要追加的日志条目的话)。一旦 AppendEntries RPC 成功,follower 的日志就和 leader 一致,并且在该任期接下来的时间里保持一致。

5.4 安全性

一个 follower 可能会进入不可用状态,在此期间,leader 可能提交了若干的日志条目,然后这个 follower 可能会被选举为 leader 并且用新的日志条目覆盖这些日志条目;结果,不同的状态机可能会执行不同的指令序列。

通过对 leader 选举增加一个限制来完善 Raft 算法。这一限制保证了对于给定的任意任期号, leader 都包含了之前各个任期所有被提交的日志条目。

5.4.1 选举限制

在任何基于 leader 的一致性算法中,leader 最终都必须存储所有已经提交的日志条目。

日志条目的传送是单向的,只从 leader 到 follower,并且 leader 从不会覆盖本地日志中已经存在的条目。

Raft 使用投票的方式来阻止 candidate 赢得选举除非该 candidate 包含了所有已经提交的日志条目。 Candidate 为了赢得选举必须与集群中的过半节点通信,这意味着至少其中一个服务器节点包含了所有已提交的日志条目。

RPC 中包含了 candidate 的日志信息,如果投票者自己的日志比 candidate 的还新,它会拒绝掉该投票请求。

Raft 通过比较两份日志中最后一条日志条目的索引值和任期号来定义谁的日志比较新。如果两份日志最后条目的任期号不同,那么任期号大的日志更新。如果两份日志最后条目的任期号相同,那么日志较长的那个更新。

5.4.2 提交之前任期内的日志条目

一旦当前任期内的某个日志条目已经存储到过半的服务器节点上,leader 就知道该日志条目已经被提交了。如果某个 leader 在提交某个日志条目之前崩溃了,以后的 leader 会试图完成该日志条目的复制。

如果是之前任期内的某个日志条目已经存储到过半的服务器节点上,leader 也无法立即断定该日志条目已经被提交了。图 8 展示了一种情况,一个已经被存储到过半节点上的老日志条目,仍然有可能会被未来的 leader 覆盖掉。

img

  • (a) 中,S1 是 leader ,部分地复制了索引位置 2 的日志条目。
  • (b) 中,S1 崩溃了,然后 S5 在任期 3 中通过 S3、S4 和自己的选票赢得选举,然后从客户端接收了一条不一样的日志条目放在了索引 2 处。
  • (c),S5 又崩溃了;S1 重新启动,选举成功,继续复制日志。此时,来自任期 2 的那条日志已经被复制到了集群中的大多数机器上,但是还没有被提交。
  • (d), 如果 S1又崩溃了,S5 可以重新被选举成功(通过来自 S2,S3 和 S4 的选票),然后覆盖了他们在索引 2 处的日志。但是,在崩溃之前,如果 S1 在自己的任期里复制了日志条目到大多数机器上,
  • (e) 中,然后这个条目就会被提交(S5 就不可能选举成功)。 在这种情况下,之前的所有日志也被提交了。

Raft 永远不会通过计算副本数目的方式来提交之前任期内的日志条目。只有 leader 当前任期内的日志条目才通过计算副本数目的方式来提交。

Raft 会在提交规则上增加额外的复杂性是因为当 leader 复制之前任期内的日志条目时,这些日志条目都保留原来的任期号。

5.4.3 安全性论证

img

Raft 要求服务器按照日志索引顺序应用日志条目。再加上状态机安全特性,这就意味着所有的服务器都会按照相同的顺序应用相同的日志条目到自己的状态机中。

5.5 Follower 和 candidate 崩溃

Raft 通过无限的重试来处理这种失败;Raft 的 RPCs 都是幂等的

5.6 定时(timing)和可用性

Raft 的要求之一就是安全性不能依赖定时

可用性(系统能够及时响应客户端)不可避免的要依赖于定时

Leader 选举是 Raft 中定时最为关键的方面。 只要整个系统满足下面的时间要求,Raft 就可以选举出并维持一个稳定的 leader:

广播时间(broadcastTime 0.5ms~20ms) « 选举超时时间(electionTimeout 10ms~500ms) « 平均故障间隔时间(MTBF)

6. 集群成员的变化

配置变更自动化并将其纳入到 Raft 一致性算法中

img

为了保证安全性,配置变更必须采用一种两阶段方法。

在 Raft 中,集群先切换到一个过渡的配置,我们称之为联合一致(joint consensus);一旦联合一致已经被提交了,那么系统就切换到新的配置上。联合一致结合了老配置和新配置:

7. 客户端和日志压缩

快照技术是日志压缩最简单的方法。

增量压缩方法,例如日志清理或者日志结构合并树(log-structured merge trees,LSM 树)

img