paxos值选择 [英] paxos value choice

查看：441
本文介绍了paxos值选择的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我已经在wiki页面和论文（paxos变得简单）上阅读过paxos。但是，我仍然对一些细节感到困惑：


  1. 在阶段1a中，提议者是否包含它想要的值


  2. 在阶段1b中，acceptor应该返回之前接受的值（如果有的话）。什么是价值的生命时间？ IOW，什么时候被接受，什么时候被覆盖/丢弃？


。 IIUC，在第一次接受后，受体应该总是具有以前接受的价值。它如何决定它是否应该在下一个承诺（1b）阶段返回？





更新2以便与@MichealDeardeuff更好地讨论：



我对paxos的理解：


通常在paxos工作流中，以前接受的值。并且当回答准备请求时，它将在promise响应中发送回值。提议者需要检查该值是否与自己在最后一轮中提出的值相同。如果不是，则提议器继续使用由acceptor返回的值发送accept请求。如果是，则提议者继而发送接受请求，其具有其在当前轮中发送的值。


以上理解是否正确？



如果不正确，请解释原因吗？



如果是正确的，我很困惑，因为paxos协议没有明确说这样。它只声明：


其中v是响应中编号最高的提案的值，或者是响应报告没有


但是，根据我的理解，提议者需要检查acceptor返回的值是否与 回合中提出的同一提议者。如果是，即使在承诺响应中有最高编号的提议的值，提议者仍然可以选择它想要的任何值，如同没有受体返回的值。



这是我想看看是否有任何参考来支持理解的原因。



非常感谢！

解决方案


在阶段1a中，提案者是否包含在提案中选择接受者的值？


提案者不需要发送它打算选择的值，直到2a阶段。另请参见我的回答以前的问题。


在阶段1b中，acceptor应该返回之前接受的值。什么是价值的生命时间？ IOW，何时被视为已接受，何时被覆盖/删除？


从除非接受方答应不接受它，否则接受方应该接受所有值。也就是说，在其发送的最后一个响应中接受round-id大于或等于round-id的任何值。



它必须接受任何其他值的原因是提议者可以发现（作为阶段1的结果）不同的值应该被选择;或者已经被选择;然后将 this 值广播给所有的接受者。当有多个提案者和/或网络分区时，可能会出现这种差异。





更新回答注释。



当接受者接受一个值时，它保持该值直到接受另一个值。



在阶段1b中，Acceptor 始终发送它的值，允许Proposer整理出实际选择的值是什么。永远不会忘记其当前值。



收到接受者的承诺后，提议者可以看到系统。 （注意：它不一定是完整的或最新的视图。）



可能是不同的接受者接受了不同的值，提议者。因此，提议者选择具有最高轮回ID的值，并向所有接受者发送值。这是为什么允许接受者的值发生变化的原因。



注释中的问题是这打破了Paxos。



但是，在我开始举一个例子之前，让我强调，使用命名阶段和消息而不是1a，1b，2a来更容易地考虑Paxos ，2b。我通常将阶段命名为准备阶段和接受阶段。消息1a为Prepare，1b为Promise，2a为Accept，2b为Accepted。



现在，让我们假设一个人们经常给出的假设例子，打破了Paxos。
假设我们有三个Acceptors A1，A2和A3。 A1和A2在第1轮都接受值ABC，A3在第2轮选择XYZ（即来自不同的提议者）。我们可以看到A1和A2形成了多数，并且ABC已经被选择。



继续这个假设的例子，提议者发送Prepare（3）来自A2和A3的响应，即承诺（ABC @ 1）和承诺（XYZ @ 2）。 Proposer看到XYZ具有最高的轮次，并在接受阶段发送，在其他主机上覆盖ABC。和中提琴，Paxos坏了，对吧？



不。问题是与开始状态，这是不可能的。让我告诉你为什么。



首先，一些命题是Paxos正确运行的关键：



strong>命题A ：对于A1和A2具有值ABC @ 1，提议者必须已经发送了Accept（ABC @ 1），这意味着它必须已经接收到多数Promises以响应发送Prepare（1）



