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

Question

这里的标题可能会产生误导。我会尽量通过一个例子来解释我的疑惑。

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

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

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

Client Proposer Acceptor Learner
| | | | | | | --- 第一个请求 ---
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 请求。以我对this blog的理解，在这种情况下，选择 C1 请求值。

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

示例(版权来自 this 博客):



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

感谢您的帮助，祝您新年快乐!

Answer 1

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

+------------------------+
|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 失败了； 它没有被选中 .失败应该返回给上层。这可能不一定意味着客户端失败(上述模型中的“您的应用程序”)。上层可以决定在事务日志中稍后的条目中重试该值；或者他们可能只是将失败返回给客户端。

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

但是在第二个示例中似乎存在一些误解。首先启动哪个请求并不重要。由于网络延迟和行星的排列，第二个请求可能会排除第一个请求。

尝试一下!以 X,Y 为值； P1,P2 作为提议者；和 A1,A2,A3 作为接受者:

P1 有 X 并发送 Prepare(1)

A1 promise 1 并返回 Accepted(0,_)

A2 promise 1 并返回 Accepted(0,_)

A3 promise 1 并返回 Accepted(0,_)

P1 仍然有 X 并发送 Accept(X,1)

A1 接受(X,1)

P2 有 Y 并发送 Prepare(2)

A2 promise 2 并返回 Accepted(1,_)

如您所见，A2 已切换为不接受任何小于 2 的回合

A2 拒绝 Accept(X,1)

A3 promise 2 并返回 Accepted(1,_)

P2 仍然有 Y 并发送 Accept(Y,2)

A2 接受(Y,2)

A3接受(Y,2)

在被简单多数接受后，Y 被选中。从现在开始，无论任何提议者做什么，Y 的值都会被选中。

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