分布式系统全景分析：从故障容错到拜占庭容错

注意:

下面提到的节点根据上下文有不同的含义，说到 zookeeper 时主要是指注册在 zookeeper 的不同类型的 znode，说到集群时是指集群的不同实例。

谈到分布式系统就避免不了 CAP 理论，分区容错对于分布式系统并不是一个可选性，多节点因为网络或自身故障引起通信延迟或丢包，从而导致系统分区时，只能在一致性和可用性之间选一个，想要保持完全一致，对外服务就只能等待，有可能会服务超时。

对于单机系统来说就不存在上述多节点通信的问题，所以排除 P,比如关系型数据库就是取了 CA，高可用和强一致性，并且由事务支持延伸出 ACID 理论。

而分布式系统基于大量实践衍生出了 BASE 理论，从高可用到基本可用 Basically Available，从强一致到最终一致性 Eventual Consistency，加上软状态 Soft State， 基本在追求一种平衡，对于一个系统来说如果一直都无法保持一致，基本也是不堪用的了，所以一致性还是基本上都是要追求的，只不过根据强弱程度可以进一步细分。

思维比较缜密的读者对于 eventual consistency 可能会有疑问，是在什么时间范围内达到一致，这里不得不提另一个理论 FLP，跟 CAP 类似，但是从另外一个角度解读，包含 safety, liveness, fault tolerance，liveness 用来指示分布式系统内的各个节点必须在合理的时间内 in bounded time 达成一致。

1.关于一致性

对于一个单机系统，一致性一般是强调在并发请求的情况下，该系统事务级别和会话级别下根据系统的设置表现出来的读写的一致或冲突，比如两个并发事务的读写冲突， 比如前面说的关系型数据库，不考虑主从数据库单机部署时，一致性的表现是会根据数据库的隔离水平设置 isolation level 有所不同，有兴趣可以自己查阅<Isolation (database systems)>。

对于分布式系统，一致性一般是强调集群内部各个节点上面的相关数据保持同步。

本质上其实都是大同小异，只是说一个是宏观从集群角度看，一个是从微观的单机看，分布式系统当成一个整体看对外部系统来说就是一个大的“单机”系统。

根据角度的不同有很多分类方式，比如根据强弱简单分为：

• 强一致性 strong consistency

• 最终一致性 eventual consistency

• 弱一致性 weak consistency

还有其他角度更细分的单调读一致性，单调写一致性，会话一致性，读后写一致性，写后读一致性，顺序一致性等， 我还看到有人根据协议进行划分：

• 留言/多播协议 gossip/multicast protocols，包括 redis 在内的很多集群都是采用 gossip

• 共识协议 consensus protocols

为了澄清更多的概念，我引用这个分类方式文 ref 中的一段话：

The former includes things like epidemic broadcast trees, bimodal multicast, SWIM, HyParView, and NeEM. These tend to be eventually consistent and/or stochastic. The latter, which I’ve described in more detail here, includes 2PC/3PC, Paxos, Raft, Zab, and chain replication. These tend to favor strong consistency over availability.

作者也很谨慎的用了 tend to，需要说明的是，前者基本上是最终一致没有什么问题， 而后者就要分清上下文了，在传统的分布式系统上这个说法问题不大，因为传统的分布式共识算法是基于故障容错 crash fault tolerance，前提是假设系统中只会存在故障节点（消息会丢失，重复）， 而在区块链的世界中，共识算法是基于拜占庭容错 Byzantine fault tolerance，前提是假设系统中存在恶意节点（会发送假消息），基本都是最终一致，而不是强一致；

通过前面关系型数据库的例子可以看到一个系统的一致性不是固定死的，很多情况下一致性会根据系统的设置或系统的架构不同发生变化，在同一个系统中不同类型的数据也可能有着不同的表现； 单机系统都如此，分布式系统更是复杂，而对于区块链来说，一致性更加有着丰富的表现，比如比特币的 6 个确认，是中本聪基于泊松分布做的一种类似联合泊松分布的概率计算， 以全网千分之一的算力来做恶意节点得出 6 个确认之后可以忽略不计，当然随着单节点算力越高，需要的确认也随之增长。

2.基于故障容错 CFT(Crash fault tolerance 或非拜占庭容错)的分布式系统

中心化系统有单点故障的风险，所以引入多个节点， 故障容错的假设是多节点中可能会存在故障节点，消息会丢失或重复，但是不会有发送假消息的恶意节点，因为都是部署在内网的可控节点。

在这种假设前提下，多个节点协同工作方式有两种思路。

2.1 主备方案和一致性状态机

2.1.1 主备方案

最直接的想法是指定一个 leader，只由 leader 单节点负责管理竞争资源，然后其他节点作为 follower 保存副本：

• 一致性，客户端写入数据请求都是交由或转发给 leader 处理，所以单节点维护保持了数据写的一致，所有节点都会接受客户端的读请求；

• 排除单点故障，当某个 follower 发生故障，leader 就将 follower 从自己的通讯录中剔除或拉黑，如果该 follower 再次重新恢复上线，leader 会将其再加回通讯录。

现在出现两个问题：

1） follower 转发写数据请求给 leader，如果他们转发的请求互相有冲突呢，比如对同一个数据同时修改；

2） 如何动态选出的 leader 并且当 leader 节点发送故障如何从 follower 中选出 leader 呢。

这两个问题都要依赖共识算法解决，比如 zookeeper 的 ZAP 协议就是解决这个问题的。

第一个问题解决方法是 2PC 即两阶段提交协议:

leader 直接或间接通过 follower 收到转发的写操作请求，都会按照 FIFO 顺序发送 proposal 给所有 follower，如果收到半数以上的 follower 的 ack 响应，leader 就会发送 commit 指令给所有 follower（注意 leader 也是自己的 follower）。