命题B ：对于A3的值为XYZ @ 2，提案者必须已发送Accept（XYZ @ 2）



现在证明：



情况1 ：A1和A2已经具有值ABC @ 1.通过命题B，对于A3具有值XYZ @ 2它必须已经从受体。由于值ABC是大多数接受者，因此至少其中一个必须已发送Promise（ABC @ 1）。 1是最高的回合ID，提议者必须选择值ABC并发送Accept（ABC @ 2）。但是没有，它发送Accept（XYZ @ 2）。一个矛盾。



情况2 ：A3已经具有XYZ @ 2的值（记住，第二轮可以在第一轮： id仅仅按照请求者单调递增。）通过命题A，对于A1和A2具有值ABC @ 1，提议者必须已经从接受者接收到大多数的承诺。同样，通过命题B，对于A3来说，它也必须已经接收了多数的承诺。这意味着在集合{A1，A2}中必须至少有一个接受者承诺两次

：接受者首先发送Promise（1），然后发送Promise（2）。然后，当它收到消息接受（ABC @ 1），它必须已经拒绝它，因为它已经答应接受没有值早于2，但它没有拒绝它，因为它的值ABC @ 1.一个矛盾。 / p>

情况2b ：接受者首先发送Promise（2）。然后，当它接收到消息Prepare（1）时，它必须已经拒绝它，因为它已经答应了更高的轮次。但它显然不是因为，通过命题A，它发送Promise（1）。一个矛盾。



哇！



我希望这可以帮助你。





更新2 ：这是Paxos的伪python实现

 从itertools导入计数
从并发导入期货
 
 
 
类接受者（）：
 def __init __ self）：
 self.acceptedValue = None 
 self.acceptedRound = None 
 
 self.promisedRound = None 
 
 def onPrepare（self，message）： 
 if self.promisedRound> message.round：
 send（message.source，new Nack（））
 
 self.promisedRound = message.round 
 response = new Promise（round = self.acceptedRound，value = self.acceptedValue）
 send（message.source，response）
 
 def onAccept（self，message）：
 if self.promisedRound> message.round：
 send（message.source，new Nack（））
 
 self.acceptedValue = message.value 
 self.acceptedRound = message.round 
 send （message.source，new Accepted（））
 
 
 
 
类Proposer（）：
 
 def __init __（self，selfId， quorum）：
 self.quorum = quorum 
 self.id = selfId 
 
＃获取唯一的起始回合，
＃假设接受者和提议者在同一台主机上
 self.initialRound = sorted（quorum）.index（selfId）
 
 def suggest（self，value）：
建议选择一个值;返回选择的实际值
 
＃round对于提议者是唯一的
＃count（start，step）返回无限序列
用于计数循环（self.initialRound，len（self.quorum）） 
 promises = self.prepare（round）
 
如果不是promises：continue 
 
＃解释准备阶段结果，可能是None 
 selectedValue = max （promises，key = lambda p：p.round或-1）
 
 accepted = self.accept（round，selectedValue或value）
 
如果接受：返回值
 
 def prepare（self，round）：
驱动准备阶段。返回接受者的承诺或无
 
 message = new准备（round，source = self.id）
 respond = [] 
为self.quorum中的acceptor：
 responses.append（send（acceptor，message）））
 
＃等待结果
 promises = [] 
在futures.as_completed 
 if response.exception（）：continue＃message died 
 
 message = response.result（）
如果不是isinstance（message，Promise）：
＃消息;中止回合我们可能有一个多数，
＃但是这加快了情况下，当我们没有
返回无
 
 promises.append（message） 
 if（len（promises）> len（self.quorum）/ 2：
 return promises 
 
＃没有多数响应
返回None 
 
 def accept（self，round，value）：
驱动接受阶段。如果值被接受，则返回True
 
 message = new Accept（round，value）
 respond = [] 
为self.quorum中的acceptor：
响应。 append（send（acceptor，message）
 
＃等待结果
 accepted = 0 
用于futures.as_completed（响应）中的响应：
 if response.exception （）：continue＃message died 
 
 message = response.result（）
