1.1　分布式数据库系统的挑战

分布式数据库系统在逻辑上可以看作一个完整的系统，用户如同在使用单机数据库系统；但是，从物理角度看，其为一个网络系统，包含若干个物理意义上的分散的节点，而节点之间通过网络进行连接，通过网络协议进行数据交换。

分布式数据系统需要应对网络故障、节点故障。网络故障会直接导致分区事件（CAP[1]原理中的P，即网络发生故障使得网络被分为多个子部分）发生，系统的可用性会受到影响；节点故障可能会引发单点故障，也就是在数据为单副本的情况下节点故障会直接导致部分数据不能被访问。为避免单点故障，数据需要有多个副本，从而使系统的可用性得到较大提高。节点故障也可能引发分区事件。

除了上述问题外，分布式数据库系统还可能带来不一致问题。比如旧读（stale read）问题，即读操作发生于数据项更新之后，此时本应该读取到的是该数据项的最新值，但是却读到了旧值。产生该问题的原因是，分布式数据库系统没有一个统一的时钟，这会导致反序读取数据的情况出现。这种情况在单机系统中是不存在的。这里所说的不一致现象，以及与其类似的不一致性现象，在本书中统一称为数据读取序不符合数据生成序，简称分布式不一致[2]。

为了解决分布式不一致问题，诸多学者经过大量的研究提出了多种分布式一致性的概念，如线性一致性（linearizability，参见参考文献[183]）、顺序一致性（sequential consistency，参见参考文献[178]）、因果一致性（causal consistency，参见参考文献[184]），以及Google Spanner的外部一致性（external consistency，参见参考文献[3][65]）等。

分布式数据库系统需要解决分布式不一致问题，使观察者能读取到满足一致性的数据，以确保数据之间的逻辑一直是有序的。本节后续内容将针对这个问题展开讨论：首先讨论通用的分布式系统所面临的问题，然后讨论因数据异常引发的一致性问题，最后讨论与分布式数据库相关的其他问题。

1.1.1　分布式系统面临的问题

本节讨论分布式系统所面临的问题，这些问题是所有分布式系统都会面临的问题，分布式数据库系统也不例外。

这些问题主要包括两类：一是系统类问题，即系统中局部出现故障；二是因分布式系统缺乏统一时钟而带来的问题，本章称之为顺序问题。

1. 故障、失效

分布式系统的健壮性依赖于硬件设备和软件系统，如节点所依托的单机系统（硬件、软件）、网络设备等。对于硬件设备来说，存在损毁或不可用的情况；对于软件系统来说，存在故障和失效的情况。

故障可分为如下两种类型。

• 节点故障：在单机系统上出现的故障统称为节点故障。节点故障包括单机数据库系统需要处理的系统故障、介质故障，也包括因节点响应不及时致使系统期待的操作超时（延时现象发生）而引发的故障。
• 网络故障：网络中的部分节点由于网络出现问题而不能提供服务的情况，通常称为网络分区或网络断裂，在本书中则统一使用“网络故障”表述。

在分布式系统中，系统的某些部分可能会受到不可预知的破坏，这种情况被称为部分失效。部分失效往往是具有不确定性的。

当分布式系统发生网络故障或节点故障时，分布式系统的一致性和可用性就可能受到影响。具体的情况按数据的副本数目细分为两个大类。

• 单副本数据：单点故障发生，服务完全不可用。
• 多副本数据：具体分为以下两种情况。
• • 可用性受出现故障的节点个数影响，拥有相同副本的节点中超过半数的节点出现问题则副本间数据的一致性不能得到保证，此时此副本组内的数据一致性和副本组的可用性同时受到影响。
  • 每个不同的副本组只要不同副本组中发生故障的节点不超过半数则系统的可用性和数据的一致性可以到保障；否则，数据的一致性和分布式系统的可用性都要受到影响。

导致网络故障的因素主要如下。

• 物理设备故障：例如，网线掉落，以及网卡、交换机损毁等。
• 网络拥塞和排队：例如，多个不同节点同时将数据包发送到同一目的地，网络交换机需要对数据包进行排队并将它们逐个送入目标网络链路，而在繁忙的网络链路上，数据包需要等待一段时间才能获得一个插槽；再如，如果传入的数据太多，交换机队列被填满，数据包将被丢弃，因此需要重新发送数据包。

以上问题，会对分布式系统形成挑战，进而影响分布式系统的设计方案及其实现。

2. 顺序问题

顺序问题涉及如下两个层面。

• 分布式操作/事件排序：分布式系统中需要为操作/事件排序。这是站在系统外部的角度，面向分布式系统整体来确认系统内部发生的操作/事件之间的关系。这种关系涉及多种分布式一致性，进一步的讨论参见2.2节和2.3节。本节将讨论分布式操作/事件无序时可能引发的问题。有一篇文章[4]将分布式系统下的不一致问题总结为永久写（immortal write）、因果反转（causal reverse）、旧读（stale read）等几类。
• 并发事务排序问题：这个问题将在3.1节讨论，这里不再展开。

