关于Paxos实现的问题

Question

我正在集群模拟器应用程序中实现 Paxos，使用 Wikipedia 中提供的文档。不幸的是，它留下了一些解释的空间，并且没有提供关于关键实施问题的太多信息。这是不清楚和不完整的。

• 假设集群分为 3 个区域，每个区域包含 3 个节点（总共 = 9 个节点）。如果区域之间的通信中断会发生什么？任何领导者都不可能达到法定人数（即 5）。

Paxos不是要进入死循环了吗？我想如果一个人无法与至少法定数量的节点进行通信，那么就不应该启动 Paxos。

• 在第 1b 阶段：“如果提案编号 N 大于任何先前的提案，则每个接受者承诺不接受小于 N 的提案，并发送它最后接受的值将此实例发送给提议者'。

什么是“它接受的最后一个值”？是提案人之前的提案编号吗？ 在这种情况下，“实例”到底指的是什么？

• 在第 1a 阶段：是否包含与“准备”消息一致的值，或者是否推迟到“接受”消息！信息？或者它确实重要吗？

• 在第 2a 阶段：“如果任何接受者已经接受了某个值，则领导者必须选择一个具有最大提案编号 N 的值”。

这里的价值是什么？是提案编号吗？我相信不是，但这句话不清楚。

• 在阶段 2a：“否则，提案者可以自由选择任何值”。这意味着什么？有什么价值？对于提案编号？

• Paxos 似乎依赖 N（提案数）不断增加的值来工作？这是正确的吗？

• 维基百科条目没有讨论节点在开始参与 Paxos 之前应设置的初始值。这些是什么？

PS：我没有足够的声誉来创建“Paxos”标签（有志愿者吗？）

Answer 1

什么是实例？

Paxos 中的命名法有点不直观。

• 实例是选择一个值的算法。
• 一轮轮次是指提议者对阶段 1 + 阶段 2 的单次尝试。一个节点可以在 Paxos 的实例中进行多个轮次。轮次 ID 对于所有节点上的每个实例都是全局唯一的。这有时称为提案号。
• 一个节点可以承担多种角色；最值得注意的是提议者和接受者。在我的回答中，我将假设每个节点都扮演这两个角色。
• 第 1 阶段也称为准备阶段。
  • 在第 1a 阶段，提案者向接受者发送一条“Prepare!(roundId)”消息
  • 在第 1b 阶段，接受方回复 Promise!(roundId, value) 或PrepareNack!()
• 第 2 阶段也称为 Accept 阶段。
  • 在阶段 2a，提案者向接受者发送 Accept!(roundId, value) 消息
  • 在第 2b 阶段，接受方回复 Accepted!(...) 或 AcceptNack!()

假设集群分为 3 个区域，每个区域包含 3 个节点（总共 = 9 个节点）。如果区域之间的通信中断会发生什么？任何领导者都不可能达到法定人数（即 5）。

Paxos 要求您至少可以获得法定人数（在您的情况下为 5 个节点）。选择您的三个区域的解决方案；三个区域之间有两个网络分区是一个非常坏的消息。我还使用 Paxos 的一个版本，它可以将节点成员资格从一个实例更改为下一个实例。这对于分区和节点故障很有用。

Paxos不是要进入无限循环了吗？

Paxos 的简单实现并不能保证终止，因为多个节点可以跳过准备阶段。有两种方法可以解决这个问题。一是在开始新的准备阶段之前进行随机退避。第二种是将所有请求路由到指定的领导者，该领导者充当提议者（领导者由 Paxos 实例选择。另请参阅 Multi-paxos）

<块引用>

在第 1b 阶段：“如果提案编号 N 大于任何先前的提案，则每个>>接受者承诺不接受小于 N 的提案，并发送>>此实例最后接受的值给提议者。

“它接受的最后一个值”是什么？是提案人之前的提案编号吗？

当节点从提议者接收到 Accept!(roundId, value) 消息并且它没有承诺不接受该值（由于准备！(higherRoundId) 消息）时，它会存储该值和 roundId（我将它们称为 acceptedValue 和 acceptedRoundId）。由于后续的 Accept!(...) 消息，它可能会覆盖这些内容。

当节点从提议者接收到Prepare!(roundId)消息时，它将roundId存储为promiseRoundId = max(roundId,promiseRoundId)。然后，它将一个 Promise!(acceptedRoundId,acceptedValue) 发送回提议者。注意：如果节点没有收到 Accept!(...) 消息，它将回复 Promise!(null, null)。

