6

在 Multi-Paxos 算法中，从接受者的角度考虑这个消息流：

接收：准备（N）

回复：承诺（N，空）

接收：接受！（N，V1）

回复：接受（N，V1）

接收：接受！（N+1，V2）

回复： ？

根据协议，在这种情况下，接受者的反应应该是什么？它应该回复 Accepted(N+1, V2)，还是应该忽略第二个 Accept！？

我相信当第二个提议者上线并相信他是（并且一直是）领导者时，这种情况可能会发生在 Multi-Paxos 中，因此他在没有准备的情况下发送了他的接受。或者，如果他的 Prepare 根本没有到达接受者。如果这种情况可能不会发生，你能解释一下原因吗？

4

4 回答 4

6

我不同意其他两个答案。

  1. Multi-Paxos 并没有说 Leader 是唯一的提议者；这会导致系统出现单点故障。即使在网络分区期间，系统也可能无法运行。Multi-Paxos 是一种优化，允许单个节点（Leader）跳过一些准备阶段。其他节点，认为领导者已经死了，可能会尝试代表她继续实例，但仍必须使用完整的 Basic-Paxos 协议。

  2. 取消接受消息违反了 Paxos 算法。接受者应该接受所有值，除非它承诺不接受它。（忽略是允许的，但不推荐；这只是因为允许丢弃的消息。）

  3. 对此也有一个优雅的解决方案。问题在于领导者的回合数（问题中的 N+1）。

以下是一些假设：

  • 您有一个方案，使得所有节点的轮 id 不相交（Paxos 无论如何都需要）。
  • 您可以确定哪个节点是每个 Paxos 实例的领导者（Multi-Paxos 需要）。Leader 能够从一个 Paxos 实例更改为下一个。
    旁白：兼职议会建议这是由领导者赢得先前的 Paxos 实例来完成的（第 3.1 节），并指出只要她还活着或最富有，她就可以继续担任领导者（第 3.3.1 节）。我有一个通过 Paxos 提出的显式 ELECT_NEW_LEADER:<node> 值。
  • Leader 只在每个实例的第一轮跳过Prepare 阶段；并在随后的回合中使用完整的 Basic Paxos。

有了这些假设，解决方案就很简单了。领导者只是为它的初始接受阶段选择了一个非常低的回合 id。这个 id（我称之为 INITIAL_ROUND_ID）可以是任何东西，只要它低于所有节点的轮 id。根据您的 id 选择方案，-1、0 或 Integer.MIN_VALUE 都可以。

它之所以有效，是因为另一个节点（我称他为 Stewart）必须通过完整的 Paxos 协议来提出任何建议，并且他的回合 id 总是大于 INITIAL_ROUND_ID。有两种情况需要考虑：Leader 的 Accept 消息是否到达了 Stewart 的 Prepare 消息到达的任何节点。

当 Leader 的 Accept 阶段没有到达任何节点时，Stewart 将不会在任何 Promise 中取回任何值，并且可以像在常规 Basic-Paxos 中一样继续进行。

并且，当 Leader 的 Accept 阶段到达一个节点时，Stewart 将在 Promise 中取回一个值，用于继续算法，就像在 Basic-Paxos 中一样。

在任何一种情况下，因为 Stewart 的轮 id 大于 INITIAL_ROUND_ID，所以节点从 Leader 接收到的任何慢速 Accept 消息都将始终导致 Nack。

Acceptor 或 Stewart 都没有特殊的逻辑。以及领导者上的最小特殊逻辑（即选择一个非常低的 INITIAL_ROUND_ID）。

请注意，如果我们将 OP 的问题更改一个字符，那么 OP 的自我回答是正确的：Nack。

  • 接收：准备（N）
  • 回复：承诺（N，空）
  • 接收：接受！（N，V1）
  • 回复：接受（N，V1）
  • 接收：接受！（N-1，V2）
  • 回复：Nack(N, V1)

但就目前而言，他的回答打破了 Paxos 算法；应该是接受！

  • 接收：准备（N）
  • 回复：承诺（N，空）
  • 接收：接受！（N，V1）
  • 回复：接受（N，V1）
  • 接收：接受！（N+1，V2）
  • 回复：接受！（N+1，V2）
于 2012-04-11T21:45:12.840 回答
0

Multi-Paxos 的正确性取决于领导者（即提议者）在连续 Paxos 实例之间不发生变化的要求。来自兼职议会第 3.1 节（多法令议会协议）：

从逻辑上讲，议会协议 [aka Multi-Paxos] 为每个法令编号使用了完整的 Synod 协议 [aka Paxos] 的单独实例。但是， 为所有这些实例选择了一位总统 [aka 提议者/领导者]，并且他只执行了协议的前两个步骤一次。
[添加的重点是我的。]

因此，Multi-Paxos 假设您描述的情况——当第二个提议者上线并相信他是（并且一直是）领导者时——永远不会发生。如果这种情况可能发生，那么不应该使用 Multi-Paxos。关于第二种可能性——当第二个提议者Prepare没有到达接受者时——第二个提议者已经发送了一个事实Accept!意味着它之前发送了一个Prepare由Promised法定人数的接受者。由于接受者已经在轮次中向第一个提议者承诺N，那么第二个提议者Prepare必须在轮次之前发送出去N。因此，决赛Accept!(N+1,V2)必须有一个小于 N的计数器。

编辑：还应该注意的是，这个版本的协议对拜占庭失败并不健壮：

[Paxon 议会的协议] 不容忍任意的恶意故障，也不保证限时响应。
—<em>兼职议会，第 4.1 节

于 2011-05-10T18:48:16.003 回答
0

也许更简单的答案是观察当 Prepare(N+1) 命令被不包括相关接受者的多数人接受时就是这种情况。

详细说明：一旦领导者知道某个多数已承诺（N+1），它就会向所有接受者发送接受（N+1，x），即使其他一些多数接受者回复接受（N+1）然后已经达成共识。

这不是那么不寻常的情况。

于 2016-09-26T09:22:53.463 回答
-2

（回答我自己的问题。）

我目前的理解是我不应该接受 N+1 中的值（即根本不回答或发送 NACK），从而迫使领导者可能用 Prepare 开始另一轮（如果大多数人尚未达成共识） . 收到 Prepare(N+2) 后，我会回复 Promise(N+2, V1) 并照常继续。

于 2011-05-12T08:46:20.863 回答