下面我们讨论分布式系统中对操作/事件进行排序时可能存在的问题。

（1）不可信的物理时钟

如图1-1所示，假定3台物理机器上各自存在一个进程，分别为P1、P2和P3，其时间戳值是不同的，每台机器上的时间戳值用逻辑时钟表示。假设P1所在的机器晶振6次为一个计时单位，P2所在的机器晶振8次为一个计时单位，P3所在的机器晶振10次为一个计时单位。在P1、P2和P3之间，发生了事件m1、m2、m3和m4。对于m3而言，其在P3上的发生时间值是60，而P2收到此事件的发生时间值却是56，这显然是不对的。所以分布式系统中如果用时间来表示事件之间的顺序，则需要一个统一的时间。解决的办法之一就是要根据事件之间的明确顺序调整时间戳（暗含了网络时钟校对的问题[5]）。如图1-1b所示，P2收到m3携带的时间值60后，与自己本地的时间值比较，取两者之间的最大者并加1（变为61）作为最终的时间值，这样可使得本地时间符合整个分布式系统要对事件顺序进行甄别的需求。抽象地看这种需求，就是识别发生事件的偏序关系或全序关系。关于偏序关系和全序关系的介绍参见1.3节。

用偏序、全序概念定义并发实体（如多进程、分布式系统），目的是解决分布式系统对物理时间的依赖。对于一个分布式系统来说，必须对事件进行排序，因此一些经典算法应运而生，但不同的算法有着不同的适用场景，当然也各自存在着不同的问题，第3章将对此进行详细讨论。

（2）日志问题

在分布式环境下，如果不能确定各个事件发生的顺序，可能会出现一些错误。例如，在分布式环境中，一个典型的问题是日志序的问题（对于分布式数据库，日志序类似分布式并发事务之间的顺序关系，对于并发事务来说，其需要一个可串行化的顺序）。

下面通过一个典型案例来解释分布式应用。假设网友那海蓝蓝要用出版社赠送的优惠码在某电子商务网站上买书。假设该电子商务网站的后台架构如下。

• 前端代理服务器：负责接收用户购书请求。
• 优惠码验证服务器：负责验证用户持有的优惠码的有效性。
• 日志服务器：专门用来存放日志。分布式系统中任何一个操作都会按照事件发生的先后顺序被记录到日志服务器中。

假设该电子商务网站的后台处理流程如下。

1）购书请求发给前端代理服务器，前端代理服务器会把购书的日志信息发送给日志服务器，并把优惠码发送给优惠码验证服务器。

2）优惠码验证服务器收到前端代理服务器发送过来的信息后，会把优惠码的日志信息发送给日志服务器。

3）按序存放日志项的日志服务器，应当先记录购书的日志信息，然后记录优惠码验证的日志信息。注意，这两条日志信息所反映的事件存在因果关系，是一对有因果序的事件。

对于日志顺序的确定，有如下两种方式。

• 在一个以流水方式记录操作事件的日志系统中，日志系统依赖于到达的每条日志的顺序，即先到达日志系统的日志项被认为是先发生的。而由于存在网络延迟、网络分区等因素，购书的日志信息可能晚于优惠码验证的日志信息到达日志服务器，如果将事件到达日志服务器的顺序作为事件发生的顺序就不能反映真实情况，就会出现“因果反转”的错误。
• 事件的顺序通常依靠物理时间来确定，即事件所在机器的物理时间代表了事件的发生时间，比较物理时间即可确认事件在日志系统的顺序。但是，如前所述，分布式系统中每个节点上的物理时间不可靠（可能优惠码验证服务器的物理时间早于前端代理服务器的物理时间），所以采用物理时间也不能解决事件排序问题。

那么，那有没有办法在不使用物理时间的情况下，给分布式环境下的所有事件排序呢？答案是有的。相关算法将在第3章探讨。

（3）时延产生的问题

时延通常是指一个报文或分组从一个网络的一端传送到另一端所需要的时间。它包括了发送时延、传播时延、处理时延、排队时延。但是，对于一个分布式系统，尤其是实时的、对时间敏感的系统来说，时延超出系统的期待时长，则用户的体验就会变差，所以时延成为一个衡量分布式系统可用性的指标。另外，分布式系统中存在时延现象，会带来一些新问题。如下为客户端因时延产生不一致的示例。

1）假设有两个节点NA和NB，NA的时间值较绝对时间偏移了100ms，NB的时间值为绝对时间值，此时假设绝对时间值为零。一个客户端（或称观察者）先后执行两个事务，先在NA上执行的事务T1，后在NB上执行事务T2，两个事务间隔10ms。忽略网络上传输命令的时间消耗。

2）在NA上执行T1，被写的数据项带有的时间标识为W(X,100)，而10ms后T2在NB上执行，被写的数据项带有的时间标识为W(Y,60)。

