重新配置状态机

原文：Reconfiguring a State Machine
作者：Leslie Lamport, Dahlia Malkhi, Lidong Zhou
发表日期：2010 年 01 月 29 日
译者：ou@https://ouonline.net/

摘要

重新配置意味着更改分布式系统中的执行任务的进程。我们介绍几种方法（包括一些新方法），用来重新配置一个使用状态机方式来实现的系统。本文将讨论这些方法与之前的重新配置算法之间的关系——特别是在组通信中的视图变更。

目录

• 1 引言
• 2 状态机
  • 2.1 准备工作
  • 2.2 垃圾回收
  • 2.3 重新配置的简单方法
  • 2.4 正确性
• 3 重新配置的复杂方法
  • 3.1 停止状态机
    • 3.1.1 “停止标记”法
    • 3.1.2 “填充”法
    • 3.1.3 “砖墙”法
  • 3.2 选择新配置
  • 3.3 组合命令序列
  • 3.4 接口
• 4 组通信中的重新配置及其它工作
• 5 总结
• 参考文献

1 引言

一个具有容错性的系统可能需要更改执行任务的进程集合，这个过程被称为重新配置。当一个进程出错后，执行重新配置可以减少进一步出错的风险 [25]，也可以在不关停系统的情况下更换硬件。从多变的通信问题中识别出进程故障通常是一个有挑战性的工程问题。重新配置的时间太长会降低容错性，但等待时间不够长又会导致系统崩溃。可重新配置的系统提供了一个用于重新配置的接口，将重新配置从什么时候重新配置以及使用哪份新配置的决策中分离出来。这个决策可以由任何期望的算法或者运维人员来作出。

一个状态机（也被称为“对象” [12]）接受命令并生成输出。任何系统的功能行为都可以通过状态机来指定 [16]。状态机方法包括将一个具有容错性的分布式系统（或子系统）看作一个状态机，以及使用一个通用的容错性算法来实现这个状态机，从而实现这个分布式系统（或子系统）[20,24]。一个状态机的定义和实现的正确性直接意味着这个系统的正确性。

状态机方法提供的一个重要属性是输出的不可撤销性。对于证券交易所而言，不可撤销性意味着，如果一个经纪人收到了系统消息说一个客户买了 100 股 Nocturnal Aviation 的股票，那么该客户就真正持有这些股票。即使这个经纪人的电脑被一颗小行星摧毁了，该客户也可以去其他任何经纪人那里出售这些股份。没有不可撤销性，很难解释容错性对系统意味着什么。

使用状态机方法，通过让状态机本身来指定配置 [18,24]，很容易使一个系统支持重新配置。尽管这个基本想法在二十多年前就被提出 [17] 并且在早前的进程控制应用中被使用 [25]，但它似乎还没有被很好地理解。因此，我们将在第 2 节的状态机方法中一起回顾这个基本想法。

另一个可能更直观的重新配置系统的方法是，先终止状态机，选择新配置，然后使用新配置的新状态机恢复执行过程。这就是在组通信中重新配置的方法 [6,8]。我们在第 3 节中将会看到，尽管它不像第 2 节中描述的经典方法那么简单，但它的确引出了新的可重新配置的状态机实现方法。这两种重新配置的方法是获得重新配置算法的不同路径，但是它们并不意味着最终算法有任何本质区别。

第 4 节讨论了状态机方法，组通信以及某些特定系统中的重新配置之间的关系。尽管我们大部分的重新配置状态机的方法都可以在存在恶意进程的情况下工作，但本文仅考虑进程崩溃的错误情况。总结中讨论了恶意错误的情况。

2 状态机

2.1 准备工作

一个状态机被描述为一个状态集，一个初始状态，以及一个用来将命令状态对映射为输出状态对的函数。如果 <c, s> 被映射为 <o, s1>，那么我们说在状态 s 下执行命令 c 会生成输出 o 并且将状态改为 s1。状态机的执行过程包括以明显的方式从初始状态开始执行一连串命令，生成一连串输出和新状态。noop 是一条特殊的命令，它生成一个空的输出并保持当前状态不变。

