分布式数据库的一致性问题与共识算法

个人笔记，不保证正确！

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

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

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

一、一致性 - Consistency

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

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

1. 事务一致性 - Transactions Consistency

「事务一致性」指的是数据库中事务的一致性，它是 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 得到的数据库，性能是非常差的。因此在关系数据库中，设计者通常会选择牺牲相对 不重要的「隔离性」来获取更好的性能。

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

• 脏写 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

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

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

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. 状态视角 - 强一致与弱一致

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

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

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

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

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

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 理论：

• 基本可用 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）。

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

常见共识算法列举如下：

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

不同共识算法的应用场景

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

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

非拜占庭错误共识算法 Paxos 与 Raft

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

能容忍拜占庭错误的 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 等新兴算法的原理与实现，将在后续的区块链 系列文章中详细介绍，尽请期待…

参考

• 《Designing Data-Intensive Applications - The Big Ideas Behind Reliable, Scalable, and Maintainable Systems (Martin Kleppmann)》
• 极客时间《分布式数据库 30 讲》
• 极客时间《分布式协议与算法实战》
• 分布式存储系统的一致性是什么？- OceanBase
• 线性一致性和 Raft - PingCAP
• 一致性模型笔记
• 条分缕析分布式：浅析强弱一致性 - 张铁蕾
• Why you should pick strong consistency, whenever possible - Google Spanner
• 拜占庭将军问题与区块链
• 区块链协议安全系列— —当拜占庭将军犯错时，区块链共识还安全么？（上集）
• Eventually Consistent - Revisited