4

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

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

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

在这之后 Acceptors 的最终状态是什么？它们是否都具有(10,Vb)最高接受的提案编号和价值，因此是同步的？

客户 提议者 接受者 学习者
   | | | | | | | --- 第一个请求 ---
   X-------->| | | | | | 要求
   | X--------->|->|->| | | 准备(10)
   | |<---------X--X--X | | 承诺(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尽管 request forV=5是客户端请求的最新更新，但最终选择了。为什么会这样？这可能会产生严重影响

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

4

1 回答 1

4

为了解释这一点，我将给出一些上下文——对 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 失败了；它没有被选中。一个失败应该返回给上层。这可能并不一定意味着客户端失败（上述模型中的“您的应用程序”）。上层可能决定在事务日志的后续条目中重试该值；或者他们可能只是将失败返回给客户端。

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

但看起来在第二个例子中存在一些误解。哪个请求首先开始并不重要。由于网络延迟和行星对齐，第二个请求可能会影响第一个请求。

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

  1. P1 有 X 并发送 Prepare(1)
  2. A1 承诺 1 并返回 Accepted(0,_)
  3. A2 承诺 1 并返回 Accepted(0,_)
  4. A3 承诺 1 并返回 Accepted(0,_)
  5. P1 仍然有 X 并发送 Accept(X,1)
  6. A1 接受(X,1)
  7. P2 有 Y 并发送 Prepare(2)
  8. A2 承诺 2 并返回 Accepted(1,_)
    • 如您所见，A2 已切换为不接受任何小于 2 的回合
  9. A2 拒绝 Accept(X,1)
  10. A3 承诺 2 并返回 Accepted(1,_)
  11. P2 仍有 Y 并发送 Accept(Y,2)
  12. A2 接受(Y,2)
  13. A3 接受(Y,2)
    • 在被简单多数接受后，Y 被选中。无论任何提议者从现在开始做什么，Y 的值都将始终被选中。

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

于 2015-01-03T18:37:00.060 回答