2.1　概述

数据库管理系统（DataBase Management System，DBMS，以下简称“数据库”），是位于用户与操作系统之间的一层数据管理软件，功能主要包括数据定义、数据操纵、数据库的运行管理、数据库的建立和维护等（见参考文献[19]）。

分布式数据库系统由分布于多个计算机节点上的若干个数据库系统组成，它提供有效的存取手段来操纵这些节点上的子数据库。分布式数据库在使用上可视为一个完整的数据库，而实际上它分散在处于不同物理位置的各个节点上。当然，分布在各个节点上的子数据库在逻辑上是相关的[1]。

分布式事务型数据库系统用于实现分布式事务处理功能。分布式事务处理技术与单机事务处理技术的不同之处是，面向的数据库系统是否为分布式的，是否引入了分布式系统的一致性问题。这类一致性问题需要与事务一致性问题一起考虑。分布式事务的重点在于ACID特性。所以，分布式事务的一致性是事务的一致性而非外部一致性，但需要考虑外部一致性的需求。

外部一致性的需求表现在这几个方面：分布式系统受多节点分布、每份数据存在多个副本、各节点间存在时延、所有节点间存在分区等问题的影响。在一个分布式系统中，读、写操作对于外部的客户端而言，需要实现外部一致性以满足客户端操作的逻辑一致性。

因为要结合数据库的事务处理模型、数据的事务一致性要求、分布式的外部一致性要求，所以分布式数据库的事务处理模型会变得更复杂，需要探索在外部一致性和事务一致性这两个需求下读、写操作之间的关系。为了在系统层面满足应用对数据库提出的高可用、高可靠的需求，分布式数据库的事务处理系统会变得更为复杂，需要探索不同层次的高可用性和分布式事务处理之间的关系，并解决各种故障，如节点上的事务故障、节点故障、分区/通信故障等。为了在系统层面满足用户对分布式数据库提出的高性能的需求，分布式数据库的事务模型需要抛弃集中式的全局事务处理机制，考虑去中心化的分布式事务模型。

对于分布式一致性来说，可简单分为如下3种类型（如果细分的话，可分为很多一致性，如顺序一致性、FIFO一致性、会话一致性、单读一致性、单写一致性等）。

• 弱一致性（weak consistency）：当写入一个新值后，读操作在数据副本上可能读出来，也可能读不出来。比如搜索引擎，不能实时反映外界信息的真实情况。
• 最终一致性（eventually consistency，见参考文献[27]）：当写入一个新值后，有可能读不出来，但在某个时间窗口之后要保证最终能读出来（“最终”的含义是所有相关的操作都完成后）。比如电子邮件系统，要保证收件人最终能够收到相关的邮件。
• 强一致性（strong consistency，见参考文献[286]）：新的数据一旦写入，在任意副本中，在任意时刻都能读到新值。比如文件系统就是强一致性的。

这3种一致性都是分布式架构带来的一致性，这里的分类方式并不十分科学，但比较形象。这3种不同的一致性，也存在共性的地方，即对数据进行操作，都涉及修改数据，修改后的数据被存储，然后再被读取这3个关键节点。但是，在最后读取这个关键节点上，3种一致性下读取数据的效果是不同的。强一致性确保写过的数据一定能被读到；弱一致不能确保写过的数据一定能被读到；最终一致性在达到“最终”之前可归入弱一致性，但比弱一致性略强一点，在历经一定时间并到“最终”时，得到了应得到的结果，这时又可等效于强一致性。从这3种一致性的归类来看，不同的一致性可以达到的目标或效果是不同的。

下面先简略讨论常见的一致性，然后对各种一致性的细节进行深入分析。

2.1.1　常见的分布式一致性

维基百科[2]讨论了几种常见的一致性，并对不同的一致性进行了定义（注意是在允许并发存在的情况下对一致性进行定义，即允许一定程度的并发事件发生）。

1. 严格一致性

严格一致性（strict consistency）是最强的一致性。在此类一致性下，任何处理器对变量的写入都需要所有处理器立即看到。这可以理解为存在一个全局时钟，在该时钟周期结束时，每个写操作都应反映在所有处理器缓存中，下一个操作只能在下一个时钟周期内发生。