状态机的实现提供了一个接口，客户端可以通过这个接口向系统发送命令并从系统接收输出。输出可能会被发送给除了命令发起者之外的客户端。但是命令发起者通常会收到输出，这样至少可以知道命令被执行了。一条命令可以包含发起命令的客户端标识。如果客户端无权发起命令，状态机可以将收到的命令视为 noop。

对状态机实现而言，安全性要求是指所有客户端收到的输出都是由一个被选定的命令序列生成的，其中的每条命令都是客户端发起的。（一个更完整的规范还要求状态机（或对象）是可线性化的 [12]。）安全性要求意味着不可撤销。

和任何具有容错性的分布式算法一样，由状态机实现所满足的精确的活性特性取决于实现的细节。这大概是说，如果有足够多的服务器正常运行，并且最终满足部分同步的要求，那么发起的命令会被加入到选定的命令序列中，并且这些命令的输出会被发送给正常运行的客户端。

有两组不相交的服务器集合，分别被称为 acceptor 和 learner。acceptor 选择要被执行的命令；learner 维护状态机的状态，获取哪些命令被选定，然后执行这些命令并生成输出。acceptor 主要提供稳定的存储，不关心哪些命令被选定。要保证系统在有 f 台服务器发生故障的情况下还能向前推进，要求至少有 2f+1 个 acceptor 和 f+1 个 learner [19]。

实现状态机的经典方法是使用一个用来选择单条命令的共识算法。这种实现方式运行一连串逻辑上独立的共识算法实例，其中的第 i 个实例用来选择第 i 条命令。大部分状态机实现都使用了一个被称为 leader 的特殊的 learner 子集。客户端通过将命令 c 发给 leader 来发起命令，然后 leader 为其分配一个编号 i，并提出把 c 作为共识实例 i 选定的命令。分配给命令 c 的编号 i 可以被包含在通过执行命令 c 生成的输出中。客户端命令怎样发送给 leader 是“分布式系统的客户端怎样定位执行该系统的服务器” 这个常见问题的一个实例。本文不讨论这个问题。

leader 不需要等到命令 i 被选定后才提出另一条命令 i+1。不同的命令可以被同时选定。一般来说，在所有编号小于 i 的命令被选定之前，命令 i 无法被执行并确定其输出。然而，在某些重要的情况下，只要某条命令被选定后就可以立刻生成输出。例如，如果输出只是显示命令的编号以及它已经被执行的事实。因为选定的命令是不可撤销的，命令被选定等同于执行它。（如果命令编号与提出命令的顺序一致，则满足线性化特性。）

2.2 垃圾回收

在不支持重新配置的系统中，我们可以允许 acceptor 一直维护每个共识算法实例的信息。learner 随时可以通过和足够多的 acceptor 通信来获取完整的被选定的命令序列，这里的“足够多”通常是指大多数。实际上，共识实例通常都需要被回收。learner 会定期保存执行过程序列中某个点的状态，然后指示 acceptor 丢弃在此之前的命令的共识实例。尽管命令索引继续单调增长，但是编号较小的命令占用的内存就可以被回收了。确切地说这是一个工程细节，本文不关心具体怎么实现。

2.3 重新配置的简单方法

配置是指执行系统的进程（客户端，acceptor，等等）集合。用于实现状态机的共识算法使用固定的配置，因此我们必须确保算法的每个实例都由单一的配置来执行。（重要的是 acceptor 集合；在执行共识算法的时候增加或移除客户端或者 learner 都不是问题。）在简单方法中，通过针对不同的实例使用不同的配置来实现重新配置。我们将编号为 i 的命令的配置定义为用于执行共识实例 i 的配置。

为了避免混乱，进程必须对命令 i 使用的配置达成一致。获得可重新配置的状态机实现的简单方法是引入一个状态机状态的组成部分 cfg，用来指定当前的配置。也就是说，命令 i 的配置由执行完命令 i-1 之后的状态下，此时此刻的 cfg 的值决定；如果 i=1 的话就是初始配置。（我们使用序数给命令编号，因此第一条命令的编号是 1。）我们增加一条重新配置的命令 rcfg(C) 用来指定新的配置 C。

