cloud - 顾客值(value)选择

Question

我已经在Wiki页面和纸上阅读了有关paxos的信息（paxos变得简单）。但是，我仍然对某些细节感到困惑：


在阶段1a中，提议者是否将打算选择的值包含在提议中给接受者？
在阶段1b中，如果有接受器，则应返回其先前接受的值。价值的使用寿命是多少？ IOW，什么时候它被接受，什么时候它被覆盖/丢弃？


有关寿命问题的一些更新。 IIUC在第一次接受之后，接受者应始终准备好先前接受的值。它如何决定是否应在下一承诺（1b）阶段将其返回？还是什么时候决定忘记价值？



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

我对paxos有以下了解：


通常在paxos工作流程中，接受者应始终准备好先前接受的值。并在回答准备请求时，它将把值发送回诺言响应中。提议者需要检查该值是否与上一轮提议的值相同。如果不是，则提议者继续发送带有接受者返回值的接受请求。如果是，则提议者然后继续发送其打算在当前回合中发送的值的接受请求。


以上理解正确吗？

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

如果正确，我会感到困惑，因为paxos协议没有明确说明。它仅说明：


其中v是回复中编号最高的提案的值，或者如果回复未报告任何提案则为任何值。


但是，据我了解，提议者需要检查并确认接受者返回的值是否与上一轮提议的提议者的值相同。如果是这样，即使在承诺响应中存在提议编号最高的提议，提议者仍然可以选择其想要的任何值，就像接受者没有返回任何值一样。

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

非常感谢！

Answer 1

在阶段1a中，提议者是否将打算选择的值包含在提议中给接受者？


在阶段2a之前，提议者不需要发送打算选择的值。另请参阅my answer到先前的问题。


在阶段1b中，如果有接受器，则应返回其先前接受的值。价值的使用寿命是多少？ IOW，什么时候它被接受，什么时候它被覆盖/丢弃？


从my answer到另一个不同的问题，“除非接受者承诺不接受，否则接受者应接受所有值。”也就是说，它应在其上次发送的响应中接受回合ID大于或等于回合ID的任何值。

它必须接受任何其他值的原因是，提议者可能会发现（作为第1阶段的结果）应该（或已经）选择了另一个值；然后，它将这个值广播给所有接受者。当存在多个提议者时和/或在网络分区期间，可能会发生这种差异。



更新以回答评论。

当接受者接受一个值时，它会保留该值，直到接受另一个值为止。 （与此同时，它存储值的取整）。

在阶段1b中，接受者总是发送其值，从而使提议者可以挑选出实际选择的值。它永远不会忘记其当前价值。曾经

在收到接受者的承诺后，提议者对系统有了很好的了解。 （注意：它不一定是完整的视图或最新视图。）

由于与不同提议者的某些争执，不同的接受者可能接受了不同的值。因此，提议者选择具有最高回合ID的值，并将该值发送给所有接受者。这就是为什么可以更改受体值的原因。

评论中担心的是，这破坏了Paxos。不是这样

但是，在我举一个例子之前，让我强调一下，使用命名的阶段和消息而不是1a，1b，2a，2b来考虑Paxos要容易得多。我通常将阶段命名为“准备”阶段和“接受”阶段。消息1a为“准备”，消息1b为“承诺”，消息2a为“接受”，消息2b为“已接受”。

现在，让我们以人们经常给出的假设示例为例，他们认为这破坏了Paxos。
假设我们有三个受体A1，A2和A3。 A1和A2在第1轮都接受了ABC值，而A3在第2轮选择了XYZ（即来自其他提议者）。我们可以看到A1和A2占多数，而ABC已被“选择”。

继续这个假设示例，提议者发送Prepare（3）并从A2和A3接收回响应，即Promise（ABC @ 1）和Promise（XYZ @ 2）。提议者认为XYZ具有最高的回合，并在接受阶段将其发送出去，从而覆盖其他主机上的ABC。中提琴，Paxos坏了，对吗？

否。问题在于启动状态，这是不可能的。让我告诉你为什么。

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

提议A：要使A1和A2的值ABC @ 1，提议者必须已发送Accept（ABC @ 1），这意味着它必须已收到大多数Promises，以响应发送Prepare（1）。

