问题标签 [paxos]

我试图理解 paxos 和两阶段提交之间的区别，作为在多台机器之间达成共识的手段。两阶段提交和三阶段提交很容易理解。3PC似乎也解决了2PC阻塞的故障问题。所以我真的不明白 Paxos 解决了什么问题。谁能告诉我 Paxos 究竟解决了什么问题？

I read how current master election algorithms like Raft, Paxos or Zab elect master on a cluster and couldn't understand why they use sophisticated algorithms instead of simple bully algorithm.

I'm developing a cluster library and use UDP Multicast for heartbeat messages. Each node joins a multicast address and also send datagram packets periodically to that address. If the nodes find out there is a new node that sends packets to this multicast address, the node is simply added to cluster and similarly when the nodes in the cluster don't get any package from a node, they remove it from the cluster. When I need to choose a master node, I simply iterate over the nodes in the cluster and choose the oldest one.

I read some articles that implies this approach is not effective and more sophisticated algorithms like Paxos should be used in order to elect a master or detect failures via heartbeat messages. I couldn't understand why Paxos is better for split-brain scenarios or other network failures than traditional bully algorithm because I can easily find out when quorum of nodes leave from the cluster without using Raft. The only benefit I see is the count of packets that each server have to handle; only master sends heartbeat messages in Raft while in this case each node has to send heartbeat message to each other. However I don't think this is a problem since I can simply implement similar heartbeat algorithm without changing my master election algorithm.

Can someone elaborate on that?

我对这两种技术感到很困惑。

1. 这两种技术之间有什么关系吗

2. 是否有任何现有的流行开源软件实现了这些技术？我知道 zookeeper 实现了 Paxos，但是两阶段提交呢？

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

我正在从 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)最高接受的提案编号和价值，因此是同步的？

2）现在是一个更复杂的情况，其中提出了两个提案，但在试图达成共识时在不同的时间点。想象一下这样一种情况：区域 A 中的客户端 C1 正在修改一些数据X并且尚未达成共识，而区域 B 中的客户端 C2 正在修改相同的数据X。客户的其中一项请求是否被拒绝？请注意 C2 比 C1 发生得晚，但尚未达成共识。如果按照顺序，必须完成 C1 请求，接受共识，然后处理 C2 请求。根据我对这篇博客的理解，在这种情况下，选择了 C1 请求值。

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

示例（来自此博客的版权）：

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

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

我确实了解 Spanner 在一个 paxos 组中的只读事务。

但是多个 paxos 组上的只读事务是如何工作的呢？该论文说它TT.now().latest用作时间戳，然后使用给定的时间戳执行快照读取。但为什么这行得通？

在每个副本中，都有一个安全时间。安全时间是副本中最后一次写入事务的时间戳。副本是最新的，如果asked timestamp <= safe time.

该论文还说，使用给定时间戳（只读事务的第二阶段）读取的快照可能需要等到副本是最新的。如果在读事务之后，将永远不会发生任何写事务，会发生什么情况？那么安全时间永远不会更新，读取事务会永远被阻塞？

我试图推理和理解算法在这些情况下是否失败，但似乎找不到他们会失败的例子。

如果他们不这样做，那么为什么不遵循其中的任何一个？

这里的文档说：

3 服务器集成允许单个服务器发生故障，并且该服务仍然可用。

但是，要建立仲裁，需要有ceil(n/2)+1节点

在3个节点的情况下，即：
ceil(3/2)+1 = ceil(1.5)+1 = 3

因此，如果 1 个节点宕机，则不应该建立仲裁，并且 zookeeper 应该宕机。

在这种情况下，上述文档是否错误？

关于 Paxos 算法，我有一个非常特殊的问题，该算法在 Cassandra 的轻量级事务中实现：

如果两个节点同时发布相同的提案会发生什么？他们都得到 ' [applied]: true ' 吗？

例如，考虑这个表：

这个查询：

如果我执行这个查询，我会得到一个响应：

如果我再次执行它，那么它不会被接受，因为 next_id ！= 1，我得到：

我的问题是 - 如果我从两个节点并行执行这个查询会发生什么。他们都有机会被录取吗？

（我的用例在这个stackoverflow问题中描述）

我正在学习 Paxos 算法（http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf），有一点我不明白。

我们知道事件遵循及时的顺序，并且它发生在例如事件 1-5 和 10 已决定，但之后的 6-9 和 11 尚未决定时。在上面的论文中，它说我们只是用无操作值填充 6-9 之间的空白，并简单地记录从 11 开始的新事件。

所以在这种情况下，由于已经记录了事件 10，我们知道在 5 到 10 之间肯定发生了某些类型的事件，但由于某些故障而没有被 Paxos 记录。如果我们简单地填写 no-op 值，这些事件将在我们的记录中丢失。

更糟糕的是，如果正如我上面链接的论文所说，事件实际上是来自客户端的命令，那么中间缺少一些命令可能会使整个操作集非法（如果不能跳过任何命令或命令其中很重要）。

那么为什么 Paxos 为事件之间的间隙填充 no-op 值仍然是合法的呢？（如果整个记录集可能由于我上面提到的 no-op 值而无效。）另外，有没有更好的方法来从这些间隙中恢复而不是使用 no-op？

阶段 2. (a) 如果提议者从大多数接受者那里收到对其准备请求（编号为 n）的响应，那么它会向这些接受者中的每一个发送一个接受请求，以获取编号为 n 且值为 v 的提议，其中 v 是响应中编号最高的提案的值，或者如果响应报告没有提案，则为任何值。

如论文所述，

提议者通过向一组接受者发送提议被接受的请求来发布提议。（这不必是响应初始请求的同一组接受者。）“

但据我了解，如果我们将阶段 2. (a) 更改为：

如果提议者从大多数接受者那里收到对其准备请求（编号为 n）的响应，则它会向任意一组多数接受者发送一个接受请求，以获取编号为 n 且值为 v 的提议，其中 v 是响应中编号最高的提案，或者如果响应没有报告提案，则为任何值。

该算法将失败，以下是一个示例。考虑总共有 3 个接受者 ABC。我们将使用 X(n:v,m) 来表示接受者 X 的状态：提案 n:v 是 X 接受的编号最大的提案，其中 n 是提案编号，v 是提案的值，m 是X 曾经响应过的最大编号的准备请求的数量。

1. P1 向 AB 发送“准备 1”
2. 两个 AB 都以不接受任何编号小于 1 的请求的承诺响应 P1。现在状态为：A(-:-,1) B(-:-,1) C(-:-,-)
3. P1 收到响应，然后卡住并运行得很慢
4. P2 向 AB 发送“准备 100”
5. 两个 AB 都以不接受任何编号小于 100 的请求的承诺响应 P2。现在状态是：A(-:-,100) B(-:-,100) C(-:-,-)
6. P2 收到响应，选择一个值 b 并将“接受 100:b”发送给 BC
7. BC接收并接受accept请求，状态为：A(-:-,100) B(100:b,100) C(100:b,-)。请注意，已选择提案 100:b。
8. P1 恢复，选择值 a 并将 'accept 1:a' 发送到 BC
9. B 不接受，但 C 接受，因为 C 从未承诺过任何事情。状态为：A(-:-,100) B(100:b,100) C(1:a,-)。选择的提案被放弃，Paxos 失败。

我在这里错过了什么吗？谢谢。