可可金融旗下CoCo交易所开放上币申请通道

零基础读懂分布式系统(二)

云宝小课堂·热度: 3650
我们需要在有坏人的情况下也可以实现共识的算法,有没有可能?莱斯利·兰伯特建立了一个模型来讨论这种可能性,该模型被称作拜占庭将军问题,其中的拜占庭节点就是坏人节点,它们会传递干扰信息阻碍整个系统达成共识。


        Paxos 虽然能实现共识,但它的算法是建立在所有计算机都是「好人」的基础上的,这些计算机要么沉默,要么发出正确的声音,因此整个系统中只有一种声音,大家就这个声音达成共识即可。而如果计算机中有「坏人」,系统里就会出现坏人的声音和好人的声音,Paxos 算法无法处理这一情况。

        我们需要在有坏人的情况下也可以实现共识的算法,有没有可能?莱斯利·兰伯特建立了一个模型来讨论这种可能性,该模型被称作拜占庭将军问题,其中的拜占庭节点就是坏人节点,它们会传递干扰信息阻碍整个系统达成共识。

        在论文《The Byzantine Generals Problem》中,兰伯特提出了几种解决方案,其中一种可以在拜占庭节点不到 1/3 时实现系统的共识。也就是说,如果系统中坏人的数量少于 1/3,就可以通过算法实现共识。

        这之后出现的 DLS 算法、PBFT 算法使用拜占庭容错算法)都是在此基础上发展出来的。

        PBFT 是具有代表性的一种拜占庭容错算法,其实现过程大致如下。不理解该过程也没关系,知道通过这种沟通方式能够达成共识就可以。

        1.pre-prepare 阶段:领导者发送结果给所有追随者。领导者在本图中是 0 号节点,它把结果发给追随者 1、2、3 号节点。

        2.prepare 阶段如果追随者认为结果没有错误,就告诉所有其他节点自己认可这个结果。比如 1 号节点会把自己的认可消息发给 0、2、3 号节点。

        3.commit 阶段:如果追随者发现超过 2/3 的节点认可了领导者的结果,就告诉所有其他节点自己接受这个结果为最终结果。

        4.reply 阶段:如果领导者和追随者发现超过 2/3 的节点接受了最终结果,就可以认为大部分节点达成了共识,就把该共识反馈给客户端;如果客户端收到超过 1/3 的节点的相同的共识,就可以认为全网达成了共识。

        到此,我们就解决了有拜占庭节点的分布式系统的共识问题。不过如果系统中坏人的数量等于或多于 1/3,依然是无法达成共识的。我们能做的是通过系统的准入条件或激励措施,让坏人可以少于 1/3。对分布式系统的第二阶段的探索到这里就结束了,接下来进入到第三阶段。


        不管 Paxos 还是 PBFT,都使用了同步性假设,事实上,大家对共识算法的研究几乎都是在该方向上的,直到中本聪共识的出现。中本聪共识使用的是非确定性机制。

        这是什么意思呢?我们可以把一个由 12 台计算机组成的分布式系统想象成一个由 12 名陪审员组成的陪审团。我们把这 12 个人关在会议室里,递进去一张纸条阐述案情,然后坐在会议室门口等他们给出审理的结果。

        这 12 个人对于如何判决会有不同的意见,随着讨论的深入也可能改变自己的立场,还有的人可能睡着了无法发表看法(参考《十二怒汉》)。那么坐在门口等的人有两种选择。第一种选择是你们去讨论吧,让我等多久都可以,但最后你们给我的必须是唯一确定的审理结果;第二种选择是我等不了,你们先把最多人同意的那个结果给我,如果之后出现一个更多人同意的结果,我再改成那个结果。

        使用同步性假设的共识算法在前文已经详细地介绍过了,它们通过引入超时概念忽略出现问题的计算机,从而达成共识。使用非确定性机制的中本聪共识描述起来也很简单:如果你看到某提议的区块拥有最多的工作量证明,就接受该区块,这也被称作最长链规则。它的具体实现过程大家都很熟悉,本文就不再赘述了。

        现在,让我们看看使用同步性假设的系统(Finality,PoS 中使用较多)和使用非确定性机制的系统(Liveness,PoW 中使用较多)有什么不同。但需要提醒的是,并非所有的 PoS 都是 Finality 路线,比如 Casper FFG 就不是;而 PoW 也不是只能走 Liveness 路线,虽然并没有人设计 PoW 上的 Finality 共识。

        PoW 和 PoS 的不同在于一个是 Work,一个是 Stake。之所以需要强调这一点,是因为在关于 PoW 和 PoS 的讨论中,我们往往不是在讨论 Work 机制与 Stake 机制的不同,而是在比较 Finality 系统与 Liveness 系统的不同。比如「无需许可」性,它基本是一个 Finality 系统与 Liveness 系统的话题,而不是 Work 与 Stake 的争论点。

        让我们回到有 12 个评审员的会议室。为了追求 Finality,每个评审员都需要了解其他每一个人的想法,也需要把自己的想法告诉其他每一个人,因此通信复杂度会随着评审员人数的增加而迅速递增,整个系统将因此不可用,所以必须控制陪审员的数量。

        那么对于一个分布式系统而言就是,只挑选少数节点进入会议室,由它们决定共识,而其他节点只接受共识。因此这种系统中有三种角色,领导者、追随者和学习者,领导者和追随者是会议室中的评审员,他们需要好好工作,不然可能导致系统无法达成共识。

        中本聪共识追求的是 Liveness,节点 / 评审员不需要与其他的每一个节点沟通,它只需要与自己身边的节点交流即可,因此通信复杂度不会因为节点数量的增加而增加。你想成为评审员,就可以走进会议室成为评审员,无需许可,也不会增加陪审团达成共识的难度,同时你也可以不工作或随时离开。该系统中只有领导者和追随者两种角色,所有人都在那间会议室里参与共识。

        这样看来中本聪共识似乎更符合大家对分布式系统的开放性的期望,但别忘了它之所以可以如此设计,是因为牺牲了 Finality,它的输出结果是一个概率上的最终结果。

        试想,你百分百在星巴克得到一杯咖啡,但星巴克并不能百分百收到钱,这并不符合大多数人能理解的世界运转规则。所以非确定性机制有它自己的短板,以及不适合的场景。

        另一方面,Finality 系统在保证了结果的确定性后,系统设计就要反过来追求 Liveness;而 Liveness 系统在保证了网络的开放性后,系统设计就要反过来追求 Finality。中本聪共识为了提高结果的确定性或安全性,就需要做出其他让步,比如 TPS。

        以比特币为例。比特币可以把出块时间从 10 分钟提高到 1 分钟,TPS 会大幅提升,但 1 分钟的时间不够把消息传遍全网,系统中就会出现很多分叉,导致结果的可确定性变低;比特币也可以把区块大小从 1MB 提高到 100MB,TPS 也会提升,但大区块对网络和节点的要求高,会增加节点的进入门槛从而带来中心化,导致输出结果容易被篡改。

        所以你看,设计分布式系统就像与撒旦做交易,你得到一些,必然要交出一些。没有最好的系统,只有适合解决某类问题的系统;没有单纯的指标比较,只有是在什么设定下实现这种指标。

如果你理解了这一点,这篇文章的目的就达到了,而我们对分布式系统的探索到此也就全部结束了。

声明:本文为入驻“火星号”作者作品,不代表火星财经官方立场。
转载请联系网页底部:内容合作栏目,邮件进行授权。授权后转载时请注明出处、作者和本文链接。 未经许可擅自转载本站文章,将追究相关法律责任,侵权必究。
提示:投资有风险,入市须谨慎,本资讯不作为投资理财建议。
语音技术由科大讯飞提供
最近更新
本文来源:
原文标题:
涨跌幅
排名币种成交额价格(USD)涨幅
您可能感兴趣的内容
暂无内容

评论0