第二个问题解决方法是：

每个节点启动后默认都是 looking 模式，当 leader 选出后，其他节点就立即变成 follower 模式，如果 leader 崩溃了，则跟 followers 的心跳连接失败，follower 又会变回 looking 模式，然后 leader 崩溃后选举新 leader 原则是采用 “Use a best-effort leader election algorithm that will elect a leader with the latest history from a quorum of servers.”，具体后面算法讲解的 leader 恢复机制； 每次选举出新的 leader 都会有自己的标志，有的叫 term 有的叫 epoch，主要是为了防止脑裂，比如挂掉的 leader 或者分区后的 leader 突然恢复连接，通过这个标志老 leader 可以知道自己已经过时了，然后转换成 follower 听从新的 leader。

2.1.2 一致性状态机

一致性状态机也是基于共识算法的，不过原则上不需要选举 leader 节点，实际的算法实现很多还是引入了 leader 来降低一些问题的实现难度， 总的来说跟主备的侧重不同：一个是构建高可用的分布式主备系统，一个是为了构建分布式一致性状态机。

我们首先要从经典的“paxos 岛兼职议会问题”说起。

希腊岛屿 Paxos 上通过议会的方式来表决通过法律，议员们通过服务员传递纸条的方式交流信息，每个议员都将通过的法律记录在自己的本子上，需要保证大家记下的法律条款都一致； 问题在于议员和服务员都是兼职的，他们随时会因为各种事情离开议会大厅，传递的消息也可能会重复或丢失，并随时可能有新的议员进入议会大厅进行法律表决，使用何种方式能够使得这个表决过程正常进行，且通过的法律不发生矛盾。 注意我们假设议员和服务员都是道德高尚的人，不会恶意发送假消息。

解决这个问题的经典故障容错算法就简称 paxos，很多其他的基于故障容错的共识算法都是基于 paxos 改进演变的，paxos 本身也有很多变种， 甚至有这种说法：“there is only one consensus protocol, and that’s Paxos — all other approaches are just broken versions of Paxos” . 所以我们只需要理解一下最基础的 Basic Paxos 这个算法的基本原理。

引用斯坦福的教学内容 Basic Paxos 的基本流程图。

basic paxos 是基于 2PC 两阶段提交协议的，这里首先引入提议者 proposer 和接受者 acceptor 作为两阶段的具体实施者，我们用一个机票预订的例子来讲解：

为了简化描述，假设我们只有 5 个节点 Node1|Node2|Node3|Node4|Node5 ，其中 Node1 和 Node2 是 proposer 角色，然后 Node3|Node4|Node5 都是 acceptor 角色， 实际上一个节点可以是多种角色，上面引用的图中是说 broadcast to all servers，实际上对于一个 2F+1 的节点配置来说，只需要得到 F+1 个节点响应即可，我们例子中忽略这些细节，集中分析主要的逻辑， 然后算法主要分两步或两阶段，提议 propose 和决议 commit，第一阶段主要是为了将已经落实的最新决议状态（数据）同步给其他节点（所有 proposer），第二阶段主要是挡住旧的决议（并落实新决议）

Node1 收到客户端请求 Alice 要预订广州到新加坡的 scoot100，座位号选择 A1,

Node1 提议者 proposer 发起一个写数据的提议 proposal:Prepare(【Node1-P-1】)，其中 P 是 Proposal，1 是编号

（加上标志 Node1 是因为每个节点都维护自己的编号，如果 Node1 同步到其他节点 Node2 的最新编号是 100 的话，就会重置自己维护的编码并加 1 变成 101）

现在 Node3|Node4|Node5 这三个 acceptor 都收到了提议 proposal，假设当前三个 acceptor 上面的 minProposal=0，acceptedProposal=null，acceptedValue=null，因为 minProposal<1 此时三个节点都会更新为

minProposal=1，acceptedProposal=null，acceptedValue=null，并返回【P-OK,acceptedProposal=null，acceptedValue=null】,P-OK 代表同意这个 Proposal

Node1 收到了全部是 P-OK，而且收到的 acceptedProposal=null，acceptedValue=null 跟自己的数据没有冲突，所以开始提出决议 commit:Accept(【Node1-C-1，“Alice 航班 scoot100，座位号 A1”】)

现在 Node3|Node4|Node5 这三个 acceptor 都收到了决议 commit，而且 1>=minProposal=1，所以三个节点都会更新 acceptedProposal=minProposal=1，acceptedValue=“Alice 航班 scoot100，座位号 A1”，并且都返回【C-OK,minProposal=1】;

Node1 收到了 result=1 判断 result>n 1>1 是 false，所以没有问题（注意假设任何一个 Acceptor 返回的是 result>1 就证明该 Acceptor 已经接受了另外一个 proposer 的更新的一个决议，那么 Node1 要立即放弃决议，重新回到第一步）

假设接着 Node2 收到客户端请求 Bob 要预订同一班次广州到新加坡的 scoot100，座位号也是选择 A1,

假设 Node2 上面的计数器没有同步最新的，所以发起一个写数据的提议 proposal:Prepare(【Node2-P-1】)

Node3|Node4|Node5 这三个 acceptor 都收到了提议 proposal，因为需要 n>minProposal=1 但是 1>1 是 false，所以会返回【P-FAIL,acceptedProposal=1，acceptedValue=“Alice 航班 scoot100，座位号 A1”】

Node2 收到任何一个 P-FAIL 后都会同步最新决议，而且 acceptedProposal=1，acceptedValue=“Alice 航班 scoot100，座位号 A1”，所以跟自己的数据"Bob 航班 scoot100，座位号 A1"有冲突，所以也是要同步最新决议，