一个明显的定义状态机的方法是，执行 rcfg(C) 会将 cfg 的值设为 C，这样重新配置就可以立即生效。我们把这个方法称为 R1。R1 的问题是不能并行处理多条不同的命令。因为通过执行命令 i 可以改变用于执行共识算法实例 i+1 的配置，这样的状态机实现方式在命令 i 被选定前就无法开始选择命令 i+1。

为了允许并行处理命令，我们通过引入额外的状态来定义状态机，使得对于正整数 a，将 rcfg(C) 作为编号为 i 的命令执行，会在执行命令 i+a-1 后改变 cfg 的值。因此，重新配置的命令会延迟 a 条命令生效，从而允许并行处理最多 a 条命令。（最初的描述是“a=3”，这是因为错误地认为将“a=3”推广到其它情况是显而易见的 [18] ¹。在此之后发表的 [21] 中介绍了一种可行的实现。）我们把这个方法称为 Ra。就像符号所暗示的那样，R1 是 Ra 在 a=1 时的情况。

为了使重新配置立刻生效，发起重新配置命令的客户端可以紧接着再发起 a-1 条 noop 命令。一个连续发起的命令序列，并且命令的编号也是连续的，可以被打包在一起，以便像处理单条命令一样，以同样的效率（使用的消息数不超过单条命令所需的消息数）来发起，选定和执行。因此，a 可以取任意大的值，以便允许并行处理任意数量的命令。为了维护正确性，该实现生成的结果必须与共识算法的每个实例单独执行时得到的结果一样。

方法 Ra 可以使用普通的状态机接口来发起重新配置的命令。只给一部分客户端授权允许发起重新配置的命令，这样可以有效地将重新配置的接口与用于发起其它命令的接口分开。

2.4 正确性

一个简单的归纳论证表明了 Ra 保持了状态机实现的安全性。特别是它满足不可撤销性。状态机实现的活性表明，只要有足够多的服务器正常运行，系统就能够向前推进。这里提出了一个问题：“足够多的服务器”是指哪些服务器？

重新配置的目的是消除对已经被配置为从系统移除的服务器的依赖。由这些服务器维护的信息必须被转移给新配置中的服务器。这是通过回收在旧配置中执行的共识实例，并将状态转移到新配置的 learner 上完成的。在过渡到新配置的过程中，只有在旧配置和新配置中都有足够多的正常运行的服务器的情况下，切换操作才能够向前推进。最终得到的算法所满足的活性属性不是很容易精确表述，但是它的一般性质直观上应该很清晰。

3 重新配置的复杂方法

第 2.3 节介绍的 Ra 算法实现中有一个缺陷，就是重新配置会引入一个长度约为 a 的 noop 命令序列。当 a 取值比较大（例如 a=$2^{64}$）时会不方便。a 所隐含的并发约束，即使不是一个实际需要关注的问题，也可能被认为是不优雅的。接下来我们提出重新配置的算法。在正常的执行过程中，在没有运行重新配置的时候，该算法允许并行选定任意数量的命令。

通过将一系列单独的不可重新配置的状态机实现的执行过程组合在一起，我们获得了可重新配置的状态机实现。为了在执行编号为 v 的状态机实现时进行重新配置，我们先停止执行过程，接着选择新的配置，然后使用新配置开始编号为 v+1 的状态机实现的执行过程。

这种方法需要解决三个大部分正交的问题：（i）停止当前状态机，（ii）选择配置来实现下一个状态机，以及（iii）将为每个单独的状态机选定的命令序列组合为一个序列。我们从实现可停止的状态机的三种基本方法开始，来分别考虑这三个问题。

3.1 停止状态机

3.1.1 “停止标记”法

“停止标记”法给状态机添加一个 stop 命令，这个命令会把后续的每个状态机命令转换为 noop。和第 2.3 节介绍的 R1 算法不同，这个方法允许并行选定多条命令。在 stop 命令之后选定的任何命令完全无效。然而，“停止标记”法有以下问题。如第 2.1 节解释的那样，普通的状态机实现允许在命令被选定后立刻生成像“这条命令已经被执行”这样的输出。对于任意一条命令，“停止标记”法在所有编号比该命令小的命令被选定之前，不允许生成任何输出，因为这些命令中的某一条可能是 stop 命令。

