disk-paxos详解

Disk Paxos使用处理器和磁盘网络实现可靠的分布式系统。 与原始 Paxos 算法一样，Disk Paxos 可以保证在任意非拜占庭故障的情况下保持一致性。 只要大多数磁盘可用，即使仅剩下一个节点也能保证进程可用，且保持一致性。

1. 简介

容错需要冗余组件。 在系统分区的情况下保持一致性使得双组件系统在任何一个组件发生故障时都无法正常工作。 用于实现分布式系统的容错算法有无数种，我们所知道的算法都将组件与处理器等同起来。 但还有其他类型的组件可以替代。 特别是，现代网络现在将磁盘驱动器作为独立组件。 由于磁盘比计算机便宜，因此使用它们作为实现容错的复制组件很有吸引力。 磁盘与处理器的不同之处在于磁盘不可编程，因此我们不能仅用磁盘替换现有算法中的处理器。

我们在这里提出一种称为 Disk Paxos 的算法，它通过处理器和磁盘网络实现任意容错系统。 它在发生任意数量的非拜占庭故障时保持一致性。也就是说，处理器可以暂停任意长的时间，可能完全失败，并且可以在失败后重新启动，只记住它已经失败了； 某些或所有处理器可能无法访问磁盘，但它可能不会损坏。 如果系统稳定并且至少有一个无故障的处理器可以读取和写入大多数磁盘，则 Disk Paxos 可以保证正常服务。 稳定性意味着每个处理器要么没有故障，要么完全失效，并且非故障处理器可以访问非故障磁盘。 例如，它允许两个处理器和三个磁盘的系统在任何一个处理器和任何一个磁盘发生故障后继续前进。

Disk Paxos 是经典 Paxos 算法的变体[3,12,14]，是一种简单、高效的算法，已在实际分布式系统中使用[15,18]。 Classic Paxos可以看作是Disk Paxos的一种实现，其中每个处理器有一个磁盘，并且磁盘只能由其处理器直接访问。在下一节中，我们回顾一下如何将实现任意分布式系统的问题简化为共识问题。 第3节非正式地描述了Disk Synod，Disk Paxos使用的共识算法。它包括一个不完全正确性证明的草图，并解释了Disk Synod和经典Paxos的Synod协议之间的关系。 第 4 节简要讨论了一些实现细节并包含常规的结论性意见。 附录给出了共识问题和 Disk Synod 算法的正式规范，并勾勒出严格的正确性证明。

缺少任何证明的附录 1 的删节版本，出现的较早 [5]。

2. 状态机

状态机 [7, 16] 是实现任意分布式系统的通用方法。 该系统被设计为执行一系列命令的确定性状态机，并且共识算法确保对于每个 n，所有处理器都同意第 n 个命令。 这减少了构建任意系统来解决共识问题的问题。 在共识问题中，每个处理器 p 以一个输入值 input[p] 开始，并且它可能输出一个值。 解决方案应该是：

• 非零解 对于某个处理器 p，任何值输出都应该是某个时间 input[p] 的值。 （如果 p 失败并重新启动，则 input[p] 的值可能会更改。）
• 一致性 所有输出的值都是相同的。当系统稳定并且无故障的处理器（非阻塞的）可以与大多数磁盘通信，那么处理器最终将输出一个值。

众所周知，使用异步消息传递的一致、非阻塞共识总是需要至少两次消息延迟 [6]。使用较少消息延迟的非阻塞算法不能保证一致性。 例如，Isis [2] 的组通信算法允许属于当前组的两个处理器对于消息是否在它们所属的前一个组中广播存在分歧。 该算法本身无法保证一致性，因为对消息是否已广播的分歧可能会导致对输出值的分歧。

经典的Paxos算法[3,12,14]使用三阶段共识协议，称为Synod算法，其中前两个阶段中的每个阶段都需要两次消息延迟，第三阶段只是广播输出值。然而，直到第二阶段才选择要输出的值。 当选举出新的领导者时，它只为所有后续系统命令执行的整个共识算法序列执行第一阶段一次。只有最后两个阶段为每个单独的命令单独执行。

