1

我读了这篇关于 Paxos paxos 价值选择的帖子， 但我仍然不清楚。假设我们第一次运行 Paxos，Proposer 发送 Prepare，Acceptors 回复 (null, null)，因为他们没有学到任何值，所以 Proposer 同意自己的值并将其发送给他们接受的接受者。让我感到困惑的是，当 Proposer 收到 Promise-acks 并需要发送 Accept 消息时：

如果任何 Acceptor 之前接受过任何提案，那么他们将把他们的值发送给 Proposer，Proposer 现在必须将其提案的值设置为与 Acceptor 报告的最高提案编号相关联的值。（来自维基百科）

我不明白——选择“与接受者报告的最高提案编号相关的值”有什么意义？有人可以举个例子来解释一下吗？

4

1 回答 1

2

在许多分布式协议和无锁/无等待算法中，一个参与者将完成另一个参与者可能尚未完成的工作。Paxos 中的提议者将尽可能完成其他提议者的工作。（这不仅仅是为了排除其他提议者。）如果原始提议者或某些接受者在算法过程中变得不可用，这非常重要。

例如，最初的 Proposer (Paul) 发送了他的 Prepares 和 Accepts，但在将 accept 发送给一个接受者 (Art) 之前就死了。大多数接受者都接受了值（A），因此选择了该值，但整个系统可能对此一无所知。随之而来的是另一位提议者佩吉。她发出了自己的建议，并从亚当那里得知值 A 已被某人接受。请注意，它可能是也可能不是多数。为了安全起见，她将 A 送回去，现在 Art 知道了价值。

Paul            Alice Adam Art            Peggy
 |-propose(1)--->|---->|--->|
 |<----ack(_,_)--|-----|----|
 |-accept(A,1)-->|---->|    X               +
 X               |<----|<---|<---propose(2)-|
                 X     |------ack(A,1)----->|
                            |-ack(_,_)----->|
                 |<----|<---|<--accept(A,2)-|
                 |-----|----|-ack---------->|

你可以看到这里至少发生了两件事：在准备阶段，Peggy学习到了接受的值；在接受阶段，她将选择的值传播给其余的接受者。

如上例所示，该值不必被大多数接受者接受。但 Peggy 只需要等待大部分准备确认，然后才能发送她的接受消息。这是因为大多数接受的答案将始终包含所选值。

（注意，如果 Peggy 没有发送值 A，她会更改选择的答案，这违反了共识不变量。）

让我们再举一个例子，prepare-ack 返回多个值：(A,1) 和 (B,2)。我们可以从这个场景中做出一些推论。

  1. (B,2) 的存在意味着大多数接受者已经确认了一个 prepare(2) 消息，因此
  2. 不太可能选择 A（但并非不可能），因为大多数接受者会拒绝接受（A，1）消息。
  3. (B,2) 的存在也意味着B可能已被大多数受体选择。提议者在收到接受确认之前不会确定。

更新：回答评论中的几个问题。

客户在这一切中扮演什么角色？

这取决于应用程序。我维护的 Paxos 应用程序由两种类型的外部事件驱动：时间和客户端写入请求。客户端请求写入数据库；服务器使用 Paxos 来复制和同意写入；然后将结果发送回客户端。我的应用程序中的客户端根本不知道 Paxos，也不参与协议。

在其他应用程序中，客户端可以扮演提议者的角色。

为什么 Peggy 在准备阶段之后不使用她自己的值？

首先，请注意 Peggy 只等待简单的大多数接受者 [ ceil( N/2 )] 响应。这意味着ceil( N/2 ) - 1Peggy 不知道接受器的结果。这个数字比简单多数少一。

如果 Peggy 从准备阶段接收到一个值，她必须假设其他主机也具有该值。这将通过简单多数的阈值，这意味着该值可能已由多数选择。如果 Peggy使用她自己的值应该可能（有时会）违反共识不变量，即一旦选择了一个值，则始终选择相同的值。

为什么 Peggy 使用与准备阶段返回的最高值关联的值？

这个问题的答案就在更新的正上方，她考虑了准备阶段返回的多个值。基本上，她假设最高返回值已被大多数接受者接受；并且大多数接受者将拒绝任何具有较低round-id的值（他们会）。

于 2013-04-21T22:10:03.580 回答