3）在客户端观察数据项X和Y发现，Y的时间戳是60，而X的时间戳是100，显然写Y的操作先于写X的操作。可这个结论明显和第一条中提及的执行顺序相悖。这就是时延问题导致观察者得到了错误的结论，这就是不一致问题。

1.1.2　数据库面临的一致性问题

数据库的事务处理技术中，有ACID四个特性。其中C是一致性，主要和数据异常相关，因此本节专门讨论数据异常相关的内容。数据异常问题在分布式数据库中也存在。

1. 数据异常研究历史

数据库层面的数据一致性（即ACID中的C）含义为：数据符合数据库的完整性约束，且当并发事务操作数据时数据需要从一个一致性状态变更为另外一个一致性状态，如果不满足一致性状态的变更，就会存在数据异常现象。

但是，数据库的数据异常现象一直没有被系统化地研究过，这主要表现在如下几个方面：一是不知道究竟有多少个数据异常；二是每个数据异常之间是否有关联关系；三是数据异常和一致性之间的关系是什么；四是数据异常和并发访问控制算法之间是怎样的关系。

从20世纪数据库技术开始发展算起，数据异常现象的研究历史主要分为四个阶段。

第一个阶段，ANSI SQL标准定义了少数几个数据异常。在数据库技术发展的早期，对各项技术的研究均不充分，这个时期，ANSI SQL标准（参见参考文献[197]）定义了4种读数据异常，分别为脏读、不可重复读、幻读、脏写。这四种数据异常是基于数据库理论和早期实践，在封锁并发访问控制机制下被定义的。ANSI SQL标准给出的定义依赖于封锁并发访问控制这一特定技术（并发访问控制技术还有其他种类，如基于时间戳排序的机制、MVCC技术等），所以有一定的局限性，且其没能给出更多的数据异常。这个阶段，人类对数据异常的研究尚处于早期阶段。

第二个阶段，重新定义数据异常。随着研究的深入，研究者通过工程实践[6]和研究发现了更多的数据异常。参考文献[113]认为，参考文献[197]基于封锁的并发访问控制协议来定义数据异常有失偏颇，使得数据异常和特定技术耦合，且不能表示更多数据异常，也不能表达数据异常的“强弱程度”。因此该参考文献定义了如表1-1所示的8种数据异常（按照异常特性发生的可能性定义的隔离类别），并给出每种数据异常的分析，指出用英语描述各种数据异常存在理解歧义的情况，同时给出精确的描述[7]。但是，该阶段也没有系统化地研究数据异常，比如没有从数量上研究有多少种数据异常，没有从本质角度探索、研究各种数据异常之间有什么关系。这个时期，可串行化技术已经成熟，从可串行化技术的角度看，那时的人们认为所有的数据异常已经能够被避免，似乎可串行化技术可以彻底解决数据一致性的问题，故而没有人有动力进一步系统化地研究数据异常了。

第三个阶段，有新的数据异常被定义，但是仅是零星地出现，没有大规模的新数据异常被定义。这个阶段已经进入20世纪90年代，数据异常研究以参考文献[226]为代表。参考文献[226]在参考文献[113]的基础上，融合带有谓词读（主要面对幻读），重新定义已知的各种数据异常和隔离级别，并指出新的定义适用于MVCC和OCC（Optimistic Concurrency Control，乐观并发访问控制算法）机制，如表1-2所示。另外，该参考文献从数据一致性的角度较为系统地研究了数据异常和一致性之间的关系。但是，该参考文献是从已知的数据异常切入的，且是基于参考文献[113，197]的，所以数据异常的覆盖范围没能有效扩展，参考文献中没有穷尽所有数据异常，仅“以点代面”式地从个例角度来介绍了全局。另外，该参考文献也缺乏对读偏序和写偏序的考虑与定义（故不适合用于MVCC技术）。

第四阶段，数据异常研究休眠期。参考文献[226]发布之后，尽管有一些其他文献讨论了一些新的数据异常，但都比较零散、不成体系，研究陷入停顿状态。如参考文献[150]以分布式事务型数据库系统为背景，提出Serial-Concurrent-Phenomenon（串并现象）和Cross-Phenomenon（交叉现象）两个分布式环境下的数据异常，但没有研究是否还有其他的分布式环境下的数据异常，也没有研究分布式数据库数据异常和单机数据库数据异常是否存在相同或不同之处。

这个世界上，究竟有多少种数据异常，那些已知的或未知的数据异常对现有的技术有着什么样的影响，这些基础问题尚没有答案。对数据异常进行体系化研究，是掌握并发访问控制算法与理解事务一致性的关键。期待将来有人能系统地讨论所有数据异常及其本质。

2. 单机数据异常