这是一种理想的一致性，对于多个要读写同一个数据项的个体（此处假设为处理器）来说，一个个体修改了数据项则其他所有个体（这是并发的场景）在既定的时间内必须获知修改事件发生。而计算机的硬件体系结构中，一个时钟周期内处理器只能完成一个最基本的动作，一个时钟周期是一个最小的读写操作发生的时长，如果跨了两个时钟周期，则其他处理器（多处理器、多核体系结构）可能读到此数据项的不同值（写操作前、写操作后读到此数据项的不同的值），从而造成“不同个体读到不同的数据值”这样的不一致。

在上面的场景中，对比Spanner等分布式系统，会发现过程非常相似。Spanner中的个体是用户，用户要读写数据；时钟周期是在时间轴上的不同时间段；时钟周期的长度对应着多节点间的网络时延。所以此处的一致性问题在本质上是对所有操作做全序排序的问题。

2. 顺序一致性

顺序一致性（sequential consistency）是一种比严格一致性更弱的一致性。在顺序一致性下，某一处理器对变量的写入，其他处理器不一定要立即看到，但是，不同处理器对变量的写入必须以相同的顺序被所有处理器看到（一个写操作的结果不能立刻被其他个体感知，但是对于其他个体来说，这个写操作的结果总是能确保被其他的个体以同样的顺序“知晓”，这样就确保了对同一个会话的结果的感知是一致的，即确保保持会话内的因果关系）。就如1979年Lamport所说：若任何执行的结果都与所有处理器的操作以某种顺序执行的结果相同，并且每个单独的处理器的操作以其程序指定的顺序出现在该顺序中，那么就可以说这个过程满足顺序一致性。

严格一致性强调的是写事件的结果应该被其他个体立刻知晓（似乎没有时延，但是处于分布式结构中，没有不耗时的消息传递），而顺序一致性强调的是“会话写事件”发生后，需要避免多个观察者观察到不同的结果。因此，顺序一致性是指“会话内的写是有序的且会按该序被有序读到”，因而在顺序一致性下，其他多个观察者看到的结果是一致的。

如图2-1a所示，P1和P2都写数据项X，若P3和P4观察X的过程（两次读X）和结果都是一致的（先读到b后读到a），则说明该过程符合顺序一致性要求。如图2-1b所示，P1和P2都写数据项X，若P3和P4观察X的过程（两次读X）和结果是不一致的（P3先读到b后读到a，P4先读到a后读到b），则说明该过程不符合顺序一致性要求。

对于图2-1所示情况，若个体都是先读到b后读到a，则认为该过程具备顺序一致性。由此可见，在顺序一致性下，只关心所有个体（进程或者节点）的历史事件是否存在唯一的偏序关系，不关心P1和P2写数据项X的偏序关系（尽管P1写X的值a在前）。在顺序一致性中，绝对时间无关紧要，事件的顺序是最重要的，即要保持一个会话内的因果序而不需要全系统遵守实时（Real-time）限制。

顺序一致性首先在参考文献[84，26]中被定义，其中参考文献[26]给出了形式化的定义。

3. 线性一致性

线性一致性（linearizability，又称原子一致性）是Herlihy和Wing在1987年提出的，他们对线性一致性的描述是“can be defined as sequential consistency with the real-time constraint”（可以定义为具有实时约束的序列一致性）。这句话很重要，说明线性一致在考虑了时间的特性后还能够保证顺序一致性，所以线性一致性比顺序一致性更为严格。

对于线性一致性，大家可以参见参考文献[183，193，26]。

线性一致强调操作是原子的，在一个原子操作发生时数据项被修改，之后（带有时间语义）的读操作都能够获取最新的被写过的数据项的数据值。

在分布式系统中，线性一致性强调的是在涉及多个节点且有多个事件发生时，不管是从哪个节点（副本）执行读操作，都能读到按实时顺序被修改后的值。

如图2-1a所示，W(x) a先于W(x) b发生，则P3和P4只有读到的顺序为“R(x)a R(x)b”才符合线性一致性。所以，线性一致性强调了实时排序（Real-time序）的因素。

线性一致的精确定义见参考文献[183，193，194，26]。

4. 因果一致性

因果一致性（causal consistency）是顺序一致性的弱化，它将事件分为因果相关和非因果相关两类。它定义了只有因果相关的写操作才需要被所有进程以相同的顺序看到。

因果一致性的特别之处在于，需要保持相关的事件的逻辑顺序以便保证一致性。遵从会话内的因果一致性为顺序一致性。因果一致性，可参考文献[178]中定义的happened-before关系。

