8

背景：

在Lamport 的论文Paxos Made Simple的第 3 节，命名为实现状态机，描述了 Multi-Paxos。Google Paxos Made Live中使用了 Multi-Paxos 。（在Apache ZooKeeper中使用了 Multi-Paxos）。在 Multi-Paxos 中，可能会出现间隙：

一般来说，假设一个领导者可以α提前获得命令——也就是说，它可以在命令 1 到命令被选择之后i + 1通过命令提出命令。然后可能会出现最多命令的间隙。i + αiα - 1

现在考虑以下场景：

整个系统采用主从架构。只有 master 服务于客户端命令。Master 和 Slave 通过 Multi-Paxos 就命令的顺序达成共识。master 是 Multi-Paxos 实例中的领导者。假设现在 master 和它的两个 slave 的状态（命令已被选择）如下图所示：

主人和奴隶.

请注意，在主状态中存在不止一个间隙。由于不同步，两个奴隶落后。这时候master就失败了。

问题：

  1. slave检测到master故障后应该怎么做（比如通过心跳机制）？

  2. 特别是与老主控的差距和缺失的命令如何处理？

关于 Zab 的更新：

正如@sbridges 所指出的，ZooKeeper使用Zab而不是 Paxos。去引用，

Zab 主要设计用于主备份（即主从）系统，如 ZooKeeper，而不是用于状态机复制。

Zab 似乎与我上面列出的问题密切相关。根据Zab 的简短概述论文，Zab 协议由两种模式组成：恢复和广播。在恢复模式下，有两个特定的保证：永远不会忘记已提交的消息和放弃已跳过的消息。我对 Zab 的困惑是：

  1. 在恢复模式下，Zab 是否也会遇到间隙问题？如果是这样，Zab 做了什么？
4

4 回答 4

2

差距应该是没有达成一致的Paxos实例。在论文Paxos Made Simple中，通过提出一个特殊的“no-op”命令来填补空白，该命令使状态保持不变。

如果您关心 Paxos 实例的选择值的顺序，最好使用 Zab，因为 Paxos 不保留因果顺序。https://cwiki.apache.org/confluence/display/ZOOKEEPER/PaxosRun

缺少的命令应该是已经达成一致但没有被学习者学习的 Paxos 实例。该值是不可变的，因为它已被接受者的法定人数接受。当您运行此实例 id 的 paxos 实例时，该值将被选择并恢复为阶段 1b 中的相同值。

当 slaves/followers 检测到 Leader 失败，或者 Leader 失去了 slaves/follower 的仲裁支持时，他们应该选举一个新的 Leader。

在 zookeeper 中，follower 通过保持 FIFO 的 TCP 与 leader 通信应该没有间隙。

In recovery mode, after the leader is elected, the follower synchronize with leader first, and apply the modification on state until NEWLEADER is received.

在广播模式下，follower 将 PROPOSAL 排队在pendingTxns中，并以相同的顺序等待 COMMIT。如果 COMMIT 的 zxid 与 pendingTxns 的 head 的zxid不匹配，follower 将退出。

https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab1.0

于 2013-10-07T14:29:54.893 回答
1

Apache ZooKeeper 中使用 Multi-Paxos

Zookeeper 使用的是zab，而不是paxos。请参阅此链接了解不同之处。

特别是，集成中的每个 zookeeper 节点都以与其他节点相同的顺序提交更新，

与客户端请求不同，状态更新必须按照主节点的原始生成顺序进行，从主节点的原始初始状态开始。如果主节点失败，执行恢复的新主节点不能任意重新排序未提交的状态更新，或从不同的初始状态开始应用它们。

于 2013-10-07T01:07:40.580 回答
1

Specifically the ZAB paper says that a newly elected leader undertakes discovery to learn the next epoch number to set and who has the most up-to-date commit history. 追随者会发送一条消息，说明它所看到ACK-E的最大连续值。zxid然后它说它进行了一个同步阶段，在这个阶段它传输他们错过的追随者的状态。它指出，有趣的优化是只选择具有最新提交历史的领导者。

使用 Paxos ，您不必允许间隙。如果您确实允许差距，那么Paxos Made Simple论文从第 9 页解释了如何解决它们。新领导者知道它看到的最后一个承诺值，可能还有上面的一些承诺值。它通过运行阶段 1 从它所知道的最低间隙探测这些槽，以向这些槽提出建议。如果这些槽中有值，它会运行阶段 2 来修复这些值，但如果它可以自由设置值，它会设置无操作值。最终，它到达没有建议值的插槽号，并且正常运行。

在回答您的问题时：

  1. slave检测到master故障后应该怎么做（比如通过心跳机制）？

他们应该在随机延迟后尝试领先，以尝试降低两名候选人同时提出建议的风险，这会浪费消息和磁盘刷新，因为只有一个人可以领先。Raft论文很好地介绍了随机领导者超时；Paxos 可以使用相同的方法。

  1. 特别是与老主控的差距和缺失的命令如何处理？

新的领导者应该探测并将间隙修复为向该槽提出的最高值，否则为空操作，直到它填补了间隙，然后它可以正常领导。

于 2014-10-28T22:35:34.440 回答
0

@Hailin 的回答对差距问题的解释如下：

在zookeeper中，follower通过保持FIFO的TCP与leader通信应该没有间隙"

为补充：

在论文A simple fully ordered broadcast protocol中，它提到 ZooKeeper 需要前缀属性：

如果 $m$ 是为领导 $L$ 传递的最后一条消息，则在 $m$ 之前由 $L$ 提出的任何消息也必须传递”。

该属性主要依赖于 Zab 中使用的 TCP 机制。在Zab Wiki中，它提到 Zab 的实现必须遵循以下假设（除了其他假设）：

服务器必须按照接收到的顺序处理数据包。由于 TCP 在发送数据包时保持顺序，这意味着数据包将按照发送方定义的顺序进行处理。

于 2013-10-09T02:15:40.677 回答