参考文献[21]总结了10种单机数据库系统的异常，如图1-2所示。这些数据异常都适用于单机系统，其中部分也适用于分布式系统。这里存在两种情况：一种是数据项没有被物理分布，那些数据异常在分布式系统中存在但不属于分布式系统特有，如脏读、不可重复读、幻读、脏写、丢失更新、游标丢失更新、Aborted Reads（中止读取）、Intermediate Reads（中间读取）等数据异常。这类数据异常本质上是单机系统的数据异常。另一种是数据项可被物理分布，那些数据异常在单机系统和分布式系统中都存在，如写偏序和读偏序数据异常，就非单机系统所独有。

1）脏读数据异常：是由当前事务读取了其他并发事务正在写的数据，并发事务之间缺乏隔离引发的。这个数据异常不仅在单机系统下存在，在分布式系统下也存在，这是因为单机系统的事务处理机制是分布式系统事务处理机制的基础（单机系统负责分布式事务的多个子事务的处理，且操作的数据项是同一个对象，其不可在分布式系统中被物理分布）。

2）不可重复读数据异常：当前事务读取了其他并发事务提交后写的数据，并发事务之间虽存在隔离，但隔离性不能影响与当前事务并发的其他事务提交的值被读到。尤其是采用了MVCC技术的数据库系统，当前事务不应因采用同一个快照而导致两次以上的读操作使用不同的快照（不同的快照意味着可以看到不同状态的数据）。这个数据异常不仅在单机系统下存在，在分布式系统下不存在，原因同脏读数据异常。

3）幻读数据异常：当前事务读取了其他事务提交后写的数据，其他事务与当前事务非并发事务，但是其操作的结果影响了当前事务的读操作中谓词的逻辑范围。这个数据异常不仅在单机系统下存在，在分布式系统下也存在，道理同上。

4）脏写数据异常：当前事务回滚触发事务的原子特性，使得与当前事务对应的数据项旧值被恢复，因此覆盖了其他事务提交后写的数据，其他事务与当前事务为并发事务。这个数据异常不仅在单机系统下存在，在分布式系统下也存在，道理同上。

5）丢失更新数据异常：因为当前事务提交而覆盖了其他事务写的数据，其他事务与当前事务为并发事务。这个数据异常不仅在单机系统下存在，在分布式系统下也存在，道理同上。

6）写偏序[8]数据异常：因为当前事务提交而覆盖了其他事务写的数据，其他事务与当前事务为并发事务，数据项上的并发操作发生在单机系统下。此类写偏序的场景可移植到分布式系统的不同节点上，因为被修改的数据项可进行物理分布。例如，表1-3所示的两个事务的写偏序数据异常。其中，Alice和Bob对应的数据可分布在两个物理节点中，致使在分布式数据库系统中如果是基于MVCC技术进行事务处理，则不仅需要处理单机系统下的写偏序数据异常，还需要处理分布式系统下的写偏序数据异常。

对表1-3说明如下。

• 表头这一行表示写偏序数据异常的两种情况，分别是由两个事务引发的数据异常和由三个事务引发的数据异常。
• 表格第一列为时间值列，表明时间值在逐渐增长，即t0<t1<t2<t3<t4<t5<t6<t7。
• 表中第一种数据异常分为两列，分别表示两个并发事务——T1和T2。而第二种数据异常，除了T1和T2两个事务外，还多了一个T3事务。
• 对于两个事务引发的数据异常（简单写偏序，Simple Write Skew）：按照时间顺序，T1在t0时刻读取了在打电话的值班医生人数，T2在t1时刻也读取了在打电话的值班医生人数。T1在t2时刻进行判断，如果在打电话的值班医生人数大于等于2人，则请Alice停止打电话。事务T2在t3时刻进行判断，如果在打电话的值班医生人数大于等于2人，则请Bob停止打电话。然后T1和T2分别提交。如果在这种并发的情况下，允许T1和T2都提交成功，则在t6时刻，Alice和Bob都会停止打电话。如果按串行执行事务，先执行T1后执行T2，则Alice会停止打电话但Bob不会停止，这与前一种情况的结果不同；如果先执行T2后执行T1，则Bob会停止打电话但Alice不会停止，这与前一种情况的结果也不同。这表明前一种并发执行是非序列化的，即T1、T2并发时违反了约束条件（约束条件为：如果同时打电话的人数大于等于2人，则请Alice或Bob中的一个人停止打电话，直到同时打电话的人数少于2人），发生写偏序数据异常。
• 对于三个事务引发的异常现象（批处理，Batch Processing）：后两个并发更新事务T3和T2是可串行化的，且不存在任何异常，但是一个只读事务T1出现在某个时刻却可能造成问题。所出现的问题是这样的，当T3提交时，T2处于活跃状态，这时T1启动，要读取T2和T3涉及的数据（current_batch和receipts），这时T1的快照包括了T3插入后的结果（因为T3已经提交）；但是，T2没有提交，它插入的数据不包含在T1的快照中。