延迟的“停止标记”法允许执行编号为 i 的命令，前提是它以及最大编号为 i-a 的命令之前的所有命令已经被选定。就像 Ra 泛化了 R1 来使重新配置命令在 a 条命令之后生效那样，延迟的“停止标记”法泛化了 stop 命令来使停止命令在 a 条命令之后生效。换句话说，如果编号为 i 的命令是 stop，那么编号从 i+a 开始的所有命令都被当做 noop。像 Ra 那样，客户端在发起 stop 命令之后可以同时发起 a-1 条连续的 noop 命令。

3.1.2 “填充”法

我们已经观察到，我们可以将一连串命令打包在一起，并且像处理它们就像处理单条命令那样轻松。如果在一连串无限的连续命令中只有有限个 noop 命令，那么这个批处理方法也可以应用在这个序列上。（很容易对执行无限数量的共识实例所需的信息设计一种有限的编码方式。）在“填充”法中，客户端通过发起无限个 noop 命令来停止状态机。更准确地说，它发起的所有编号大于某个值 i 的命令都是 noop。对于所有的正整数 j，当编号为 j 的命令被选定时，状态机就停止了。

3.1.3 “砖墙”法

“停止标记”法和“填充”法使用了基础状态机实现，因此它们的正确性由该实现的正确性决定。然而，它们看起来并不直观：“停止标记”法可以选择永远不会被状态机执行的命令，“填充”法使用无限多个 noop 填充命令序列。我们现在介绍的“砖墙”法概念上相对比较简单，但是需要一种被称为 Stoppable Paxos 的新状态机实现。

像“停止标记”法一样，Stoppable Paxos 使用一个特殊的 stop 命令。然而，它保证了如果 stop 被选定为编号为 i 的命令，那么对于大于 i 的任意编号都不会有命令被选定。[14] 中给出了 Stoppable Paxos 的精确描述和严格的正确性证明。这里我们从经典的 Paxos 算法的描述开始，来简要地介绍一下 Stoppable Paxos。

如第 2.1 节所述，Paxos 通过使用逻辑上分离的共识算法实例来实现状态机。它使用了一种选举 leader 的方法，仅当有唯一的 leader 时才保证系统能够向前推进。（在有多个 leader 的情况下也能保证安全性。）Paxos 共识算法使用带编号的选票，每张选票最多由一个 leader 发起。（不要将选票编号和共识实例（或命令编号）混淆。）新选出来的 leader 选择一个选票编号 b（它认为 b 比所有已经使用的编号都要大），然后开始通过发送阶段 1a 的消息给所有的 acceptor 来发起对 b 的投票。acceptor 收到阶段 1a 的消息后会回复阶段 1b 的消息。如果 leader 已经选定了足够大的 b，并且它从大多数 acceptor 收到了阶段 1b 消息，那么它将知道：

• P1. 编号较小的选票可能已经选定了命令 c（除了 c 没有其它命令），或者
• P2. 编号较小的选票没有选定任何命令。

然后，leader 通过向 acceptor 发送阶段 2a 消息，在选票 b 中发起命令：如果是 P1 则发起命令 c，是 P2 则可以发起任意命令。如果没有出现编号更大的选票，当大多数 acceptor 都收到阶段 2a 消息的时候，命令就被选定了。Paxos 状态机算法之所以高效，是因为对于所有共识实例，任何一个进程发送的阶段 1a 和阶段 1b 消息都被打包进一条物理消息中。

如果 stop 可以被选定为编号较小的命令，Stoppable Paxos ² 会阻止 leader 发起命令。为了描述这是怎么做到的，对于共识实例 i 的选票 b，我们首先定义 $\xi(b, i)$，如果是 P1 则等于命令 c，如果是 P2 则等于 $\bot$。针对 leader 可以在实例 i 的选票 b 中发起的命令，Stoppable Paxos ² 增加了下面两个额外的限制：

