《区块链底层设计Java实战》之第五章分布式一致性与共识算法
hweiyi 2019-01-23
第5 章 分布式一致性与共识算法
愿得一人心 白首不相离
第5 章 分布式一致性与共识算法 ........................................................................ 97
5.1 区块链的分布式 ....................................................................................... 98
5.2 Paxos 算法 ................................................................................................ 99
5.3 ZooKeeper 中的分布式一致算法实现 .................................................. 100
5.4 二、三阶段提交协议 ............................................................................. 103
5.4.1 二阶段提交协议 ......................................................................... 104
5.4.2 三阶段提交协议 ......................................................................... 105
5.5 区块链中的分布式一致性 ..................................................................... 106
5.5.1 PoW 算法 ................................................................................... 107
5.5.2 PoW 算法在比特币系统的源码实现 ........................................ 107
5.5.3 以太坊的PoW 实现 ................................................................... 109
5.6 联盟链中PBFT 的实现 .......................................................................... 111
5.6.1 什么是PBFT ............................................................................... 112
5.6.2 PBFT 基于WebSocket 的实现 ................................................... 114
5.6.3 PBFT 基于t-io 的实现 .............................................................. 128
5.7 小结 ......................................................................................................... 147
前面讲述了区块链系统中的两大基石——密码学的应用和P2P 网络的构建，本
章将介绍区块链系统的另一个基石——共识算法。
什么是共识呢？通常的理解是共同的认识、一致的看法。在区块链系统中，共
识指的是区块链系统中各个节点账本数据同步的实现。
共识算法并非凭空而生，而是基于分布式系统中为众人所知的分布式一致算法
得来的。因此，本章将从简单的分布式一致算法开始，一步步引导读者学习共识算
法。只要能掌握分布式一致算法的“美人心”，各类共识算法都会有似曾相识之感。
5.1 区块链的分布式
区块链系统本质上是分布式网络系统，而在分布式系统中，最核心的问题就是
“一致性（Consistency）的问题”，即在分布式网络的各个节点中如何保持节点数据的
一致性。如果在分布式系统中，一致性无法保证，那么分布式系统就变成了不可用
的系统，因此保证一致性是分布式系统中最为重要的内容。
熟悉分布式网络的读者，看到一致性时，往往会自然联想到分布式领域的CAP
理论。CAP 理论中论述了在任何一个分布式系统都无法同时满足Consistency（一致
性）、Availability（可用性）和Partition tolerance（分区容错性）这三个基本需求。最
多只能满足其中两项，而一致性是不能丢弃的。
当然，分布式系统中的分布式的一致性问题主要还是用来保证数据的一致性。
目前，各类分布式系统中使用的分布式一致性算法比较多，但基本都是源于
Paxos 分布式一致算法。正如Google Chubby 的作者Mike Burrows 所言：
“there is only one consensus protocol, and that’s Paxos – all other approaches are just
broken versions of Paxos. ”
中文可翻译为：世上只有一种一致性算法，那就是Paxos，所有其他一致性算法
都是Paxos 算法的不完整版。
因此分布式系统的一致性算法讲解将从Paxos 算法开始。
5.2 Paxos 算法
Paxos 算法是莱斯利·兰伯特（Leslie Lamport，现就职于微软研究院）于1990
年提出的，是一种基于消息传递的一致性算法。莱斯利·兰伯特于2013 年获得了图
灵奖。他的分布式计算理论奠定了这门学科的基础。
莱斯利·兰伯特在1978 年发表了论文《分布式系统内的时间、时钟事件顺序》
（Time, Clocks, and the Ordering of Events in a Distributed System），这篇论文成为目前
计算机科学史上被引用最多的文献。他的论文为并发系统的规范与验证课题的研究
贡献了核心原理。
Paxos 算法是在莱斯利·兰伯特的论文The Part-Time Parliament 中提出的。在论
文中，他以故事的方式讲述了Paxos 算法。
这个故事的主要内容如下：
古希腊有一个叫Paxos 的岛屿，是爱琴海上的一个小岛，Paxos 是一个兴盛
的商业贸易中心。在这个岛屿上，法律的制定与修订通过议会表决的形式
进行，而非传统的神权统治。
所有法律都必须经由议会成员投票表决后才能生效实施，而且已通过的律
法必须被记录在案。
在岛上，商业繁荣，做生意赚钱才是头等大事，因此没有人愿意始终在议
会大厅里从头到尾参与每一个法律表决的会议。为此，每一个议员都来维
护一个法律律簿，用来记录一系列已通过的法令，每个法令带有一个唯一
编号。为了保持各个议员法律律簿内容的一致性，法律律簿是用擦不掉的
墨水书写而成的，所以内容一旦书写就不能改变。
在议会中有多个角色的成员：议员和服务员。服务员的工作是在比较嘈杂
的议会厅里传递信息，议员的工作是发起法律提案或将通过的法律记录在
自己的法律律簿上。
由于议员和服务员有可能并不可靠，他们可能随时会因为各种事情临时甚
至是彻底离开议会大厅，服务员也有可能重复传递消息，当然也可能有新
的议员在临时事务处理完毕后再回到议会大厅进行法律表决，因此议会的
协议要求保证在上述情况下能够正确地修订法律并且不会产生冲突。
在法律表决时，议员的角色分为proposers 和acceptors。
通过一个法律决议时，分为两个阶段：
阶段1：prepare 阶段
proposer 选择一个提案编号n，并将prepare 请求发送给acceptors 群体。
acceptor 收到prepare 消息后，如果提案的编号大于它已经回复的所有
prepare 消息，则acceptor 将自己上次接受的提案回复给proposer，并承诺不
再回复小于n 的提案；如果提案的编号小于等于它已经回复的所有prepare
消息，则说明是重复消息，不再重复处理。
阶段2：批准阶段
当proposer 收到多数acceptors 对prepare 的回复后，就进入批准阶段。它要
向回复prepare 请求的acceptors 发送accept 请求。acceptor 收到accept 请求
后，则立即接受这个请求。
除经典的分布式一致性算法Paxos 外，还有一些算法也隐藏于我们常用的中间件
中，如ZooKeeper，二、三阶段提交协议等。下面将分别介绍分布式一致性算法在
Zookeeper 和二、三阶段提交协议中的应用。
5.3 ZooKeeper 中的分布式一致算法实现
ZooKeeper 是一个开源的分布式协调服务，分布式应用程序可以基于它实现诸如
数据发布/发布、负载均衡、命名服务、分布式协调/通知、集群管理、Master 选举、
分布式锁和分布式队列等功能。ZooKeeper 的设计思想源于Google 的Chubby，目前
是Hadoop 和Hbase 中的重要组件。
更多详细内容详见：
《区块链底层设计Java实战》二维码