7）读偏序数据异常：道理同写偏序数据异常，数据分布策略使得相关数据项物理分布，因而读偏序数据异常不仅发生在单机系统中，也发生在分布式系统中。当单机系统基于MVCC技术时，当前事务（表1-4中所示的事务T1）如果使用同一个快照读数据，则可以避免读偏序数据异常；当分布式系统基于MVCC技术时，需要使用全局的同一个快照来避免读偏序数据异常。

对表1-4说明如下。

• 表格头两行，表明读偏序异常现象是由两个事务引发的。
• 表格第一列，时间值列，表明时间值在逐渐增长，即t0<t1<t2<t3。
• 读偏序异常分为两列，表示有两个并发的事务——T1和T2。
• T1在t0时刻读出数据x，T2在t1时刻对数据x和y进行了修改并在t2时刻提交，T1在t3时刻读取y，此时y是被T2修改后的数据，已经不是t0时刻T1读取x时对应的y值，数据处于不一致状态（注意，此时不是x处于不一致状态，而是y处于不一致状态）。

8）游标丢失更新数据异常、Aborted Reads（中止读）数据异常、Intermediate Reads（中间读）数据异常：因操作同一个数据项而被限制在了单机系统下，数据项没有被物理分布，因此这些数据异常在分布式系统中存在。

3. 分布式数据异常

参考文献[150]介绍了两种分布式数据库环境下的数据异常。

（1）Serial-Concurrent-Phenomenon

按字面意思，Serial-Concurrent-Phenomenon是指分布式并发事务的子事务之间同时存在串行和并发的情况。如图1-3所示，这种情况发生时，node 1上两个子事务x、y并发执行，子事务y先开始写数据项的值为a1，子事务x只能读到数据项的旧值a0；而在node 2节点上，两个子事务是串行执行的，子事务y写的数据项b1因已提交，可以被子事务x读取到，所以子事务x读取到的是y提交后的值。矛盾的地方在于，node 1和node 2上的分布式事务x，分别读到另外一个事务y提交前和提交后的值，这个值处于不一致的状态。参考文献[128]把这样的数据异常命名为分布式读半已提交异常（Distributed Read Committed-Committing anomaly，DRCC）。

Serial-Concurrent-Phenomenon异常发生的条件：需要在各个子节点上支持MVCC算法，这样才能读到不同版本的数据，即事务x读到（a0，b1）这样一个不一致状态的数据。

在实际的账户转账业务中，如果并发访问控制算法处理不当，则会发生这种数据异常。如参考文献[186]中举的例子：分布式写事务正在执行从Na节点的账户X转账10元到Nb节点的账户Y。当Na节点完成提交，而Nb节点尚未提交，此时，一个读事务从Na节点读取到的是新值X-10，而从Nb节点读取到的是旧值Y，对照写事务之前的X+Y与读事务读到的X-10+Y，账户总账不平。

（2）Cross-Phenomenon

按字面意思，Cross-Phenomenon是指分布式并发的事务的子事务受到其他写事务的影响，致使并发事务之间有了“交叉关系”，如图1-4所示。

例如，两个分布式事务x和y并发执行，node 1上局部事务s将数据项的值修改为a1后，子事务y读数据项的值为a1。而在node 2节点上，与node 1相似，局部事务t修改了数据项的值为b1后，子事务x读数据项的值为b1。所以事务x读取到的是（a0，b1）这样一个不一致状态的数据。同理，事务y读取到的是（a1，b0）这样一个不一致状态的数据。

在实际的账户对账业务中，如果并发访问控制算法处理不当，则会发生这种数据异常。例如，事务x和y分别是两个对账人员，他们同时进行对账，但是他们的对账结果不同，这样的差异会令人费解。

参考文献[155，186]也给出了类似Serial-Concurrent-Phenomenon的数据异常，并给出解法。参考文献[186]称类似Serial-Concurrent-Phenomenon的数据异常为读半已提交数据异常。

分布式数据库系统中，是否还存在其他由分布式架构引发的数据异常，尚待继续探索。

4. 其他异常

参考文献[86]介绍了一种数据异常，如表1-5所示。这种异常假定背景是银行系统，X是取款账户，Y是存款账户，账户初始值都是0（可看作一个总账户下的两个虚拟子账户）。银行规则定义（约束）：取款时，如果发现X+Y余额小于等于0，则扣款1元。当事务T1存款和事务T2取款同时发生的时候，事务T3对账户的监控/查验同时进行（假设事务T3和事务T2被同一人从不同设备上登录），则在t5时刻，事务T3查验账户余额大于0，但之前发生的事务T2取款还没有完成，即t5时刻账户实际已经不用执行上述约束，但事务T2不知此情况，依旧用读取到的旧值作为约束条件进行判断，因此只能被多扣款1元，加上取款10元，共计从账户上扣款11元。

从理论上看，事务T2读写依赖于事务T1，事务T3读写依赖于事务T2，事务T1写读依赖于事务T3（反依赖），形式上3个事务构成了一个环，因此这样的并发调度是非可串行化调度。这种数据异常显然不符合客户利益，容易引发纠纷，故需要通过打破环来解决这样的数据异常问题。