在 Disk Synod 算法（DiskPaxos 使用的共识算法）中，每个处理器在每个磁盘上都有一个分配的块。 该算法有两个阶段。 在每个阶段，处理器写入自己的块并读取大多数磁盘上其他处理器的块。 每个命令仅需要重新执行最后一个阶段。 因此，在正常的稳态情况下，领导者通过对其每个块执行一次写入，并对每个其他处理器的块执行一次读取来选择状态机命令。

Disk Paxos 与经典 Paxos 一样，不做时序假设； 进程可能是完全异步的。 Fischer、Lynch 和 Paterson [4] 的经典结果意味着纯粹的异步非阻塞共识算法是不可能的。 因此，必须引入时钟和实时假设。 典型的行业方法是使用基于超时的临时算法来选举领导者，然后让领导者选择输出[17, 19]。 设计一种在系统稳定时有效的领导者选举算法很容易，这意味着它在大多数时间都有效。 很难做出一个即使在系统不稳定的情况下也能始终正常工作的系统。 经典 Paxos 和 Disk Paxos 都采用实时算法来选举领导者。 然而，领导者仅用于确保进度。即使有多个领导者，也能保持一致性。 因此，如果领导者选举算法由于网络不稳定而失败，系统可能无法取得进展，它不会变得不一致。 当系统变得稳定并选出一位领导者时，系统将再次取得进展。

3. disk synod的非正式描述

我们现在非正式地描述 Disk Synod 算法并解释它的工作原理。 我们还讨论了它与经典 Paxos 的 Synod 协议的关系。请记住，在正常操作中，只有一个领导者将执行该算法。 其他处理器不执行任何操作； 他们只是等待领导者通知他们结果。 然而，即使由多个处理器执行，或者领导者在宣布结果之前失败并选择新的领导者，该算法也必须保持一致性。

3.1 算法描述

我们假设每个处理器 p 以一个输入值 input[p] 开始。Asin Paxos 的 Synod 算法，处理器执行一系列编号选票，选票编号不断增加。 选票号是正整数，不同的处理器使用不同的选票号。 例如，如果处理器编号为 1 到 N ，则处理器 i 可以使用选票编号 i、i + N 、 i + 2N 等。处理器 p 分两个阶段执行选票，第一个阶段尝试选择一个值，第二个阶段尝试提交该值：

• 阶段一 确定 p 是否可以选择其输入值 input[p] 或者必须选择其他值。选择一个值v。
• 阶段二 尝试提交v。 值 v 的选择发生在从阶段 1 到阶段 2 的过渡中。当 p 完成阶段 2 时，该值被提交并可以输出。

在任一阶段，如果处理者得知另一个处理者已开始编号更高的投票，则它会中止其投票。 在这种情况下，处理者可以选择更高的选票号码并开始新的选票。 （如果它仍然认为自己是领导者，它就会这样做。）如果处理器完成第 2 阶段而没有中止，即没有获知更高编号的选票，则值 v 被提交并且处理器可以输出它。 处理器 p 在进入阶段 2 之前不需要知道input[p]的值，因此可以针对算法的任意数量的单独实例提前执行阶段 1。

为了确保一致性，我们必须保证两个不同的值不能成功提交——无论是由不同的处理器（因为领导者选举算法尚未成功）还是由同一处理器在两次不同的选票中成功提交（因为它失败并重新启动）。 为了确保算法是非阻塞的，我们必须保证，如果只有一个处理器 p 执行它，那么 p 最终会提交一个值。

实际上，当处理器成功提交一个值时，它将在其磁盘块上写入该值已提交，并将该事实广播给其他处理器。 如果处理器得知某个值已被提交，它将中止其投票并简单地输出该值。 很明显，这种优化保留了正确性； 我们不会进一步考虑它。为了执行该算法，处理器 p 维护一条记录 dblock[p]，其中包含以下三个组成部分：

• bal 当前选票号
• mbal p进入第2阶段的最大选票数
• inp 值 尝试在选票号 bal 中提交的值