• S1. 对于 j < i，如果 leader 在实例 j 的选票 b 中发起了一个重新配置的命令，也就是说 $\xi(b, j)$ 是一个重新配置命令，那么它就不能再发起任何命令。
• S2. 对于 k > i，如果 leader 已经在实例 k 的选票 b 中发起了命令，也就是说 $\xi(b, k) \neq \bot$，那么它就不能发起重新配置命令。

不难证明，如果某个编号比 i 小的实例选定了 stop 命令，则 S1 和 S2 会阻止实例 i 选定任何命令。然而，在实例 j（j < i）中，如果一个重新配置命令被发起，但还没被编号小于 b 的选票选定，S1 就可能阻止系统向前推进。为了消除这个问题，我们将 $\xi$ 的定义大致修改为这样：在 P1 中，如果 c 是在选票 b1（b1 < b）中发起的重新配置命令，并且在实例 k 的选票 b2 中发起了某个命令（其中 b2 > b1 并且 k > i），那么 $\xi(b, i)$ 等于 $\bot$ 。精确的定义和这个算法确实起作用的证明并非无关紧要。

3.2 选择新配置

当从状态机实现 v 变为状态机实现 v+1 时，有两种基本方法可以用来选择执行实现 v+1 的新配置：

• R1. 状态机 v 执行一条重新配置命令，该命令选定了新配置。
• R2. 使用一个特殊的共识算法实例，该实例由和执行状态机 v 的相同配置来执行。

选项 R2 的潜在的优势是可以在状态机 v 停止之前确定配置 v+1 中的进程并为状态机 v+1 选定命令。目前还不清楚这在实践中是否是个好主意。为了使选项 R1 起作用，我们必须：

• （a）确保在配置 v 终止前传递了重新配置命令，并且
• （b）确定在传递了多个重新配置命令的情况下要怎么处理。

在“停止标记”法和“砖墙”法中，对于（a）的解决方法是显而易见的——即，让 stop 命令指定新配置。在“填充”法中，客户端要保证重新配置命令已经被选定，然后再发起一连串无限的 noop 命令。（如果重新配置命令没有被选定，那么配置 v+1 和配置 v 相同）。

在“砖墙”法中不存在问题（b）。对其它方法来说有两个显而易见的选择：使用已传递的第一个或最后一个重新配置命令。如果我们使用第一个命令，那么一旦知道通过第一个重新配置命令所选定的所有命令，系统就可以开始为配置 v+1 选择命令。

3.3 组合命令序列

我们已经展示了怎样启动和执行一连串状态机实现。所有的实现，可能除了最后一个之外，都停止了。编号为 v 的状态机使用配置 v 执行。

如果状态机已经停止，它具有唯一的“最后一个有趣的”命令。对于“停止标记”法或者“砖墙”法，该命令是（第一个）stop 命令。对于延迟的“停止标记”法，它是 stop 命令后面的第 a-1 个命令。对于“填充”法，它是最后一个非 noop 的命令。令 $\eta(v)$ 为编号为 v 的状态机的最后一个有趣的命令的编号，并且定义 $\eta(0)$ 等于 0。

让我们把“编号” <v, i> 分配给编号为 v 的状态机选定的第 i 条命令。使用常用的字典序给这些“编号”排序，这为所有选定的命令序列提供了一个线性排序的编号。然而这并不是一个有用的编号方案，因为它不会告诉客户端在“编号”分别为 <4, 417> 和 <5, 1> 的两个命令之间是否有任何命令。最好使用连续的正整数为命令编号。

为了给命令提供整数编号，我们观察到状态机的命令编号不一定要从 1 开始。让我们将起始编号作为状态机的一个参数，并且让编号为 v+1 的状态机的第一条命令的编号比状态机 v 的最后一条有趣的命令的编号大 1。换句话说，状态机 v+1 的第一条命令的编号是 $\eta(v)+1$。因此，命令 i 是编号为 v 的状态机选定的编号为 i 的命令，其中 $\eta(v-1) < i \le \eta(v)$。为了实现这一点，需要先知道 $\eta(v)$ 的值，然后才能开始在状态机 v+1 中选择命令。

