关于Paxos实施的问题

Question

我正在使用维基百科中提供的文档在集群模拟器应用程序中实现Paxos .不幸的是,它留下了几个可以解释的门,并没有提供关于关键实施问题的大量信息.目前还不清楚和不完整.

• 假设一个簇分为3个区域,每个区域包含3个节点(总共= 9个节点).如果地区之间的沟通中断,会发生什么？任何领导者都无法达到法定人数(即5).

Paxos不会进入无限循环吗？我想如果一个人无法与至少一个法定数量的节点通信,就不应该发起Paxos.

• 1B阶段:" 如果提案数N大于以往任何建议时,则每个接受者承诺不接受建议小于N,并把它最后接受了价值为这种情况下,以投保人 ".

什么是"它接受的最后价值"？来自提议者的任何先前提案编号是什么？在这种情况下,'实例'究竟是指什么？

• 在阶段1a:是否包含与准备消息达成一致的值,或者是否延迟到接受!信息？或者它确实重要？

• 在阶段2a:' 如果任何接受者已经接受了值,则领导者必须选择具有最大提议号N '的值.

这里有什么价值？是提案编号吗？我不相信,但这句话不清楚.

• 在阶段2a:'否则,提议者可以自由选择任何值'.这是什么意思？什么价值？对于提案号码？

• Paxos似乎依赖于增加的N(提案号)值来运作？它是否正确？

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

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

Answer 1

什么是实例？

Paxos中的术语有点不直观.

• 一个实例是选择算法一个值.
• 甲轮指提议者的阶段1 + 2 A相节点的单次尝试可以有多个轮在一个实例的Paxos的.所有节点上的每个实例的圆形id是全局唯一的.这有时称为提案编号.
• 节点可以承担多个角色; 最值得注意的是Proposer和Acceptor.在我的回答中,我假设每个节点都承担两个角色.
• 阶段1也称为准备阶段.
  • 在阶段1a中,提议者向接受者发送准备!(roundId)消息
  • 在阶段1b中,接受者回复Promise!(roundId,value)或PrepareNack!()
• 阶段2也称为接受阶段.
  • 在阶段2a中,Proposer向Acceptors发送Accept!(roundId,value)消息
  • 在阶段2b中,接受者以Accepted!(...)或AcceptNack回复!()

假设一个簇分为3个区域,每个区域包含3个节点(总共= 9个节点).如果地区之间的沟通中断,会发生什么？任何领导者都无法达到法定人数(即5).

Paxos要求您至少可以达到法定人数(在您的情况下为5个节点).选择三个区域的解决方案; 在这三个地区之间有两个网络分区是非常坏的消息.我还使用了一个版本的Paxos,可以将节点成员资格从一个实例更改为下一个实例.这对分区和节点故障很有用.

Paxos不会进入无限循环吗？

Paxos的天真实现不能保证终止,因为多个节点可以跳跃准备阶段.有两种方法来解决这个问题.一种是在开始新的准备阶段之前进行随机退避.第二种方法是将所有请求路由到指定的领导者,该领导者充当提议者(领导者由Paxos实例选择.参见多篇文章)

在阶段1b:'如果提议编号N大于任何先前的提议,则每个>> Acceptor承诺不接受小于N的提议,并将其最后接受的值>>此实例发送给提议者'.

什么是"它接受的最后价值"？来自提议者的任何先前提案编号是什么？

当节点收到来自Proposer的Accept!(roundId,value)消息并且它未承诺不接受该值(由于Prepare!(higherRoundId)消息),它存储值和roundId(我将叫他们acceptedValue和acceptedRoundId).由于后续的Accept!(...)消息,它可能会覆盖这些消息.

当节点从Proposer收到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),并可以选择任何值发送给接受者.

注意:这里的提案号与roundId相同.

在阶段2a:'否则,提议者可以自由选择任何值'.这是什么意思？什么价值？对于提案号码？

这是您希望达成共识的价值.这通常是跨分布式系统的状态更改,可能由客户端请求触发.

Paxos似乎依赖于增加的N(提案号)值来运作？它是否正确？

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

圆形ID(也就是提议编号)应该增加,并且在所有节点上每个实例必须是唯一的.Paxos论文假设您可以这样做,因为实现它是微不足道的.这是一个在所有节点上产生相同结果的方案:

1. 假设有M个节点参与Paxos实例.
2. 按字典顺序对所有节点排序.index [node]是此排序列表中节点的索引.
3. 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
    }
}