共识算法

共识(Consensus),很多时候会见到与一致性(Consistency)术语放在一起讨论。严谨地讲,两者的含义并不完全相同。

一致性的含义比共识宽泛,在不同场景(基于事务的数据库、分布式系统等)下意义不同。具体到分布式系统场景下,一致性指的是多个副本对外呈现的状态。如前面提到的顺序一致性、线性一致性,描述了多节点对数据状态的共同维护能力。而共识,则特指在分布式系统中多个节点之间对某个事情(例如多个事务请求,先执行谁?)达成一致看法的过程。因此,达成某种共识并不意味着就保障了一致性。

实践中,要保障系统满足不同程度的一致性,往往需要通过共识算法来达成。

共识算法解决的是分布式系统对某个提案(Proposal),大部分节点达成一致意见的过程。提案的含义在分布式系统中十分宽泛,如多个事件发生的顺序、某个键对应的值、谁是主节点……等等。可以认为任何可以达成一致的信息都是一个提案。

对于分布式系统来讲,各个节点通常都是相同的确定性状态机模型(又称为状态机复制问题,State-Machine Replication),从相同初始状态开始接收相同顺序的指令,则可以保证相同的结果状态。因此,系统中多个节点最关键地是对多个事件的顺序进行共识,即排序。

注:计算机世界里采用的是典型的“多数人暴政”,足够简单、高效。

问题与挑战

无论是在现实生活中,还是计算机世界里,达成共识都要解决两个基本的问题:

  • 首先,如何提出一个待共识的提案?如通过令牌传递、随机选取、权重比较、求解难题……等;
  • 其次,如何让多个节点对该提案达成共识(同意或拒绝),如投票、规则验证……等。

理论上,如果分布式系统中各节点都能以十分“理想”的性能(瞬间响应、超高吞吐)稳定运行,节点之间通信瞬时送达(如量子纠缠),则实现共识过程并不十分困难,简单地通过广播进行瞬时投票和应答即可。

可惜地是,现实中这样的“理想”系统并不存在。不同节点之间通信存在延迟(光速物理限制、通信处理延迟),并且任意环节都可能存在故障(系统规模越大,发生故障可能性越高)。如通信网络会发生中断、节点会发生故障、甚至存在被入侵的节点故意伪造消息,破坏正常的共识过程。

一般地,把出现故障(Crash 或 Fail-stop,即不响应)但不会伪造信息的情况称为“非拜占庭错误(Non-Byzantine Fault)”或“故障错误(Crash Fault)”;伪造信息恶意响应的情况称为“拜占庭错误”(Byzantine Fault),对应节点为拜占庭节点。显然,后者场景中因为存在“捣乱者”更难达成共识。

此外,任何处理都需要成本,共识也是如此。当存在一定信任前提(如接入节点都经过验证、节点性能稳定、安全保障很高)时,达成共识相对容易,共识性能也较高;反之在不可信的场景下,达成共识很难,需要付出较大成本(如时间、经济、安全等),而且性能往往较差(如工作量证明算法)。

注:非拜占庭场景的典型例子是通过报数来统计人数,即便偶有冲突(如两人同时报一个数)也能很快解决;拜占庭场景的一个常见例子是“杀人游戏”,当参与者众多时很难快速达成共识。

常见算法

根据解决的场景是否允许拜占庭错误情况,共识算法可以分为 Crash Fault Tolerance (CFT) 和 Byzantine Fault Tolerance(BFT)两类。

对于非拜占庭错误的情况,已经存在不少经典的算法,包括 Paxos(1990 年)、Raft(2014 年)及其变种等。这类容错算法往往性能比较好,处理较快,容忍不超过一半的故障节点。

对于要能容忍拜占庭错误的情况,包括 PBFT(Practical Byzantine Fault Tolerance,1999 年)为代表的确定性系列算法、PoW(1997 年)为代表的概率算法等。确定性算法一旦达成共识就不可逆转,即共识是最终结果;而概率类算法的共识结果则是临时的,随着时间推移或某种强化,共识结果被推翻的概率越来越小,最终成为事实上结果。拜占庭类容错算法往往性能较差,容忍不超过 1/3 的故障节点。

此外,XFT(Cross Fault Tolerance,2015 年)等最近提出的改进算法可以提供类似 CFT 的处理响应速度,并能在大多数节点正常工作时提供 BFT 保障。

Algorand 算法(2017 年)基于 PBFT 进行改进,通过引入可验证随机函数解决了提案选择的问题,理论上可以在容忍拜占庭错误的前提下实现更好的性能(1000+ TPS)。

注:实践中,对客户端来说要拿到共识结果需要自行验证,典型地,可访问足够多个服务节点来比对结果,确保获取结果的准确性。

理论界限

科学家都喜欢探寻问题最坏情况的理论界限。那么,共识问题的最坏界限在哪里呢?很不幸,在推广到任意情况时,分布式系统的共识问题无通用解。

这似乎很容易理解,当多个节点之间的通信网络自身不可靠情况下,很显然,无法确保实现共识(例如,所有涉及共识的消息都丢失)。那么,对于一个设计得当,可以大概率保证消息正确送达的网络,是不是一定能获得共识呢?

理论证明告诉我们,即便在网络通信可靠情况下,一个可扩展的分布式系统的共识问题通用解法的下限是——没有下限(无解)。

这个结论,被称为“FLP 不可能原理”。该原理极其重要,可以看做是分布式领域里的“测不准原理”。

注:不光分布式系统领域,实际上很多领域都存在类似测不准原理的约束,或许说明世界本源就存在限制。