提议B：要使A3的值XYZ @ 2，提议者必须已发送Accept（XYZ @ 2），这意味着它必须已收到大多数Promises，以响应发送Prepare（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。（请记住，第2轮可以出现在第1轮之前：每个提议者的回合ID只是单调增加。）根据命题A，对于A1和A2的值ABC @ 1，a提议者必须已从接受者那里收到大部分承诺。同样，根据提案B，要使A3拥有它，也必须已经收到了大部分的承诺。这意味着在集合{A1，A2}中必须至少有一个接受者两次承诺过。

情况2a：接受者先发送Promise（1），然后发送Promise（2）。然后，当它收到消息Accept（ABC @ 1）时，它肯定已经拒绝了它，因为它已承诺不接受早于2的任何值。但是它没有拒绝它，因为它具有的值为ABC @1。这是一个矛盾。

情况2b：接受者首先发送Promise（2）。然后，当它收到消息Prepare（1）时，它一定已经拒绝了它，因为它已经承诺要进行更高级别的回合。但这显然不是因为命题A发送了Promise（1）。一个矛盾。

哇！

我希望这能够帮到你。



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

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

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


…如果与上一轮发送的提议者的值相同，我们希望提议者忽略它（否则我们将陷入死循环，对吗？）


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

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

如果“准备”阶段产生的值与上一轮中看到的值相同，则出于多种原因，无论如何它应该继续接受阶段。


如果提议者提前退出循环，则可能是另一个提议者失败了。这可能会导致没有选择任何值。
如果它提前退出循环，那么另一个提议者也是合理的，遵循相同的算法也退出了循环。再次导致可能没有选择任何值。
如果碰巧实际上已经选择了该值，则可能不是所有节点都已收到该值（由于网络分区）或具有不同的值（由于与其他提议者的争斗）。因此，出于持久性考虑，最好将值推入节点。


另一方面，当两个或多个提议者之间存在争执并且遇到一些不幸时，Paxos可能陷入无限循环。 （这对于任何共识算法都是正确的，并且在实际发现任何共识算法之前已由Liskov等人进行了证明。）因此，该理论说，但是在实际系统中很容易绕开：在随后的每一轮中，随机停顿一段时间有时间让其他提议者有机会赢得比赛。当然，仍然可能有无限循环，但在宇宙的生命周期内不可能发生。


您是否有任何支持该论点的参考文献？


我主要根据自己的学习和经验发言。我所在的团队负责开发和维护以Paxos为核心的系统。我还对该主题进行了广泛的研究。

以下是一些有关该主题的好论文：


Paxos Made Simple（您已经说过已经读过）
The Paxon Parliament（原始论文）
Deconstructing Paxos（将Paxos模块化为几个组件，然后针对不同情况对其进行调整）
The ABCDs of Paxos（巴特勒·兰普森（Butler Lampson）推广了Paxos，但有时他可能会感到困惑。




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


通常在paxos工作流程中，接受者应始终准备好先前接受的值。并在回答准备请求时，它将把值发送回诺言响应中。提议者需要检查该值是否与上一轮提议的值相同。如果不是，则提议者继续发送带有接受者返回值的接受请求。


好的，到目前为止。但是提议者不需要在两轮之间保持状态。我们将很快找出原因。


如果它是[相同的值]，那么提议者将继续发送其打算在当前回合中发送的值的接受请求。


如果接受者返回任何值，则在接受阶段必须使用具有最高回合ID的值。如果接受者未返回任何值，则可以使用任何值：我的逻辑建议这将是客户端传递给提议者的值。

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


...其中v是回应中编号最高的提议的值，或者如果回应中没有报告提议，则为任何值。


（很难在两篇论文之间切换术语。Lamport在这里使用编号提案，而在其他地方他在使用round-id。两者是相同的。）

假设提议者运行准备阶段，并在接受者中看到此状态。

             A1   A2  A3
promise:      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或其他 round-based register之类的协议。或者，您可以将Paxos视为在状态机中选择过渡。换句话说，每次要更改变量时，都运行新的Paxos算法以选择过渡。这就是我的系统所做的事情（我敢说大多数实用的Paxos系统）。

请注意，ABD和基于回合的寄存器的行为与Paxos相似，但稍微简单一点，因为它们不必保证上述一致性属性（选择一次，始终选择）。但是基于Paxos的状态机允许对变量执行CAS操作。