在分布式系统下，账户X和账户Y可以分布在不同的物理节点上，因此在分布式系统中，此类数据异常也存在。参考文献[88]在快照隔离的背景下，也对该种数据异常进行了描述，并指出参考文献[113]提出的“只读事务不会和其他并发事务构成数据异常”的结论是不对的，典型案例如表1-5所示。

总之，对数据异常的研究，无论是在单机系统下还是在分布式系统下，目前都处于研究阶段，尚缺乏系统化的研究和相关成果。

1.1.3　分布式数据库系统面临的问题

单机数据库系统为了应对事务故障和对事务进行管理，专门提供了UNDO日志、回滚段等措施，目的就是实现事务的回滚；为了应对系统故障，采用了WAL技术做日志，目的是先于事务进行持久化存储；为了应对介质故障，专门提供了逻辑备份、物理备份等多种手段，目的是在数据层面、日志层面和物理数据块层面实现数据冗余存储。

相对于单机数据库系统而言，除了上述问题外，分布式数据库系统面临着更多的挑战。这些挑战源自分布式数据库系统的架构，其和单机数据库系统不同，因而在技术层面上存在差异。

1. 架构异常

架构异常是指用户因数据库的架构而产生的数据异常，严格地讲，这不属于数据库系统领域的数据异常。从用户的角度看，事务一直在执行中，但是读写数据时产生了类似前述的顺序问题、数据异常等，本书统称这种异常为架构异常。架构异常和分布式架构相关，分布式架构包括一主一备架构、一主多备架构、多主多备架构等。在分布式架构中，前端可能都有一个类似代理（proxy）的组件面向用户提供透明的高可用服务，代理组件屏蔽了后端多个单机系统故障，所以在用户看来，分布式架构上的所有操作都是在一个事务中进行的，而因架构引发的异常也是数据异常。

如下讨论一种已知的架构异常，该架构异常会导致读取到的数据不一致。我们以MySQL的主备架构Master-Slave[10]为例进行说明（其他数据库的同类架构存在类似隐患）。此类不一致是这样产生的。MySQL支持Master-Slave架构。假设在Master上执行事务T，此时先按条件“score>90”进行查询，发现没有符合条件的事务，故成功写入Binlog File的数据，假设其为95（事务提交），然后在复制的过程中宕机，导致复制失败。Master重启时，会直接对数据95进行提交操作，之后Master会将数据95异步复制到Slave。但是，此时原来的Slave可能已经切换为主机并开始提供服务，比如新事务写入数据98，而原来Master上的95没有被复制到新Master上，这就会造成两台MySQL主机的数据不一致。

如果在主备MySQL服务前端还有一个代理服务器，对用户而言，这会屏蔽后台的主备服务，用户就会认为“只有一个MySQL”提供服务，因此数据95丢失对用户而言是不可接受的。

还有一种情况，如果代理服务器在原始的Master宕机后没有结束用户的事务T，而是把事务T连接到原备机，并将原备机变更为新Master。这时，对于新Master而言，会发生两个事务，一个新事务T1在一定WHERE条件下写入98，另一个是继续执行的原事务T，若此时原事务T再次发起读操作（逻辑上还在同一个事务内），就会发现自己写过的数据95消失了，这对于用户而言是不可接受的。从分布式一致性的角度看，这违背了“Read-your-writes”（读你所写）原则。从事务的角度看，可能出现“幻读”，即再次按条件“score>90”查询，额外读到事务T1写入的98，所以出现了事务的数据异常。

与上述相似，官方对MySQL上出现Master-Slave之间数据不一致的情况，也进行了描述[11]。

如图1-5所示，如果把数据扩展到多副本，把读操作扩展到允许从任何副本读取数据，把写操作扩展到允许向任何副本写入数据，如果是去中心化的架构（即没有单一的全局事务管理机制）且发生了网络分区或延，则在事务一致性视角、分布式一致性视角下去观察数据的读或写操作，会发现存在更为复杂的问题。

Distributed algorithms and protocols[12]讨论了一种在多副本情况下，副本间数据同步与数据可见性的异常情况，其所用的示例如图1-5所示：足球世界杯比赛结果出炉，比赛结果经过Leader节点记录到数据库。事实结果是德国赢得了世界杯冠军。但是，数据从Leader节点同步到两个不同的Follower节点的时候，Alice和Bob同处一室，从不同的Follower节点上查询世界杯的比赛消息，结果Alice得知德国夺冠，而Bob却得到比赛还没有结束的消息。二人得到了不同的消息，产生了不一致。这也是分布式架构下因多副本支持Follower读带来的不一致的问题。

2. 分布式一致性和事务一致性

本节旨在引出一些问题，读者如果不了解基础的技术背景知识，或者暂不能理解下面提及的技术概念，那么无须纠结具体技术，只需了解这里提出的问题即可。为了帮助大家充分理解分布式系统中存在的问题，我们不妨做一个类比。