在第 1a 阶段：是否包含与“准备”消息一致的值，或者是否推迟到“接受”消息！信息？还是说这很重要？

无需发送。我不知道。

在第 2a 阶段：“如果任何接受者已经接受了某个值，则领导者必须选择一个最大提案数为 N 的值”。

这里的价值是什么？是提案编号吗？我相信不是，但这句话不清楚。

该值是算法正在达成共识的实际数据。我将其改写为

要开始接受阶段，提案者必须根据准备阶段的结果选择要接受的值。如果任何 Acceptor 回复 Promise(roundId, value)，则 Proposer 必须使用与最高 roundId 关联的值。否则，Proposer 只收到 Promise(null, null)，并且可以选择任何值发送给接受者。

注意：这里的 Proposal 编号与 roundId 相同。

在阶段 2a：“否则，提案者可以自由选择任何值”。这意味着什么？有什么价值？对于提案编号？

这是你想要达成共识的价值观。这通常是分布式系统中的状态更改，可能由客户端请求触发。

Paxos 似乎依赖 N（提案数）不断增加的值来工作？这是正确的吗？

维基百科条目没有讨论节点在开始参与 Paxos 之前应设置的初始值。这些是什么？

回合 ID（又名提案编号）应该不断增加，并且必须在所有节点上的每个实例都是唯一的。 Paxos 论文假设您可以做到这一点，因为实现起来很简单。这是一种在所有节点上产生相同结果的方案：

1. 假设有 M 个节点参与 Paxos 实例。
2. 按字典顺序对所有节点进行排序。 index[node] 是此排序列表中节点的索引。
3. roundId = i*M + index[node] ，其中 i 是该节点开始的第 i 轮（即 i 对于每个 paxos 实例的每个节点都是唯一的，并且单调递增）。

或者用伪代码（显然缺乏一些主要的优化）：

define runPaxos( allNodesThisPaxosInstance, myValue ) {
    allNodesThisPaxosInstance.sort()
    offset = allNodesThisPaxosInstance.indexOf( thisNode )
    for (i = 0; true; i++) {
        roundId = offset + i * allNodesThisPaxosInstance.size()
        prepareResult = doPreparePhase( roundId )
        
        if (!prepareResult.shouldContinue?)
            return

        if (prepareResult.hasAnyValue?)
           chosenValue = prepareResult.valueWithHighestRoundId
        else
            chosenValue = myValue
        
        acceptResult = doAcceptPhase( roundId, chosenValue )
        
        if (!acceptResult.shouldContinue?)
            return
    }
}

Answer 2

我找到了以下文档解释Paxos 的更多细节。我已经相应地更新了维基百科条目。

我能找到的问题的答案是：

Paxos不是要进入无限了吗
循环？

Paxos 仅在至少有法定数量的节点可以相互通信时才起作用（在我们的例子中为 5）。因此，如果一个节点无法与至少法定数量的节点通信，则它不应该尝试 Paxos。

“它接受的最后一个值”是什么？

它是最后接受的命题编号和对应的值。

在这种情况下，“实例”到底指什么？

它指的是接受者。

其中是否包含达成一致的值
与准备消息或者是这样的
推迟到接受！信息？或者它
有关系吗？

该值不包含在Prepare消息中，而是留给Accept Request消息。

这里的价值是什么？是提案吗
数字？我不信，但是这句话
不清楚。

'否则，提案者可以自由地
选择任何值'。这是做什么的
意思是？有什么价值？对于
提案编号？

如果接受者已经接受了提案者的提案，他们可以返回相应的提案编号和值，否则什么也不返回。

第二个问题落下，因为维基百科条目具有误导性。人们可以为给定的提案选择任意值，或者从与先前接受的提案相对应的值中导出它。

Paxos 似乎依赖 N（提案数）不断增加的值来工作？这是正确的吗？

是的。提案者 p 需要不断增加其提案的数量。

维基百科条目没有讨论节点在开始参与 Paxos 之前应设置的初始值。这些是什么？

节点应保留其最后接受的提案编号，并最终保留相应的值。他们应该坚持下去。首次连接时，给定提议者的初始提议编号应为空（或任何等效值）。

Answer 3

Paxos seems to rely on an increasing value of N (proposal number) to work? Is this correct?

每个提议者都有稳定的存储。每个提案者都会记住（在稳定存储中）其尝试发布的编号最高的提案，并以比其已使用的提案编号更高的提案编号开始第一阶段。