PROSAGA码农传奇-共识算法-一致性算法如何保证一致性？

0# 张三岁 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    Paxos是一种点对点协作算法。正如其他答案所述，它需要
     <code>
 2F+1
 </code>
     节点继续接受写入
     <code>
 F
 </code>
     失败意味着集群规模
     <code>
 3, 5, 7
 </code>
     可以活下来
     <code>
 1, 2, 3
 </code>
     故障。该
    <a href="https://en.m.wikipedia.org/wiki/Byzantine_Generals" rel="nofollow">
      Byzantine_Generals
    </A>
     谈论需要更多节点交叉检查事实以清除错误信息。对于标准paxos，您假设节点没有谎言或有错误它们都运行相同的良好代码，并且问题是崩溃，丢失或不可读的消息（例如传输噪声），或者延迟或重新排序的消息（例如闪烁的网络链路）。它不使用全局时钟，因为它使用对等方式递增在节点之间传递的计数器。
  
  
    最初你没有领导者。节点需要听到群集配置（或DNS）中列出的大多数节点的积极响应才能引导。因此，除非你启动大多数节点，否则它们都会喋喋不休，但没有一个会引导。当足够的节点启动时，将随机超时
     <code>
 propose(N)
 </code>
     哪里
     <code>
 N
 </code>
     它试图在全局序列中设置下一个数字并成为领导者。所有尚未听到更高的节点
     <code>
 N
 </code>
     积极回应（ack）。听到更多号码的节点会做出负面反应（nack），并且会通过他们听过的最高号码。这使得节点都可以发现当前的最高值
     <code>
 N
 </code>
     最终。你不希望很多节点在同一时间超时并争取成为领导者，因为他们只会无休止地将它们推向高处
     <code>
 N
 </code>
     提案。因此，获得领导者是一个微妙的时刻。节点应该在他们提出建议之前等待随机超时，如果他们听到另一个具有更高数字的潜在领导者，则应该退出。
  
  
    至关重要的是每个节点使用交错的数字。例如它可能是
     <code>
 N=C*100+X
 </code>
     哪里
     <code>
 C
 </code>
     是一个柜台和
     <code>
 X<100
 </code>
     是节点号。如果任何节点看到另一个更高
     <code>
 N
 </code>
     比它上次发送的它可以反向计算
     <code>
 C
 </code>
    增加它，然后再创新高
     <code>
 N
 </code>
    。这意味着
     <code>
 N
 </code>
     不是顺序的（有间隙<100），但每个节点都是唯一的
     <code>
 N
 </code>
     可以命令看到最高。
  
  
    当节点听到大多数ack时，它知道它现在是领导者。现在我们遇到了任何前任领导人未提交工作的问题。之前的领导者可能刚刚失去了网络，因为当网络挂起时，当它发送提交消息时，大多数节点都接受了它的最后一个值。没有证据表明它已经死亡。在任何时候，它的提交消息都可以到达并竞争并击败新领导者的任何新消息。因此，新领导者不会试图忽略或覆盖最后一位领导者的工作：它合作并承诺左边的工作。赛车消息的协作和写入安全性是使用
     <code>
 N
 </code>
     数字和承诺。承诺是接受提案的节点将拒绝所有较低的消息
     <code>
 N
 </code>
    。
  
  
    当节点回应任何新领导者的新提议时，他们会回复任何剩余的工作
     <code>
 Vold
 </code>
     来自前任领导人的陈述
     <code>
 Nold,Vold
 </code>
     哪里
     <code>
 Nold
 </code>
     这是老领导人提出的工作建议
     <code>
 Vold
 </code>
    。节点只需告诉新领导者任何未提交的最高工作
     <code>
 N
 </code>
     因为承诺拒绝低价值的消息。新领导者将了解任何节点已经看到并选择提交的最高未提交工作
     <code>
 Vmax
 </code>
     作为它的第一个行动。它首先在一条消息中发送该作品
     <code>
 accept(N,V)
 </code>
    。当大多数节点响应时
     <code>
 accepted(N)
 </code>
     （如果他们没有做出新的承诺），领导者知道工作是在承诺的。然后它可以告诉所有节点
     <code>
 N
 </code>
     是承诺，他们可以承诺
     <code>
 V
 </code>
    。一旦它完成了最后一位领导者留下的任何未完成的工作，它就会通过发送这些新值并等待听到多数人的接受确认，然后告诉客户工作已经完成而开始新的客户工作。如果领导者崩溃，那么工作将继续保持，因为下一个领导者将完成提交的工作，其中任何节点尚未学习已经提交的值。
  
  
    这个答案中的一些术语可能含糊不清并导致更多问题。我不能指望说服任何人理解完整算法就足够了一旦。我的希望是，让读者对于paxos核心的优雅感到好奇;点对点协作。数学和形式证明它非常坚固很难;但直觉是，如果节点互相帮助，它们将最终保持一致应该很容易。我建议
    <a href="http://the-paper-trail.org/blog/consensus-protocols-paxos/" rel="nofollow">
      这篇论文的博客
    </A>
     作为阅读更多细节的良好来源。
  
</DIV>

1# afs-loliaholic | 2019-08-31 10-32

2# v-star*위위 | 2019-08-31 10-32