最初，bal 等于 0，inp 等于特殊值 NotAnInput，它不是可能的输入值，mbal 是其任何可能的选票号码。 我们让disk[d][p]为磁盘d上的块，处理器p在其中写入dblock[p]。 我们假设读取和写入块是原子操作。

处理器 p 如下执行投票的阶段 1 或阶段 2。 对于每个 diskd，它首先尝试将 dblock[p] 写入 disk[d][p]，然后为所有其他处理器 q 读取 disk[d][q]。 如果对于任何 d 和 q，它发现disk[d][q].mbal > dblock[p].mbal，则中止投票。 当 p 写入并读取大多数磁盘时，该阶段完成，且不读取 mbal 分量大于 dblock[p].mbal 的任何块。 当它完成阶段 1 时，p 选择 dblock[p].inp 的新值，将 dblock[p].bal 设置为 dblock[p].mbal（其当前选票编号），并开始阶段 2。当它完成阶段 2 时，phas 提交 dblock[p].inp。

为了完成对这两个阶段的描述，我们现在描述处理器 p 如何选择它在阶段 2 中尝试提交的 dblock[p].inp 的值。令blocksSeen 为由 dblock[p] 和 p 在阶段 1 中读取的所有磁盘[d][q]记录组成的集合。令 nonInitBlks 为由 inp 字段不是 NotAnInput 的记录组成的blocksSeen 的子集。 如果 nonInitBlks 为空，则 p 将 dblock[p].inp 设置为其自己的输入值 input[p]。 否则，对于 nonInitBlks 中具有 bk.bal 最大值的某些记录 bk，它将 dblock[p].inp 设置为 bk.inp。

最后，我们描述处理器 p 从故障中恢复时执行的操作。 在这种情况下，p 从大多数 disksd 中读取自己的块 disk[d][p]。 然后，它将 dblock[p] 设置为它读取的具有 bk.mbal 最大值的任何块 bk，并通过增加 dblock[p].mbal 并开始阶段 1 来开始新的投票。

图 1 非正式地总结了该算法，该图描述了处理器 p 如何执行单次投票。 处理器通过执行开始投票操作来开始投票。 如果投票中止，或者在任何其他时间，它可以开始新的投票 - 除非失败，在这种情况下，它必须执行“失败后重新启动”操作。 附录中给出了该算法的精确规范。

3.2 为什么算法可以安全运行

我们直观地解释了为什么Disk Synod算法满足非平凡性和一致性这两个安全属性。 非零解是平凡的，因为任何块的 val 字段总是设置为其他块的 val 字段或处理器 p 的 input[p]。因此，提交的值必须在某一时刻是某个处理器的输入值。

我们现在解释为什么 Disk Synod 算法保持一致性。首先，我们考虑以下使用单写入器、多读取器常规寄存器的共享内存版本的算法。处理器 p 不是写入磁盘，而是将 dblock[p] 写入共享寄存器；它从寄存器中读取其他处理器 q 的 dblock[q] 值。处理器选择第 2 阶段的 bal 和 inp 值的方式与以前相同，不同之处在于它只为每个其他处理器读取一个 dblock 值，而不是从每个磁盘读取一个 dblock 值。我们现在假设处理器不会出现故障。

为了证明一致性，我们必须证明，对于任何处理器 p 和 q，如果 p 完成阶段 2 并提交值 vp，并且 q 完成阶段 2 并提交值 vq ，则 vp = vq 。令 bp 和 bq 分别为提交这些值的相应选票号。不失一般性，我们可以假设 bp ≤ bq 。此外，使用 bq 上的归纳法，我们可以假设，如果处理器 r 在 bp ≤ br < bq 的情况下为选票 br 启动第 2 阶段，那么它会以 dblock[r ].inp=vp 来执行此操作。

