分布式系统的核心:共识问题

用户头像
多颗糖
关注
发布于: 2020 年 10 月 03 日

写在前面



混乱的“一致性”问题

Consensus != Consistency



受翻译影响,网上很多讨论 paxos 或 raft 的博客使用“分布式一致性协议”或者“分布式一致性算法”这样的字眼,虽然在汉语中“达成共识”和“达成一致”是一个意思,但是必须要说明在这里讨论的是 consensus 问题,使用“共识”来表达更清晰一些。而 CAP 定理中的 C 和数据库 ACID 的 C 才是真正的“一致性”—— consistency 问题,尽管这两个 C 讨论的也不是同一个问题,但在这里不展开。



为了规范和清晰表达,在讨论 consensus 问题的时候统一使用“共识”一词。





注:在早些的文献中,共识(consensus)也叫做协商(agreement)。

共识问题



那么共识问题到底是什么呢?举个生活中的例子,小明和小王出去聚会,小明问:“小王,我们喝点什么吧?”

小王:“喝咖啡怎么样?”

小明:“好啊,那就来杯咖啡。”



在上面的场景中,小王提议喝一杯咖啡,小明表示同意,两人就“喝杯咖啡”这个问题达成共识,并根据这个结果采取行动。这就是生活中的共识。



在分布式系统中,共识就是系统中的多个节点对某个值达成一致。共识问题可以用数学语言来描述:一个分布式系统包含 n 个进程 {0, 1, 2,..., n-1},每个进程都有一个初值,进程之间互相通信,设计一种算法使得尽管出现故障,进程们仍协商出某个不可撤销的最终决定值,且每次执行都满足以下三个性质:

  • 终止性(Termination):所有正确的进程最终都会认同某一个值。

  • 协定性(Agreement):所有正确的进程认同的值都是同一个值。

  • 完整性(Integrity),也称作有效性(Validity):如果正确的进程都提议同一个值,那么所有处于认同状态的正确进程都选择该值。



完整性可以有一些变化,例如,一种较弱的完整性是认定值等于某些正确经常提议的值,而不必是所有进程提议的值。完整性也隐含了,最终被认同的值必定是某个节点提出过的。



为什么要达成共识?

我们首先介绍分布式系统达成共识的动机。



在[前文]()中,我们已经了解到分布式系统的几个主要难题:

  • 网络问题

  • 时钟问题

  • 节点故障问题



第一篇提到共识问题的文献[^1] 来自于 lamport 的 "[Time, Clocks and the Ordering of Events in a Distributed System](http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf)[^2]",尽管它并没有明确的提出共识(consensus)或者协商(agreement)的概念。论文阐述了在分布式系统中,你无法判断事件 A 是否发生在事件 B 之前,除非 A 和 B 存在某种依赖关系。由此还引出了分布式状态机的概念。



在分布式系统中,共识就常常应用在这种多副本状态机(Replicated state machines),状态机在每台节点上都存有副本,这些状态机都有相同的初始状态,每次状态转变、下个状态是什么都由相关进程共同决定,每一台节点的日志的值和顺序都相同。每个状态机在“哪个状态是下一个需要处理的状态”这个问题上达成共识,这就是一个共识问题。





最终,这些节点看起来就像一个单独的、高可靠的状态机。Raft 的论文[^3]提到,使用状态机我们就能克服上述三个问题:

  • 满足在所有非拜占庭条件下确保安全(不会返回错误结果),包括网络延迟、分区、丢包、重复和重排序。

  • 不依赖于时序。

  • 高可用。只要集群中的大部分节点正常运行,并能够互相通信且可以同客户端通信,这个集群就完全可用。因此,拥有5个节点的集群可以容忍其中的2个节点失败。假使通过停掉某些节点使其失败,稍后它们会从持久化存储的状态进行恢复,并重新加入到集群中。