注意，在 simple paxos 算法中，不管 P-FAIL 还算 P-OK，只要任何一个返回中的 acceptedValue 有值都要立即同步，因为是代表通过的最新的决议，

所以 Node2 会同步更新本地的 value=“Alice 航班 scoot100，座位号 A1”，并且继续广播决议 commit：Accept【Node2-C-1,“Alice 航班 scoot100，座位号 A1”】看到这里可以感觉是无用功，实际上 PAXOS 算法却是复杂，而且有很多变种，我们只是讲解基本的逻辑，

实际中可以做各种优化，不过这一步可能还真有用，比如可以同步之前掉线的 Acceptor 节点，要看具体实现中的考虑；

Node3|Node4|Node5 这三个 acceptor 都收到了决议，更新并返回【C-OK,minProposal=1】;

Node2 收到了 result=1 判断 result>n 1>1 是 false，所以没有问题。

目前都是假设节点正常运作，paxos 算法的意义就是可以在某些节点崩溃及通信延迟的情况下仍然可以达到最终一致的效果，所以你可以自行想一下如果 proposer 节点或者 acceptor 节点掉线会不会影响系统稳定，比较显然不再赘述， 这里需要多提一个概念叫做活锁 livelock。

Node1 发起一个写数据的提议 proposal:Prepare(【Node1-P-1】),假设 Node1 已经完成了 Prepre，意思是 Node3|4|5 都返回了，现在开始提交决议【Node1-C-1,Value】

此时 Node2 发起一个写数据的提议 proposal:Prepare(【Node2-P-2】)，根据前面的分析，Node3|4|5 收到后会更新 minimalProposal=2,从而会拒绝 Node1 的决议【Node1-C-1,Value】，

再根据前面的分析，Node1 会从头开始重新提议【Node1-P-3】，

然后刚刚 Node2 完成了提议，开始提交决议【Node2-C-2,Value】，但是 Node3|4|5 已经收到了 Node1 的新提议【Node1-P-3】，所以 minimalProposal=3，所以会拒绝 Node2 的决议【Node2-C-2,Value】，

所以 Node2 也只好放弃重头开始重新提议【Node2-P-4】…如此循环，谁也无法成功实现决议。

解决上面的活锁问题有两种方法，一个是在每次重头开始提新提议的时候加一个随机的 delay 延迟，这样会可以给机会让其中一个 proposer 成功完成提议和决议； 另一种比较更多采用的做法就是从 proposer 中选一个 leader 出来，由 leader 统一提议决议，避免冲突。

说到这里，还有一个问题，上面说了对于 2F+1 个节点，只需要 F+1 个节点达成一致就可以 move forward，即对外部提供服务了，所以 paxos 为了满足 FLP 理论的 liveness 要求，引入了一个 learner 的概念。

Acceptor 接受决议后会通知给每一个 learner 节点，learner 在判断已经有 F+1 个节点达成共识后就可以返回给客户端以及同步给其他 Acceptor 节点， 当然 paxos 算法本身并不保证 liveness，只是引入 learner 可以改善 liveness。

PAXOS 很经典但是也是比较臭名昭著的复杂，RAFT 是其实现的简化版本，RAFT 主要包含选举 leader election 和日志拷贝 log replication。

其 leader election 也是利用心跳和过半数选举的机制，并且 leader 也是有第几代 leader 的 term 标志，ZAP 用的是 epoch，simple paxos 没有 leader 概念； 然后 log replication 跟 simple paxos 的 2PC 些许类似，首先所有客户端的写请求都会转发给 leader 来处理，然后 leader 写入日志，状态是 uncommitted，通过心跳发给所有 followers， follower 收到后也写入自己的日志，状态是 uncommitted，leader 等得到过半数的 followers 的 ack 响应后将状态改为 committed，然后再通知所有 follower，follower 收到后也更新数据更改状态为 committed， 注意写日志的时候，leader 是将请求变成 entry，然后每个 entry 都有一个 index 值用来保持操作的有序性，类似于 ZAP 协议中的 leader 广播 message 赋值的单调递增 monotonically increasing unique id 的 zxid，paxos 中则类似每个 proposer 使用的 Ballot Number； 除了系统上线第一次 leader election，后续各种原因触发的重新选举都需要一个 recovery protocol，term+index，epoch+zxid 是为了在 leader 选举的时候选择有着最完美日志的节点作为 leader 进行恢复。

下面拿 RAFT 协议来举例完善一下前面没详细说的分区容错 partition tolerance：

可以看到网络分为两个分区，两个 leader，他们的时代是不同的一个是 term=1 一个是 term=2，互相不知道彼此，但是由于 term=1 在更改数据的时候无法得到超过半数的响应， 所以所有数据更改都会处于 uncommit 未提交状态；而反之在另一边 term=2 这里，是可以达成共识的； 最后一旦网络恢复正常，term=1 的分区就会发现自己全部过时了，就会放弃自己的 uncommit 日志，同步 term=2 的提交日志； 由此可见在网络分区的情况下分布式状态机一样可以实现一致性。

实际上前面“主备方案”中提到的 zookeeper 本质也是一个状态机模型，只不过是利用状态机的状态实现了主备方案， 从大的角度讲 zookeeper 的 ZAP 协议分为 3 个阶段，Discovery，Sync，Boradcast，跟前面这些协议都是大同小异，只需要说下不同点。

和 raft 的有序性不同，ZAP 协议有序性（znode 节点操作）不仅体现在采用的 FIFO 先进先出队列，还有重新选举恢复的时候需要 Sync。