如图2-2所示，P3和P4采用了同样的顺序（过程一致），却没有读到同样的值（结果不一致），这不符合顺序一致性，但是符合因果一致性。因为P2读取到a值后才写x为b值，而P3和P4都先期读到了a值。

在分布式环境内，一个典型的例子是：创建一个用户，然后用此用户登录系统。这两个动作前后带有逻辑关系。如果从一个节点先进行登录，而该节点不知道用户被创建这个事实，则登录必然因用户不存在而失败，但事实上确实用户已经在另外一个节点上创建完毕，只是在这个节点上暂时没有获取到这个用户存在的事实（数据）。

5. 可串行化一致性

如果事务调度的结果（例如，生成的数据库状态）等于其串行执行的事务的结果，则事务调度是可串行化的，也就是其具有可串行化的一致性（Serializability），或者说事务具有一致性。

可串行化一致性是数据库范围内的事务一致性，其和分布式环境、并发环境下的一致性不同，它们也不可简单放在一起比较。但是，事务一致性和分布式一致性可以高度融合，成为新的一致性体系，对于这种一致性的研究目前尚在推进中。注意，在分布式数据库中，事务一致性常和分布式环境中的一致性交叉，对此需要仔细甄别（初步讨论参见2.4节）。

6. 强一致性

所谓强一致性（strong consistency）是指所有访问被所有并行进程（或节点、处理器等）以相同顺序（顺序）看到。

从并发的角度看，强一致性会使所有参与者观察到的结果相同。这是通过线性一致性和顺序一致性来保证的。

强一致性，更多是从一个系统外部的角度看并发系统的数据是否处于一致的状态。所以对于一个分布式数据库系统而言，强一致性需要保证：系统既要满足事务的可串行化一致性又要满足分布式系统的一致性（线性一致性或顺序一致性）。

7. 最终一致性

最终一致性（eventual consistency）是分布式计算中用于实现高可用性的一致性，它非正式地保证：如果对给定数据项没有新的更新，那么最终对该项的所有访问都将返回上次更新的值。

最终一致性服务通常被归类为提供BASE（基本可用、软状态、最终一致性），即基本语义的服务，而不是提供传统的ACID保证。

强一致性与最终一致性都是从一个系统外部的角度看并发系统的数据是否处于一致的状态。但在最终一致性条件下，在某些时间点上，可能存在不一致，随着时间的推移，最终会达成一致（比如多副本之间要达成一致，先让半数以上达成一致，余者逐步达成一致）。

2.1.2　科研情况一览

分布式系统的一致性主要包括线性一致性、顺序一致性、因果一致性等，更多精确定义见参考文献[21，26，27，28，29]等。

参考文献[26]中对非事务存储系统中的一致性进行了详细介绍，突出了非事务存储系统中多种一致性模型中微妙但有意义的差异。这有助于更好地理解非事务存储系统中一致性之间的联系与差异。详情可参见2.3节。

参考文献[22]中把非事务相关的一致性统一归为操作一致性，其中包含因果一致性、线性一致性等，并把操作一致性定义为“在多副本的分布式系统下，单次读写操作访问单个数据项时所能够满足的语义”，还把“操作一致性”分为两级——强一致性和弱一致性。强一致性通常被等同于线性一致性和顺序一致性，弱一致性则放松了线性一致性对读写操作“保持操作发生时的时间顺序的逻辑”的要求。

参考文献[22]中还分析了操作一致性和事务一致性之间的关系：

• 操作一致性是事务一致性实现的基础。
• 即使操作一致性得到了全面保障，也不能说明事务一致性会得到保障。
• 操作一致性是事务一致性的必要条件。

对于操作一致性的定义，存在的可讨论之处如下。

• 操作顺序：单次读写操作，是读在前还是写在前？如果是读在前，先读后写为什么会在多副本的分布式系统中在同一个数据项上发生不一致？之所以会发生不一致，是因为一部分副本先进行写操作，其他的副本虽然在这之后进行读操作，但写入的数据没有同步到其他副本，致使其他副本提供了旧值，进而造成最新的写结果不能被后发生的读操作读取。所以“单次读写操作”应该是“单次先写后读操作”。
• 单次的概念：“单次”的含义是什么？在参考文献[22]中把非事务相关的一致性统一称为“操作一致性”，故“单次”必然不是针对一个事务的，即对于单次来说没有事务的概念。没有事务的概念意味着每个操作都是独立的，所以先发生的写操作和后发生的读操作是两个操作，不是单次操作。由上可知，“单次”不是指操作的个数。