不仅如此,达成共识还可以解决分布式系统中的以下经典问题:



  • 互斥(Mutual exclusion):哪个进程进入临界区访问资源?分布式锁?

  • 选主(Leader election):在单主复制的数据库,需要所有节点就哪个节点是领导者达成共识。如果一些由于网络故障而无法与其他节点通信,可能会产生两个领导者,它们都会接受写入,数据就可能会产生分歧,从而导致数据不一致或丢失。

  • 原子提交(Atomic commit):跨多节点或跨多分区事务的数据库中,一个事务可能在某些节点上失败,但在其他节点上成功。如果我们想要维护这种事务的原子性,必须让所有节点对事务的结果达成共识:要么全部提交,要么全部中止/回滚。



总而言之,在共识的帮助下,分布式系统就可以像单一节点一样工作——所以共识问题是分布式系统最基本的问题。



系统模型

在考虑如何达成共识之前,需要考虑分布式系统中有哪些可供选择的计算模型。主要有以下几个方面:



网络模型:

  • 同步(Synchronous):响应时间是在一个固定且已知的有限范围内。

  • 异步(Asynchronous):响应时间是无限的。



故障类型:

  • Fail-stop failures:节点突然宕机并停止响应其它节点。

  • Byzantine failures:源自“拜占庭将军问题” ,是指节点响应的数据会产生无法预料的结果,可能会互相矛盾或完全没有意义,这个节点甚至是在“说谎”,例如一个被黑客入侵的节点。



消息模型:

  • 口头消息(oral messages):消息被转述的时候是可能被篡改的。

  • 签名消息(signed messages):消息被发出来之后是无法伪造的,只要被篡改就会被发现。



作为最常见的,我们将分别讨论在同步系统和异步系统中的共识。在同步通信系统中达成共识是可行的(下文将会谈论这点),但是,在实际的分布式系统中同步通信是不切实际的,我们不知道消息是故障了还是延迟了。异步与同步相比是一种更通用的情况。一个适用于异步系统的算法,也能被用于同步系统,但是反过来并不成立。





让我们先从异步的情况开始。



异步系统中的共识



FLP 不可能(FLP Impossibility)



早在 1985 年,Fischer、Lynch 和 Paterson (FLP)在 "Impossibility of Distributed Consensus with One Faulty Process"[^4] 证明了:在一个异步系统中,即使只有一个进程出现了故障,也没有算法能保证达成共识。





简单来说,因为在一个异步系统中,进程可以随时发出响应,所以没有办法分辨一个进程是速度很慢还是已经崩溃,这不满足终止性(Termination)。详细的证明已经超出本文范围,不在细述[^5]。



此时,人们意识到一个分布式共识算法需要具有的两个属性:安全性(safety)和*活性(liveness)*。安全性意味着所有正确的进程都认同同一个值,活性意味着分布式系统最终会认同某一个值。每个共识算法要么牺牲掉一个属性,要么放宽对网络异步的假设。



虽然 FLP 不可能定理听着让人望而生畏,但也给后来的人们提供了研究的思路——不再尝试寻找异步通信系统中共识问题完全正确的解法。FLP 不可能是指无法确保达成共识,并不是说如果有一个进程出错,就永远无法达成共识。这种不可能的结果来自于算法流程中最坏的结果

  • 一个完全异步的系统

  • 发生了故障

  • 最后,不可能有一个确定的共识算法。



针对这些最坏的情况,可以找到一些方法,尽可能去绕过 FLP 不可能,能满足大部分情况下都能达成共识。《分布式系统:概念与设计》提到一般有三种办法:

  1. 故障屏蔽(Fault masking)

  2. 使用故障检测器(Failure detectors)

  3. 使用随机性算法(Non-Determinism)



1、故障屏蔽(Fault masking)



既然异步系统中无法证明能够达成共识,我们可以将异步系统转换为同步系统,故障屏蔽就是第一种方法。故障屏蔽假设故障的进程最终会恢复,并找到一种重新加入分布式系统的方式。如果没有收到来自某个进程的消息,就一直等待直到收到预期的消息。



例如,两阶段提交事务使用持久存储,能够从崩溃中恢复。如果一个进程崩溃,它会被重启(自动重启或由管理员重启)。进程在程序的关键点的持久存储中保留了足够多的信息,以便在崩溃和重启时能够利用这些数据继续工作。换句话说故障程序也能够像正确的进程一样工作,只是它有时候需要很长时间来执行一个恢复处理。



