关于Paxos实现的问题 [英] Questions about Paxos implementation

问题描述

我正在集群模拟器应用程序中实施Paxos，使用维基百科一>。不幸的是，它有几门可以解释，并没有提供关键实施问题的很多信息。不清楚和不完整。

I am implementing Paxos in a cluster simulator application, using the documentation available in Wikipedia. Unfortunately, it leaves several doors open to interpretation and does not provide much information on key implementation issues. It is unclear and incomplete.

• 假设一个集群分为3个区域，每个区域包含3个节点（总共9个节点）。如果区域之间的沟通破裂会怎么样？没有任何领导可以达到法定人数（这是5）。

Paxos是不是进入无限循环？如果不能与至少一个节点通信，我不应该启动Paxos。

Isn't Paxos going to enter an infinite loop? I guess one should not initiate Paxos if one cannot communicate with at least a quorum of nodes.

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

• 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'.

什么是接受的最后一个值？以前提案人的提案号码是否过去？
在这种情况下，实例是什么意思？

What is 'the last value it accepted'? Is it any previous proposal number from the proposer? What does 'instance' refer to exactly in this case?

• 在阶段1a中：是否包含值同意准备信息或是延期到接受！信息？或者它是否重要？

• 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?

在阶段2a：'如果任何接受者已经接受了一个值，领导者必须选择一个

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.

• 在第2a阶段：否则，投标人可以自由选择任何值。这是什么意思？一个值为什么？对于提案号码？

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

Paxos似乎依靠N（提案号）的价值增加工作吗？这是正确的吗？

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

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

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

PS：我没有足够的声誉创建一个Paxos标签（任何志愿者

P.S.: I don't have enough reputation to create a 'Paxos' tag (any volunteer?)

推荐答案

什么是实例？

What is an instance?

Paxos的命名有点不直观。

The nomenclature in Paxos is a little unintuitive.

• 一个实例是用于选择一个值的算法。


• 一个轮是指一个提议者单次尝试阶段1 +阶段2节点可以在Paxos的实例中具有多个轮回。所有节点上的每个实例的round id是全局唯一的。这有时称为提案编号。


• 节点可能承担多个角色;最着名的是提案者和接受者。在我的答案中，我将假设每个节点都承担两个角色。


• 阶段1也称为准备阶段。
  
• 
  
• 在阶段1a中，投标人将一个Prepare！（roundId）消息发送给接受者


• 在第1b阶段，承诺（RoundId，value）或PrepareNack！（）

