> For the complete documentation index, see [llms.txt](https://yeasy.gitbook.io/blockchain_guide/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yeasy.gitbook.io/blockchain_guide/04_distributed_system/problem.md).

# 一致性问题

一致性问题是分布式领域最基础、最重要的问题，也是半个世纪以来的研究热点。

随着业务场景越来越复杂，计算规模越来越庞大，单点系统往往难以满足高可扩展（Scalability）和高容错（Fault-tolerance）两方面的需求。此时就需要多台服务器通过组成集群，构建更加强大和稳定的“虚拟超级服务器”。

任务量越大，处理集群的规模越大，设计和管理的挑战也就越高。谷歌公司的全球搜索集群系统，包括数十万台服务器，每天响应百亿次的互联网搜索请求。

集群系统要实现一致性不是一件容易的事。不同节点可能处于不同的状态，不同时刻收到不同的请求，而且随时可能有节点出现故障。要保持对外响应的“一致性”，好比训练一群鸭子齐步走，难度可想而知。

## 定义与重要性

**定义** 一致性（Consistency），早期也叫（Agreement），在分布式系统领域中是指对于多个服务节点，给定一系列操作，在约定协议的保障下，使得它们对处理结果达成“某种程度”的协同。

理想情况（不考虑节点故障）下，如果各个服务节点严格遵循相同的处理协议（即构成相同的状态机逻辑），则在给定相同的初始状态和输入序列时，可以确保处理过程中的每个步骤的执行结果都相同。因此，传统分布式系统中讨论一致性，往往是指在外部任意发起请求（如向多个节点发送不同请求）的情况下，确保系统内大部分节点实际处理请求序列的一致，即对请求进行全局排序。

那么，为什么说一致性问题十分重要呢？

举个现实生活中的例子，多个售票处同时出售某线路上的火车票，该线路上存在多个经停站，怎么才能保证在任意区间都不会出现超售（同一个座位卖给两个人）的情况？

这个问题看起来似乎没那么难，现实生活中经常通过分段分站售票的机制。然而，要支持海量的用户进行并行购票，并非易事（如 12306 网站高峰期日均访问量超过 500 亿次）。特别是计算机系统往往需要达到远超物理世界的高性能和高可扩展性需求，挑战会变得更大。这也是为何每年到了促销季，各大电商平台都要提前完善系统。

*注：一致性关注的是系统呈现的状态，并不关注结果是否正确；例如，所有节点都对某请求达成否定状态也是一种一致性。*

## 问题挑战

计算机固然很快，但在很多地方都比人类世界脆弱的多。典型的，在分布式系统中，存在不少挑战：

* 节点完成请求的时间无法保障，处理的结果可能是错误的，甚至节点自身随时可能发生故障；
* 为了实现可扩展性，集群往往要采用异步设计，依靠网络消息交互，意味着不可预测的通信延迟、丢失或错误。

仍以火车票售卖问题为例，愿意动脑筋的读者可能已经想到了一些不错的解决思路，例如：

* 要出售任意一张票前，先打电话给其他售票处，确认下当前这张票不冲突。即退化为同步调用来避免冲突；
* 多个售票处提前约好隔离的售票时间。比如第一家可以在上午 8 点到 9 点期间卖票，接下来一个小时是另外一家……即通过令牌机制来避免冲突；
* 成立一个第三方的存票机构，票集中存放，每次卖票前找存票机构查询。此时问题退化为中心化中介机制。

这些思路假设售票处都能保证正常工作，并且消息传递不会出现错误。

当然，还可以设计出更多更完善的方案，但它们背后的核心思想，都是**将可能引发不一致的并行操作进行串行化**。这实际上也是现代分布式系统处理一致性问题的基础思路。另外，由于普通计算机硬件和软件的可靠性不足，在工程实现上还要对核心部件稳定性进行加强。

反过来，如果节点都很鲁棒，性能足够强，同时网络带宽足够大、延迟足够低，这样的集群系统往往更容易实现一致性。

然而，真实情况可能比人们预期的糟糕。2015年，论文《Taming Uncertainty in Distributed Systems with Help from the Network》中指出，即便部署了专业设备和冗余网络的中等规模的数据中心，每个月发生的网络故障高达 12 次。

## 一致性的要求

规范来看，分布式系统达成一致的过程，应该满足：

* 可终止性（Termination）：一致的结果在有限时间内能完成；
* 约同性（Agreement）：不同节点最终完成决策的结果是相同的；
* 合法性（Validity）：决策的结果必须是某个节点提出的提案。

可终止性很容易理解。有限时间内完成，意味着可以保障提供服务（Liveness）。这是计算机系统可以被正常使用的前提。需要注意，在现实生活中这点并不是总能得到保障的。例如取款机有时候会出现“服务中断”；拨打电话有时候是“无法连接”的。

约同性看似容易，实际上暗含了一些潜在信息。决策的结果相同，意味着算法要么不给出结果，要么任何给出的结果必定是达成了共识的，即安全性（Safety）。挑战在于算法必须要考虑的是可能会处理任意的情形。凡事一旦推广到任意情形，往往就不像看起来那么简单。例如现在就剩一张某区间（如北京 --> 南京）的车票了，两个售票处也分别刚通过某种方式确认过这张票的存在。这时，两家售票处几乎同时分别来了一个乘客要买这张票，从各自“观察”看来，自己一方的乘客都是先到的……这种情况下，怎么能达成对结果的共识呢？看起来很容易，卖给物理时间上率先提交请求的乘客即可。然而，对于两个来自不同位置的请求来说，要判断在时间上的“先后”关系并不是那么容易。两个车站的时钟时刻可能是不一致的；时钟计时可能不精确的……根据相对论的观点，不同空间位置的时间是不一致的。因此追求绝对时间戳的方案是不可行的，能做的是要对事件的发生进行排序。

事件发生的相对先后顺序（逻辑时钟）十分重要，确定了顺序，就没有了分歧。这也是解决分布式系统领域很多问题的核心秘诀：**把不同时空发生的多个事件进行全局唯一排序，而且这个顺序还得是大家都认可的**。

如果存在可靠的物理时钟，实现排序往往更为简单。高精度的石英钟的漂移率为 $$10^{-7}$$，最准确的原子震荡时钟的漂移率为 $$10^{-13}$$。Google 曾在其分布式数据库 Spanner 中采用基于原子时钟和 GPS 的“TrueTime”方案，能够将不同数据中心的时间偏差控制在 10ms 置信区间。在不考虑成本的前提下，这种方案简单、有效。然而，计算机系统的时钟误差要大得多，这就造成分布式系统达成一致顺序十分具有挑战。

*注：Leslie Lamport 在 1978 年发表的论文《Time, Clocks and the Ordering of Events in a Distributed System》中将分布式系统中顺序与相对论进行对比，提出了偏序关系的观点。而根据相对论，并不存在绝对的时间。因此，先后顺序可能更有意义。*

最后的合法性看似绕口，但其实比较容易理解，即达成的结果必须是节点执行操作的结果。仍以卖票为例，如果两个售票处分别决策某张票出售给张三和李四，那么最终达成一致的结果要么是张三，要么是李四，而不能是其他人。

## 带约束的一致性

从前面的分析可以看出，要实现理想的严格一致性（Strict Consistency）代价很大。除非系统所有节点都不发生任何故障，而且节点间通信没有延迟，此时整个系统等价于一台机器。实际上，实现较强的一致性要求同步操作，容错性差，同时会牺牲部分性能和可扩展性。实际系统往往会选择不同强度的一致性，主要包括强一致性（Strong Consistency）和弱一致性（Weak Consistency）两大类。

强一致性主要包括顺序一致性（[Sequential Consistency](https://en.wikipedia.org/wiki/Sequential_consistency)）和线性一致性（[Linearizability Consistency](https://en.wikipedia.org/wiki/Linearizability)）：

* 顺序一致性：最早由 Leslie Lamport 1979 年经典论文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》中提出，是一种较强的约束。所有进程看到的全局执行顺序（total order）一致；并且每个进程看自身操作的顺序（local order）跟实际发生顺序一致。例如，某进程先执行 A，后执行 B，则实际得到的全局结果（其它进程也看到这个结果）中就应该为 A 在 B 前面，而不能反过来。如果另一个进程先后执行了 C、D 操作，则全局顺序可以共识为 A、B、C、D 或 A、C、B、D 或 C、A、B、D 或 C、D、A、B 的一种（即 A、B 和 C、D 的组合），决不能出现 B、A 或 D、C。顺序一致性限制了各进程自身指令的偏序关系，但不要求不同进程之间按照真实物理时间排序，属于实践中应用较多的强一致性。以算盘为例，每个进程的事件是某根横轴上的算珠，它们可以前后拨动（改变不同进程之间先后顺序），但同一个横轴上的算珠的相对先后顺序无法改变。
* 线性一致性：由 Maurice P. Herlihy 与 Jeannette M. Wing 在 1990 年经典论文《Linearizability: A Correctness Condition for Concurrent Objects》中共同提出，是单对象场景下很强的一致性。它在顺序一致性前提下增加了真实时间顺序要求：如果操作 A 完成后操作 B 才开始，则全局顺序中 A 必须排在 B 前面。线性一致性要求系统看起来似乎只有一个数据副本，客户端操作都是原子的，并且顺序执行。例如某个客户端写入成功后，另一个客户端随后发起读取，就应该看到该写入或更新的结果。线性一致性较难实现，目前基本上要么依赖于全局的时钟或锁，要么通过一些共识算法，性能往往不高。

因果一致性（Causal Consistency）弱于顺序一致性。它要求所有进程以相同顺序观察存在因果关系的操作，但允许对并发且互不依赖的操作观察到不同顺序。例如先发问题再收到回答，任何人都不应先看到回答再看到问题；但两个互不依赖的回答可以被不同人以不同顺序看到。

强一致性比较难实现，很多场景下可以放宽对一致性的要求，采用部分异步操作，从而提升性能、可扩展性，降低响应延迟，这些在某些方面弱化的一致性都笼统称为弱一致性。例如互联网领域常用的最终一致性（Eventual Consistency），允许出现临时不一致或看到过时数据，但在经历一段时间后可以达到一致的状态。例如电商购物时将某物品放入购物车，但是可能在最终付款时才提示物品已经售罄了。