如果不是isinstance（message，Accepted）：
＃一个nack消息有多数，
＃但是这加快了我们没有的情况。
 return False 
 
 accept = accepted + 1 
如果接受> len （self.quorum）/ 2：
 return True 
 
＃没有大多数回应
 return False





更新3 从评论中回答更多问题。


...如果它是在最后一轮发送的相同值提议者，我们希望提议者忽略它（否则我们最终在死循环，对吗？）


（我假设忽略该值意味着提前退出循环。）



首先，请注意，当提议者收到大多数接受者确认已选择值的确认时，循环结束。因此，如果提议者发现自己正在进行后续准备阶段，则可以确定它与另一个提议者竞争或发生了某个网络分区。第二，请注意，如果只有一个接受者接受了一个值，那么prepare阶段会返回一个值，即使 （意味着该值可能未被多数接受。）



如果准备阶段产生的值，并且它与上一轮中看到的值相同，则应该继续使用Accept阶段，原因有几个。




  • 如果提议者提前退出循环，可能是另一个提议者失败了。这可能导致选择无值。

  • 如果它提前退出循环，那么另一个提议器是合理的， ;再次导致可能选择无值。

  • 如果发生实际上已选择的值，则可能并非所有节点都已接收该值（由于网络分区）或具有不同的值（由于与另一个提议者的争斗）。



另一方面，它是当两个或多个提议者之间存在争用和一些运气不佳时，Paxos可能进入无限循环。 （这是任何一致性算法的真实性，并且在任何一致性算法实际被发现之前由Liskov等人证实。）因此，理论说，但在实际系统中很容易解决：在每个后续回合中，暂停一段随机时间，让其他提案者有机会赢得比赛。当然，它仍然是可能的有一个无限循环，但它不可能发生在宇宙的生命中。


你有任何参考来支持这个论点吗？


我主要是根据自己的学习和经验。我是一个团队，开发和维护一个以Paxos为核心的系统。



以下是一些关于这个主题的好文章：



更新4 回答问题中的更新。



< >

通常在paxos工作流中，接受者应该总是具有以前接受的值。并且当回答准备请求时，它将在promise响应中发送回值。提议者需要检查该值是否与自己在最后一轮中提出的值相同。如果不是，请求者继续使用接受者返回的值发送接受请求。


好吧，到目前为止。但是提出者不需要在轮次之间保持状态。我们很快就会找出原因。


如果它是[相同的值]，则提议者继续发送接受请求 $ 。 由接受者，在接受阶段中必须使用具有最高轮次标识的那个。如果接受者返回了 no 值，则可以使用任何值：我的逻辑表明这将是客户端传递给请求者的值。



与 Paxos进行比较Made Simple （第6页）：


...其中v是最高编号的提案的值


（这是很难的术语开关这里Lamport使用术语编号的提案，在他们使用术语 round-id 的其他地方。有一个和相同的。）



假设提议者运行准备阶段，并在接受者之间看到这种状态。

  A1 A2 A3 
承诺：3？ 4 
 value @ round：x @ 3？ y @ 4

其中实际状态为

  A1 A2 A3 
 promise：3 4 4 
 value @ round：x @ 3 y @ 4 y @ 4

现在，假设它使用值y运行前一轮。 如果，此时允许选择任何值，则可以强制使用此状态：

  A1 A2 A3 
 value @ round：z @ 5 z @ 5 z @ 5

）覆盖所选择的值，违反了一致性的一致性属性（Viz，最多只能选择一个值）。

如果您希望这种行为，您不能使用一致的协议。您可以使用 ABD 等协议，或其他基于回合的注册表。或者您可以将Paxos视为在状态机中选择转换。换句话说，每次你想改变一个变量，你运行一个新的Paxos算法来选择转换。这是我的系统做的（我敢说最实用的Paxos系统）。



注意，ABD和基于轮回的寄存器的行为类似于Paxos，更简单，因为他们不必保证上面的一致性属性（一旦选择，总是选择）。但是基于Paxos的状态机允许对变量进行CAS操作。