当在阶段 2 中读取时，p 无法看到 q 在阶段 1 中写入的 dblock[q].mbal 的值，否则 p 将中止。 因此，第 2 阶段中 p 的 dblock[q] 读取并未遵循 q 的第 1 阶段写入。 因为在每个阶段中读取都在写入之后，这意味着 q 对 dblock[p] 的第 1 阶段读取必须在 p 的第 2 阶段写入之后。 因此，q 在阶段 1 中读取 dblock[p] 的当前（最终）值，即具有 bal 字段 bp 和 inp 字段 vp 的记录。令 bk 为 q 在其阶段 1 中读取的任何其他块。由于 q 没有中止，因此 bq > bk.mbal。 由于对于任何块 bk，bk.mbal ≥ bk.bal，这意味着 bq > bk.bal。 通过归纳假设，我们得到，如果bk.bal ≥ bp，则bk.inp = vp。 由于这对于第 1 阶段 q 读取的所有块 bk 都是如此，并且由于 q 读取 dblock[p] 的最终值，因此该算法意味着 q 必须在第 2 阶段将 dblock[q].inp 设置为 vp ，说明 vp = vq 。

• 开始投票

1. 将 dblock[p].mbar 设置为大于其当前值的值。
2. 将blocksSeen 设置为dblock[p]。
3. 开始第一阶段。

• 阶段一或者阶段二

同时对每个磁盘 d 执行
    将 `dblock[p]` 写入disk[d][p].
    对于每个处理器 q（不等于p）执行
        读取disk[d][q]并将其插入到设置的blocksSeen中。
    如果 disk[d][q].mbal > `dblock[p]`.mbal，则中止投票。
直到对大多数磁盘完成此操作。
如果是阶段一
    将 `dblock[p]`.bal 设置为 `dblock[p]`.mbal，nonInitBlks 为blocksSeen 中的元素bk 的集合，
    其中bk.inp不等于NotAnInput
    如果nonInitBlks为空
        `dblock[p]`.inp设置为input[p]
    否则
        `dblock[p]`.inp 设置为 nonInitBlks 的元素 bk，其最大值为bk.bal
    开始第二阶段
否则
    提交`dblock[p]`.inp

• 失败后重启

设置tempset为空集
同时对每个磁盘d执行
    读取disk[d][q]并将其插入到设置的tempSet中。
直到大多数磁盘完成操作
将 `dblock[p]` 设置为 tempSet 中最大值为 mbal 的元素 bk。
开始投票

为了从共享内存版本获得 Disk Synod 算法，我们使用 Attiya、Bar-Noy 和 Dolev [1] 提出的技术来实现单写入器、多读取器在磁盘网络上的注册。 为了写入值，处理器将该值与版本号一起写入大多数磁盘。 读取时，处理器读取大多数磁盘并获取版本号最大的值。 由于两个大多数磁盘包含至少一个共同的磁盘，因此读取必须获取完成写入的最后一个版本，或者获取更新的版本。 因此，这实现了一个常规寄存器。 通过这种技术，我们将共享内存版本转换为用于处理器和磁盘网络的版本。

实际的Disk Synod算法通过两种方式简化了这种变换得到的算法。 首先，不需要版本号。 mbal 和 bal 值起到版本号的作用。 其次，处理器 p 不需要从它从磁盘读取的版本中选择 dblock[q] 的单个版本。 由于 mbal 和 bal 值不会减小，因此早期版本没有效果。

到目前为止，我们忽略了处理器故障。 有一种简单的方法可以扩展共享内存算法以允许处理器发生故障。 处理器只需从寄存器中读取 dblock 值并开始新的投票即可恢复。 失败的流程就像处理者可以随时开始新投票的流程一样。 我们可以证明这个广义版本也是正确的。 然而，在实际的磁盘算法中，处理器在写入时可能会发生故障。 这可能会使其磁盘块处于大多数磁盘都没有写入任何值的状态。 这种状态在共享内存版本中没有对应的状态。 似乎没有简单的方法可以从共享内存算法中导出恢复过程。 完整的 Disk Synod 算法的证明（有失败）比简单的共享内存版本的证明要复杂得多。 尝试为简单算法编写上面给出的那种行为证明会导致我们已经学会避免的复杂且容易出错的推理。 相反，我们在附录中概述了严格的断言证明。

liveness

