🧭
🧭
🧭
🧭
区块链技术指南
搜索文档…
🧭
🧭
🧭
🧭
区块链技术指南
前言
修订记录
如何贡献
区块链的诞生
核心技术概览
典型应用场景
分布式系统核心技术
一致性问题
共识算法
FLP 不可能原理
CAP 原理
ACID 原则与多阶段提交
Paxos 算法与 Raft 算法
拜占庭问题与算法
可靠性指标
本章小结
密码学与安全技术
比特币 —— 初露锋芒的区块链
以太坊 —— 挣脱加密货币的枷锁
超级账本 —— 面向企业的分布式账本
Fabric 安装与部署
智能合约开发
Fabric 架构与设计
区块链服务平台设计
性能与评测
附录
由
GitBook
提供支持
共识算法
共识(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 不可能原理”。该原理极其重要,可以看做是分布式领域里的“测不准原理”。
注:不光分布式系统领域,实际上很多领域都存在类似测不准原理的约束,或许说明世界本源就存在限制。
以前
一致性问题
下一个
FLP 不可能原理
最近更新
4mo ago
复制链接
在 GitHub 上编辑
内容
问题与挑战
常见算法
理论界限