25

看了paxos和raft论文后，我有以下困惑：paxos论文只描述了对单个日志条目的共识，相当于raft算法的leader选举部分。在 raft 的 leader 选举中，paxos 的方法相对于简单的随机超时方法有什么优势？

4

3 回答 3

28

最初的 Paxos 论文没有使用稳定的领导者，这是一个普遍的误解。在Paxos Made Simple第 6 页标题为“实施”的部分中，Lamport 写道：

该算法选择一个领导者，领导者扮演杰出提议者和杰出学习者的角色。

这可以通过使用准备和承诺的第一阶段消息传递来简单地实现。

然后在第 9 页和第 10 页的“实现状态机”部分下，我们有：

在正常操作中，单个服务器被选为领导者，它在共识算法的所有实例中充当杰出的提议者（唯一尝试发布提议的人）。

在这里，它在最一般意义上使用术语“状态机”，涵盖显而易见的情况，例如我们复制应用于存储的操作日志的键值存储或数据库服务器。

人们对此感到困惑，因为 Lamport 证明 Paxos 的方式现在是它的教学方式。Lamport 证明了被称为 Paxos 的一类应用程序的正确性，将其分解为一个可以推理的数学模型。他在原始论文《兼职议会》中称其为“单一法令会议” ：

帕克森宗教领袖要求数学家制定一个选择主教会议法令的协议。该协议的要求和假设与后来的议会基本相同，除了不是包含一系列法令，分类帐最多有一个法令。此处描述了生成的 Synod 协议；议会协议在第 3 节中描述。

如果您发现该陈述令人困惑，请不要担心，这是一个糟糕的笑话；字面上地。用我自己的话翻译成这样：

“为了证明选择命令流的共识算法的正确性，我们可以首先证明选择单个命令的数学模型的正确性。只要不违反单命令数学模型的不变量，就可以将选择单个命令的数学模型扩展到选择命令流的实用算法（第 3 节）。” – 辛博1905

为了证明我的解释是正确的，我们可以看一下题为“多法令议会”的第 3 节，它说：

帕克森议会不仅要通过一项法令，还必须通过一系列编号的法令。正如在主教会议协议中一样，选举了一位主席。任何想要通过法令的人都会通知总统，总统会为法令分配一个编号并试图通过它。从逻辑上讲，议会协议为每个法令编号使用了完整的 Synod 协议的单独实例。然而，为所有这些情况选择了一位总统，他只执行了协议的前两个步骤一次。

为了说明这一点，最初的“兼职议会”论文介绍了 Paxos，因为它的多度算法对计算机科学家来说很有趣；议会议定书。那和澄清文件“Paxos Made Simple”都将 Paxos 定义为有一个杰出的领导者，为命令流分配序列号。此外，杰出的领导者仅在担任领导时才发送“准备”消息。之后，在稳定状态下，杰出的领导者只流式传输“接受”消息。他还在论文的其他地方说要折叠角色并让所有服务器运行算法的所有三个角色。

当你问“在 raft 的领导人选举中，Paxos 的方法与简单的随机超时方法相比有什么优势？” 我不确定您指的是什么方法？使用 Paxos，您可以随机化超时并发出 Prepare 消息。Paxos Made Simple 论文指出，只要您遵循 Paxos 协议以“确保安全”，您就可以自由使用超时或者其他一些更快的机制：

Fischer、Lynch 和 Patterson 的著名结果1意味着选举提议者的可靠算法必须使用随机性或实时性——例如，通过使用超时。但是，无论选举成功与否，都可以确保安全。

随机超时非常容易编码并且非常容易理解。然而，在更糟糕的情况下，它们可能会导致恢复的长期延迟。你不喜欢你可以使用自己的领导选举机制。比如这个。

于 2017-09-02T09:05:47.317 回答
6

在阅读了问题和@simbo1905 的答案后，我觉得我必须投入 2 美分，因为我认为问题没有得到解答。

在 raft 的 leader 选举中，paxos 的方法相对于简单的随机超时方法有什么优势？

tl;dr：Paxos 是最优的，但 Raft 对活性有更强的实际保证。

如需更多信息，请继续阅读。

正如 Lamport 在Paxos Made Simple的第 3 节中所述，

可以看出，Paxos 共识算法的第 2 阶段具有在存在故障的情况下达成一致的任何算法的最小可能成本[2]。因此，Paxos 算法本质上是最优的。

因此，Paxos 以一种在没有错误时效率最高的方式来实现共识。

另一方面，在同一节中，他还指出

如果多个服务器认为他们是领导者，那么他们都可以在同一个共识算法实例中提出值，这可能会阻止任何值被选择。但是，安全性得到了保护——两个不同的服务器永远不会在选择作为第 i 个状态机命令的值上存在分歧。只需要选举一个领导人以确保取得进展。

这意味着实际上Paxos 可以看到违反其活性保证的情况。

于 2018-12-13T15:56:18.660 回答
-7

Raft 是 Paxos

8-O

...更具体地说，它的多法令版本具有不同的命名。

于 2019-01-04T11:20:37.290 回答