在简单的实现中，每个进程都维护一个二维数组，其中元素 <v, i> 包含了编号为 v 的状态机的共识实例 i 的数据。然而，如果 $i < \eta(v-1)$，状态机 v 中不存在共识实例 i；并且，如果 $i > \eta(v)$，实例 i 选定什么值都不重要。在任何基于完全独立的共识实例序列的状态机实现中，进程只需要维护编号最大的状态机 v 的实例 i 的信息，其中状态机 v 的命令 i 已经开始被处理。为了可以使用诸如 Stoppable Paxos 的状态机实现，并且在实现中，其它共识实例的执行过程可以取决于共识实例 i 的状态，这些实现必须被修改，以便当 $i > \eta(v)$ 的时候可以忘记实例 i 的状态。对于 Stoppable Paxos 来说修改很简单。

3.4 接口

在基于状态机序列的重新配置方法中，可以通过发起一个 stop 命令或者一连串无限的 noop 命令来停止状态机。如果新的配置由状态机命令指定（选项 R1），则整个重新配置都使用普通的状态机接口来执行。如果新的配置由不属于状态机执行过程的特殊的共识实例来决定（选项 R2），那么需要单独的接口来指定配置。

实际上，这些方法中的任何一种都需要使用单独的接口来发起重新配置请求。leader 发起执行重新配置所需的状态机命令，同时也会启动选项 R2 中的特殊的共识实例。

4 组通信中的重新配置及其它工作

组通信（GC）是另一种实现具有容错性的分布式系统的方法。其中被称为“视图”的一组进程执行广播机制，使得视图中所有正常运行的进程都接收相同的消息集合 [6,5]。重新配置是 GC 实现容错性的不可缺少的一部分。有许多不同版本的 GC 提供不同的保证。这里我们只考虑几个版本，这些版本都会生成一致完全有序的已投递消息。读者可以参阅 [8] 所做的调查以便更详细地了解以前的成果。

GC 服务提供接口，视图中的进程在该接口中发送消息。已发送消息的有序序列会被投递给所有进程。视图中的进程通常使用不可靠的共识算法来选定每个被投递的消息。该算法确保最多只有一条消息被选定，但是即使只有一个进程出错也有可能阻止系统向前推进。（不可靠的一致性算法中通常有一个 leader 角色，leader 的出错会阻止系统向前推进。）当故障发生时，当前视图会终止并开始一个新视图。通过使用具有容错性的共识算法来确定（i）旧视图中被投递的消息序列以及（ii）新视图的成员，从而执行视图变更。GC 服务提供的接口通常允许进程进入和离开视图，并了解哪些进程属于该视图，但是该实现在出错的时候可能自发地改变视图。

在 GC 和状态机方法之间有明显的对应关系，那就是视图和配置对应。我们可以基于 GC 服务来考虑状态机实现，其中消息就是命令，被投递的消息就是被选定的命令。对于第 3 节介绍的基于状态机序列的实现，这种对应关系最明显。相反地，我们也可以考虑将 GC 服务实现为某种状态机的形式，其中命令就是“发送消息 m”这样的形式，状态就是被投递的消息序列。

如果 GC 服务实现了一个具有不可撤销的消息发送特性的真正的消息发送状态机，那么使用它来实现一个任意状态机将非常简单。它是否可行取决于准确地执行视图变更的方法。[6] 中将 GC 视图变更操作所需的属性称为“虚拟同步”。正如定义所说，虚拟同步要求新视图包含旧视图中的大多数进程，并且，被投递给这些进程的消息在旧视图中也已经被投递成功。这个要求不足以保证不可撤销性，因为如果交易员的电脑被小行星击中了，它将不会出现在新视图中。因此，不需要视图变更来声明股票买卖的消息已经被投递。（这在 [23,13] 之前已经被观察到。）

不难实现更强的约束，即旧视图中任何进程投递的消息都被声明为已投递。我们只需要求，某个进程投递消息前了解了“视图中大多数进程已经知道了该消息已经被发出”这个事情。向视图变更的共识算法发起的值是旧视图中的已投递消息序列，该值必须包含所有的消息——某个大多数进程的集合知道这些消息已经被发送。通过更强的约束，很容易使用 GC 服务来实现状态机。确实存在更强的服务，包括 Isis 的 GBCAST 协议 [6] 以及 Transis [9] 和 Totem [2] 中的“安全”消息。视图中所有成员收到 GBCAST（或“安全”）消息后，该消息才会被投递。这些服务通过实施一个视图变更的决策来提供一致的完全有序的广播，这个决策是：强制交付收到的任何 GBCAST（或“安全”）的消息 [10,13,23]。[4] 直接采取延迟投递消息的方法，直到大多数进程确认已收到消息为止。