比如 leader 在崩溃之前广播出去的数据（proposal 和 commit）不会丢失，由 leader 产生但没有广播出去的 proposal 和 commit 则跳过，但是如果该 leader 之后重新被再次选举为新 leader，其上没有提交的事务需要根据判断其 epoch 是否小于当前的 epoch，是则丢弃，如果相同则还会被提交。

这也是 zookeeper 可以作为分布式框架保证 primary order 基本顺序的信心保证。

RAFT 没有 ZAP 的 sync 这个阶段，而是靠 AppendEntries RPC 同步纠正，而 paxos 算法本身没有保证有序性 paxos run。

2.2 分布式产品和 zookeeper

前面讲了很多理论，现在我们落实到市面上的各种分布式产品，看看具体大家都是如何实现的：

• 分布式服务框架 zookeeper 的 ZAP 协议；

• 分布式消息队列集群 Kafka；

• 分布式计算 spark, storm 以及 Hadoop mapreduce2.0；

• 分布式存储系统：hbase 基于 zookeeper, 而 ETCD 采用 RAFT 协议；

• 分布式任务调度：Elastic-Job 等。

挑几个产品看看它们的架构图就会发现一种现象，很多产品都是依赖 zookeeper，为什么呢？

简单回答，不要重复造轮子！

Zookeeper 适用的场景：ref

• 统一命名服务（Name Service）

• 配置管理（Configuration Management）

• 集群管理（Group Membership）

• 共享锁（Locks）：共享锁在同一个进程中很容易实现，但是在跨进程或者在不同 Server 之间就不好实现了,依赖 zookeeper 这样的分布式框架实现大大降低难度。

3.基于拜占庭容错 BFT(Byzantine fault tolerance)的分布式账本技术

我们前面的分布式产品都是部署在内网中，不管是私有云公有云还是自己的机房，都不会给外界暴露端口，一般更不会允许外面的节点随便连进来，属于关在笼子里面的内部系统， 一切的根源都在于以上前提假设都是基于故障容错的，都是假设不会有恶意节点，因为都是公司内网可控的内部节点。

而区块链技术，又被称作分布式账本技术 Distributed Ledger Technology，简称 DLT，尤其是比特币作为区块链的第一应用，才算是真正意义上的去中心化分布式技术，不管是手机，普通电脑，还是矿机，都可以运行一个比特币节点，随时加入退出， 甚至你可以恶意篡改比特币源码的节点都没关系，只要算力不超过 51%，都不会影响比特币的正常运行，那么他的共识算法跟以上的共识算法有什么区别呢？ 下面我开始给大家介绍下区块链技术的入门知识。

3.1 区块链分类简介

单纯从技术上来说区块链分为 permissioned 和 permissionless blockchain，前者是私有链和联盟链，后者是公链； 如果从去中心化角度来说只有公链技术才算区块链，当然这个涉及到关于中心化的辩论，属于哲学问题，不予讨论。

私有链基本上没有任何意义，唯一用武之处就是用来教学演示，对于正常的普通企业用传统的办法更高效，如果真的要搞行业级别的集成自然是选择联盟链， 我就以 IBM 的 hyperledger fabric 为代表来讲解下联盟链。

直接看核心流程图，我只是简略说主要内容，不会讲解他的会员系统（节点的加入都是要经过审核后配置到系统中），也不会细分 peer 节点的类型。

客户端发一个 transaction 请求，实现了 hyperledger sdk 的客户端程序接收请求，验证后发给 peers 节点，peers 节点验证并进行 endorse 签名然后返回结果给客户端， 客户端收到一定数量（一定数量决定于事前设定的 policy，比如半数以上）的 endorse 之后就发起提交请求，将 transaction 及 endorsement 一起发给 ordering service，又是一种 2PC 两阶段提交， ordering service 排序打包交易到一个区块再发给 peers，peers 会验证区块中的每个交易，然后更新账本。

不过等等，这里的 ordering service 听起来像是一个单节点，不像 peers 那样有多个节点，难道是个中心化的排序服务吗？然后我们看 IBM 文档的说法如下：

看到没，关键的 ordering service 可以是一个单节点或者 kafka 集群，单节点不用说了，kafka 集群仍然是基于故障容错的分布式产品； 不过共识这块 hyperledger 是可以插拔自定义的，实际上 V1.4 版本引入了 RAFT 算法，当然也是基于故障容错的。

近期 hyperledger 的另外一个产品 Sawtooth 开始推出 PBFT,据说跟 fabric 不同，Sawtooth 可以支持 permissionless 网络，有兴趣的读者可以自行研究。

公链有两大代表：区块链第一应用比特币及支持智能合约的超级计算机以太坊，当然还有 EOS，BTS 等等其他公链，他们的共识算法都是基于解决拜占庭将军问题的算法， 注意这里并非特指拜占庭容错算法 BFT 或 PBFT，而是泛指，区块链的共识算法也经常被称作 trustless consensus，意思是无信任共识，换句话说跟前面那些故障容错算法的假设不同，对于无信任共识来说节点之间是不可以相互信任的， 会有好节点和发送假消息的坏节点。

3.2 拜占庭将军问题和实用拜占庭容错算法 PBFT

拜占庭将军问题

东罗马帝国也就是拜占庭帝国国王准备攻打一座城堡， 拜占庭军队的多个军区驻扎在城外，每个军区都有一个将军 Generals， 由于这些将军相距很远只能通过信使 messengers 传递消息， 现在军队必须在撤退和进攻两个命令中达成一致并且同时行动，否则就会被击败。

归纳为规则 A 和 B:

A. All loyal generals decide upon the same plan of action. 叛徒可以任意而为，但是忠诚的将军必须达成一致的计划 agreement（进攻或撤退），所有节点不仅要达成共识而且是要合理的共识 agreement；

B. A small number of traitors cannot cause the loyal generals to adopt a bad plan. 我们无须考虑什么是 bad plan，只需要确认忠诚的将军节点如何做出决定 decision。

假设 v(i)代表第 i 个将军发送的信息，那么 n 个将军的信息就是 v(1),…v(n) 所以满足 A 很简单，只需要所有节点按照同一个方法将收到的 v(1),…v(n)转成行动，输入一样则输出一样。

而对于 B,假设最终的决定只有进攻和撤退两种，那么第 i 个将军的决定可以基于最多的投票， 如果叛徒节点多到刚好让诚实的节点平均分成攻击和撤退两个阵营则第 i 个将军无法做出决定。

A 的前提可以归纳为条件 1：

condition1：每个节点都收到同样的 v(1),…v(n)， 但是有可能所有的诚实节点都是发送进攻的消息，但是一部分叛徒会导致诚实节点发送 retreat。

为了满足 B 归纳出条件 2：

condition2：如果第 i 个节点是忠诚的，那么发送的 v(i)必须被每个忠诚的节点使用。

结合 condition2，我们可以重写 condition1 变成 condition1’:任意两个忠诚的节点都使用相同的 v(i)。

至此，condition1’和 condition2 都是基于第 i 个将军发送的信息 v(i)，所以到这里我们可以把问题转化成：一个将军节点如何发送信息给其他节点；我们重新组织语言，将问题转化归纳为：

将军节点如何发送命令给他的 lieutenants 副官们，具体来说是一个将军节点如何发送命令给他的 n-1 个副官节点，并且满足以下两个条件。

IC1. 所有的忠诚副官节点都遵守同一个命令。

IC2. 如果将军是诚实的，每一个诚实副官都应该遵守将军发送的命令。

IC1 和 IC2 统称为 interactive consistency conditions 交互型一致条件。

fig2 违背了 IC1，所以 3 个节点中有一个叛徒是无解的，我们由此就证明了对付 m 个叛徒至少要 3m+1 个节点，黑人问号，什么时候证明的？

The proof is by contradiction，很简单，上面 3 个节点 1 个叛徒无解，设 m=1，3m=3 个节点无解，所以反正法结束！

定义口头信息算法 Oral Message algorithms OM(m), ∀m∈N, m>0，将军向 n-1 个副官发送命令，定义函数 majority（v1 ,…,vn-1）的值两种取法：

假设数值是二元的则取少数服从多数，比如多数是进攻则进攻,否则默认值为撤退；

假设数值是一个可排序序列则选择中位数；

执行方法是：OM(m)调用 n-1 次 OM(m-1)算法，每一个算法 OM(m-1)再分别调用 n-2 次的 OM(m-2)，如此直至 m=0。

下面假设 m=1，3m+1=4：