I've read about paxos on wiki page and the paper (paxos made simple). However, I'm still confused by some details:

  1. In phase 1a, does the proposer include the value that it intends to choose in the proposal to acceptors?

  2. In phase 1b, acceptor is supposed to return the value that it accepted previously if any. what is the life time of the value? IOW, when is it considered accepted and when does it get overwritten/dropped?

Some updates about the life time question. IIUC, after the first acceptance, an acceptor should always have a previously accepted value at hand. How does it decide if it should return it in the next promise (1b) phase? Or when does it decide to forget the value?

Updates 2 to better discuss with @MichealDeardeuff:

I have bellow understanding for paxos:

Normally in a paxos workflow, an acceptor should always have a previously accepted value at hand. And when answering a prepare request, it will send the value back in the promise response. And the proposer need to check if the value is the same value as itself proposed in the last round. If it is not, the proposer proceeds to send accept request with the value returned by acceptor. If it is, the proposer then proceeds to send Accept request with the value it intended to send in current round.

Is above understanding correct?

If it is not correct, would you please explain why?

If it is correct, I am confused because the paxos protocol doesn't explicitly say so. It only states:

where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

However, to my understanding, the proposer need to check and see if the value returned by acceptor is the same value as the same proposer proposed in the last round. If it is, even though there is a value with the highest-numbered proposal among the promise responses, the proposer can still choose any value it wants as if there were no values returned by acceptors.

And that is the reason that I want to see if there is any reference to support the understanding.

Thanks very much!

解决方案

In phase 1a, does the proposer include the value that it intends to choose in the proposal to acceptors?

The proposer doesn't need to send the value it intends to choose until phase 2a. See also my answer to an earlier question.

In phase 1b, acceptor is supposed to return the value that it accepted previously if any. what is the life time of the value? IOW, when is it considered accepted and when does it get overwritten/dropped?

From my answer to another different question, "An acceptor should accept all values unless it has promised to not accept it." That is, it should accept any value with a round-id greater than or equal to the round-id in the last response it sent.

The reason it must accept any other value is that a proposer may discover (as a result of phase 1) that a different value should be—or already has been—chosen; it then broadcasts this value to all the acceptors. This discrepancy can happen when there are multiple proposers and/or during a network partition.

Update to answer the comment.

When an acceptor accepts a value, it holds on to that value until it accepts another value. (along with this it stores the round of the value).

In Phase 1b, the Acceptor always sends its value, allowing the Proposer to sort out what the actual chosen value is. It never forgets its current value. Ever.

After receiving the promises from the acceptors, the proposer has a nice view of the system. (Note: it is not necessarily a complete or up-to-date view.)

It could be that different acceptors have accepted different values due to some contention with a different proposer. So, the proposer chooses the value with the highest round id and sends that value to all the acceptors. This is why acceptors values are allowed to change.

The concern in the comments is that this breaks Paxos. Not so.

But, before I get into an example, let me stress that it's much easier to think about Paxos with named phases and messages instead of 1a, 1b, 2a, 2b. I typically name the phases the Prepare phase and the Accept phase. With message 1a as Prepare, 1b as Promise, 2a as Accept, and 2b as Accepted.

Now, let's take a hypothetical example that people often give, and which they think breaks Paxos. Suppose we have three Acceptors A1, A2, and A3. A1 and A2 have both accepted value ABC at round 1 and A3 has chosen XYZ at round 2 (ie. from a different proposer). We can see that A1 and A2 form a majority and that ABC has been "chosen."

Continuing along this hypothetical example, a proposer sends Prepare(3) and receives back responses from A2 and A3, viz Promise(ABC @ 1) and Promise(XYZ @ 2). The Proposer sees XYZ has the highest round, and sends that along in the Accept phase, overwriting ABC on the other hosts. And viola, Paxos is broken, Right?

No. The problem is with the start state, which is impossible. Let me show you why.

First, some propositions, which are key to Paxos running correctly:

Proposition A: For A1 and A2 to have the value ABC @ 1, a proposer must have sent Accept(ABC @ 1) which means it must have received a majority of Promises in response to sending Prepare(1).

Proposition B: For A3 to have the value XYZ @ 2, a proposer must have sent Accept(XYZ @ 2) which means it must have received a majority of Promises in response to sending Prepare(2).

And now the proof:

Case 1: A1 and A2 already have values ABC @ 1. By Proposition B, for A3 to have value XYZ @ 2 it must have received a majority of Promises from the acceptors. Since value ABC is on a majority of acceptors, then at least one of them must have sent Promise(ABC @ 1). With 1 being the highest round id, the proposer must have select the value ABC and sent Accept(ABC @ 2). But it didn't, it sent Accept(XYZ @ 2). A contradiction.

Case 2: A3 already has the value XYZ @ 2. (Remember, round 2 can come before round 1: the round id's are only monotonically increasing per proposer.) By Proposition A, for A1 and A2 to have value ABC @ 1, a proposer must have received a majority of Promises from the acceptors. Likewise, by Proposition B, for A3 to have it, too, must have received a majority of Promises. That means there must have been at least one acceptor in the set {A1, A2} that Promised twice.

Case 2a: The acceptor sent Promise(1) first, then Promise(2). Then when it received the message Accept(ABC @ 1), it must have rejected it because it has promised to accept no value earlier than 2. But it didn't reject it because it has the value ABC @ 1. A contradiction.

Case 2b: The acceptor sent Promise(2) first. Then, when it received the message Prepare(1), it must have rejected it because it had already promised for a higher round. But it clearly didn't because, by proposition A, it sent Promise(1). A contradiction.

Wow!

I hope this helps you out.

Update 2: Here's a pseudo-python implementation of Paxos

from itertools import count
from concurrent import futures



class Acceptor():
    def __init__(self):
        self.acceptedValue = None
        self.acceptedRound = None

        self.promisedRound = None

    def onPrepare(self, message):
        if self.promisedRound > message.round:
            send(message.source, new Nack())

        self.promisedRound = message.round
        response = new Promise(round=self.acceptedRound, value=self.acceptedValue)
        send(message.source, response)

    def onAccept(self, message):
        if self.promisedRound > message.round:
            send(message.source, new Nack())

        self.acceptedValue = message.value
        self.acceptedRound = message.round
        send(message.source, new Accepted())




class Proposer():

    def __init__(self, selfId, quorum):
        self.quorum = quorum
        self.id = selfId

        # get a unique starting round, 
        # assumes acceptors and proposers are on same hosts
        self.initialRound = sorted(quorum).index(selfId)

    def propose(self, value):
        "Propose a value to be chosen; returns actual value chosen"

        # round is always unique to a proposer
        # count(start, step) returns an infinite sequence
        for round in count(self.initialRound, len(self.quorum))
            promises = self.prepare(round)

            if not promises: continue

            # interpret the prepare phase results, may be None
            selectedValue = max(promises, key=lambda p: p.round or -1)

            accepted = self.accept(round, selectedValue or value)

            if accepted: return value

    def prepare(self, round):
        "Drive the Prepare phase. returns the promises from the acceptors or None"

        message = new Prepare(round, source=self.id)
        responses = []
        for acceptor in self.quorum:
            responses.append(send(acceptor, message)))

        # wait for the results
        promises = []
        for response in futures.as_completed(responses):
            if response.exception(): continue # message died

            message = response.result()
            if not isinstance(message, Promise):
                # A nack message; abort the round. We may have got a majority,
                # but this speeds up the case when we didn't.
                return None

            promises.append(message)
            if (len(promises) > len(self.quorum) / 2:
                return promises

        # No majority of responses
        return None

    def accept(self, round, value):
        "Drive the Accept phase. returns True iff the value was accepted"

        message = new Accept(round, value)
        responses = []
        for acceptor in self.quorum:
            responses.append(send(acceptor, message)

        # wait for the results
        accepts = 0
        for response in futures.as_completed(responses):
            if response.exception(): continue # message died

            message = response.result()
            if not isinstance(message, Accepted):
                # A nack message; abort the round. We may have got a majority,
                # but this speeds up the case when we didn't.
                return False

            accepts = accepts + 1
            if accepts > len(self.quorum) / 2:
                return True

        # No majority of responses
        return False

Update 3 To answer more questions from the comments.

…if it is the same value proposer sent in last round, we want proposer to ignore it (otherwise we end up in a dead loop, right?)

(I’m assuming that "ignoring" the value means exiting the loop early.)

First, please notice the loop ends when the proposer receives acknowledgement from a majority of the acceptors that a value has been chosen. So, if a proposer finds itself doing a subsequent Prepare phase, you can be sure that it is contending with another proposer OR some network partition happened. Second, please notice the prepare phase returns a value even if only one acceptor has accepted a value (meaning the value may not have been accepted by a majority.)

If the Prepare phase results in a value and it’s the same value it saw in the previous round, it should carry on with the Accept phase anyway for several reasons.

  • If the proposer quits the loop early, It may be that the other proposer has failed. This may result in no value being chosen.
  • If it exits the loop early, it is reasonable the other proposer, following the same algorithm has exited the loop too; again resulting in possibly no value being chosen.
  • If it so happens that the value actually had been chosen, it may be that not all of the nodes have received the value (due to network partition) or have a different value (due to that fight with the other proposer). It is good, then, to push the value to the nodes for durability sake.

On the other hand, it is possible for Paxos to go into an infinite loop when there is contention between two or more proposers and some bad luck. (This is true of any consensus algorithm and was proven by Liskov et al before any consensus algorithm was actually discovered.) So the theory says, but in practical systems it is easy to get around: on each subsequent round, pause for a random amount of time to let the other proposer have the chance of winning the race. Sure, it is still possible to have an infinite loop, but it unlikely to ever happen in the lifetime of the universe.

Do you have any reference to support the argument?

I speak mostly from my own learning and experience. I am on a team that develops and maintains a system built with Paxos at the core. I’ve also done extensive study on the subject.

Here are some good papers on the subject:

Update 4 Answering updates in the question.

Normally in a paxos workflow, an acceptor should always have a previously accepted value at hand. And when answering a prepare request, it will send the value back in the promise response. And the proposer need to check if the value is the same value as itself proposed in the last round. If it is not, the proposer proceeds to send accept request with the value returned by acceptor.

Okay, so far. But the proposer doesn't need to keep state between rounds. We'll soon find out why.

If it is [the same value], the proposer then proceeds to send Accept request with the value it intended to send in current round.

If any value is returned by an acceptor, the one with the highest round-id must be used in the Accept phase. If no value is returned by an acceptor, than any value may be used: my logic suggests this would be the value the client passed to the proposer.

Compare this with Paxos Made Simple (pg 6):

...where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

(It’s kind of hard that terminology switches between the papers. Here Lamport uses the term numbered proposals, elsewhere they he uses the term round-id. There are the one and the same.)

Suppose a proposer runs a prepare phase and sees this state among the acceptors.

             A1   A2  A3
promise:      3    ?   4
value@round:  x@3  ?  y@4

where the actual state is

              A1  A2  A3
promise:       3   4   4
value@round:  x@3 y@4 y@4

Now, suppose it had run the previous round with the value y. IF it is allowed to choose any value at this point, it could force this state:

              A1  A2  A3
value@round:  z@5 z@5 z@5

This overwrites the chosen value, violating the consistency property of consensus (Viz, At most one value can be chosen.).

If you want this kind of behavior, you cannot use a consensus protocol as is. You can use protocols like ABD, or other round-based register. Or you can think of Paxos as choosing a transition in a state machine. In other words, each time you want to change a variable you run a new Paxos algorithm to choose the transition. This is what my system does (and I dare say most practical Paxos systems).

Note, the ABD and round-based registers act similarly to Paxos, but are a little simpler because they don't have to guarantee the above consistency property (once chosen, always chosen). But a Paxos-based state machine allows for CAS operations on the variables.

这篇关于paxos值选择的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
云存储最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