状态机的实现看起来和 GC 有很大不同。状态机的实现使用可靠的共识算法来选择每个命令；但 GC 的实现使用不可靠的共识算法来广播消息，只有在视图变更的时候才会使用可靠的共识算法。然而，异步的共识算法会执行一系列不可靠的共识算法——例如，Paxos 中的单次投票——当命令被选定时就会停止。GC 用来广播消息的不可靠的共识算法可以被看作是可靠的共识算法的第一步，其余的共识算法是在视图变更时对所有消息同时执行的。这实际上是在 Paxos 中当 leader 出错后共识算法的所有实例同时发起一个新投票的情况。状态机实现和一个增强的 GC 服务执行基本相同的操作，只是两者对这些操作的解读不同。从状态机的角度看正确性显而易见；从 GC 的角度看实现方法更明显。

所有提供增强 GC 服务的协议都会阻止在视图变更开始后投递任何消息。它们实际上使用了“砖墙”法来停止状态机。Totem [2] 同时选择在旧视图和新视图中被投递的最后一条消息的编号，这个过程类似于第 3.2 节中的选项 R1。[13] 中首先选择新配置，然后决定旧配置中哪些消息被投递了，这类似于选项 R2。

在传统的 GC 中，视图变更共识算法由新视图中的进程来执行，而在方法 Ra 和第 3 节介绍的方法中，新配置是通过使用旧配置执行的共识算法选定的。（在方法 Ra 和在第 3.2 节的选项 R1 中，共识算法是指用来选择普通状态机命令的算法。）

维持唯一的配置序列要求新配置由旧配置中的 acceptor 来选定，但是要保证系统能够向前推进则要求新配置中的 learner 了解新配置。因为原始的 GC 不区分 acceptor 和 learner，它通过让新视图中的进程执行共识算法来保证向前推进，通过要求新视图包含旧视图中的大多数进程来确保视图的唯一性。正如我们的算法所示，新旧视图之间不一定要有交集。新视图中的进程只需要学习旧视图选定的新视图。

也有一些可重新配置的系统没有提供状态机实现的功能。RAMBO [7,11,22] 是一个提供简单的读写操作的具有容错性的系统。它基于 ABD 算法 [3]，该算法的角色就是共识算法在状态机实现中的角色。在 RAMBO 中，通过使用单独的状态机选择新配置来完成重新配置，该新配置可以在执行单个读写的过程中生效。这类似于我们尚未讨论过的 Paxos 中的另一种重新配置的方法 [15]。有趣的是，最近发现，对于重新配置的决策，可以在不依赖共识的情况下构造可重新配置的原子读写对象 [1]。

5 总结

在状态机方法中，具有容错性的分布式系统建立在具有容错性的状态机实现之上。系统的正确性，包括不可撤销性，取决于状态机的定义和状态机实现的正确性。可重新配置的状态机实现提供了一个接口，用来选择用于执行系统的配置。第 2 节回顾了一个明显正确的使状态机实现可重新配置的方法 Ra。第 3 节介绍了其它实现方法。除了“砖墙”方法，其它方法的正确性直接取决于基础共识算法的正确性。

我们仅考虑了非恶意故障的情况。如果基础共识算法可以容忍恶意故障，则使用除了“砖墙”法（第 3.1.3 节）以外的任何算法获得的状态机实现同样可以做到。我们还必须设计状态机来容忍恶意客户端——包括发起重新配置的客户端。达成目标的方法是要求仅当有足够多的不同客户端发起请求时才执行诸如停止当前配置或者选择新配置之类的关键操作。在“停止标记”法（第 3.1.1 节）中，stop 命令是触发停止的请求。对于选项 R2，新视图由单独的共识算法选定（第 3.2 节），该算法被一个具有容错性的状态机代替。

参考文献