对于操作一致性的合理理解应当是，“单个会话”内发生的先写后读两个作用在同一个数据对象上的操作，后面发生的读操作一定能够读取到前面的写操作写入的数据，所以对于多副本的分布式系统而言，要么区分主备副本且只在主副本上提供读服务，要么副本间必须强同步后才可以从任何副本上读取数据。但是，后者显然需要有事务功能的支持才能确保写多个副本时“要么成功要么失败”（至少是写多个副本时操作是满足ACID中的“原子性”的）。

参考文献[29]把分布式系统中的“单调读”“单调写”“因果一致性”等一致性归于“session guarantees”（会话保证），这意味着分布式系统下的一部分一致性问题是与会话（session）相关的。

对于操作一致性的另外一种理解是，“多个会话”发生了先写后读事件，此时需有机制确定不同会话间发生的事件的先后顺序，比如Spanner利用Truetime机制排序任何会话上发生的操作。

以上情况，均不是“单次”之意所能表达的。因此，本章将分布式系统涉及的一致性，统一称为分布式一致性，其中包括了强一致性的外部一致性，弱一致性的最终一致性。而分布式一致性有一部分一致性，如单调读、单调写、因果一致性等，更强调读和写操作，或者说读和写事件之间发生的顺序，这是一种逻辑关系。而表示顺序的逻辑关系的天然方式就是时间，因此一些系统利用时间对读和写事件的前后逻辑关系进行标识。另外，强一致性中诸如外部一致性，对于一系列的操作（如事务内的多个写操作）更多强调其操作序列的原子性，也强调在多副本下同步数据的原子性，只有原子性得到保障，才能进一步考虑分布式系统下的带有“前后关系的逻辑特性”。

对于分布式数据库系统（非NoSQL系统），根据CAP分布式原理，可以把因分布式系统对数据库的影响限制在较强的一致性上（顺序一致性、线性一致性等）。

参考文献[261]统一定义了多种一致性，并试图把分布式一致性和事务一致性进行结合（见图2-3），但是这种结合还是着力在分布式一致性上，使得分布式一致性和事务一致性的结合只落脚在严格可串行化（strict serializability）上，参考文献中没有更深入探索如何把二者紧密结合，这类似参考文献[29]给出的关系，如图2-4所示（结合点只有一个，即严格可串行化）。

在分布式架构中，物理节点是分离的，每个节点相对独立，节点间通过网络相连，全部独立的节点和网络构成一个完整的系统。

分布式架构中，实体对象有两类——物理节点和网络。物理节点存在失效（故障）的可能，网络也存在失效的可能。这两类对象的失效为分布式系统带来了可靠性、可用性方面的问题。即使不失效，网络上也存在时延的问题，时延为分布式系统带来了可用性方面的问题（参见1.2.2节）。

另外，分布式系统中并发事件间的顺序会引发一致性问题，这涉及不同的读、写操作对存储的数据项进行的并发操作，以及并发操作事件在数据项上体现出的对结果是否可读、何时可读的问题，这样的问题就是分布式架构为分布式系统带来的复杂的一致性——分布式一致性。本章开篇曾介绍过，分布式一致性又可分为结果一致性（consensus，共识，一致的意见）[6]和次序一致性（consistency，一致的顺序），后者是本书讨论的重点。

另外，对于分布式事务型数据库，还有事务的一致性问题，这将在2.4节讨论。

接下来的两节将分别对结果一致性和次序一致性进行讨论。

---

[1]参见https://baike.baidu.com/item/分布式系统/4905336?fr=aladdin。

[2]https://en.wikipedia.org/wiki/Consistency_model。

[3]参见http://regal.csep.umflint.edu/~swturner/Classes/csc577/Online/Chapter06/img06.html。

[4]http://regal.csep.umflint.edu/~swturner/Classes/csc577/Online/Chapter06/img10.html。

[5]图中使用结果可见性来定义一系列共识和一致性。选中标记表示在一致性中被强制执行的约束。这里我们假设程序、会话和事务是等价的。注意，因为结果可见性是一个不变量，所以约束是可加的，不需要提前执行。因此，我们可以仅使用结果可见性来构造此表的列，从而简洁地表示各种排序保证。

[6]结果一致性，可用consensus一词表达其含义，即为“共识”。所谓共识就是对某种行为、结果实现共同认可。