• An instance is the algorithm for choosing one value.
• A round refers to a proposer's single attempt of a Phase 1 + Phase 2. A node can have multiple rounds in an instance of Paxos. A round id is globaly unique per instance across all nodes. This is sometimes called proposal number.
• A node may take on several roles; most notably Proposer and Acceptor. In my answers, I'll assume each node takes on both roles.
• Phase 1 is also known as the Prepare phase.
  • In Phase 1a, a Proposer sends a Prepare!(roundId) message to the Acceptors
  • In Phase 1b, the Acceptors reply with either Promise!(roundId, value) or PrepareNack!()
  
  
  • 在阶段2a中，投标人向Acceptors
  
  
  • 发送Accept！（roundId，value）消息。在阶段2b中，回复与Accepted！（...）或AcceptNack！（）
  
  

  
  

  假设一个集群分为3个区域，每个区域包含3个节点（总共9个节点）。如果区域之间的沟通破裂会怎么样？没有任何领导可以达到法定人数（这是5）。

  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，它可以将节点成员资格从一个实例更改为下一个实例。这对于分区和节点失败是有用的。

  Paxos requires you can get at least a quorum (5 nodes in your case). Go with your solution of three regions; having two network partitions between the three regions is very bad news. I also use a version of Paxos which can change node membership from one instance to the next. This is useful for partitions and node failure.

  
  

  Paxos是否会进入无限循环？

  Isn't Paxos going to enter an infinite loop?

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

  A naive implementation of Paxos is not guaranteed to terminate because multiple nodes can leap-frog Prepare phases. There are two ways of getting around this. One is to have a random backoff before starting new Prepare phases. The second is to route all requests to a designated leader, that acts as proposer (The leader is chosen by a Paxos instance. See also Multi-paxos)

  
  

  
  

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

  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'.

  什么是'接受的最后一个值'？是否有来自提案者的任何以前的提案号？

  What is 'the last value it accepted'? Is it any previous proposal number from the proposer?

  当节点从Proposer收到一个Accept！（roundId，value） em>和它没有答应不接受该值（由于Prepare！（higherRoundId）消息），它存储该值和roundId（我将其称为 acceptedValue 和 acceptedRoundId ）。由于后续的Accept！（...）消息，可能会写入这些消息。

  When a node receives an Accept!(roundId, value) message from a Proposer and it hasn't promised to not accept the value (due to a Prepare!(higherRoundId) message), it stores the value and the roundId (I'll call them acceptedValue and acceptedRoundId). It may write over these due to subsequent Accept!(...) messages.

  当一个节点从一个Proposer收到一个Prepare！（roundId）消息时，它会存储roundId作为 promiseRoundId = max（roundId，promiseRoundId）。然后它将一个 Promise！（acceptedRoundId，acceptedValue）发回提交者。注意：如果一个节点没有收到一个Accept！（...）消息，它将回复 Promise！（null，null）。

  When a node receives a Prepare!(roundId) message from a Proposer, it stores roundId as promiseRoundId = max(roundId, promiseRoundId). It then sends a Promise!(acceptedRoundId, acceptedValue) back to the Proposer. NB: if a node hasn't received an Accept!(...) message, it replies with Promise!(null, null).

  
  

  在阶段1a：一个是否包含与准备消息同意的值，或者被推迟到接受！信息？或者它有关系吗？

  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?

  没有必要发送它。我没有。

  There is no need to send it. I don't.

  
  

  在阶段2a中：如果任何接受者已经接受了一个值，领导者必须选择一个值最高提案号码N'。

  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.

  该值是算法达成共识的实际数据。我将重新表述为

  The value is the actual data the algorithm is reaching consensus on. I'll rephrase this to

  要启动接受阶段，投标人必须根据准备阶段的结果选择要接受的值。如果任何Acceptor使用Promise（roundId，value）回复，则Proposer必须使用与最高roundId相关联的值。否则，投标人只收到承诺（null，null），并可以选择任何值发送给接受者。

  注意：这里的提案号是相同的事情，如roundId。

  NB: Proposal number here is the same thing as roundId.

  
  

  在阶段2a：否则，投标人可以自由选择任何值。这是什么意思？一个值为什么？对于提案号码？

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

  这是您想达成共识的价值。这通常是分布式系统的状态变化，可能是由客户端请求引发的。

  This is the value you want to have consensus on. This is typically a state change across the distributed system, perhaps triggered by a client request.

  
  

  Paxos似乎依赖于N值越来越大（提案号）上班吗？这是否正确？

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

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

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

  圆形ids（又称提案编号）应该增加，必须在所有节点上都是唯一的。 Paxos纸假设你可以做到这一点，因为它是微不足道的。这是一个在所有节点上产生相同结果的方案：

  Round ids (aka proposal numbers) should be increasing and must be unique per instance across all nodes. The Paxos paper assumes you can do this because it is trivial to achieve. Here's one scheme that produces the same results on all nodes:

  
  
  1. 说有M个节点参与了Paxos的实例。
     
  2. 按字典顺序排列所有节点。 index [node]是此排序列表中节点的索引。
  
  
  3. roundId = i * M +索引[node] 其中我是这个节点开始的第i个循环（这是每个paxos实例的每个节点唯一的，并且单调增加）。
  
  
  1. Say there are M nodes participating in an instance of Paxos.
  2. Sort all the nodes lexicographically. index[node] is the index of a node in this sorted list.
  3. roundId = i*M + index[node] where i is the ith round this node is starting (that is i is unique per node per paxos instance, and is monotonically increasing).

  或者在伪代码中（显然缺少一些主要的优化）：

  Or in pseudo-code (which is clearly lacking a few major optimizations):

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

  这篇关于关于Paxos实现的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！