时光倒流
分布式系统是一个非常广的领域,但为了简化并寻找相关性,我们将只关注 共识(consensus) 子领域。让我们从最开始说起,时间回溯到上世纪 80 年代。一群非常聪明的计算机科学家试图解答这样一个问题:一组机器如何才能在信息上达成一致?我们要逐步分解这个问题,因为讲道理,这个问题比较奇怪。
假设你有一个数据库,它将存储任务关键数据,例如,金融信息(银行等企业)。你不能丢失(数据库中的)任何信息,因此你将立刻尝试将数据复制到其他机器上,标记为 m0,m1,……,mn。如果任意某台机器宕机了,并不会彻底丢失关键信息。
我们可以用最直观的方法构建这个系统,即:将其中一台机器设置为“领导者(leader)”(比如,m0),其他机器制定为追随者(followers)。每当有来自客户端的新交易(例如,“从 Bob 的账户上减少 10 美元”)时,领导则命令全部追随者执行该交易。这听起来不错,只是有一些问题。比如, m0 命令 m3 从 Bob 的账户上减去 10 美元,但是信息丢失了,它没有送达 m3,那么系统会出现什么情况呢?这种情况就太糟糕了。我们不能再依据 m3 恢复数据,因为它现在已经包含 不一致的数据。注意:不一致的数据意味着你的计算机现在存储了与其他机器不同的数据,而它们本不应该存储不同的数据。
开动脑筋
该问题的基础解决方法是确保 m3 真正收到了该信息(即,交易执行信息)。我们现在已经接触到了我们的第一个原子提交协议,即两阶段提交(2PC)。它之所以具有原子性,是因为它的思想是:如果要提交交易,那么这笔交易要么在 所有节点都提交,要么在 所有节点都不提交(是的,我知道你在想啥,看起来这并不解决问题)。但是,你需要认识到:m0 不仅仅盲目地从客户端接收信息,并把这些信息发送给其他机器,它也保证副本机器 确实收到 信息。好的,但如果 m6 出现了某些问题,即使其他机器已经从 Bob 的账户中扣除了 10 美元,那么又将发生什么呢?不用担心,只要回滚就可以解决!具体流程图如下:
共识简介
聪明的读者可能已经注意到我们的 2PC/3PC 结构上的一些漏洞。例如,如果领导者宕机了,它需要被取代。然而,还有其他更紧迫的缺陷。
首先,要不我们在系统中引入另外一个领导者(m1)?我们为了不被 m0 的故障所困,确实需要这么做。然而,这就会引起协调问题。如果 Bob 发出了两笔交易,其中, T1 = “给 Bob 的账户减少 10 美元”,T2 = “给 Bob 的账户减少 20 美元”,但 Bob 账户上实际只有 20 美元,那么可能会产生混乱。m0 可能在网络中发布 T1,但是 m1 可能发布 T2。(最终结果)取决于操作发生的顺序,追随者机器将会验证交易,但会产生不一致的数据。那么现在 Bob 剩余 10 美元还是 0 美元呢?对于分布式系统而言,这是最糟糕的情况。
其次,假设我们解决了领导者之间的协调问题。如果某些追随者节点宕机又会怎么样呢?毕竟,这就是我们最初的假设。我们需要怎么处理这些节点呢?如果我们等待它们重新上线,可能会严重影响系统性能,尤其是在需要人为干预以恢复某些服务器的情况下。如果我们选择忽略掉一些宕机的机器,那么我们应该选择忽略多少呢?更重要的是,如果有些机器在线,但是它们硬盘坏了怎么办?它们可能正运行协议,但是并不能成功写入硬盘。预测这些问题是一件非常复杂的事情,所以我们需要一个真正强健的机制,能够简单地忽略所有这些问题,确保机器 在某些阈值的范围内能够正确执行。就分布式系统而言,这就是圣杯。
这些(以及其他)问题将带领我们认识第一个共识协议,Paxos。这也让我们回到了最初的问题:一组机器如何才能在信息上达成一致?由 Leslie Lamport 提出的 Paxos 共识协议,应用于计算 宕机故障(Crash Fault) 模型中。我们不会具体介绍 Paxos 共识算法的运行细节,因为这些细节非常晦涩难懂,但是从高度抽象的层面来看,它实际上又很简单。协议以“轮次”为单位运行,在每一轮中,某一台机器都会提出一个新的数字(比如,索引 n)。如果机群中的大多数机器支持该数值,那么就由提议者收集投票并在网络中发布一次提交。如果另一名提议者也在第 n 轮发布了一个数字,那么它将会被拒绝。Paxos 共识算法的神奇之处在于只要大多数机器接受某个提案,那么 Paxos 就能保证系统永远不会到达一个不一致的状态。这很神奇,现在你只需要知道这些。
此外,我在上一段提到的术语“宕机故障”。宕机故障是网络中的机器在最坏情况下也只会死机,而不会随意行动。这意味着机器要拒绝信息时不会发出“好的,我接受这笔交易”的反馈。这让我们理解区块链的运行原理更前进了一步。
千奇百怪的故障
事实证明,宕机故障模型基本上是当今数据中心实际在使用的模型。任何企业如果正在部署需要共识协议的分布式应用程序(看到这里,你应该也能真正明白我们为什么需要共识协议了),那么它们很可能在宕机故障模型中运行,例如,Paxos。
但是等等,如果机器被黑了又会发生什么情况呢?大多数企业都认为这种情况不会发生,的确,采用 ***、防火墙以及其他安全措施相结合的方式,基本不可能发生黑客攻击。但是,如果我们仍然关心是否有黑客入侵,我们就需要一个能容忍机器“说谎”的共识协议。这就涉及到拜占庭容错(Byzantine Fault Tolerance,BFT)的相关内容。为什么叫做拜占庭呢?因为在当时,这个问题(同样是由 Lamport 提出的)是用拜占庭将军通信问题的形式提出来的,拜占庭将军及其下属被敌军分隔开来,但他们想就进攻计划互相沟通。
一些(烦人但必要的)术语
你也许会问:“好吧,Kevin,我没有很多时间学习这方面内容,我只需要知道宕机故障(crash-fault)和拜占庭故障(Byzantine-fault)两个术语就能成为分布式系统专家么?”答案 几乎是 肯定的。你确实不用费心去理解共识协议的具体内容,但是你需要理解出现的一些通用的术语。这里有一些:
故障类型:
宕机故障:正如我们所说的,如果假设网络中的机器在最坏情况下也只会死机,则需要应用共识协议以解决宕机故障。
拜占庭故障:机器可能不仅会出现宕机故障,他们还可能撒谎。实际上,他们可以任意行事。
网络模型:
同步:我们不仅需要考虑机器可能遇到的故障类型,还需要考虑我们可以做出的网络通信假设的类型。在同步通信模型中,假设正常节点将在 已知时间上限的时间内 发送和接收信息。例如,可以假设每条信息都在 5 秒、5 分钟或 5 小时内送达。
异步:异步与同步完全相反。即使对于正常节点,消息延迟也是不可确定的。这里的一个重要的结论是,无法区分响应时间无限长的正常节点与宕机的节点。
部分同步:部分同步模型介于全同步和全异步之间。即,延迟存在上界,但上界不可确定。这个模型有一些奇怪的结果,它们会增加我们理解的复杂性。需要理解的最重要的一点是,这种通信模型最接近于实际的广域网通信(即,互联网)。这仅仅代表我的观点,如果其他专家不赞同也请不要深究我的错误。
信息模型:在此我只讨论一种模型:认证通信。意味着节点必须对信息签名,每个节点都可以验证来自其他节点的信息是否经过了签名(认证)。为什么这是唯一要考虑的模型呢?因为,在(上文介绍的)所有类型的网络模型中,不可能使用非认证信息通信来达成共识。所以,我们不考虑其他模型,而仅关注认证通信的情况。
安全保证模型:名字有点奇怪,但是我认为这是最恰当的表述。
非概率性:如果某个共识协议是非概率性(即确定性的)的,意味着只要正常节点数量超过阈值,(系统)安全就得到保障(没有概率分布)。这其实很令人困惑,但当我介绍下一个模型时,这个模型就好理解了。
概率性:如果某个共识协议是概率性的,那么便自然存在一个概率分布。通常来说,这种模式保证安全的概率只有 1 - ϵ,其中 ϵ 是由系统设计者规定的某个数值。例如,即便 正常节点数量超过阈值,概率协议也只能保证 99% 的正确性。记住这一点!这非常重要!
基本上,这就是你现在需要知道的所有术语。至此,我们介绍了共识算法是用来做什么的,共识算法种类、基本思想。现在,让我们来吃蛋糕(区块链)吧!
区块链,或者说……其实我真的不在乎它叫啥
好的,让我们一起复习一下。共识协议本质上就是一些算法,据此我们可以在许多或多或少相互怀疑的机器之间部署数据库(也就是说,它们不相信特定某个人说的东西,但是它们相信大多数人会说出真相)。我们介绍了在选择共识协议时可以做出的不同假设,包括同步假设或不同步假设,也包括确定性地保证安全或仅在概率性下保证安全。
当我在上文介绍 Paxos 时,我提到了节点 对提案进行投票。事实证明,投票是几十年来唯一使用的机制。投票适用于大多数情况。然而,假设我想 公开 部署数据库,允许任何人加入并发布交易。现在就会有一个巨大的问题:如果我允许任何人加入我的系统,我就不能确定谁是谁。我并不清楚谁参加了。基本上,没有身份认证的共识是不可能的。或者更确切地说,直到 Satoshi 出现(这个问题才解决)。
比特币确实解决了这个问题。Satoshi 的独到见解是,我们可以使用不同的机制来代替投票,即工作量证明(Proof-of-work,PoW)。比特币是第一个对网络中人完全没有任何假设的共识算法。由于不需要身份认证,比特币能够完美地部署在 无认证设置(permissionless) 的环境下,在这个环境中节点不需要其他节点许可便可以加入网络。比特币很棒,又很简单:节点不投票,而是使用附加在每个提案上的权重来进行提议(数值)。这个权重就是工作量证明,通过求解密码学难题来得到。提案被连接在一起,从而使最重(而不是最长的,这经常被误解)的提案构成“正确的”历史。这就是比特币的基本原理,就是这样!
最后一件事:比特币是我们上面讨论的哪种模型呢?比特币在拜占庭容错模型下运行,网络是同步的(校对注:原文如此,疑为作者笔误),信息都是认证过的(由私钥持有者签名),并且以一定概率保证安全性。意味着如果存在分叉的情况下,区块链可能在任意时刻回滚。换句话说,你可能会接受 Bob 现在只有 10 美元的事实,但也要意识到你有可能是错的。
结论
基本内容我们已经讲完了。你已经知道了一个研究分布式系统的博士生到底在研究啥了。你现在已经是区块链世界中一个自信、见多识广的读者了。
BitMere.com is Information release platform,just provides information storage space services.
The opinions expressed are solely those of the author,Does not constitute advice, please treat with caution.
The opinions expressed are solely those of the author,Does not constitute advice, please treat with caution.
Write the first review