第三代分布式数据库（4）——为什么要100%保证数据的正确性？（上）
数据库范围内，ACID中的C和I，是两个非常重要的特性，I表示并发执行的事务在执行过程中互不影响，即互相处于“隔离”状态，C要求并发执行的事务最终结果是正确的。
尽管C和I非常重要，但遗憾的是，传统的数据库知识从未把这他们的概念清晰表达，而是存在二义性（完整性约束和ACID之C的二义差异），并且缺乏用严谨的数学方式加以定义。
另外，更重要的是：没有直接把前述的数据异常和一致性的概念关联起来。在大众的头脑中，似乎数据异常和一致性有着很强的关系，但是没有从数学的角度把他们之间的关系完全掲示出来。
除了事务处理技术领域，谈及事务一致性外，还有其他领域，都在提及一致，如操作系统领域会涉及cache一致性、大型分布式缓冲软件系统会涉及缓冲一致性、CAP中的C也是在谈及一致性，这些不同领域的一致性有什么不同？他们之间的本质是否存在某种必然的联系？
事实上，一致领域存在诸多的问题，他们可以用“一致性24字问题”加以概括：
1. 范围不清：是从整体上描述数据正确性问题存在边界不清晰的问题，如数据库的一致性和Cache一致性、分布式一致性等之间的边界模糊，这使得各个领域似乎都在解决一致性问题，但都各自为战，不能形成有效的统一的体系系统化地解决数据正确性问题。
2. 定义不明：指每个领域内的一致性的定义是不明确的，缺乏形式化的表达，即缺乏科学的定义方式，这表明我们并没有深入理解其本质问题。
3. 多意：在数据库中，一致性的含义有不同的内容，如完整性约束表达的一致性，有ACID的C表达的因并发操作同一对象导致的一致性，因此一致性这个词是存在多种解释的，这会使得学习数据库的人困惑不解。
4. 多词：在数据库中，一致性和数据异常和数据正确性等，似乎存在着某种关系，但是却用了不同的词表达，且词与词之间的含义、关系是不明确的，这也会使得学习数据库的人困惑不解。根据文献[6]可推知，有冲突环图一定不一致性（有环是充分条件非必要条件）；但不能知道不一致一定是有环（有三个数据异常游离于冲突环外，分别是：Dirty Read、Dirty Write、Intermediate Read）；
5. 理论有缺：事务一致性依赖的可串行化理论不完备；可串行化不能消除所有的数据异常；冲突可串行化也不能消除所有的数据异常（根据文献[6]需要处理如Dirty Read等特例）。
6. 扩展无法：事务一致性和分布式一致性的关系不清晰，导致单机系统的数据正确性无法扩展到分布式系统中（目前只能依据经验解决而不能有明确的定义和规则）：在分布式数据库系统中，CAP的C和ACID的C之间的关系是什么？“严格可串行化”是最严格的一致性语义，这个概念是结合了可串行化和线性一致性的语义而成的，适用于分布式事务型数据库系统；但分布式系统是否只存在“严格可串行化”这一种一致性？
7. 系统难评：无论是单机还是分布式数据库，都缺乏一致性检测体系。Oracle数据库有可串行化隔离级别，但是在运行了若干年之后，被发现其所谓的可串行化隔离级别不能消除Write Skew数据异常，因此是一个假的数据异常；而其他的数据库系统，号称实现了可串行化，但是没有一个验证标准，可把数据库作为一个黑盒子进行一致性验证；数据库厂商提供不了数据正确性的评测方法，理论界也不能提供（参考“第三代分布式数据库（3）——一致性八仙图”关于“一致性八仙图”和Jepsen的讨论）。
相关概念混淆：无论是学术界还是工程界，因为一致性缺乏明确的定义，因此不同人对该概念有着不同的理解。有些词经常混淆在一起，如事务范围内容和ACID相关的一致性，分布式系统下和线性一致性、因果一致性等相关的分布式一致性，强一致性（多指多副本复制时被复制的数据与原始数据自己的一致性），最终一致性等。
一言以蔽之：乱！
让我们沿着时间的轨迹来梳理人类对于数据异常的认知过程，感悟技术的进步与发展过程。
数据异常，至今尚没有明确的定义。业界对于数据异常，只有一个个具体的数据异常名称，每个数据异常对应一个形式化表达式。即过往对于数据异常的研究，止于具体的案例（如脏写、脏读、不可重复读、幻读等数据异常），且不能让人明白各种数据异常之间的关系。在事务处理领域，尚存在一些基本问题，如“数据异常究竟有多少个？数据异常之间的关系是什么？”是不为人所知晓的。
本节讨论数据异常的研究历史和其中存在的一些问题。在事务处理技术的发展历史上，不同人定义过不同的数据异常。
1. ANSI/ISO-SQL标准定义的数据异常
ANSI/ISO-SQL标准[7]定义了四种数据异常，分别是：脏写（Dirty Write）、脏读（Dirty Read）、不可重复读（Non-repeatable Read）和幻读（/Phantom）数据异常。
这四种数据异常，后文会另行介绍，在此不再赘述。
2. Jim Gray等定义的数据异常
数据异常，不只是ANSI/ISO-SQL标准所定义的四种，还有更多数据异常。Jim Gray等人在参考文献[6]中定义了八种数据异常，除了ANSI-SQL标准定义的四种外，新增加了丢失更新（Lost Update）、游标丢失更新（Cursor Lost Update）、读偏序（Read Skew）和写偏序（Write Skew）数据异常。
该参考文献给出的新的数据异常的形式化定义如表1所示。其中，丢失更新的定义存在难以理解之处。例如：
H1 = R1[x]...W2[x]...W1[x]...C1 （丢失更新异常的定义）
H2 = R1[x=100] R2[x=100] W2[x=120] C2 W1[x=130] C1（丢失更新示例）
H1是丢失更新数据异常的形式化定义，但该定义中的“W2[x]...W1[x]”构成一个脏写异常，因此该形式化定义和脏写异常的定义冲突，不能判断该定义究竟应属于哪种数据异常。该文献对丢失更新举例如H2，其中“W2[x=120] C2 W1[x=130]”中存在有“C2”这使得该示例与脏写异常不存在冲突之处，因此其定义应该更新为H3。
H3 = R1[x]...W2[x] ...C2...W1[x]...C1 （丢失更新异常的新定义）
游标丢失更新数据异常的定义类似丢失更新，出现在支持“游标（Cursor）”功能的数据库系统中，如DB2、Informix、MySQL、PostgreSQL等。
读偏序数据异常，其定义为H4。对于事务T1和T2，是两个事务作用在两个变量上，按照冲突可串行化理论，在变量x上形成RW冲突，在变量y上形成WR冲突。但是，为什么在“W2[y]...C2...R1[y]”中需要有“C2”存在呢？如果不采用读已提交规则，则完全可以存在H5的方式。所以，是否存在一种可能，使得H4和H5，都是读偏序异常呢？
H4 = R1[x]...W2[x]...W2[y]...C2...R1[y]...（C1 or A1）（读偏序异常的定义）
H5 = R1[x]...W2[x]...W2[y]...R1[y]...（C1 or A1）（读偏序异常的另外一种形式）
写偏序数据异常的定义为H6。对于事务T1和T2，是两个事务作用在两个变量上，按照冲突可串行化理论，在变量x上形成RW冲突，在变量y上形成RW冲突，即该异常有两个RW冲突这点不同于读偏序异常的一个RW一个WR冲突。而该定义中“C1 and C2”位于表达式的最后，但是，H7中只是把“C1”提前到“W2[x]”，这样对于事务T2而言，无任何影响，所以是否我们可以认为，H6存在H7这样的等价变形形式？即是不是H6并没有把写偏序的定义完整表达？
H6 = R1[x]...R2[y]...W1[y]...W2[x]...（C1 and C2 occur）（写偏序异常的定义）
H7 = R1[x]...R2[y]...W1[y]...C1...W2[x]..C2（写偏序异常的定义另外一种形式）
表1 《A Critique of ANSI/ISO-SQL Isolation Levels》定义的新的数据异常
异常名称 | 形式化定义 |
丢失更新 | R1[x]...W2[x]...W1[x]...C1 |
游标丢失更新 | RC1[x]...W2[x]...W1[x]...C1 |
读偏序 | R1[x]...W2[x]...W2[y]...C2...R1[y]...（C1 or A1） |
写偏序 | R1[x]...R2[y]...W1[y]...W2[x]...（C1 and C2 occur） |
3. 已知的数据异常与问题思考
前两节讨论了不同组织或学者发现并定义了不同个数的数据异常，ANSI/ISO-SQL标准定义了四种而Jim Gray等定义了八种，自然而然的，我们会产生这样一个疑问：究竟还有没有新的数据异常？
如表2，汇总了19种数据异常。该表的“异常名称”列还给出报告该异常的文献和文献发表的年份，可以看出，从1992年到2019年近三十年的时间里，不断有新的数据异常被报告。由此，我们会产生一系列疑问：究竟有多少种数据异常？数据异常之间，有什么必然联系？数据异常的命名，是不是也是有规律可循的？新的数据异常，应该在哪个隔离级别下被消除（即数据异常和隔离级别的关系，究竟是什么）？
表2中，“Cross-Phenomenon”数据异常，是四个事务作用在两个变量上构成的数据异常，这样的数据异常，为什么是“数据异常”？为什么该异常和其他的数据异常有不同？不同之处又在哪里？还有，上一节我们讨论了写偏序异常，而表2给出了一个称为“谓词写偏序（Predicate-Based Write Skew）”的数据异常，这两类数据异常看起来有些相似之处，都是两个事务在两个变量上存在两个RW冲突关系，但是后者的读操作带有谓词，那么，是否每一个带有读操作的数据异常都对应有一个谓词类数据异常？如果是这样，为什么到目前为止，只报告有幻读和谓词写偏序数据异常这两个谓词类的数据异常，而没有报告出更多的谓词类数据异常？
另外，表2中，第十个和第十一数据异常，表达式相同，但却是被不同的参考文献在不同的场景下报告得出：在2014参考文献[3]和2017年参考文献[1]报告的“fractured reads”是一个不区分分布式环境的数据异常，在2014年参考文献[2]报告的“Serial-Concurrent-Phenomenon”是一个分布式环境下的数据异常。根据这样的情况，我们可以思考，为什么同样的数据异常会被命名不同且数据异常？数据异常和分布式环境有着什么样的关系？
再如，表2中，大部分数据异常都是涉及单个变量的数据异常，而 “Read Skew”却有两个变量，这是为什么？根据这样的情况，我们可以思考，是否会有三个变量或更多变量的数据异常存在？数据异常和变量个数之间有着什么样的关系？
表2表明数据异常有很多个，他们都是一个个具体的案例，我们可以思考：如何对这些数据异常分类？是否可以从数据异常整体的角度，给数据异常一个简洁而统一的科学定义？
前述这些问题，表明数据异常的研究，尚不充分。这就需要我们对数据异常开展系统化的研究工作。参考文献[5]给出了如何对数据异常开展体系化研究的工作。
表2 已知数据异常汇总表[3]
编号 | 异常名称 | 形式化定义（源自对应的文献） |
1 | Dirty Write， 1992， 1995 | W1[x]...W2[x]...（（C1 or A1） and （C2 or A2） in any order） |
2 | Lost Update， 1995 | R1[x]...W2[x]...W1[x]...C1 |
3 | Dirty Read， 1992， 1995 | W1[x]...R2[x]...（A1 and C2 in either order） |
4 | Aborted Reads， 2000， 2015 | W1[x1：i]...R2[x1：i]...（A1 and C2 in any order） |
5 | Fuzzy OR Non-Repeatable Read， 1992 | R1[x]...W2[x]...C2...R1[x]...C1 |
6 | Phantom， 1992 | R1[P]...W2[y in P]...C2...R1[P]...C1 |
7 | Intermediate Reads， 2000， 2015 | W1[x1：i]...R2[x1：i]...W1[x1：j]...C2 |
8 | Read Skew， 1995 | R1[x]...W2[x]...W2[y]...C2...R1[y]...（C1 or A1） |
9 | 未命名的异常， 2000 | R3[y] R1[x] W1[x] R1[y] W1[y] C1 R2[x] W2[x] R2[z] W2[z] C2 R3[z] C3 |
10 | fractured reads， 2014， 2017 | R1[x0]...W2[x1]...W2[y1]...C2...R1[y1] |
11 | Serial-Concurrent-Phenomenon， 2014 | R1[x0]...W2[x1]...W2[y1]...C2...R1[y1] |
12 | Cross-Phenomenon， 2014 | R1[x0]...R2[y0]...W3[x1]...C3...W4[y1] C4...R2[x1]...R1[y1] |
13 | long fork anomaly， 2017 | R4[x0]...W1[x1]...R3[y0]...R3[x1]...W2[y1]...R4[y1] |
14 | causality violation anomaly， 2017 | R3[x0]...W1[x1]...C1...R2[x1]...W2[y1]...C2...R3[y1] |
15 | A read-only transaction anomaly， 1982，[8] 2004 | R2[x0，0] R2[y0，0] R1[y0，0] W1[y1，20] C1 R3[x0，0] R3[y1，20] C3 W2[x2，-11] C2 |
16 | Write Skew， 1995 | R1[x]...R2[y]...W1[y]...W2[x]...（C1 and C2 occur） |
17 | Predicate-Based Write Skew， 2005 | R1[{x0 in P}]...R2[{y0 in P}]...W1[{y1 in P}]...C1...W2[{x1 in P}] |
18 | 读半已提交数据异常(分布式系统)， 2019 | R1[x]...W2[x]...W2[y]...C2...R1[y]...（C1 or A1） |
19 | Prefix violation 2015 | R1[x,1]...W1[x,2]...R2[y,1]...W2[y,2]...R3[x,2]...R3[y,1]...R4[y,2]...R4[x,1] |
4. 为什么会产生数据异常？
可串行化理论源自串行化的思路，直观地看，如果所有的事务都串行执行，则数据的一致性不会被破坏，即在单个事务的操作下，事务使得数据能够从一个初始的合法状态变迁为事务结束后的另一个合法状态。因此不会有数据异常发生。
而一个事务对数据的操作，抽象后无非是两种，读操作和写操作。如果有两个或两个以上的事务并发地操作相同的数据项，则存在四种组合情况，分别是读读、读写、写读和写写。其中，只有读读不会改变数据的状态，而其他三种组合都会改变数据的状态，因此存在出现数据异常的可能。但是，这并不意味着数据异常一定会出现。
例如，表2中的脏写定义如H8。该异常的定义中包括了事务的提交或回滚的状态，且“any order”表明T1和T2的提交或回滚的状态可以交换位置，因此存在表3中的八种情况。该表采用数据状态变迁方法，观察不同操作对数据状态的变迁变化，来观察数据一致性的保持情况，其中事务执行过程中允许数据处于不一致性的状态，但事务结束必须使得数据处于一致性状态。
H8 = W1[x]...W2[x]...（（C1 or A1） and （C2 or A2） in any order）
表3中编号1到6的存在数据不一致的情况，但编号7和编号8实际上不存在数据不一致，但是“WW”却被定义为脏写，这不合理。或者说，为什么没有文献讨论脏写因何会被这样定义？作者的理解是，对于编号7和编号8的情况，因为都涉及了回滚操作，而这样的回滚操作是浪费计算资源的操作，与其允许其发生而浪费计算资源，倒不如禁止“WW”发生而节省计算资源为好，因此“WW”被直接定义为了数据异常。但是这样的定义方式，不利于理解“什么是数据异常”。
因此，我们提出疑问：究竟是什么原因使得数据异常产生？前述这些问题，不由得促使我们深思。
表3 “W1[x]...W2[x]”的事务状态展开的八种情况表
编号 | 状态组合 | 分析（x0表示初始状态，x1表示W1执行后的状态，x2表示W2执行后的状态）。本分析遵循严格一致性，即每个事务提交成功，则所写过的数据项的值一定能够被读取到 |
1 | C1C2 | C1完成后T1事务所写的数据x1应该可见，但W1所写的值x1却被W2覆盖为x2而不能读取到，因此C1后C2前存在数据不一致性状态，即存在脏写数据异常 |
2 | C1A2 | 同上 |
3 | A1C2 | A1执行使得数据被恢复为W1所写之前的前像即x1，此前像x1覆盖了W2所写的值x2，致使C2执行完成后依然不能读取到W2所写的值x2，因此存在数据不一致性状态，即存在脏写数据异常 |
4 | A1A2 | A1执行使得数据被恢复为W1所写之前的前像即x1，此前像x1覆盖了W2所写的值x2，而A2执行完成后数据被恢复为值x1而不是x0，因此存在数据不一致性状态，即存在脏写数据异常 |
5 | C2C1 | C1完成后却读不到T1所写的x1，因此存在数据不一致性状态，即存在脏写数据异常 |
6 | C2A1 | A1完成后数据被恢复为T1所写的前像x0而覆盖了x2，因此存在数据不一致性状态，即存在脏写数据异常 |
7 | A2C1 | A2把T2的写结果撤销，即数据恢复为W1所写的状态，因此C1提交后能够读取到W1所写的值，因此不存在数据异常 |
8 | A2A1 | A2把T2的写结果撤销，即数据恢复为W1所写的状态，而A1回滚，使得数据恢复到W1所写之前的状态，因此不存在数据异常 |
接下来，我们将继续谈“为什么要100%保证数据正确性？”，如果您知道原因，欢迎来讨论，讨论特别热烈者，将赠送出一本《分布式数据库原理、架构和实践》作者签名版。
[1] Andrea Cerone， Alexey Gotsman， and Hongseok Yang. Algebraic laws for weak consistency. International Conference on Concurrency Theory (CONCUR 2017)， LIPICS 85， pages 26：1-26：18， 2017.
[2] Lamport L， Shostak R， Pease M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS)， 1982，4(3)： 382-401
[3] P. Bailis， A. Fekete， J. M. Hellerstein， A. Ghodsi， and I. Stoica， “Scalable atomic visibility with ramp transactions，” in SIGMOD， 2014， pp. 27–38.
[4] Hal Berenson， Philip A. Bernstein， Jim Gray， Jim Melton， Elizabeth J. O'Neil， Patrick E. O'Neil： A Critique of ANSI/ISO-SQL Isolation Levels. SIGMOD Conference 1995： 1-10
[5] 李海翔，李晓燕，刘畅，杜小勇，卢卫，潘安群.数据库管理系统中数据异常体系化定义与分类.软件学报，2022，33(3)：0
[6] A. Adya， B. Liskov， and P. O’Neil. Generalized isolation level definitions. In Proceedings of the 16th International Conference on Data Engineering， ICDE ’00， pages 67–78， Washington， DC， USA， 2000. IEEE Computer Society.
[7] ANSI X3.135-1992, American National Standard for Information Systems – Database Language – SQL, Nov 1992.