如果paxos"ignore"与acceptor发送的最高提案号不同步，是否请求更新值？

Question

此处的标题可能具有误导性。我会尽力通过一个例子来解释我的疑问。

我正在从 wiki 和其他来源阅读有关 paxos 算法的信息。

1) 想象这样一种情况，其中处理了客户端更新值的请求（下例中的 X）。在一轮 Paxos 之后，选择了一个值 Vb，因为 Acceptors 对 Proposers 的回复包含他们之前接受的 Proposal 编号和相应的值。在下面的例子中，三个接受者发送 (8,Va),(9,Vb),(7,Vc) 给当前有 (10,X) 的提议者。它选择 (9,Vb) 因为它是它收到的最高提案编号，并将值 (10,Vb) 广播给所有接受者以供接受。因此，处理这一整轮 Paxos 的初始值 X 从未更新过。那么在这种情况下更新到X的客户端事务是否失败？

这之后 Acceptors 的最终状态是什么？他们是否都将 (10,Vb) 作为他们接受的最高提案编号和值，从而保持同步？

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) 现在是一个更复杂的情况，其中提出了两个提案，但在试图达成共识时处于不同的时间点。想象这样一种情况，区域 A 中的客户端 C1 正在修改某些数据 X 并且尚未达成共识，而区域 B 中的客户端 C2 正在修改相同的数据 X。客户的请求之一被拒绝了吗？请注意 C2 晚于 C1 发生，只是尚未达成共识。如果遵循顺序，则必须完成 C1 请求，接受共识，然后处理 C2 请求。根据我对this blog的理解，在这种情况下，选择了C1请求值。

所以C2请求被放弃了吗？这可能不是一个好的选择。

示例（版权来自 this 博客）：

在这种情况下，最终选择了 v=8，尽管对 V=5 的请求是客户端请求的最新更新。为什么会这样？这可能会产生严重影响

感谢您的帮助，新年快乐！

Answer 1

为了解释这一点，我将给出一些上下文——对 OSI 协议栈的解释：

+------------------------+
|100. Your Application   |
#========================#
|8. Some state machine   |
|   or key/value store   |
+------------------------+
|7. Transaction log      |
+------------------------+
|6. Paxos                |
+------------------------+
|5. Some framing protocol|
+------------------------+
|4. TCP                  |
+------------------------+
|...                     |
+------------------------+

我见过的每个认真的 paxos 实现都使用类似的模型（而且我见过很多认真的实现）。也就是说，Paxos 用于为状态机选择事务日志中的下一个条目（因为没有事务日志，数据库只是一个昂贵、缓慢、有缺陷的缓存）。事务日志中的每个条目都有一个不同的 Paxos 实例；他们是完全独立的；如果系统的设计者特别聪明，Paxos实例甚至可以运行并行。

现在回答你的问题。

是的，你第一个例子中的 X 失败了； 它没有被选中。失败应该returned到上层。这不一定意味着客户端失败（上述模型中的"your application"）。上层可能决定重试事务日志中稍后条目中的值；或者他们可能只是 return 对客户的失败。

在你的第二个例子中，其中一个请求必须最终被拒绝——Paxos 最多选择一个值。一旦选择了该值，它就会保持选中状态。好像查克诺里斯选择了它。

不过第二个例子好像有点误会。哪个请求先开始并不重要。由于网络延迟和行星对齐，第二个请求可能会超过第一个。

试试吧！以 X,Y 为值； P1,P2作为提议者；和 A1、A2、A3 作为受体：

P1 有 X 并发送 Prepare(1)
A1 承诺 1 和 returns Accepted(0,_)
A2 承诺 1 和 returns Accepted(0,_)
A3 承诺 1 和 returns Accepted(0,_)
P1还有X，发送Accept(X,1)
A1 接受 (X,1)
P2 有 Y 并发送 Prepare(2)
A2 承诺 2 和 returns Accepted(1,_)
- 如你所见，A2已经切换为不接受任何小于2的回合
A2 拒绝接受 (X,1)
A3 承诺 2 和 returns Accepted(1,_)
P2还有Y，发送Accept(Y,2)
A2 接受(Y,2)
A3 接受(Y,2)
- 被简单多数接受后，Y 被选中。无论任何提议者从现在开始做什么，Y 的值将始终被选中。

这实际上开始有点像你在第二个例子中的图片，但在这个例子中网络支持第二个提议者。

如果paxos"ignore"与acceptor发送的最高提案号不同步，是否请求更新值？

Does paxos "ignore" the request for updating the value if it is not in sync with highest proposal number sent by acceptor?

distributed-computing

consensus

paxos