Disk Synod 算法的活跃度（进度）需要领导者选举算法的活跃度。 处理器执行 Disk Synod 算法的步骤当且仅当它认为自己是领导者。 我们表明，如果最终，可以读取和写入大多数磁盘的单个无故障处理器 p 永远是唯一的领导者，则将提交一个值。

假设 p 是唯一的领导者，它可以读写大多数磁盘。 由于 p 可以访问大多数磁盘，因此它执行的每个阶段要么完成，要么中止。 仅当 p 读取的 mbal 值大于其自身的值时，阶段才会中止，并且 p 在中止时会增加其自己的 mbal 值。 由于 p 是唯一的领导者，因此只有它写入磁盘。 因此，如果 p 没有完成阶段 1 和阶段 2，那么它的 mbal 值最终将大于它读取的每个磁盘块的值。 因此，p 最终必须完成阶段 1 和阶段 2 而不会中止，从而提交一个值。

3.3 从 Disk Paxos 推导经典 Paxos

在分布式容错系统的通常视图中，处理器执行操作并在本地内存中维护其状态，使用稳定的存储从故障中恢复。 另一种观点是，处理器维护其稳定存储的状态，仅使用本地内存来缓存稳定存储的内容。 识别具有稳定存储的磁盘，传统的分布式系统是磁盘和处理器的网络，其中每个磁盘属于一个单独的处理器； 其他处理器只能通过向其所有者发送消息来读取磁盘。

现在让我们考虑如何在每个处理器都有自己的磁盘的处理器网络上实现 Disk Synod。 为了执行阶段 1 或阶段 2，处理器 p 将通过向磁盘 d 的所有者 q 发送包含 dblock[p] 的消息来访问磁盘 d。 处理器 q 可以将 dblock[p] 写入磁盘[d][p]，读取所有 r 6= p 的磁盘[d][r ]，并将其读回的值发送回 p。 然而，检查 Disk Synod 算法表明不需要发回所有数据。 所有 p 需要 (i) 了解其 mbal 字段是否大于任何其他块的 mbal 字段，如果是，(ii) 具有最大 bal 字段的块的 bal 和 inp 字段。 因此，q 只需要在磁盘上存储三个值：具有最大 bal 字段的块的 bal 和 inp 字段，以及所有磁盘块的最大 mbal 字段。 当然，q 会将这些值缓存在其内存中，因此仅当这些值中的任何一个发生更改时它才会实际写入磁盘。

处理器还必须读取自己的磁盘块才能从故障中恢复。 假设我们通过让 p 在将消息发送到任何其他处理器之前先写入自己的磁盘来实现 Disk Synod。 这样就保证了自己的磁盘在所有磁盘d中disk[d][p].mbal的值最大。 因此，要在故障后重新启动，p 只需要从其自己的磁盘读取其块。 除了上面提到的 mbal、bal 和 inp 值之外，p 还将在其磁盘上保留 dblock[p] 的值。

我们现在可以将该算法与经典 Paxos 的 Synod 协议进行比较 [12]。 dblock[p] 的 mbal、bal 和 inp 组件就是 Synod 协议的 lastTried[p]、nextBal[p] 和 prevVote[p]。 Disk Synod 算法的阶段 1 对应于在 Synod 协议中发送 NextBallot 消息并接收 LastVote 响应。 第 2 阶段对应于发送 BeginBallot 并接收投票回复。 Synod Pro tocol 的 Success 消息对应于上面提到的在磁盘上记录已提交值的优化。

此版本的磁盘 Synod 算法与 Synod 协议有两个不同之处。 首先，Synod Protocol 的 NextBallot 消息仅包含 mbal 值； 它不包含 bal 和 inp 值。 为了获得 Synod 协议，我们必须修改 Disk Synod 算法，以便在阶段 1 中仅写入其磁盘块的 mbal 字段，并保持 bal 和 inp 字段不变。 在这种修改下，算法仍然是正确的，并且证明基本相同。 然而，修改使得该算法更难在真实磁盘上实现。

