Oli*_*ung 11 distributed-system consensus paxos raft
在阅读了paxos和筏纸之后,我有以下困惑:paxos论文仅描述了单日志条目的共识,这相当于筏算法的领导者选举部分.在木筏领导者选举中,paxos的方法优于简单的随机超时方法有什么优势？
sim*_*905 15
一种常见的误解是,原始的Paxos论文没有使用稳定的领导者.在Paxtos Made Simple的第6页,标题为"实施"的部分,Lamport写道:
该算法选择一个领导者,该领导者扮演着名的提议者和杰出的学习者的角色.
这可以通过准备和承诺的第1阶段消息传递来实现.
然后在"实施状态机"部分的第9页和第10页,我们有:
在正常操作中,单个服务器被选为领导者,其在共识算法的所有实例中充当杰出的提议者(唯一尝试发布提议的提议者).
这里使用的术语"状态机"在最一般意义上涵盖了明显的情况,例如键值存储或数据库服务器,我们复制应用于存储的操作日志.
人们对此感到困惑,因为Lamport证明了Paxos的方式,现在就是它的教学方式.Lamport通过将其拆分为可以推理的数学模型,证明了一类被称为Paxos的应用程序的正确性.他在原始论文"兼职议会"中称之为"单一法令大会" :
Paxon宗教领袖要求数学家制定一个选择宗教会议法令的协议.议定书的要求和假设基本上与后来议会的要求和假设相同,除了不包含一系列法令,分类帐最多只能有一个法令.这里描述了生成的Synod协议; 议会议定书在第3节中描述.
如果你觉得这句话令人困惑,不要担心这是一个糟糕的笑话; 从字面上.用我自己的话来翻译这将是:
"为了证明用于选择命令流的一致性算法的正确性,我们可以首先证明选择单个命令的数学模型的正确性.只要不违反单一命令数学模型的假设,用于选择单个命令的数学模型就可以扩展到用于选择命令流的实用算法(第3节)." - simbo1905
为了证明我的解释,我们可以看看题为"多议会议会"的第3节,其中说:
Paxon议会不得不通过一项法令,而是必须通过一系列有序的法令.在议会议定书中,总统当选.任何想要通过法令的人都会告知总统,总统会为法令指定一个号码并试图通过该法令.从逻辑上讲,议会协议为每个法令号使用了完整的Synod协议的单独实例.但是,为所有这些实例选择了一位总统,他只执行了一次协议的前两步.
为了解决这个问题,最初的"兼职议案"论文引入了Paxos因为它的多度算法而对计算机科学家感兴趣; 议会议定书.这和澄清论文"Paxos Made Simple"都将Paxos定义为具有一个杰出的领导者,将序列号分配给命令流.此外,尊敬的领导者在领导时只发送"准备"信息; 在稳定状态之后,尊贵的领导者仅流"接受"消息.他还说文章中的其他部分可以解除角色,让所有服务器都运行算法的所有三个角色.
阅读问题和@simbo1905 的回答后，我觉得我必须投入 2 美分，因为我认为问题没有得到解答。
在 raft 的 leader 选举中，paxos 的方法比简单的随机超时方法有什么优势？
TL; DR：的Paxos是最佳的，但筏具有较强的实际活跃的保证。
有关更多信息，请继续阅读。
正如 Lamport 在Paxos Made Simple 的第 3 节中所述，
可以证明，Paxos 共识算法的第 2 阶段在出现故障的情况下达成一致的任何算法的成本可能最低[2]。因此，Paxos 算法本质上是最优的。
所以 Paxos 以一种在没有故障时效率最高的方式来实现共识。
另一方面，在同一部分，他还指出
如果多个服务器认为他们是领导者，那么他们都可以在共识算法的同一个实例中提出值，这可能会阻止任何值被选中。但是，安全性得到了保护——两个不同的服务器永远不会在选择作为第 i 个状态机命令的值上存在分歧。只需要选举一个领导人来确保进展。
这意味着实际上Paxos 可以看到违反其活性保证的情况。