分布式数据库的一致性问题与共识算法-工具盒子

个人笔记，不保证正确！

谈到分布式数据库，不论是 Etcd/Zookeeper 这样的中心化数据库，还是 Ethereum 区块链这样的去中心化数据库，都避免不了两个关键词：「一致性 」跟「共识」。

本文是笔者学习「一致性 」和「共识」以及相关的理论知识时记录的笔记，这些知识能帮助我们了解 Etcd/Zookeeper/Consul/MySQL/PostgreSQL/DynamoDB/Cassandra/MongoDB/CockroachDB/TiDB 等一众数据库的区别，理解各数据库的优势与局限性，搞懂数据库隔离级别的含义以及应该如何设置，并使我们能在各种应用场景中选择出适用的数据库。

如果你对区块链感兴趣，那这篇文章也能帮助你了解区块链这样的去中心化数据库，跟业界流行的分布式数据库在技术上有何区别，又有哪些共同点，具体是如何实现。

一、一致性 - Consistency {#一一致性---consistency}

「一致性」本身是一个比较模糊的定义，视使用场景的不同，存在许多不同的含义。由于数据库仍然是一个新兴领域，目前存在许多不同的一致性模型，其中的一些术语描述的一致性之间可能还有重叠关系，这些关系甚至会困扰专业的数据库开发人员。

但是究其根本，实际上在谈论一致性时，我们是在谈论事务一致性 跟数据一致性，下面我们分别介绍下这两个一致性。

1. 事务一致性 - Transactions Consistency {#1-事务一致性---transactions-consistency}

「事务一致性」指的是数据库中事务的一致性，它是 ACID 理论中最不起眼的特性，也并不是本文的重点。但是这里就写这么一句话也说不过去，所以下面就仔细介绍下事务与 ACID 理论。

事务与 ACID 理论 {#事务与-acid-理论}

事务是一种「要么全部完成，要么完全不做（All or Nothing）」的指令运行机制。

ACID 理论定义，拥有如下四个特性的「数据库指令序列」，就被称为事务：

原子性 Atomicity ：事务是一个不可分割的工作单元，事务中的所有操作，要么全部完成，要么全部不完成，不可能停滞在某个中间状态。
- 比如 A 转账 100 元给 B，要么转账失败，要么转账成功，不可能卡在 A 被扣除了 100 元，而 B 还没收到 100 元的中间状态。
- 原子性在单机数据库上已得到妥善解决，但是在分布式数据库上它成为一项新的挑战。要在分布式架构下支持原子性并不容易，所以不少 NoSQL 产品都选择绕过这个问题，聚焦到那些对原子性不敏感的细分场景。
一致性 Consistency ：也叫数据的「正确性 Correctness 」或者完整性，指事务对数据库状态的变更必须满足所有预定义的规则，包括「约束 constraints」、「级联 cascades」、「触发器 triggers」以及这些规则的任何组合。
- 比如如果用户为某个字段设置了约束条件 unique，那么事务对该表的所有修改都必须保证此约束成立，否则它将会失败。
- 是存在感最低的特性
隔离性 Isolation ：并发执行的多个事务之间是完全隔离的 ，它们的执行效果跟按事务的开始顺序串行执行完全一致。
- 事务中最复杂的特性
持久性 Durability：事务执行完毕后，结果就保存不变了。这个最好理解。

ACID 是传统的单机数据库的核心特性，比如 MySQL/PostgreSQL.

ACID 中最复杂的特性 - 隔离性 {#acid-中最复杂的特性---隔离性}

完全地实现 ACID 得到的数据库，性能是非常差的。因此在关系数据库中，设计者通常会选择牺牲相对不重要的「隔离性」来获取更好的性能。

而一旦隔离不够彻底，就可能会遇到一些事务之间互相影响的异常情况，这些异常被分为如下几种：

脏写 Dirty writes ：即事务 T1 跟事务 T2 同时在原数据的基础上更新同一个数据，导致结果不符合预期。
- 案例：两个事务同时尝试从账户中扣款 1000 元，但是它们读到的初始状态都是 5000 元，于是都尝试将账户修改为 4000 元，结果就是少扣了 1000 元。
- 最简单的解决方法：针对 UPDATE table SET field = field - 1000 WHERE id = 1 这类数据增删改的逻辑，需要对被更新的行加一把「行写锁」，使其他需要写此数据的事务等待。
脏读 Dirty reads ：事务 T1 读取了事务 T2 未提交的数据。这个数据不一定准确，被称为脏数据，因为假如事务 T2 回滚了，T1 拿到的就是一个错误的数据
- 案例：假设小明小红在一个银行账户存了 5000 元，小明小红在用这同一个账户消费 1000 元，这中间小明付款的事务读取到账户已经被小红的事务修改为了 4000 元，于是它把余额修改为 3000 元，然后付款成功。但是在小明的付款事务成功后，小红的付款失败回滚了，余额又从 3000 被修改回 5000 元。小明就完成了 0 元购的壮举。
- 最简单的解决方法：事务 T2 写数据时对被修改的行加「行写锁」，T2 结束后再释放锁，这样事务 T1 的读取就会被阻塞，直到锁释放。
不可重复读 Non-repeatable reads ：事务 T1 读取数据后，紧接着事务 T2 就更新了数据并提交，事务 T1 再次读取的时候发现数据不一致了
- 案例：
  - 小明在京东上抢购商品，抢购事务启动时事务读到还剩 36 件商品，于是继续执行抢购逻辑，之后事务因为某种原因需要再读一次商品数量，结果发现商品数量已经变成 0 了，抢购失败。
  - 更麻烦的是，不可重复读导致 SELECT 跟 UPDATE 之间也可能出现数据变更，如果你在事务中先通过 SELECT field INTO myvar FROM mytable WHERE uid = 1 读到余额，再在此基础上通过UPDATE 去更新余额，很可能导致数据变得一团糟！
    - 正确的做法是使用 UPDATE mytable SET field = field - 1000 WHERE id = 1，因为每一条 SQL 命令本身都是原子的，这个 SQL 不会有问题。
- 最简单的解决办法：事务 T1 读数据时，也加一把「行」锁，直到不再需要读该数据了，再释放锁。
幻读 Phantom reads ：事务 T1 在多次批量读数据时，事务 T2 往其中执行了插入/删除操作，导致 T1 读到的是旧数据的一个残影，而非当前真实的数据状态。
- 最简单的解决办法：事务 T1 在批量读数据时，先加一把范围锁，在事务 T1 结束读取之后，再释放这把锁。这能同时解决「幻读」跟「不可重复读」的问题。

根据隔离程度，ANSI SQL-92 标准中将「隔离性」细分为四个等级（避免「脏写」是数据库的必备要求，因此未记录在下面的四个等级中）：

串行化 Serializable：也就是完全的隔离，只要事务之间存在互相影响的可能，就（通过锁机制）强制它们串行执行。
可重复读 Repeatable read：可避免脏读、不可重复读的发生，但是解决不了幻读的问题。
读已提交 Read committed：只能避免脏读
读未提交 Read uncommitted：最低级别，完全放弃隔离性

MySQL 默认的隔离级别为「可重复读 Repeatable Read」，PostgreSQL 和 Oracle 默认隔离级别为「读已提交 Read committed」。

为什么 MySQL/PostgreSQL/Oracle 的默认隔离级别是这样设置的呢？该如何选择正确的隔离级别呢？我们针对普通的高并发业务场景做个简单分析：

首先，「脏读」是必须避免的，它会使事务读到错误的数据！最低的「读未提交」级别直接排除
「串行化」的性能太差，也直接排除
只要 SQL 用得对，「不可重复读」问题对业务逻辑的正确性通常并无影响，所以是可以容忍的。
因此一般「读已提交」是最佳的隔离级别，这也是 PostgreSQL/Oracle 将其设为默认隔离级别的原因。
那么为什么 MySQL 这么特立独行，将默认隔离级别提高到了「可重复读」呢？为啥阿里这种大的互联网公司又会把 MySQL 默认的隔离级别改成「读已提交」？
- 根据网上查到的资料，这是 MySQL 的历史问题导致的。MySQL 5.0 之前只支持 statement 这种 binlog 格式，此格式在「读已提交」的隔离级别下会出现诸多问题，最明显的就是可能会导致主从数据库的数据不一致。
- 除了设置默认的隔离级别外，MySQL 还禁止在使用 statement 格式的 binlog 时，使用 READ COMMITTED 作为事务隔离级别，尝试修改隔离级别会报错Transaction level 'READ-COMMITTED' in InnoDB is not safe for binlog mode 'STATEMENT'
- 而互联网公司将隔离级别改为「读已提交」的原因也很好理解，正如前文所述「读已提交」是最佳的隔离级别，这样修改能够提升数据库的性能。

「隔离性」的本质其实就是事务的并发控制 ，不同的隔离级别代表了对并发事务的隔离程度，主要的实现手段是「多版本并发控制 MVCC」与「锁」。锁机制前面已经简单介绍过了，而 MVCC 其实就是为每个事务创建一个特定隔离级别的快照，这样读写不会互相阻塞，性能就提升了。（MVCC 暂时也是超纲知识，后面再研究吧 emmmm）

ANSI SQL-92 对异常现象的分析仍然太过简单了，1995 年新发布的论文A Critique of ANSI SQL Isolation Levels 丰富和细化了 SQL-92 的内容，定义了六种隔离级别和八种异常现象（有大佬强烈建议通读此论文，重点是文中的快照隔离（Snapshot Isolation, SI）级别）。

2. 数据一致性 Data Consistency {#2-数据一致性-data-consistency}

「数据一致性」是指对数据库的每一次读操作都应该读到最新写入的数据，或者直接报错。

对单机数据库而言「数据一致性」往往不是问题，因为它通常只有一份保存在磁盘或内存中的数据。但是在分布式系统中，为了数据安全性或者为了性能，往往每一份数据都在多个节点上存有其副本，这就引出了数据副本们的一致性问题。因此，我们通常谈论的「数据一致性」就是指分布式系统的「数据一致性」。

CAP 原则 是分布式系统领域一个著名的理论，它告诉我们在分布式系统中如下三种属性不可能全部达成，因此也被称作「CAP 不可能三角」：

数据一致性 Data Consistency ：客户端的每次读操作，不管访问系统的哪个节点，要么读到的都是同一份最新写入的数据，要么读取失败
- 强调数据完全正确
可用性 Availability ：任何来自客户端的请求，不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据
- 强调的是服务可用，但不保证数据正确
分区容错性 Partition Tolerance ：即使节点之间出现了任意数量的消息丢失或者高延迟，系统仍能正常运行
- 就是说网络丢包或延迟会导致系统被分成多个 Partition，系统能够容忍这种情况

为了保证分区容错性 P，考虑当分布式系统因为网络问题被割裂成多个分区时，每个分区只有如下两种选择，A 跟 C 必须牺牲掉其中之一：

取消操作并拒绝提供服务，这降低了可用性，但是能确保数据一致性
继续处理请求，这确保了可用性，但是数据一致性就无法保证了

如果系统的多个分区都在同时提供服务，导致数据不一致并且存在冲突无法合并，这就被称为分布式系统的「脑裂」，显然任何分布式系统都不会希望发生「脑裂」。

因为分布式系统与单机系统不同，它涉及到多节点间的网络通讯和交互，但是只要有网络交互就一定会有延迟和数据丢失，节点间的分区故障是很有可能发生的。因此为了正常运行，P 是分布式系统必须保证的特性，在出现分区故障时，为了 P 只能牺牲掉 A 或者 C。

工程上是要 AP 还是 CP，得视情况而定：

Etcd/Zookeeper/Consul: 它们通常被用于存储系统运行的关键元信息，每次读，都要能读取到最新数据。因此它们实现了 CP，牺牲了 A
DynamoDB/Cassandra/MongoDB：不要求数据一致性，一段时间内用旧的缓存问题也不大，但是要求可用性，因此应该实现 AP，牺牲掉 C

数据一致性模型 {#数据一致性模型}

分布式系统中，多副本数据上的一组读写策略，被称为「（数据）一致性模型 Consistency Model」。一致性模型数量很多，让人难以分辨。为了便于理解，我们先从状态视角出发区分一下强一致与弱一致的概念，在这个的基础上再从操作视角去理解这众多的一致性模型。

1. 状态视角 - 强一致与弱一致 {#1-状态视角---强一致与弱一致}

我们首先把整个分布式系统看作一个白盒，从状态视角看，任何变更操作后，分布式系统的多个数据副本只有如下三种状态：

在某些条件下，各副本状态不一致的现象只是暂时的，后续还会转换到一致的状态，这被称为「弱一致 」；
- 这通常是使用异步复制来同步各副本的状态。
相对的说，如果系统各副本不存在「不一致」这种状态，只要变更操作成功数据就一定完全一致，那它就被称为「强一致 」。
- 这要求所有副本之间的数据更新必须完全同步，就必须使用全同步复制。
永远不会一致：这在分布式系统中就是 bug 了，也被称为「脑裂」。

上面描述的是整个系统的客观、实际状态，但对于绝大部分用户而言分布式系统更多的是一个黑盒，因此更流行的是基于「黑盒」的分类方式，它根据系统的对外状态将系统分成两种类型：

强一致 ：指对系统的任何节点/进程，写操作完成后，任何用户对任何节点的后续访问都能读到新的值。就好像系统只存在一个副本一样。
- 最常用算法是 Raft/Paxos，它们的写操作只要求超过半数节点写入成功，因此写入完成时，内部状态实际是不一致的，但是对它进行读写，效果跟「全同步复制」没有区别。
弱一致 ：指对系统的任何节点/进程，写操作完成后，后续的任何访问可能会拿到的值是不确定的，但经过一段时间后，后续的任何访问都能读到新的值。
- 弱一致是非常模糊的定义。如果我们把最终所有用户都能访问到新的值被称为「系统收敛」，系统收敛的用时可以有明确边界，也可以没有。系统收敛前的访问行为可以有明确规范，也可以不存在规范。一切都看具体系统的实现。
- 如果系统能够在有限时间内收敛，那它就是「最终一致 」，否则可以认为它是「不一致」。

为了实际需要，数据库专家对系统收敛之前的读写效果进行各种限制，对系统的收敛时间进行各种限制，得到了许多一致性模型。

2. 操作视角 - 多种一致性模型 {#2-操作视角---多种一致性模型}

从每个客户端的操作角度看，有四种一致性模型：

写后读一致性 Read after Write Consistency ：也被称作「读自己所写一致性」，即自己写完数据版本 N 后，后续读到的版本一定不小于版本 N。
- 它解决的问题：A 发了个抖音视频，刷新页面后却莫名其妙消失了（旧版本），几分钟后才重新刷出来。
- 实现方式之一：为写入者单独添加一个读取规则，他的读都由已更新其写入数据的副本来处理。
单调读一致性 Monotonic Read Consistency ：保证多个读操作的顺序，即客户端一旦读到某个数据版本 N，后续不会读到比 N 更低的版本。
- 它解决的问题是：A 删除了一个抖音视频，可多次刷新，偶尔刷不到视频，偶尔又能刷到被删除视频（旧版本），几分钟后才彻底被删除。
- 实现方式之一：为每个用户的读都创建一个副本映射，后续的读都由一个固定的副本处理，避免随机切换副本而读到更老的值。
单调写一致性 Monotonic Write Consistency：保证多个写操作的顺序，即客户端对同一数据的两次写入操作，一定按其被提交的顺序被执行。
读后写一致性 Write after Read Consistency：读后写一致性，保证一个客户端读到数据版本 N 后（可能是其他客户端写入的），随后对同一数据的写操作必须要在版本号大于等于 N 的副本上执行。

上述四个一致性模型都只从每个客户端自身的角度定义规则，比较片面，因此它们都是「弱一致模型」。

而不考虑客户端，直接从所有数据库用户的操作视角看，有如下几种一致性模型：

线性一致性 Linearizability ：线性一致性利用了事件的提交顺序，它保证任何读操作得到的数据，其顺序跟读/写事件的提交顺序一致。
- 简单的说它要求整个系统表现得像只存在一个副本，所有操作的执行结果就跟这些事件按提交顺序完全串行执行一样。这实际也是在说所有并发事件都是原子的，一旦互相之间存在冲突，就一定得按顺序执行，因此也有人称它为「原子一致性」。
- 线性一致性，完全等价于系统对外状态的「强一致性」
- 线性一致性的系统是完全确定性的
- 实现方式：需要一个所有节点都一致的「全局时钟 」，这样才可以对所有事件进行全局排序。
  - 大多数分布式数据库如 TiDB/Etcd 都是通过 NTP 等协议进行单点授时与同步实现的全局时钟。
  - 有全球化部署需要的 Google Spanner 是使用 GPS + 原子钟实现的全局时钟 TrueTime，全局误差可以控制在 7ms 以内。
- 局限性：根据爱因斯坦相对论，「时间是相对的」，实际上并不存在绝对的时间，因此线性一致性只在经典物理学范围内适用。
顺序一致性 Sequentially Consistent ：顺序一致性最早是 Leslie Lamport 用来描述多核 CPU 的行为的，在分布式系统领域用得较少。
- 顺序一致性的要求有两点：
  - 从单个进程（副本）的角度看，所有指令的执行顺序跟代码逻辑的顺序完全一致。
  - 从所有的处理器（整个分布式系统）角度看，写操作不必立即对所有用户可见，但是所有副本必须以相同的顺序接收这些写操作。
- 顺序一致性和线性一致性都是要找到一个满足「写后读」的一组操作历史，差异在于线性一致性要求严格的时间序，而顺序一致性只要求满足代码的逻辑顺序，而其他代码逻辑未定义的事件顺序（比如多副本上各事件之间的顺序），具体是什么样的顺序无所谓，只要所有副本看到的事件顺序都相同就行。
- 顺序一致性并不能提供「确定性」，相同的两次操作仍然可能得到不同的事件顺序。
- 实现方式：因为不要求严格的全局时间序，它就不需要一个全局时钟了，但实际上为了满足全局的确定性，仍然需要一些复杂的操作。
因果一致性 Causal Consistency ：线性一致性的全局时钟有其局限性，而因果一致性基于写事件的「偏序关系」提出了「逻辑时钟 」的概念，并保证读顺序与逻辑时钟上的写事件顺序一致。
- 写事件的「偏序关系」关系是指，至少部分事件（比如一个节点内部的事件）是可以使用本地时钟直接排序的，而节点之间发生通讯时，接收方的事件一定晚于调用方的事件。基于这一点可以实现一个「逻辑时钟」，但逻辑时钟的缺点在于，如果某两个事件不存在相关性，那逻辑时钟给出的顺序就没有任何意义。
- 多数观点认为，因果一致性弱于线性一致性，但在并发性能上具有优势，也足以处理多数的异常现象，所以因果一致性也在工业界得到了应用。
- CockroachDB 和 YugabyteDB 都在设计中采用了逻辑混合时钟（Hybrid Logical Clocks），这个方案源自 Lamport 的逻辑时钟，也取得了不错的效果
前缀一致性 Consistent Prefix ：副本之间的同步过程中，会存在一些副本接收数据的顺序并不一致。「前缀一致性」是说所有用户读到的数据顺序的前缀永远是一致的。
- 「前缀」是指程序在执行写操作时，需要显式声明其「前缀」事件，这样每个事件就都存在一个由其他写事件排列而成的前缀。比如当前有写事件排列「A B C D」，那所有用户读到的数据都拥有同样的写事件前缀，比如「A」、「A B」、「A B C」、「A B C D」，但不可能出现「A C」或者「C A」等结果。
- 它解决的是分片分布式数据库的一致性问题：A B C 因为地域区别读写的是不同的副本，B 在抖音评论区问了个问题，然后 A 作出了回答。但是问题跟回答两个数据如果处于不同的分片，副本同步时这两个数据的顺序是无法保证的，C 可能会先读到回答信息，之后才刷新出 B 的提问，历史事件的顺序就乱了。
- 实现方式：需要程序主动为消息之间添加显式的依赖关系，再据此控制其读取顺序，实现比较复杂。
- 存在的问题：只有被显式定义了因果关系的事件，它们之间的顺序才能被保证。

其中线性一致性 就是强一致性 ，其他所有的模型都是弱一致性模型 或者说最终一致性模型。所有这些模型按强度降序排列如下：

线性一致性/强一致性：系统对外表现得好像整个系统完全一致，不存在不一致的情况。
顺序一致性：只保证每个节点上的事件顺序一致，对节点之间的事件顺序只有非常宽松的要求。
因果一致性：同样只保证每个节点上的事件顺序一致，但是对节点之间的事件顺序的要求比顺序一致性更宽松。
有界旧一致性（Bounded Staleness）：保证读到的数据与最新版本的差距不超过 K 个版本
会话一致性（Session Consistency）：在一个会话内保证单调读，单调写，和读自己所写，会话之间不保证
前缀一致性：在每个会话内保证了单调读，会话之间不保证
客户端角度的四个一致性模型：写后读、单调读、单调写、读后写。这四个模型的视角都非常片面，通常被包含在前述的一致性模型中。

更完整的关系树状图：Consistency Models

二、分布式系统的 BASE 与最终一致性 {#二分布式系统的-base-与最终一致性}

BASE 理论：

基本可用 Basically Available ：当分布式系统在出现不可预知的故障时，允许损失部分功能的可用性，保障核心功能的可用性
- 四种实现基本可用的手段：流量削峰、延迟响应、体验降级、过载保护
软状态 Soft state：在柔性事务中，允许系统存在中间状态，且这个中间状态不会影响系统整体可用性。比如，数据库读写分离，写库同步到读库（主库同步到从库）会有一个延时，其实就是一种柔性状态。
最终一致性 Eventually consistent：前面已经说得很详细了，它指对系统的任何节点/进程，写操作完成后，后续的任何访问可能会拿到的值是不确定的，但经过有限的一段时间后，后续的任何访问都能读到新的值。

ACID 与 BASE 实质上是分布式系统实现中的的两个极端：

ACID 理论就如它的含义「酸」一样，是 CAP 原则中一致性的边界------最强的一致性，是牺牲掉 A 后达到 CP 的极致。
BASE 翻译过来就是「碱」，它是 CAP 原则中可用性的边界------最高的可用性，最弱的一致性，通过牺牲掉 C 来达到 AP 的极致。

根据 CAP 理论，如果在分布式系统中实现了一致性，可用性必然受到影响。比如，如果出现一个节点故障，则整个分布式事务的执行都是失败的。实际上，绝大部分场景对一致性要求没那么高，短暂的不一致是能接受的，另外，也基于可用性和并发性能的考虑，建议在开发实现分布式系统时，如果不是必须，尽量不要实现事务，可以考虑采用最终一致性。

最终一致性的实现手段：

读时修复：在读取数据时，检测数据的不一致，进行修复
写时修复：在写入数据时，检测数据的不一致，进行修复
异步修复：这个是最常用的方式，通过定时对账，检测副本数据的一致性并修复

在实现最终一致性的时候，还推荐同时实现自定义写一致性级别（比如 All、Quorum、One、Any），许多分布式数据库的最终一致性级别都是可调的。

但是随着 TiDB 等分布式关系数据库的兴起，分布式领域的 BASE 理论实际上正在被 ACID 赶超，ACID 焕发又一春了。

三、共识算法 {#三共识算法}

共识算法，也被称为一致性协议，是指在分布式系统中多个节点之间对某个提案 Proposal（例如多个事务请求，先执行谁？）达成一致看法的一套流程。

提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是主节点......等等。可以认为任何可以达成一致的信息都是一个提案。

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

共识算法是达成数据一致性的一种手段，而且是数据强一致性的必要非充分条件。比如直接使用 Raft 算法，但是允许读取集群的任何节点，只能得到数据的最终一致性，还需要其他手段才能确保强一致性。

拜占庭将军问题与拜占庭容错 {#拜占庭将军问题与拜占庭容错}

拜占庭错误是 1982 年兰伯特在《拜占庭将军问题》中提出的一个错误模型，描述了在少数节点不仅存在故障，还存在恶意行为的场景下，能否达成共识这样一个问题，论文描述如下：

9 位拜占庭将军分别率领一支军队要共同围困一座城市，因为这座城市很强大，如果不协调统一将军们的行动策略，部分军队进攻、部分军队撤退会造成围困失败，因此各位将军必须通过投票来达成一致策略，要么一起进攻，要么一起撤退。

因为各位将军分别占据城市的一角，他们只能通过信使互相联系。在协调过程中每位将军都将自己投票"进攻"还是"撤退"的消息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他将军送过来的投票，就可以知道投票结果，从而决定是进攻还是撤退。

而问题的复杂性就在于：将军中可能出现叛徒，他们不仅可以投票给错误的决策，还可能会选择性地发送投票。假设 9 位将军中有 1 名叛徒，8 位忠诚的将军中出现了 4 人投"进攻"，4 人投"撤退 "，这时候叛徒可能故意给 4 名投"进攻"的将军投"进攻"，而给另外 4 名投"撤退"的将军投"撤退 "。这样在 4 名投"进攻"的将军看来，投票是 5 人投"进攻"，从而发动进攻；而另外 4 名将军看来是 5 人投"撤退"，从而撤退。这样，一致性就遭到了破坏。

还有一种情况，因为将军之间需要通过信使交流，即便所有的将军都是忠诚的，派出去的信使也可能被敌军截杀，甚至被间谍替换，也就是说将军之间进行交流的信息通道是不能保证可靠性的。所以在没有收到对应将军消息的时候，将军们会默认投一个票，例如"进攻"。

更一般地，在已知有 N 个将军谋反的情况下，其余 M 个忠诚的将军在不受叛徒的影响下能否达成共识？有什么样的前提条件，该如何达成共识？这就是拜占庭将军问题。

如果一个共识算法在一定条件下能够解决拜占庭将军问题，那我们就称这个算法是「拜占庭容错 Byzantine Fault Tolerance（BFT） 」算法。反之如果一个共识算法无法接受任何一个节点作恶，那它就被称为「非拜占庭容错 Crash Fault Tolerance (CFT)」算法。

可以通过简单穷举发现，二忠一叛是无法达成共识的，这个结论结合反证法可证明，拜占庭容错算法要求叛徒的比例必须低于 1/3。

常用共识算法 {#常用共识算法}

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

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

此外，XFT（Cross Fault Tolerance，2015 年）等最近提出的改进算法可以提供类似 CFT 的处理响应速度，并能在大多数节点正常工作时提供 BFT 保障。Algorand 算法（2017 年）基于 PBFT 进行改进，通过引入可验证随机函数解决了提案选择的问题，理论上可以在容忍拜占庭错误的前提下实现更好的性能（1000+ TPS）。

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

常见共识算法列举如下：

| | 拜占庭容错 | 一致性 | 性能 | 可用性（能容忍多大比例的节点出现故障） | |------------------------------------------------------------------------------------------------|-------|-------|----|---------------------| | 两阶段提交 2PC | 否 | 强一致性 | 低 | 低 | | TCC(try-confirm-cancel) | 否 | 最终一致性 | 低 | 低 | | Paxos | 否 | 强一致性 | 中 | 中 | | ZAB | 否 | 最终一致性 | 中 | 中 | | Raft | 否 | 强一致性 | 中 | 中 | | Gossip | 否 | 最终一致性 | 高 | 高 | | Quorum NWR | 否 | 强一致性 | 中 | 中 | | PBFT | 是 | N/A | 低 | 中 | | PoW | 是 | N/A | 低 | 中 | | PoS | 是 | N/A | 低 | 中 | | PoH | 是 | N/A | 中 | 中 |

注：这里虽然列出了 PoW/PoS/PoH 等应用在区块链中的一致性算法，但是它们跟 PBFT 等其他拜占庭容错算法存在很大的区别，后面会给出介绍。

不同共识算法的应用场景 {#不同共识算法的应用场景}

在不可信环境中，因为可能存在恶意行为，就需要使用支持拜占庭容错的共识算法如 PoW/PoS，使系统在存在部分节点作恶的情况下仍然能达成共识。这就是区块链使用 PoW/PoS 算法而不是 Paxos/Raft 算法的原因。

而在企业内网等场景下，可以认为是可信环境，基本不会出现恶意节点或者可以通过 mTLS 等手段进行节点身份认证，这种场景下系统具有故障容错能力就够了，就没必要做到拜占庭容错，因此常用 Raft/Paxos 等算法。

非拜占庭错误共识算法 Paxos 与 Raft {#非拜占庭错误共识算法-paxos-与-raft}

受限于篇幅与笔者精力，这部分暂时跳过...后面可能会写篇新的文章专门介绍 Paxos/Raft 算法。

能容忍拜占庭错误的 PoW 概率共识算法 {#能容忍拜占庭错误的-pow-概率共识算法}

PoW 即 Proof of Work 工作量证明，指系统为达到某一目标而设置的度量方法。简单理解就是一份证明，用来确认你做过一定量的工作。监测工作的整个过程通常是极为低效的，而通过对工作的结果进行认证来证明完成了相应的工作量，这个认证流程是非常简单高效的，这就是 PoW 的优势所在。

在 1993 年，Cynthia Dwork 和 Moni Naor 设计了一个系统用于反垃圾邮件、避免资源被滥用，这是 PoW 算法的雏形。其核心思想如下：

The main idea is to require a user to compute a moderately hard but not intractable function in order to gain access to the resource, thus preventing frivolous use.

翻译成中文：

其主要思想是要求用户计算一个中等难度但不难处理的函数，以获得对资源的访问，从而防止（系统资源被）滥用。

在 1999 年，Markus Jakobsson 与 Ari Juels 第一次从各种协议中提炼出 Proofs of Work 这个概念。

POW 系统中一定有两个角色，工作者和验证者，他们需要具有以下特点：

工作者需要完成的工作必须有一定的量，这个量由工作验证者给出。
验证者可以迅速的检验工作量是否达标。
工作者无法自己"创造工作"，必须由验证者发布工作。
工作者无法找到很快完成工作的办法。

说到这里，我们对 PoW 应该有足够的理解了，它就是让工作者消耗一定的资源作为使用系统的成本。对于正常的用户而言这部分被消耗的资源是完全可以接受的，但是对于恶意攻击者而言，它如果想滥用系统的资源或者发送海量的垃圾邮件，就需要消耗海量的计算资源作为成本，这样就极大地提升了攻击成本。

再总结下，PoW 算法的核心是它为信息发送加入了成本，降低了信息传递的速率。

把比特币区块链转换成拜占庭将军问题来看，它的思路是这样的：

限制一段时间内提案的个数，只有拥有对应权限的节点（将军）可以发起提案。
- 这是通过 PoW 工作量证明实现的，比特币区块链要求节点进行海量的哈希计算作为获得提案权限的代价，算法难度每隔两周调整一次以保证整个系统找到正确 Hash 值的平均用时大约为 10 分钟。
由强一致性放宽至最终一致性。
- 对应一次提案的结果不需要全部的节点马上跟进，只需要在节点能搜寻到的全网络中的所有链条中，选取最长的链条进行后续拓展就可以。
使用非对称加密算法对节点间的消息传递提供签名技术支持，每个节点（将军）都有属于自己的秘钥（公钥私钥），唯一标识节点身份。
- 使用非对称加密算法传递消息，能够保证消息传递的私密性。而且消息签名不可篡改，这避免了消息被恶意节点伪造。

我们前面有给出一个结论：拜占庭容错算法要求叛徒的比例必须低于 1/3。

但是区块链与拜占庭将军问题的区别很大，举例如下：

区块链允许任何节点随时加入或离开区块链，而拜占庭将军问题是预设了节点数，而且不考虑节点的添加或删除。
比特币区块链的 PoW 算法只能保证整个系统找到正确 Hash 值的平均用时大约为 10 分钟，那肯定就存在性能更好的节点用时更短，性能更差的节点用时更长，甚至某些节点运气好几秒钟就算出了结果，这都是完全可能的。而越早算出这个 Hash 值的节点，它的提案（区块）成为最长链条的概率就越大。
PoW 由强一致性放宽至最终一致性，系统总会选取最长的链进行后续拓展，那如果某个链条一开始不长，但是它的拓展速度足够快，它就能成为最长的链条。而拜占庭将军问题不允许任何分支，只存在一个结果！
- 只是受限于算力，随着时间的推移，短的链条追上最长链条的概率会越来越小。

总之因为区块链这样的特点，它会产生一些跟拜占庭容错算法不同的结果：

攻击者拥有的节点数量占比是毫无意义的，核心是算力，也就对应着区块链中的提案权。
- 即使攻击者拥有了 99% 的节点，但是它的总体算力很弱的话，它的提案（区块）成为最长链条的概率也会很低。
区块链的 51% 攻击：因为「系统总是选取最长链条进行后续拓展」这个原则，只有某个攻击者拥有了超过 50% 算力的情况下，它才拥有绝对性的优势，使它的区块在一定时间后一定能成为最长的链条，并且始终维持这样一个优势，从而达成攻击目的。

至于 PoW 算法的具体实现，以及它的替代算法 PoS/PoH 等新兴算法的原理与实现，将在后续的区块链系列文章中详细介绍，尽请期待...