问题描述
此处的标题可能会引起误解。我将通过一个示例来尽力解释我的疑问。
我正在从Wiki和其他来源阅读有关paxos算法的信息。
1）想象一下处理客户请求更新值的情况（下例中为 X ）。
经过一轮Paxos之后，选择了 Vb 值，因为接受者对投标者的答复包含其先前接受的投标编号和相应的值。在以下情况下，三个接受者将（8，Va），（9，Vb），（7，Vc）发送给当前拥有的提议者（10，X）。它选择（9，Vb），因为它是收到的最高提案编号，并广播了值（10，Vb）接受所有接受者。因此，整个Paxos处理的初始值 X 从未更新。
在此之后，接受方的最终状态是什么？他们是否都将（10，Vb）作为其接受的最高投标编号和值，从而保持同步？
客户提议者接受者学习者
| | | | | | | ---第一个请求---
X --------> | | | | | |要求
| X ---------> |-> |-> | | |准备（10）
| |< --------- X--X--X | | Promise（10，{（8，Va），（9，Vb），（7，Vc）}
| X ---------> |-> |-> | | | |接受！（10,9，Vb）
| |< --------- X--X--X ------> |-> |接受（10 ，9，Vb）
|< --------------------------------- X--X响应
| | | | | | |
2）现在是一个更复杂的情况，其中提出了两个建议，但建议不同达成共识的时间点。可以想象这样一种情况：区域A中的客户端C1正在修改某些数据 X ，但尚未达成共识，而区域B中的客户端C2正在修改相同的数据 X 。客户的要求之一被拒绝了吗？请注意，C2的发生晚于C1，但尚未达成共识。如果遵循订购，则必须完成C1请求，接受共识，然后再处理C2请求。根据我对的理解，在这种情况下，选择了C1请求值。
那么C2请求被放弃了吗？
示例（来自博客）：
在这种情况下，尽管最终选择了 v = 8 V = 5 的请求是客户端请求的最新更新。为什么会这样呢？
感谢帮助和新年快乐！
为了解释这一点，我将提供一些上下文信息-OSI协议栈的解释：
+ ------------------------ +
| 100。您的申请|
＃======================＃
| 8。一些状态机|
|或键/值存储|
+ ------------------------ +
| 7。交易记录|
+ ------------------------ +
| 6。 Paxos |
+ ------------------------ +
| 5。一些成帧协议|
+ ------------------------ +
| 4。 TCP |
+ ------------------------ +
| ... |
+ ------------------------ +
我见过的每一个paxos的严肃实现都使用类似的模型（而且我见过许多严肃的实现）。也就是说，Paxos用于选择状态机的事务日志中的下一个条目（因为没有事务日志，数据库只是一个昂贵，缓慢，有漏洞的缓存）。事务日志中的每个条目都有一个不同的Paxos实例。他们是完全独立的；如果系统的设计人员非常聪明，那么Paxos实例甚至可以并行运行。
现在问您一个问题。
是的，第一个示例中的X失败； 未选择。失败应返回到上层。这不一定意味着客户端发生故障（上述模型中的您的应用程序）。高层可以决定在事务日志的后续条目中重试该值；
在第二个示例中，这些请求之一必须最终被拒绝-Paxos最多选择一个值。一旦选择了该值，它将保持不变。好像是查克·诺里斯（Chuck Norris）选择了它。哪个请求首先开始并不重要。由于网络延迟和行星对齐，第二个请求可能会超出第一个请求。
尝试一下！以X，Y为值； P1，P2作为提议者；和A1，A2，A3作为接受者：
- P1有X并发送Prepare（1）
- A1承诺1并返回Accepted（0，_）
- A2承诺1并返回Accepted（0，_）
- A3承诺1 1并返回Accepted（0，_）
- P1仍然有X并发送Accept（X，1）
- A1 accepts（X，1）
- P2有Y并发送Prepare（2）
- A2对2的承诺并返回Accepted（1，_）
- 如您所见，A2已切换为不接受任何小于2的回合
- A2拒绝接受（X，1）
- A3承诺2并返回Accepted（1，_）
- P2仍然具有Y并发送Accept（Y，2 ）
- A2接受（Y，2）
- A3接受（Y，2）
- 并且已被简单多数所接受，因此选择了Y。无论任何提议者从现在开始做什么，都将始终选择Y的值。
实际上，它的开始有点像第二个示例中的图片，但是在此示例中，网络偏爱第二个提议者。
Title here could be misleading. I will try my best to explain my doubt through an example.
I am reading about paxos algorithm from wiki and other sources.
1) Imagine a situation where a client's request to update a value (X in below example) is processed.After one round of Paxos, a value Vb is chosen because Acceptors reply's to Proposers contain their previously accepted Proposal number and the corresponding value. In the case below, the three acceptors send (8,Va),(9,Vb),(7,Vc) to proposer which currently has (10,X). It picks up (9,Vb) since it is the highest proposal number it received and broadcast the value (10,Vb) to all acceptors for acceptance. So the initial value X for which this whole round of Paxos was processed never got updated. so is the client transaction of updating to X failed in this case?
What is the final state of Acceptors after this? Do they all have (10,Vb) as their highest accepted proposal number and values and thus be in sync?
Client Proposer Acceptor Learner
| | | | | | | --- First Request ---
X-------->| | | | | | Request
| X--------->|->|->| | | Prepare(10)
| |<---------X--X--X | | Promise(10,{(8,Va),(9,Vb),(7,Vc)}
| X--------->|->|->| | | Accept!(10,9,Vb)
| |<---------X--X--X------>|->| Accepted(10,9,Vb)
|<---------------------------------X--X Response
| | | | | | |
2) Now is a more complex case, where two proposals are made but at different time points when trying to reach consensus. That is imagine a situation where a client C1 in Region A is modifying some data X and has not yet reached consensus while client C2 in Region B is modifying same data X. Is one of Client's request rejected? please note C2 happens later than C1 but just that consensus has not reached yet. If ordering is followed, C1 request must be finished, consensus accepted and then C2 request be processed. From my understanding of this blog, in this case, C1 request value is chosen.
So Is C2 request abandoned? that might not be a good option.
Example (Copyright from this blog):
In this case, the v=8 is chosen finally, although request for V=5 is the most recent updated requested by client. why is it so? This could have serious impacts
Thanks for help and a happy new year!
To explain this I'm going to give some context--an interpretation of the OSI protocol stack:
+------------------------+
|100. Your Application |
#========================#
|8. Some state machine |
| or key/value store |
+------------------------+
|7. Transaction log |
+------------------------+
|6. Paxos |
+------------------------+
|5. Some framing protocol|
+------------------------+
|4. TCP |
+------------------------+
|... |
+------------------------+
Every serious implementation of paxos that I've seen uses a similar model (and I've seen many serious implementations). That is, Paxos is used to choose the next entry in a transaction log for a state-machine (becuase without a transaction log a database is just an expensive, slow, buggy cache). There is a different Paxos instance for every entry in the transaction log; they are completely independent; and if the designer of the system is exceptionally smart, the Paxos instances can even run in parallel.
Now on to your question.
Yes, X in your first example failed; it wasn't chosen. A failure should be returned to the upper layer. That may not necessarily mean a failure to the client ("your application" in the above model). The upper layers may decide to retry the value in a later entry in the transaction log; or they may just return a failure to the client.
In your second example, one of those requests MUST be rejected in the end--Paxos chooses at most ONE value. And once that value is chosen it stays chosen. As if Chuck Norris had chosen it.
But it looks like there is a little mis-understanding in that second example. It doesn't matter which request started first. Due to network latencies and the alignment of planets, the second request could muscle out the first.
Try it! With X,Y as values; P1,P2 as proposers; and A1,A2,A3 as acceptors:
- P1 has X and sends Prepare(1)
- A1 promises for 1 and returns Accepted(0,_)
- A2 promises for 1 and returns Accepted(0,_)
- A3 promises for 1 and returns Accepted(0,_)
- P1 still has X and sends Accept(X,1)
- A1 accepts(X,1)
- P2 has Y and sends Prepare(2)
- A2 promises for 2 and returns Accepted(1,_)
- As you can see, A2 has switched to not accept any round less than 2
- A2 rejects the Accept(X,1)
- A3 promises for 2 and returns Accepted(1,_)
- P2 still has Y and sends Accept(Y,2)
- A2 accepts(Y,2)
- A3 accepts(Y,2)
- And having been accepted by the simple majority, Y has been chosen. No matter what any proposer does from here on out, the value of Y will always be chosen.
This is actually starts somewhat like the picture you have in your second example, but in this example the network favored the second proposer.
这篇关于paxos是否“忽略”？如果更新值与接受方发送的最高投标编号不同步，请求更新？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！