故障屏蔽被应用在各种系统设计中。



2、使用故障检测器(Failure detectors)



将异步系统转换为同步系统的第二个办法就是引入故障检测器,进程可以认为在超过一定时间没有响应的进程已经故障。一种很常见的故障检测器的实现:超时(timeout)。



但是,这种办法要求故障检测器是精确的。如果故障器不精确的话,系统可能放弃一个正常的进程;如果超时时间设定得很长,进程就需要等待(并且不能执行任何工作)较长的时间才能得出出错的结论。这个方法甚至有可能导致网络分区。



解决办法是使用“不完美”的故障检测器。Chanadra 和 Toueg 在 "The weakest failure detector for solving consensus[^6]" 中分析了一个故障检测器必须拥有的两个属性:

  • 完全性(Completeness):每一个故障的进程都会被每一个正确的进程怀疑。

  • 精确性(Accuracy):正确的进程没有被怀疑。



同时,他们还证明了,即使是使用不可靠的故障检测器,只要通信可靠,崩溃的进程不超过 N/2,那么共识问题是可以解决的。我们不需要实现 Strong Completeness 和 Strong Accuracy,只需要一个最终弱故障检测器(eventually weakly failure detector),该检测器具有如下性质:

  • 最终弱完全性(eventually weakly complete):每一个错误进程最终常常被一些正确进程怀疑;

  • 最终弱精确性(eventually weakly accurate):经过某个时刻后,至少一个正确的进程从来没有被其它正确进程怀疑。





该论文还证明了,在异步系统中,我们不能只依靠消息来实现一个最终弱故障检测器。但是,实际的故障检测器能够根据观察到的响应时间调节它的超时值。如果一个进程或者一个到检测器的连接很慢,那么超时值就会增加,那么错误地怀疑一个进程的情况将变得很少。从实用目的来看,这样的弱故障检测器与理想的最终弱故障检测器十分接近。



3、使用随机性算法(Non-Determinism)



这种解决不可能性的技术是引入一个随机算法,随机算法的输出不仅取决于外部的输入,还取决于执行过程中的随机概率。因此,给定两个完全相同的输入,该算法可能会输出两个不同的值。随机性算法使得“敌人”不能有效地阻碍达成共识。



和传统选出领导、节点再协作的模式不同,像区块链这类共识是基于哪个节点最快计算出难题来达成的。区块链中每一个新区块都由本轮最快计算出数学难题的节点添加,整个分布式网络持续不断地建设这条有时间戳的区块链,而承载了最多计算量的区块链正是达成了共识的主链(即累积计算难度最大)。



比特币使用了 PoW(Proof of Work)来维持共识,一些其它加密货币(如 DASH、NEO)使用 PoS(Proof of Stake),还有一些(如 Ripple)使用分布式账本(ledger)。



但是,这些随机性算法都无法严格满足安全性(safety)。攻击者可以囤积巨量算力,从而控制或影响网络的大量正常节点,例如控制 50% 以上网络算力即可以对 PoW 发起女巫攻击(Sybil Attack)。只不过前提是攻击者需要付出一大笔资金来囤积算力,实际中这种风险性很低,如果有这么强的算力还不如直接挖矿赚取收益。



同步系统中的共识



上述的方法 1 和 2,都想办法让系统比较“同步”。我们熟知的 Paxos 在异步系统中,由于活锁的存在,并没有完全解决共识问题(liveness不满足)。但 Paxos 被广泛应用在各种分布式系统中,就是因为在达成共识之前,系统并没有那么“异步”,还是有极大概率达成共识的。



Dolev 和 Strong 在 "Authenticated Algorithms for Byzantine Agreement[^7]" 证明了:同步系统中,如果 N 个进程中最多有 f 个会出现崩溃故障,那么经过 f + 1 轮消息传递后即可达成共识。



Fischer 和 Lynch 的 "A lower bound for the time to assure interactive consistency[^8]" 证明了,该结论同样适用于拜占庭故障



