implementation - 关于Paxos实现的问题

Question

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

假设一个集群分为 3 个区域，每个区域包含 3 个节点(总共 = 9 个节点)。如果区域之间的通信中断会怎样？任何领导者都无法达到法定人数(即 5)。

Paxos是不是要进入无限循环了？我想如果不能与至少法定人数的节点通信，就不应该启动 Paxos。

在阶段 1b 中:'如果提案编号 N 大于任何先前的提案，则每个 Acceptor promise 不接受小于 N 的提案，并发送 它上次接受的值 为 此实例 给提案人”。

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

在阶段 1a:是否包含与 Prepare 消息达成一致的值，或者是否将其推迟到 Accept!信息？或者有关系吗？

在阶段 2a 中:'如果任何一个接受者已经接受了一个值，领导者必须 选择一个值 具有最大提案数 N'。

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

在阶段 2a:“否则，提议者可以自由选择任何值”。这是什么意思？有什么值(value)？对于提案编号？

Paxos 似乎依赖于 N(提案数)的递增值来工作？这样对吗？

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

PS:我没有足够的声誉来创建“Paxos”标签(任何志愿者？)

Answer 1

What is an instance?

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

安 实例是选择一个值的算法。

A 圆形是指提议者在第 1 阶段 + 第 2 阶段的单次尝试。一个节点在一个 Paxos 实例中可以有多个轮次。轮 ID 在所有节点上的每个实例都是全局唯一的。这有时称为 提案编号 .

一个节点可以承担多种角色；最显着的是提议者和接受者。在我的回答中，我将假设每个节点都扮演两个角色。

阶段 1 也称为准备阶段。

在阶段 1a 中，Proposer 向 Acceptor 发送 Prepare!(roundId) 消息

在阶段 1b，接受者回复 Promise!(roundId, value) 或 PrepareNack!()

阶段 2 也称为接受阶段。

在阶段 2a 中，Proposer 向 Acceptor 发送 Accept!(roundId, value) 消息

在阶段 2b 中，接受者回复 Accepted!(...) 或 AcceptNack!()

Assuming a cluster divided in 3 regions, each containing 3 nodes (total = 9 nodes). What happens if communication is broken between regions? There is no way any leader can reach quorum (which is 5).

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

Isn't Paxos going to enter an infinite loop?

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

In Phase 1b: 'If the proposal number N is larger than any previous proposal, then each >>Acceptor promises not to accept proposals less than N, and sends the value it last accepted for >>this instance to the Proposer'.

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

当一个节点收到来自 Proposer 的 Accept!(roundId, value) 消息并且它没有 promise 不接受该值时(由于 Prepare!(higherRoundId) 消息)，它存储该值和 roundId(我将调用他们 acceptedValue 和 acceptedRoundId )。由于随后的 Accept!(...) 消息，它可能会覆盖这些。
当节点收到来自 Proposer 的 Prepare!(roundId) 消息时，它会将 roundId 存储为 promiseRoundId = max(roundId, promiseRoundId) .然后它发送一个 Promise!(acceptedRoundId, acceptedValue)回到提案人。注意:如果节点没有收到 Accept!(...) 消息，它会回复 Promise!(null, null) .

In Phase 1a: Does one include the value to agree on with the Prepare message or is this deferred to the Accept! message? Or it does matter?

没有必要发送它。我不。

In Phase 2a: 'If any of the Acceptors have already accepted a value, the leader must Choose a value with the maximum proposal number N'.

What is value here? Is it the proposal number? I believe not, but this phrase is unclear.

该值是算法正在达成共识的实际数据。我将改写为
要开始接受阶段，提议者必须根据准备阶段的结果选择一个要接受的值。如果任何 Acceptor 回复 Promise(roundId, value)，Proposer 必须使用与最高 roundId 关联的值。否则，Proposer 只收到 Promise(null, null)，并且可以选择任何值发送给接受者。
注意:这里的提案编号与 roundId 相同。

In Phase 2a: 'Otherwise, the Proposer is free to choose any value'. What does this mean? A value for what? For the proposal number?

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

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

The wikipedia entry does not discuss the initial values a node should set before starting to participate in Paxos. What are these?

轮次 id(又名提案编号)应该增加，并且在所有节点中每个实例必须是唯一的。 Paxos 论文假设您可以做到这一点，因为实现起来很简单。这是在所有节点上产生相同结果的一种方案:

假设有 M 个节点参与一个 Paxos 实例。

按字典顺序对所有节点进行排序。 index[node] 是此排序列表中节点的索引。

roundId = i*M + index[node]其中 i 是该节点开始的第 i 轮(即每个节点每个 paxos 实例的 i 是唯一的，并且是单调递增的)。

或者在伪代码中(显然缺少一些主要优化):

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
    }
}