此版本的磁盘 Synod 算法与 Synod 协议之间的第二个区别在于重新启动过程。 磁盘仅包含上述 mbal、bal 和 inp 值。 它不包含其所有者的 dblock 值的单独副本。 Synod 协议可以从 Disk Synod 算法的以下变体获得。 令bk为重启过程中处理器p读取的具有最大bal字段的块disk[d][p]。 处理器 p 可以使用从任何磁盘块 bk0 获取并由任何处理器写入的 bal 和 inp 值开始阶段 1，使得 bk0 .bal ≥ bk.bal。 可以看出，在这种修改下，Disk Synod 算法仍然是正确的。

4. 结论

4.1 实现注意事项

我们对 Disk Synod 算法的描述中隐含了有关通过网络访问磁盘时如何实现读写的某些假设。 如果发送到磁盘的操作可能会丢失，则处理器 p 必须从磁盘 d 接收其对磁盘 [d][p] 的写入成功的确认。 这可能需要 p 在写入后显式读取其磁盘块。 如果操作到达磁盘的顺序可能与发送时的顺序不同，则 p 在从 d 读取其他处理器的块之前必须等待其写入磁盘 d 成功的确认。 此外，需要某种机制来确保来自较早选票的写入不会在同一处理器来自较晚选票的写入之后到达，从而用较早的值覆盖较晚的值。 如何实现这一点将取决于系统。 （如果对磁盘的写入可以在网络中停留任意长的时间并导致后来的值被覆盖，则不可能实现任何容错系统。）

回想一下，在 Disk Paxos 中，Disk Synod 算法的一系列实例用于提交一系列命令。 在 Disk Paxos 的简单实现中，处理器 p 会将当前 Disk Synod 实例的 dblock[p] 值以及已提交的所有命令的序列写入其磁盘块。 已提交的所有命令的序列可能太大，无法容纳在单个磁盘块上。 然而，完整的序列可以存储在多个磁盘块上。 所有必须与 dblock[p] 保存在同一磁盘块中的是指向队列头部的指针。 对于大多数应用程序，没有必要记住整个命令序列[12，第 3.3.2 节]。 在许多情况下，必须保留的所有数据都适合单个磁盘块。

在设计 Disk Paxos 的应用程序（未来的康柏产品）中，处理器集是事先未知的。 每个磁盘都包含一个目录，列出了处理器及其磁盘块的位置。 在读取磁盘之前，处理器会读取磁盘的目录。 要写入磁盘的目录，处理器必须通过执行基于 Fischer 协议的实时互斥算法来获取该磁盘的锁 [9]。 处理器通过将自身添加到大多数磁盘上的目录来加入系统。

4.2 结束语

我们提出了 Disk Paxos，这是系统中状态机方法的有效实现，其中处理器通过访问普通（不可编程）磁盘进行通信。 在正常情况下，领导者通过写入自己的块并读取大多数共享磁盘上的每个其他处理器的块来提交命令。 这显然是共识算法所需的最小磁盘访问次数，即使任何少数磁盘和任何单个处理器发生故障，该算法仍能取得进展。

Disk Paxos 的灵感来自于存储区域网络 (SAN) 的最新发展，该架构由计算机和磁盘网络组成，其中每台计算机都可以访问所有磁盘。 商品磁盘比计算机便宜，因此使用冗余磁盘进行容错比使用冗余计算机更经济。 此外，由于磁盘不运行应用程序级程序，因此它们比计算机更不容易崩溃。

由于商品磁盘不可编程，因此我们不能简单地用磁盘替代经典 Paxos 算法中的处理器。 相反，我们 11 采用了经典 Paxos 的思想并将其移植到 SAN 环境中。 我们得到的几乎是经典 Paxos 的概括，但不完全是。 事实上，当 Disk Paxos 实例化为单个磁盘时，我们获得了所谓的共享内存 Paxos。 共享内存的算法通常比消息传递算法更简洁、清晰。 因此，单个磁盘的 Disk Paxos 可以被认为是对经典 Paxos 的又一次重温，它通过消除消息传递混乱来揭示其基本思想。 也许其他分布式算法也可以通过在共享内存设置中重铸它们来变得更加清晰。