基于此,大多数实际应用都依赖于同步系统或部分同步系统的假设。



同步系统中的拜占庭将军问题

Leslie Lamport、Robert Shostak 和 Marshall Pease 在 "拜占庭将军问题(The Byzantine General’s Problem)[^9]" 论文中讨论了 3 个进程互相发送未签名(口头的)的消息,并证明了只要有一个进程出现故障,就无法满足拜占庭将军的条件。但如果使用签名的消息,那么 3 个将军中有一个出现故障,也能实现拜占庭共识。



Pease 将这种情况推广到了 N 个进程,也就是在一个有 f 个拜占庭故障节点的系统中,必须总共至少有 3f + 1 个节点才能够达成共识。即 N >= 3f + 1。



虽然同步系统下拜占庭将军问题的确存在解,但是代价很高,需要 O(N^f+1 ) 的信息交换量,只有在那些安全威胁很严重的地方使用(例如:航天工业)。



PBFT 算法



PBFT(Practical Byzantine Fault Tolerance) [^10] 算法顾名思义是一种实用的拜占庭容错算法,由 Miguel Castro 和 Barbara Liskov 发表于 1999 年。



算法的主要细节不再展开。PBFT 也是通过使用同步假设保证活性来绕过 FLP 不可能。PBFT 算法容错数量同样也是 N >= 3f + 1,但只需要 O(n^2 ) 信息交换量,即每台计算机都需要与网络中其他所有计算机通讯。



虽然 PBFT 已经有了一定的改进,但在大量参与者的场景还是不够实用,不过在拜占庭容错上已经作出很重要的突破,一些重要的思想也被后面的共识算法所借鉴。



结语



本文参考了很多资料文献,对“共识问题”的研究历史做一些基础概述,希望能对你带来一点帮助。



本文提到的论文,很多直接谈论结果,忽略了其中的数学证明,一是本文只是提纲挈领的讨论共识问题,建立一个知识框架,后续方便往里面填充内容;二是考虑到大部分读者对数学证明过程并不敢兴趣,也不想本文变成一本书那么长。本文也遗漏许多重要算法,后续如有必要会继续补充。



限于本人能力,恳请读者们对本文存在的错误和不足之处,欢迎留言或私信告诉我。



下篇我们将会讨论 Paxos 算法。



Reference



[^1]: Mark Mc Keown: "A brief history of Consensus, 2PC and Transaction"



[^2]: Lamport, Leslie (July 1978). "Time, Clocks and the Ordering of Events in a Distributed System". Communications of the ACM. 21 (7): 558–565.



[^3]: Ongaro, D., and Ousterhout, J. "In Search of an Understandable Consensus Algorithm". In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference (USA, 2014), USENIX ATC’14, USENIX Association, pp. 305–320.



[^4]: Fischer, M. J.; Lynch, N. A.; Paterson, M. S. (1985). "Impossibility of Distributed Consensus with One Faulty Process" . Journal of the ACM. 32 (2): 374–382.



[^5]: A Brief Tour of FLP Impossibility



[^6]: Chandra, T. D., Hadzilacos, V. & Toueg, S. (1992), "The weakest failure detector for solving consensus", in `Proc. of the 11th Annual ACM Symposium on Principles of Distributed Computing’.



[^7]: Dolev, D.; Strong, H.R. (1983). "Authenticated Algorithms for Byzantine Agreement". SIAM Journal on Computing. 12 (4).



[^8]: Michael J. Fischer, Nancy A. Lynch: "A lower bound for the time to assure interactive consistency". Inf. Process. Lett. 14(4): 183-186(1982)



[^9]: Lamport, L.; Shostak, R.; Pease, M. (1982). "The Byzantine Generals Problem". ACM Transactions on Programming Languages and Systems.



[^10]: Castro, Miguel; Liskov, Barbara (1999). Practical Byzantine Fault Tolerance. OSDI.





发布于: 2020 年 10 月 03 日 阅读数: 1116
用户头像

多颗糖

关注

还未添加个人签名 2018.05.18 加入

还未添加个人简介

评论

发布
暂无评论
分布式系统的核心:共识问题