回顾历史,展望未来
我本人比较关注共识算法和它们的应用。共识算法不同于普通的算法,共识算法本身要考虑到分布式系统的特点,比如:
- 系统通信模型,同步还是异步。同步有强保证,但是性能低;异步则相反
- 没有精确的全局时钟,精确的本地时钟之间存在时钟漂移,无法构建全序关系,只有偏序
- 不可靠的网络,消息可能延迟、丢失、重复、乱序,网络可能分区
- 节点随时可能崩溃(硬件软件),甚至被攻击(拜占庭错误)
- 如何从故障中恢复
在如此复杂的情况下,让多个节点作出相同的决定是十分复杂困难的。
Raft算法在2013年才被提出,以可理解性闻名,短短几年就有了数十个实现。在此之前,它的前辈Paxos由于晦涩难懂、工程落地困难,少有开源实现。
Google专门写了一篇论文( Paxos made live )讨论Paxos实现过程中遇到的种种困难。Google采用的方法比较厉害,先是写了一个形式化状态机验证语言及其翻译器,先把Paxos形式化保证其正确性,再自动翻译成C++做工程优化。即便是这样,Google也采了不少坑:生成的代码不能满足性能要求,论文也没有考虑过一些实际需求( Lamport: “我就是搞数学的,搞工程太low了” ),所以要对算法进行优化和修改,但是论文的形式证明不能保证修改后的算法的正确性,算法在一些corner case中会出错。
与Paxos进行数学证明的风格相比,Raft大论文不仅有算法伪代码,还指出如何实现线性一致性、集群成员变更如何进行、以及各种优化方法,这也是为什么它更易于理解和工程落地。
但Raft、Paxos、ZAB、VR并不是完美的,除了各自的性能差别,它们只适合应用在数据中心、集群等环境,对于内部网络有很高要求。比如Raft,如果Leader A和一个follower B之间的连接不稳定,不时地断开又恢复,那么leadership可能在AB之间不断转移,导致整个集群把时间浪费在election上。在移动网络环境下,Raft几乎无法运行。
Paxos的变种算法不断提出。如2017年提出的EPaxos,采用no-leader结构+因果一致性,吞吐比Multi-Paxos强,但算法十分复杂。Raft和Paxos只关心如何达成共识,并不关心达成共识的内容是什么。而EPaxos则进一步考虑了内容的依赖关系:存在依赖的操作要依次执行,没有依赖关系的操作可以乱序提交。
除去分布式关系型数据库这些场景,共识算法的另一个热点应用就是区块链。区块链的形成共识的过程,就是确定下一个区块的内容是什么。
此外,区块链需要拜占庭容错(BFT),因为任何节点都可能是恶意的。早在Lamport在他的拜占庭将军问题论文中提出OM和SM两个算法,每轮共识需要O(nf+1)次通信而且要求可靠的网络,不具有现实可行性。
1999年提出了一种PBFT(实用拜占庭容错)算法,每一轮共识需要O(n2)次通信,其中n为系统中节点的个数。
然而最初的区块链系统采用的不是PBFT,而是PoW(工作量证明)。这不仅与PBFT的通信复杂度(100个节点就很慢了)有关,更与中本聪的理念有关,他在论文中提出了“one CPU one vote”的口号,期望通过算力而不是节点的数量来衡量投票权。
PoW与Paxos类算法不一样地方在于:
- Paxos及其衍生算法采取Quorum机制,也就是通过任意两个Majority集合(超过一半节点)的交集必定非空,从而在每一轮共识起到信息传递作用。共识一旦达成不可逆转。
- PoW通过算力竞争来产生下一个区块,但是已经形成的区块是可能被覆盖的,只要对方算力够强。
区块链的共识算法会深刻影响系统的利益分配,比如BTC的PoW机制,算力越强收益越大;未来以太坊要采用的PoS机制,谁的币龄越大谁的权力就越大。
就目前来说,公众对区块链的热度逐渐褪色,但是学界和业界也逐渐关注区块链的应用,也提出了很多的共识算法来弥补当前的不足。
目前的共识算法远不是十全十美,比如:
- PoW耗电惊人,仅2018一年BTC + ETH的用电量占全球用电量的0.40%,在全世界国家耗电量中排行50+。
- PoW还导致算力分布集中在极少数大型矿场上,与最初去中心化的目标产生了偏差。
- 最为人诟病的是性能问题:如BTC平均出块时间为十分钟,一个区块只能承载几千个交易,远不能大规模使用。
现在还出现了一些基于有向无环图的共识算法,在吞吐上能大幅度超越PBFT和PoW。
总的来说,共识算法在蓬勃发展。在复杂、不可靠、不可信任的环境下,数以千计、万计的节点通过共识算法作出相同的决定,推动系统前进,这是一个令人惊叹的成就,这也是共识算法最为吸引我的地方。