若是世界上只有一个人，那么这个世界的关系是非常简单的，但是一旦有多个人，“社会”就会形成。其中，社会关系指的就是人与人之间建立的关系，这种关系会随着人的数量的增加而不断复杂化。这种复杂的社会关系与数据库结合到一起得到的就是分布式数据库系统，社会中的人就相当于分布式数据库系统中的一个物理节点或者一个物理节点中的一份数据副本。图1-6以一个NewSQL系统的架构[13]为例描述分布式数据库中存在的多个问题。

因为分布式数据库要存储海量数据，要对数据分而治之，所以引入了数据分片的概念。从逻辑的角度看，每个节点的数据都是一个或多个数据分片，但是数据库要满足“高可用、高可靠”以及在线实时提供服务的特性，因此每个数据分片就有了多个副本。数据多副本使得分布式数据库的“一致性”问题变得更为复杂。

我们从读和写两个不同的角度来感性了解一下分布式数据库中存在哪些不一致的问题。

首先，图1-6所示的分布式数据库系统存在4个数据分片——A、B、C、D，每个分片又存在3个副本，且每个分片的3个副本中有一个是Leader，另外两个是Follower（比如Raft分布式协议中的Leader和Follower）。

其次，对于写操作，图1-6所示有如下两种情况。

1）写单个数据分片——W1：在这种情况下，一个事务不能针对多个节点进行操作，所以这样的事务是典型的单节点事务，类似于单机数据库系统中的事务。写单个数据分片可以由单个节点上的事务处理机制来确保其具有ACID特性。为了实现写单个数据分片的数据一致性，可只使用数据库系统中的并发访问控制技术，如2PL（Two-phase Locking，两阶段封锁）、TO（Timestamp Ordering，时间戳排序）、MVCC（Multi Version Concurrency Control，多版本并发控制）等。

2）写多个数据分片——W2：通过一个事务写多个数据分片，这就是典型的分布式事务了，此时需要借助诸如分布式并发访问控制等技术来保证分布式事务的一致性，需要借助2PC（Two-phase Commit，两阶段提交）技术保证跨节点写操作的原子性。另外，如果需要实现强一致性（详见5.6节），还需要考虑在分布式数据库范围内，确保ACID中的C和CAP[14]中的C的强一致性相结合（即可串行化和线性一致性、顺序一致性的结合）。诸如Spanner等很多数据库系统，都使用线性一致性、SS2PL（Strong Strict 2PL）技术和2PC技术来实现分布式写事务的强一致性。CockroachDB、Percolator等分布式数据库则使用了OCC类的技术做并发访问控制来确保事务一致性（可串行化），并使用2PC来确保分布式提交的原子性，但它们没有实现强一致性，其中CockroachDB只实现了顺序可串行化。保证分布式事务一致性的技术还有很多，第4章将详细讨论。

对于写多个数据分片的情况来说，因为在每个数据分片内部存在多个副本，所以如何保证副本之间的数据一致性，也是一个典型的分布式系统一致性问题（第2章会详细讨论分布式系统的一致性问题，第3章会详细讨论多副本在共识算法加持下的一致性问题），著名的Paxos、Raft等协议就是用来解决分布式系统的多副本共识问题的。此种情况下，通常没有写操作会发生在图1-6所示的A的Leader和B的Follower这样的组合中。

如果一个系统支持多写操作，则多写会同时发生在多个数据分片的Leader上。

对于读操作，图1-6所示也有如下两种情况。

1）读单个数据分片——R1：如果一个事务只涉及单个节点，则这个事务读取操作的数据一致性一定能保障（通过节点上的事务机制来保障）。如果涉及多个节点，那么此时的R1就会被分为R11和R12两种读取方式。

• R11方式用于读取Leader：因为进行写操作时首先写的是Leader，所以如果写事务已经提交，那么一定能够保证R11读取的数据是已经提交了的最新数据。如果写事务没有提交，那么此时Leader上若是采用MVCC技术，则R11读取的会是一个旧数据，这样的读取机制可以保证R11读数据的一致性；Leader上若是采用封锁并发访问控制机制，则读操作会被阻塞直至写事务提交，因而在这种机制下R11读取的是提交后的值，从而保证读数据的一致性，换句话说，这种情况下，保证数据一致性依赖的是单节点上的事务并发访问控制机制。同时，这也意味着一个分布式数据库系统中单个节点的事务处理机制应该具备完备的事务处理功能。
• R12的方式用于读取Follower：读取Follower时又分为如下两种情况。
• • 在一个分片内部，主副本和从副本（即Leader和Follower）之间是强同步的（Leader向所有Follower同步数据并在应用成功之后向客户端返回结果）。这种情况下不管是读Leader还是读Follower，数据一定是完全相同的，读取的数据一定是一致的。
  • Leader和Follower之间是弱同步的（Leader没有等所有Follower同步数据并应用成功之后，就向客户端返回结果），如采用多数派协议就可实现弱同步。此时Leader和Follower之间会存在写数据延时，即从Follower上读取到的可能是一个旧数据，但是因为事务的读操作只涉及一个节点，所以也不会产生读操作数据不一致的问题。这就如同MySQL的主备复制系统中备机可以提供只读服务一样。