[1] M. K. Aguilera, I. Keidar, D. Malkhi, and A. Shraer. Dynamic atomic storage without consensus. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), August 2009.

[2] Y. Amir, L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal, and P. Ciarfella. The Totem single-ring ordering and membership protocol. ACM Transactions on Computer Systems, 13(4):311-342, 1995.

[3] Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. J. ACM, 42(1):124-142, 1995.

[4] Ozalp Babaoglu, Renzo Davoli, and Alberto Montresor. Group communication in partitionable systems: Specification and algorithms. Software Engineering, 27(4):308-336, 2001.

[5] Kenneth Birman and Tommy Joseph. Exploiting virtual synchrony in distributed systems. In Eleventh ACM Symposium on Operating Systems Principles, pages 123-138, 1987.

[6] Kenneth P. Birman and Thomas A. Joseph. Reliable communication in the presence of failures. ACM Transactions on Computer Systems, 5(1):47-76, February 1987.

[7] Gregory Chockler, Seth Gilbert, Vincent C. Gramoli, Peter M. Musial, and Alex A. Shvartsman. Reconfigurable distributed storage for dynamic networks. In 9th International Conference on Principles of Distributed Systems (OPODIS), 2005.

[8] Gregory Chockler, Idit Keidar, and Roman Vitenberg. Group communication specifications: a comprehensive study. ACM Computing Surveys, 33(4):427-469, 2001.

[9] Danny Dolev and Dalia Malki. The Transis approach to high availability cluster communication. Communications of the ACM, 39(4):64-70, 1996.

[10] Alan Fekete, Nancy Lynch, and Alex Shvartsman. Specifying and using a partitionable group communication service. ACM Transactions on Computer Systems, 19(2):171-216, 2001.

[11] Seth Gilbert, Nancy A. Lynch, and Alex A. Shvartsman. RAMBO II: Rapidly reconfigurable atomic memory for dynamic networks. In International Conference on Dependable Systems and Networks (DSN), 2003.

[12] M.P. Herlihy and J.M. Wing. Axioms for concurrent objects. In Proceedings of the Fourteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 13-26, Munich, January 1987. ACM.

[13] Idit Keidar and Danny Dolev. Efficient message ordering in dynamic networks. In Fifteenth ACM Symp. on Principles of Distributed Computing (PODC), pages 68-76, 1996.

[14] L. Lamport, D. Malkhi, and L. Zhou. Stoppable paxos. Technical report, Microsoft Research, April 2008.

[15] L. Lamport, D. Malkhi, and L. Zhou. Brief announcement: Vertical paxos and primary-backup replication. In The ACM Symposium on Principles of Distributed Computing (PODC 2009), August 2009.

[16] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558-565, July 1978.

[17] Leslie Lamport. Using time instead of timeout for fault-tolerant distributed systems. ACM Transactions on Programming Languages and Systems, 6(2):254-280, April 1984.

[18] Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133-169, May 1998.

[19] Leslie Lamport. Lower bounds for asynchronous consensus. Distributed Computing, 19(2):104-125, October 2006.

[20] Butler W. Lampson. How to build a highly available system using consensus. In Ozalp Babaoglu and Keith Marzullo, editors, Distributed Algorithms, volume 1151 of Lecture Notes in Computer Science, pages 1-17, Berlin, 1996. Springer-Verlag.

[21] J. R. Lorch, A. Adya, W. J. Bolosky, R. Chaiken, J. R. Douceur, and J. Howell. The smart way to migrate replicated stateful services. In Proceedings of ACM Eurosys, 2006.

[22] Nancy A. Lynch and Alex A. Shvartsman. RAMBO: A reconfigurable atomic memory service for dynamic networks. In 5th International Symposium on Distributed Computing (DISC), 2002.

[23] Louise E. Moser, Yair Amir, P. Michael Melliar-Smith, and Deborah A. Agarwal. Extended virtual synchrony. In The 14th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 56-65, 1994.

[24] Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299-319, December 1990.

[25] J. Wensley et al. SIFT: Design and analysis of a fault-tolerant computer for aircraft control. Proceedings of the IEEE, 66(10):1240-1254, October 1978.

译者注