我已经在维基页面和论文(paxos变得简单)上阅读了关于paxos的内容.但是,我仍然对一些细节感到困惑:
在阶段1a,提议者是否包括它打算在接受者提案中选择的值？
在阶段1b中,接受者应该返回先前接受的值(如果有的话).这个价值的生命周期是多少？IOW,什么时候被认为是被接受的,什么时候被覆盖/丢弃？
关于终身问题的一些更新.国际工会联合会在首次接受后,接受方应始终具有先前已接受的价值.它如何决定是否应该在下一个承诺(1b)阶段归还？或者它何时决定忘记价值？
更新2以更好地与@MichealDeardeuff讨论:
我对paxos有如下理解:
通常在paxos工作流程中,接受者应始终具有先前接受的值.在回答准备请求时,它会在promise响应中发回值.并且提议者需要检查该值是否与上一轮中提出的值相同.如果不是,则提议者继续发送接受请求,其中包含接受者返回的值.如果是,则提议者继续发送具有其打算在当前轮次中发送的值的Accept请求.
以上理解是否正确？
如果不正确,请您解释原因？
如果它是正确的,我很困惑,因为paxos协议没有明确说明.它只说明:
其中v是响应中编号最高的提议的值,如果响应未报告提议,则为任何值.
但是,根据我的理解,提议者需要检查并查看acceptor返回的值是否与上一轮中提出的相同提议者的值相同.如果是,即使在promise响应中存在具有编号最高的提议的值,提议者仍然可以选择它想要的任何值,就好像没有接受者返回的值.
这就是我想看看是否有任何参考支持理解的原因.
非常感谢!
Mic*_*uff 10
在阶段1a,提议者是否包括它打算在接受者提案中选择的值？
在阶段2a之前,提议者不需要发送它打算选择的值.另见我对之前问题的回答.
在阶段1b中,接受者应该返回先前接受的值(如果有的话).这个价值的生命周期是多少？IOW,什么时候被认为是被接受的,什么时候被覆盖/丢弃？
从我对另一个不同问题的回答,"接受者应该接受所有价值观,除非它承诺不接受它." 也就是说,它应该接受round-id大于或等于它发送的最后一个响应中的round-id的任何值.
它必须接受任何其他价值的原因是提议者可能发现(作为第1阶段的结果)应该 - 或者已经选择了不同的值 ; 然后它将此值广播给所有接受者.当存在多个提议者和/或在网络分区期间,可能发生这种差异.
更新以回答评论.
当接受者接受一个值时,它会保持该值,直到它接受另一个值.(与此同时它存储了值的一轮).
在阶段1b中,Acceptor 总是发送其值,允许Proposer整理出实际选择的值.它永远不会忘记它的当前价值.永远.
在接受来自接受者的承诺后,提议者可以很好地了解系统.(注意:它不一定是完整或最新的视图.)
可能是由于与不同提议者的某些争论,不同的接受者已经接受了不同的值.因此,提议者选择具有最高舍入id的值并将该值发送给所有接受者.这就是允许接受者值改变的原因.
评论中的关注点是这打破了Paxos.不是这样.
但是,在我进入一个例子之前,让我强调一下,考虑Paxos的命名阶段和消息而不是1a,1b,2a,2b要容易得多.我通常将阶段命名为准备阶段和接受阶段.消息1a为Prepare,1b为Promise,2a为Accept,2b为Accepted.
现在,让我们假设人们经常给出一个假设的例子,他们认为这会打破Paxos.假设我们有三个接受器A1,A2和A3.A1和A2在第1轮都有接受值ABC,A3在第2轮选择了XYZ(即来自不同的提议者).我们可以看到A1和A2构成了多数,ABC已被"选中".
继续这个假设的例子,提议者发送Prepare(3)并接收来自A2和A3的回复,即Promise(ABC @ 1)和Promise(XYZ @ 2).Proposer认为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,对于具有值XYZ @ 2的A3,它必须已经从接受者接收了大部分Promise.由于价值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为核心构建的系统的团队.我也对这个问题进行了广泛的研究.
这里有一些关于这个主题的好文章:
更新4回答问题中的更新.
通常在paxos工作流程中,接受者应始终具有先前接受的值.在回答准备请求时,它会在promise响应中发回值.并且提议者需要检查该值是否与上一轮中提出的值相同.如果不是,则提议者继续发送接受请求,其中包含接受者返回的值.
好的,到目前为止.但提议者不需要在轮次之间保持状态.我们很快就会找到原因.
如果它是[相同的值],则提议者继续发送具有它打算在当前轮次中发送的值的Accept请求.
如果接受者返回任何值,则必须在Accept阶段使用具有最高round-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
这会覆盖所选择的值,违反共识的一致性属性(即,最多可以选择一个值).
如果您想要这种行为,则不能使用共识协议.您可以使用ABD等协议或其他基于循环的寄存器.或者您可以将Paxos视为在状态机中选择转换.换句话说,每次要更改变量时,都会运行新的Paxos算法来选择转换.这就是我的系统所做的(我敢说最实用的Paxos系统).
注意,ABD和基于循环的寄存器与Paxos的行为类似,但稍微简单一些,因为它们不必保证上述一致性属性(一旦选择,总是选择).但是基于Paxos的状态机允许对变量进行CAS操作.