2）读多个数据分片——R2：注意这种情况下的读操作会跨多个分片/节点，如果事务处理机制不妥当，会产生不一致的问题。而这样的不一致问题，既可能是事务的不一致，也可能是分布式系统的不一致。下面还是以图1-6所示为例进行介绍。假设只读取A、B两个数据分片，这时有如下4种情况。

• 读A的Leader和B的Leader，这种情况简称全L问题。
• • 事务的一致性：如果存在全局的事务管理器，那么此时读多个数据分片的操作如同在单机系统进行数据的读操作，通过封锁并发访问控制协议或者MVCC（全局快照点）等技术，可以确保读操作过程中不发生数据异常。因为其他事务的写操作会为本事务的读操作带来数据不一致的问题，所以通过全局的并发访问控制协议（如全局封锁并发访问控制协议等技术），能够避免出现事务层面的数据不一致问题。但是，如果没有全局的并发访问控制协调者，则容易出现跨节点的数据异常，所以需要由特定的并发访问控制协议加以控制。
  • 分布式系统的一致性：这类问题只在“读A的Leader和B的Leader”这种结构中存在，分布式数据库需要通过实现“强一致性”来规避因分布和并发带来的分布式事务型数据系统的一致性问题。具体可能出现的问题会在第2章介绍。
• 读A的Leader和B的Follower，这种情况简称LF问题。B的Leader和Follower之间存在时延，即传输存在时延，从而带来主备复制之间的数据不一致问题。如果支持“读A的Leader和B的Follower”这样的方式，需要确保所读取的节点（A的Leader节点、B的Follower节点）上存在共同的事务状态。
• 读A的Follower和B的Leader，这种情况简称FL问题。问题的分析和解决方法同上。
• 读A的Follower和B的Follower，这种情况简称全F问题。问题的分析和解决方法同上。

若是在读数据时，同时存在事务的一致性和分布式系统的一致性问题，那么就需要通过强一致性来解决。

总体来说，事务的一致性是因并发的事务间并发访问（读写、写读、写写冲突）同一个数据项造成的，而分布式一致性是因多个节点分散、节点使用各自的时钟，以及没有对各个节点上发生的操作进行排序造成的。

---

[1]CAP指的是一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）。

[2]一致性问题最早源于对Share Memory（共享存储）多读多写的讨论，参见参考文献[26，28，261，284，285，288，289]等。本书讨论分布式数据系统，因此把问题定义为分布式系统下的问题，但原理与Share Memory多读多写问题的原理相同。

[3]事务ACID中的一致性和分布式系统的线性一致性结合。ACID，即原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）。

[4]参见http://dbmsmusings.blogspot.com/2019/08/an-explanation-of-difference-between.html。

[5]时间同步问题涉及网络时间同步技术NTP（Network Time Protocol，网络时间同步协议）/PTP（Precision Time Protocol，精确时间同步协议）、单向授时技术、双向授时技术（北斗单向卫星授时精度100ns，双向卫星授时精度20ns）。

[6]如读偏序（read skew）、写偏序（write skew）数据异常，都是在实践中出现了数据不一致现象，后经深入研究才发现的。

[7]原文称精确和不精确的两种解释为strict and broad interpretations。

[8]写偏序，英文表述为Write Skew，此处的偏序和后续描述的顺序中的偏序无关，为更好表达其含义，写偏序数据异常表述为写偏斜数据异常更合适。

[9]示例源自论文Dan R. K. Ports和Kevin Grittner所写的Serializable Snapshot Isolation in PostgreSQL。

[10]2020年，MySQL官方把Master-Slave（主-从）改名为Source-Replica（源-副本）。

[11]更多信息可参考：http://bugs.mysql.com/bug.php?id=80395和https://mariadb.atlassian.net/browse/MDEV-162。

[12]参见https://www.cl.cam.ac.uk/teaching/0809/DistSys/3-algs.pdf。

[13]数据库系统的架构演进经历了3个阶段：一是单机系统，二是主-从架构系统，三是纯粹的分布式系统（如NewSQL架构系统）。其中主-从架构系统是为了实现数据库系统的高可用性而生的，因而早期的研究多集中在复制数据库（Replicated Database）（即主-从架构）方向，这个阶段一主多读架构成为流行架构。该架构应对了读多写少的需求（读多写少符合互联网的需求），这使得该架构在互联网早期大行其道。更多研究详见参考文献[59，93，151，182，185，263，289] 等。NewSQL架构则以去中心化架构为典型代表，如Google IS Spanner系统，见参考文献[65，66]。

[14]CAP是指一致性（Consistency，C）、可用性（Availability，A）、分区容错性（Partition Tolerance，P）。