fig3，OM(m=1）将军首先发送 v 给所有节点，然后 OM(m=0)副官 1 发送 v 给副官 2，副官 3 发送 x 给副官 2，副官 2 有 v1=v2=v，v3=x，v=majority（v,v,x），其他副官同理； 同时还可以判断出副官 3 是叛徒。

fig4，OM(m=1)将军首先分别发送 x，y，z 给副官 1，2，3，OM(m=0)，副官 1 发送 x 给副官 2，副官 3 发送 z 给副官 2，副官 2 收到（x,y,z），同理所以每个副官都收到(x,y,z)， 可以判断将军是叛徒。

实用拜占庭容错算法 PBFT

主节点 p = v mod |R|。v：视图编号（类似前面提到的 term），|R|节点个数，p：主节点编号 现在 R=4,v=0,p=0。

1.client c 客户端发送请求<REQUEST, o, t, c>给主节点 0:

REQUEST 包含消息内容 m，以及消息摘要 d(m),客户端对请求进行签名; o: 请求的具体操作，t: 请求时客户端追加的时间戳，c：客户端标识。

2.主节点 0 预准备 pre-prepare：

主节点校验消息签名并拒绝非法请求； 校验通过则分配编号 n，用于对客户端请求的排序； 然后多播消息<<PRE-PREPARE, v=0, n, d>, m>给其他副本节点： d 为客户端消息摘要，m 为消息内容，n 是要在范围区间内的[h, H]，用于垃圾回收； 对<PRE-PREPARE, v, n, d>签名。

3.副本节点发送 PREPARE：

副本节点 1、2、3 收到主节点 0 的 PRE-PREPARE 消息，校验并拒绝非法请求： 主节点 PRE-PREPARE 消息签名； 当前副本节点是否已经收到了一条在同一 v=0 下并且编号也是 n，但是签名不同的 PRE-PREPARE 信息； d 与 m 的摘要是否一致； n 是否在区间[h, H]内。

然后副本节点都向其他节点发送 prepare 消息<PREPARE, v=0, n, d, i>,i 是当前副本节点编号; 节点 i 对<PREPARE, v, n, d, i>进行签名; PRE-PREPARE 和 PREPARE 消息写入 log，用于 View Change 时恢复未完成的操作。

4.全部节点 COMMIT：

所有节点收到 PREPARE 消息，校验并拒绝非法请求： 节点 PREPARE 消息签名是否正确； 当前节点是否已经收到了同一视图 v 下的 n； n 是否在区间[h, H]内； d 是否和当前已收到 PRE-PPREPARE 中的 d 相同。

节点 i 等待 2f+1 个验证通过的 PREPARE 消息（对于副本节点来说包括自己）则进入 prepared 状态并向其他节点发送 commit 消息<COMMIT, v=0, n, D(m), i>， 节点 i 对<COMMIT, v, n, d, i>签名； COMMIT 消息写入日志，用于 View Change 时恢复未完成的操作。

5.全部节点 REPLY：

所有节点收到 COMMIT 消息，校验并拒绝非法请求： 节点 COMMIT 消息签名是否正确； 当前节点是否已经收到了同一视图 v 下的 n； d 与 m 的摘要是否一致； n 是否在区间[h, H]内。

节点 i 等待 2f+1 个验证通过的 COMMIT 消息（包括自己），进入 commit 状态，说明当前网络中的大部分节点已经达成共识，运行客户端的请求操作 o，并返回<REPLY, v, t, c, i, r>给客户端， r 是请求操作结果。

6.客户端 client c 等待 f+1 个 reply 如果收到 f+1 个相同的 REPLY 消息，说明请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点； 记录节点发送的 COMMIT 消息到 log 中。

算法其他细节：垃圾回收，视图更改请自行查阅，不是讨论重点。

几个问题：

• i.为什么需要一个 primary 节点 ？

• PBFT 的理论之一 primary-backup [Alsberg and Day 1976] 跟 paxos 和 raft 类似的思想，用 leader 节点可以避免多个 proposer 的冲突，以及排序 client 端的请求，降低算法实现难度，比如恢复，在 PBFT 的概念里 epoch 或 term 变成了 view，然后 leader 叫做 primary，其他的 follower 叫做 backups， 主节点负责将来自 Client 的请求给排好序，然后按序发送给备份节点； 如果主节点可能会是恶意节点，比如给不同的请求编上相同的编号或者不分配编号或者编号跳跃不连续，备份节点会动检查这些序号的合法性，如果有发现问题，备份节点就会触发 view change 协议来选举出新的主节点，当然备份节点也会通过 timeout 心跳检查主节点是不是挂掉。

• ii.主节点如果是恶意节点，是否可以通过篡改消息来作恶呢，如果是的话又会怎样 ？

• 首先，肯定是可以的，但是要分两方面来说，如果是篡改客户端发来的消息，这个是行不通的，会被备份节点通过检查签名发现问题，注意一般单纯用 pbft 的都是封闭系统，客户端也是要经过注册的， 当然主节点可以完全用自己的私钥来签名发起一个恶意的消息，客户端通过公钥验证是肯定通过的，这种情况从算法角度看是无法解决的。

• iii.为什么 prepare 和 commit 是等待 2f+1 不是 f+1 个消息， 对于 paxo 或 raft 等基于 CFT 算法 f+1 个消息就能少数服从多数过半数确定下一步，但是为什么 PBFT 需要 2f+1 才能确定下一步呢？

• PBFT 的理论之一 quorum replication [Gifford 1979] 假设节点总数为|R|的共识系统中选择|Q|个节点作为一个仲裁机制，需要保证这任意两个 Q 必须至少得有一个节点交集，不然可能会导致不一样的共识结果，根据韦恩图的计算法则： 2|Q| - |R| >= 1 => |Q| >= (|R| + 1) / 2, 对于 CFT,|R| = 2 f + 1 => |Q| >= f + 1 这是针对 CFT 的情况，对于 BFT 交集还得容纳 f 个恶意节点 2|Q| - |R| >= 1 + f => |Q| >= (|R| + f + 1) / 2, |R| = 3 f + 1 => |Q| >= 2f + 1 举个例子，假设 f=2，3*2+1=7 个节点的情况下，i=0,1,2,3,4,5,6 其中 5，6 是坏节点，假设 prepare 阶段，极端情况每个节点 0 1 2 3 4 都先收到了 5 和 6 的假消息及 f 个假消息，加上各自节点自己的 1 个消息， 是 f+1 个，可见，这种情况下就达成共识就是错误的结果或者达不成共识，取决于具体实现，比如至少不应该进入下一步； 对于 CTF 的 f+1，是因为挂掉的节点无法发消息，所以 f+1 是为了假设半数发的是旧消息 proposer，所以用过半来做判断确认半数认为这个消息是可以共识的。

• iv.为什么 client 是等待 f+1 个 reply？

• 前面说了根据 qurom 理论，任意两个 Q 至少一个交集，并且允许容纳 f 个恶意节点，所以 f+1 隐含的意思是即使有 f 个都是恶意节点，至少一个节点的 reply 是诚实的，有一个诚实节点隐含着客户端的操作已经达成共识操作完成。

拜占庭容错算法有着很多限制：

• A.需要保证网络上不超过 1/3 的节点作恶，1/3 的来源是前面拜占庭将军问题的反证法，另外根据前面的 quorum 理论也能证明, 对于一个 permissioned network 比如公司内网或者类似类似 hyperledger 这有的联盟链来说比较容易监控， 但是对于一个开放式的网络，每分钟都可能有节点加入退出，根本无从监控和得知某个时间范围内到底有多少恶意节点，简单的数学模型是无法解决这个问题的。

• B.节点数过多会影响 PBFT 节点达成共识的速度，我们简单计算下互相发送的信息数量就大概知道随着节点增多这种共识方式是不实际的。

• pre-prepare 的消息数是接收者排除主节点自己 1*（3f+1-1）=3f。

• prepare 是【2f3f，3f3f】： 最少：发送者排除主节点和坏节点：3f+1-1-f=2f，接收者排除自己 3f+1-1=3f 最多:发送者排除主节点:3f+1-1=3f,接收者排除自己 3f+1-1=3f。

• commit 是【(3f+1-f)(3f+1),(3f+1)3f】； 最少：发送者排除坏节点:3f+1-f=2f+1,接收者排除自己:3f+1-1=3f 最多:发送者:3f+1,接收者排除自己 3f+1-1=3f。

• repy 是【2f+1,3f+1】。

• C.拜占庭容错算法本身是易于被 Sybil attack， 因为默认情况下一个节点不需要花费任何代价就很容易伪造多个身份，由上面我们可以看到节点的区分只是序号 i,，当然我们看到除了 i 之外还有签名，签名就涉及用公钥验证，如果我们可以保证这些节点是可以“中心化”去管理公私钥配置的就可以防止 sybil attack，不过代价是又变回了封闭式的系统，hyerledger， 对于一个 closed system 只要加上类似的身份控制就可以避免 sybil attack，sybil attack 只针对"decentralized and permissionless peer to peer network"。

在实际项目中 pbft 经常是跟其他算法一起使用，比如 Zilliqa 就是结合 pbft 和 POW，另外 PBFT 看起来感觉跟 paxos 有几分相似，确实，实际上 paxos 可以升级成 BFT paxos，也有 raft 版本的 BFT raft。

从故障容错到拜占庭容错，我们算是跳跃了一步，允许有恶意节点，但是限制为不超过全网 1/3 的恶意节点， 我们接下来还要再跳跃更大的一步，因为我们要面向全网，不做任何限制：不限制节点数，无法得知恶意节点数，节点可以任意时刻加入退出，同时我们还要保证节点达成正确的共识结果, 下面我们看下比特币是如何做到的。

3.3 比特币共识算法

1.第一步 共识的门票：创造随机事件

首先，比特币的业务比较简单（其实可以通过 bitcoin script 制造很多复杂的场景，具体可以学习Mastering Bitcoin）, 基本场景就是 Alice 给 bob 转一定数目的 bitcoin。

现在问题是，这么简单的一项业务功能，Alice 转给 bob 0.1 个 btc，验证，打包，落库（发布到链上，即大部分节点同意把新区块放到各自的本地最长的区块链头上），整过过程是谁发起的呢？

开始，Alice 通过自己喜欢的比特币钱包或者命令行（或者自己编写的比特币钱包）生成交易，钱包通过 P2P 协议把签名好的交易广播出去，接下来的问题是谁来验证打包？

我们前面谈了那么多复杂的算法，基本都是要选一个 leader 出来做事情，而比特币的目的是节点之间大家都是平等的，没有 leader worker 之分，参与节点都有打包的权利， 首先为什么有人想要打包，这是因为有 incentive 激励机制，打包成功可以获取若干比特币作为奖励，还可以获取区块中每笔交易的费用，继续打包权利游戏， 比特币为此创造了一个猜谜游戏，我们称作工作量证明 POW,简单来说，这个游戏就是定一个目标：打包好的区块的区块头取 SHA256 哈希值需要小于二进制 01000000 即 64 的数值即 0 到 63 之间的任何值， 而且找到后要立即全网广播。

区块头包含版本号，上一个区块的哈希值，默克尔树根哈希，时间戳，难度目标，随机值 nonce，其中默克尔树根的哈希简单来说就是以交易作为叶子节点的哈希树的树根，哈希的哈希， 可见这里面很多变量，所以最终获取一个小于目标 01000000 的哈希值是很不容易的事情，找不到就需要调整 Nonce 值，再不行就需要调整区块中的交易，总之是一个很激烈的随机数寻找游戏， 至于难度值，简单理解，如果调高，比如目标变成 00100000，前面 0 多了一个，可选的就剩下 0 到 31，缩了一半，靶子越小越难打，如果全网算力提高，比特币会动态调整难度，保持平均每 10 分钟出一个区块的速度。

一轮游戏就是代表一个区块的产生，游戏又称挖矿，参与竞争的节点也叫矿工节点。

比特币创造的这个随机游戏，为后面泊松分布的证明写下了伏笔。

另外由于比特币创造性的使用了脚本技术也保证了交易本身无法被篡改，比如最基础的 P2PKH (pay to public key hash)：

保险箱 scriptPubKey： OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG

解锁 scriptSig：<Sig><PubKey>

虎符拼起来：<Sig><PubKey> OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG ，执行顺序：

OP_DUP(PubKey)=PubKeyOP_HASH160(PubKey) = PubKeyHashOP_EQUALVERIFY(PubKeyHash,PubKeyHash)==TRUEOP_CHECKSIG(Sig)==TRUE

就是这么简洁优美！

当然还有其他的比如 P2SH(pay to script hash)，在以后区块链的文章里会再解析，这里不赘述。

还有一个概念是 utxo 即未花费输出 unspent transaction output，在比特币的世界中，比特币是以 utxo 的形式存在的，每个比特币，准确说是每个 fraction of bitcoin， 或者每个 satoshi（比特币最小单位）都是以 utxo 的形式存在脚本保险箱中，只有私钥的持有者才可以打开保险箱取出 utxo 使用； 因此解决了拜占庭将军传递假消息的问题，除了私钥拥有者，没有人能够伪造或者篡改交易，从而可以让交易通过不安全的网络传输，不管是公网还是蓝牙设置卫星通信都可以。

好像讲到这里漏了点什么，对的，我前面说了 POW 工作量证明的原理以及这个游戏规则，那么可能会有很多节点几乎同时或者先后找到小于目标值的谜底并广播出去， 那么这一轮到底谁算获胜者呢，第一个找到谜底的人？第一个找到并广播出去的人？

这里不得不说很多人将 POW 和 POS 误解为共识算法，我在另外一篇文章是专门讲了这个问题解密挖矿与共识的误解。

至于谁是某一轮游戏的获胜者，还要各位往下接着看。

2.第二步 长链胜出：泊松分布的胜利

揭晓谜底，我们假设当前区块高度是 666666，区块高度就是目前链上的区块数，假设我们就一条干干净净的链，从第一块算起，现在是第 666666 个区块， 先假设一个极端情况只有 M1 M2 M3 这 3 个节点参与挖矿，M1 率先打包了一个新的区块并满足条件，然后迅速广播出去， 其他节点收到消息之后 full validate block and activate best chain，即验证区块中每笔交易的合法性，如果有不合法的则区块失效， 所以所有节点最开始在接收到交易的时候就应该做验证，否则后面打包无效交易也是浪费自己的算力， 如果区块合法，M2 和 M3 就立即 connect to the tip 并激活 best chain，就是将 M1 打包的区块作为第 666667 个区块加到链的顶端。

那么寻找第 666667 个区块的游戏的胜出者就是 M1 吗，M1 可以立即拿到矿工奖励吗？ 答案是未必，因为现实世界是在 M1 出包的同时，还有可能上千个其他节点也出包了，甚至是别的节点出包落后，但是网络比 M1 的快，更快的覆盖全网最多的节点， 所以实际上在每个出包的时候，全网节点上的区块链一般都是处于分叉状态，有的同步到 M1，有的同步到比如 M100，所以第 666667 个区块现在可能有两个， 那么就要看下一轮第 666668 个区块是谁挖的，假设 666668 这个区块是 M2 挖的，刚好 M2 又是支持 M1 的，即 666668 个区块是基于 M1 挖到的 666667 个区块之上挖的， 我们说 666667 这个区块现在有了 2 个确认，全网其他节点假设他们上面还是停留在 M100 的 666667 个区块高度，那么随着 M2 的 666668 的广播，他们会迅速切换到最长链上， 此刻就是以 M2 为首的 666668 个区块。

退一步说再假设区块 666668 这个高度的时候，刚好 M2 挖到的时候又有 M200 挖到第 666668 个区块并且 M200 是基于 M100 的第 666667 挖的，此刻全网仍然是两条链不分伯仲，随着游戏的继续进行，总会分出胜负， 在实际情况下，一般都是一两个区块的临时分叉，不太会有更多的区块分叉，除非是全球网络刚好因为灾害导致长时间物理隔离成了多个分区，那么各自分区肯定是各自的长链， 随着网络恢复，肯定还会选出一个最长链，一个区块是 10 分钟，而且前面提到的奖励确实是挖到新区块就产生的，但是这个奖励需要 100 个确认才能被使用，意思是 100×10 分钟=16 个多小时， 全球网络断开 16 多个小时除了世界大战我是想不到还有什么会造成这个状况，所以小概率事件可以忽略。

说到这里基本原理都说完了，但是还是缺点东西，因为前面说的都是正常的节点竞争，我们现在谈的是基于拜占庭将军问题的共识，自然少不了恶意节点， 前面又说了因为密码学保证了恶意节点无法篡改现有交易，但是恶意节点还可以干另外一件事情。

通过前面分析，我们大概知道比特币这条链因为竞争挖矿时刻处于一两个区块的分叉之中，不过一般我们说等待 6 个确认就可以认为交易成功了，为什么是 6 个确认？ 我们先说恶意节点可以做的一件坏事就是尝试双花攻击 double spent，恶意节点首先做一笔交易从 evil 比特币账号卖给 Alice 20 个比特币，完全合法的交易，并且 Alice 的比特币钱包确实也收到了， 显示目前是一个确认，然后又等了一会变成 2 个确认，Alice 开心的通知第三方平台把押金释放给 evil 的银行帐号， 其实恶意节点在广播给 Alice20 个比特币之前就悄悄生成了另一笔交易，将那 20 个比特币转给自己的另外一个比特币地址，并且已经悄悄打包好了一个甚至是多个区块，Alice 不是看到了 2 个确认吗， 恶意节点准备了 3 个区块，立马广播出去，变成最长链，Alice 看到的两个确认的区块作废，被全网抛弃，全部切换为更长的链，恶意节点一毛钱没花，还挣了 3 个区块的矿工奖励，额外还有 Alice 的银行资金。

上面这个理论是成立的，概率有多大呢，跟 6 个确认又有啥关系呢？

在《Bitcoin: A Peer-to-Peer Electronic Cash System》里有着清晰的证明，泊松分布提供了理论依据：

泊松分布比较简单就不再介绍，当 n 趋向无穷，及把离散事件变成连续事件，可以推导出泊松分布公式也不难，至于泊松密度，我的数学也是半桶水，所以就给了比较简单的注释：

k>z,每一次随机事件中攻击者都会得逞，所以是这里的泊松密度是 1， 而 k<=z，攻击者需要 z-k 个区块才能追上诚实节点，然后每一个区块成功的可能是 q/p，每次都是独立的，所以是(q/p)^(z-k)；

由图上面的计算可见只要单节点的算力不高，超过 5 个确认之后，恶意节点成功的概率都会很低。

实际上比特币作为一个史无前例的社会实验，是密码学、软件、经济、哲学的混合产物：

“destroying the Bitcoin system will also undermine the effectiveness of his own wealth”

所以对于理性的节点来说，利益驱使下去正常挖矿获得收益也比想办法作弊恶意攻击的收益大的多。

综上所述，这些理论的总和就构成了 nakamoto consensus 中本聪共识算法的基础， 至此我们相对完整的从故障容错讲到拜占庭容错，从传统的分布式系统讲到新兴的区块链技术， 希望对大家有所帮助，话题有点大，难免有所疏漏，欢迎批评指正。

作者介绍：

刘跃，现在就职于 APEX - Asia Pacific Exchange 亚太交易所（新加坡），目前主要关注系统架构、区块链、渗透测试。