数据库并发控制理论
本文主要系统性的讲了并发控制相关的理论，但不会过多涉及 MySQL 等数据库的实现细节，避免局限于这些数据库的具体实现。
概述
并发控制技术，是数据库事务实现的基石，在确保事务隔离性正确的前提下，尽可能提高事务的并发度。
广义上看，并发控制属于事务调度，调度的种类非常多，串行化、可串行化、不可恢复性等等；在这里，我们更多从狭义上来讲调度，指可串行化的调度。
事务的正确性主要体现在 ACID 特性上，而并发控制主要涉及其中的 I 即 Isolation，即事务隔离性，避免脏读，幻读，写偏斜等读写异常。且满足事务的可恢复性属性。
为了提高事务的并发度，则 ISO 定义了几种不同的隔离级别，让数据库在不同隔离级别下提供不同的正确性保证，在并发度和正确性之间取舍。
本文主要描述关系数据库的并发控制理论，不会过多涉及 MySQL 等数据库的实现细节，避免局限于这些数据库的具体实现。
理论
实现方向
并发控制技术，从检测是否存在冲突的角度看，包括乐观的，悲观的，处于两者之间的半乐观方法
乐观（optimistic concurrency control，OCC）：从一开始，每一项操作都允许进行，但在事务提交的时刻，进行隔离性和完整性约束的检查，如果有违反则事务被回滚
悲观（pessimistic concurrency control，PCC）：从一开始，即检查每一项操作是否会违反隔离性和完整性约束，如果可能违反，则阻塞这样的操作
从控制冲突的时机看，包括基于锁的，基于时间的，基于提交顺序的，基于串行化图测试检验的各种方法，还有基于多版本并发控制的技术。
串行化的含义是完全限制并发；可串行化是在能保证一致性的情况下，允许某些并发的操作被执行；以提高数据库整体的运行效率。数据确保事务特性的前提下，还要在不同的调度下能满足事务的属性：可串行化(serializability)，可恢复性(recoverability)。然而不是所有的调度都是满足事务属性的，有的调度可以牺牲可串行化或者可恢复性，以获得更高的并发度。
可串行化
Serial schedule
要想事务不互相影响，那么最简单的方式就是让事务的执行是串行的，不交叉执行，称这种执行调度为 serial schedule，串行化调度（也有翻译称序列化调度的）。
然而多个事务在这种调度下是无法并发执行的，那么执行效率就非常低下。数据库要能够并发执行，就不能使用串行化的调度策略，但是又要保证性能和隔离性，也就是等价于 serial schedule，那么我们称这种调度策略为 serializable schedule，可串行化调度。
那么，如何理解"等价于"呢？也就是事务执行的正确性？
数据库系统中，将"等价"分为三种
final state equivalence 终态等价
view equivalence 视图等价
conflict equivalence 冲突等价
所以按照这三种等价于 serial schedule 的调度也分为三种：
final state serializability 终态串行化
view serializability 视图串行化
conflict serializability 冲突串行化
终态可串行化
终态可串行化，final state serializability，又称为 result equivalence serializability。
如果两个调度的执行结果一样，则认为两个调度是 final state equivalent 的，如果调度的执行结果和 serial schedule 一样，则是 final state serializability 的。就像两个函数，输入的参数一样，如果返回的结果也一样的话，则两者是 final state equivalent 的。其忽略了如何实现函数的内部结构，把函数当成黑盒了。
那如何判断两个调度是否为 final state equivalent 的呢？把两个调度各自执行一遍？显然这是不可能的，也有研究将调度操作转换成有向图，但要确保正确性就需要将调度的所有操作（读、写和控制流）都加入到有向图中，那和执行一遍调度几乎没有什么区别。
所以 final state serializability 对于现实工程实现并没有什么指导意义。
冲突可串行化
冲突可串行化， conflict serializability
冲突行为
当下面三种条件都满足时，我们将两个操作视为冲突
两个操作属于不同的事务
两个操作访问和处理的数据集有重叠
至少有一个操作的是写操作
从定义中，我们可以将不同事务并发操作同一数据产生的冲突分为三类
R-W 冲突：事务 Ti 读取了数据 O 但还没提交，事务 Tj 修改了 O，（造成不可重复读）
W-R 冲突：事务 Ti 修改了数据 O 但还没提交，事务 Tj 读取了 O，（造成读未提交）
W-W 冲突：事务 Ti 修改了数据 O 但还没提交，事务 Tj 也修改了 O，（造成丢失更新）
conflict equivalence
如果某个调度能通过交换非冲突操作来将调度转换成 serial schedule，则两者是 conflict equivalent 的，则称这种调度为 conflict serializability。
例如：事务的执行
可能的 serial schedules：
现在我们通过交换非冲突操作来达到 conflict serializability
T1 的 R(B), W(B) 和 T2 的 R(A), W(A)是非冲突的，所以可以将他们进行交换。
通过两次交换，可以将 S1 转换成 T1->T2 的 serial schedule，所以 S1 是 conflict serializability。
再看看不是 conflict serializability 的例子
可以看出，T1 对 A 和 B 的操作，都没有办法交换到 T2 的前面或后面。所以 S2 不是 conflict serializability。
优先图检测冲突可串行化
然而对两三个事务进行判断 conflict serializability 相对还比较简单，但是对很多事务要进行判断却是非常困难的，那要如何检测呢？
我们以事务为单位，使用事务之间的冲突行为定义事务执行的先后顺序。
如 Ti 的 Ri(A)与 Tj 的 Wj(A)冲突，而Ri(A)<Wj(A)，所以 Ti 就要先于 Tj 执行，所以就可以使用优先图来检测冲突可串行化。而如果优先图(precedence graph)没有环，则说明调度是冲突可串行化的。因为如果 Ti 需要在 Tj 前执行，又有 Tj 需要在 Ti 前执行，显然这是矛盾的，所以存在环则不是冲突可串行化的。
可以看出，T1 先写了 A，T2 后读了 A，所以 wr 冲突，T1 优先于 T2；而 T2 读取了 B，后面 T1 又修改了 B，那么 rw 冲突，T2 优先于 T1。所以形成了环，说明不是冲突可串行化的。
实际上，这只是一种研究的理论方向，从现有主流并发控制技术来看，基于锁的并发控制实现，将冲突操作通过锁的方式来互斥，就这天然的阻止了冲突操作中环的形成。
视图可串行化
视图可串行化, view serializability。
《concurrency control and recovery in database systems》定义两个 schedule S1 和 S2 是 view-equivalent 的，只有满足：
S1 和 S2 的 transactions 相同。如果在 S1 中，T1 最先读取 A，则在 S2 中，也必须是 T1 最先读取 A。
读写依赖：对于 S1 和 S2 中的 Ti 和 Tj，如果在 S1 中，Oi 从 Oj 中读取，那么在 S2 中，Oi 也从 Oj 中读取。Tj 先写了 O，而 Ti 后读取 O，
Wj(O) < Ri(O)最后写(final write)：如果在 S1 中 Ti 最后写入 O，那么 S2 中也是 Ti 最后写入 O。
读写
两种调度对同一对象的读写顺序必须一致，其实也就是其冲突操作是要一致的，和 conflict equivelance 一样。
如上面两个调度就不是 view-equivalent 的，S1 中，T3 读取 A 的值是由 T2 更新的，而 S2 中 T3 读取的 A 是由 T1 更新了。
最后写
如果 S1 中事务 Ti 最后修改了数据 O，则在 S2 最后修改数据 O 的也是事务 Ti。
如上，S1 和 S2 不是 view-equivalence 的，因为 S1 最后写 A 的是 T1，而 S2 中最后写 A 的是 T2。
从上面可以看出，view-equivalence 和 conflict-equivalence 不一样的是，view-equivalence 增加了 final write 的条件，这样相对于 conflict-equivalence，反而约束宽松了。
如下调度
由于此调度的优先图存在环(T1 的 R(A)或 W(A)与 W(A)也无法交换)，所以调度不是 conflict serializability 的。
但 T3 的 W(A)在最后写（盲写 blind write），所以和 serial schedule(T1->T2->T3) 是 view-equivalent 的。
可以看出，优先图存在一定的局限性，虽然调度不是 conflict serializability 的，却可能是 view serializability 的，其实 conflict serializability 是 view serializability 的一个子集。但现在仍没有一种高效的方法来判断调度是否为 view serializability 的，所以 view serializability 没有实用价值。
可恢复性
可恢复性的定义如下：
Recoverability means that committed transactions have not read data written by aborted transactions（whose effects do not exist in the resulting database states）。
即：已经提交的事务没有读过被中止的事务写的数据。否则脏读异常发生，导致数据不一致。
其实可恢复性对事务回滚进行了定义，所以和可串行性一起保证事务正确执行
可串行性：当所有事务提交时，调度执行的顺序和串行执行的结果一样
可恢复性：当有事务回滚时，不会存在由于脏读导致数据不一致。
下面调度，是可串行化的，T1 在 T2 前执行，但 T2 先提交，所以不满足可恢复性。可以想象如果发生崩溃，T2 的提交记录到达磁盘，而 T1 没有到达，那么恢复后，T2 都处于提交状态，而 T1 会回滚。C 指 Commit。
级联回滚
由于允许脏读（读取还未提交事务修改的数据），所以如果一个更新某些数据的事务回滚，则其他读取了这些数据的事务也会导致回滚。
如下，T2 读取了 T1 更新的值，T3 读取了 T2 更新的值，那么 T1 回滚，为了避免数据不一致，所以 T2 和 T3 必须回滚。A 指 Abort。
所以级联回滚对性能影响很大，应该尽量避免。
避免级联回滚
cascadeless schedule，又称为 avoiding cascading aborts (ACA)，避免级联回滚。
其定义如下：
A strategy to prevent cascading aborts is to disallow a transaction from reading uncommitted changes from another transaction in the same schedule.
既然脏读导致了级联回滚，那么不允许脏读就可以避免级联回滚了。也就是只允许读取已经提交事务修改的数据。
如以下调度，必须等到 T1 完成提交，T2 才能读取 A
严格性
严格性 strictness
A schedule is strict - has the strictness property - if for any two transactions T1, T2, if a write operation of T1 precedes a conflicting operation of T2 (either read or write), then the commit or abort event of T1 also precedes that conflicting operation of T2.
避免级联回滚虽然不允许脏读，但是忽略了一个问题，就是丢失更新。不允许读取未提交事务修改的数据，没有不允许修改未提交事务修改的数据。所以严格性就对此做了限制，即不允许读取或修改未提交事务修改过的数据。
如以下调度就是 ACA 的，但不是 strictness 的
为什么不允许写未提交事务修改的数据呢？
我们可以想象以下场景：
T1 abort 时，将 y 从 11 改成 1(称为 before image 前像)，但当 T2 abort 时，T2 其执行 W2(y, 22)的前像是 11，T2 如果简单回滚到前像，则会出错。这样就增加了回滚复杂度。
属性关系
我们引用维基百科的一张图来描述属性之间的关系
从串行化的角度看，严格程度的次序(前松后紧)：
从可恢复性的角度看，严格程度的次序：
基于锁的并发控制
基于锁的并发控制相关知识有很多，如
锁的粒度，tuple，page，table 等等
锁的类型：排他锁，共享锁，意向锁
锁的合并与升级
锁的管理：死锁检测、预防等
不打算在本文中来聊这些技术实现，因为涉及到的内容实在太多了，如死锁预防，相关手段就非常多，每一种都是一个细化的研究方向。
本文只关注如何通过锁来实现可串行化的并发控制，至于其他工程优化手段等，以后再写专门的文章来讨论吧。
如果锁是普通的加锁与解锁，我们看看会有什么问题
如果是序列化执行，不管 T1 先执行还是 T2 先执行，那么 T2 得出的A+B结果都是 40。
而此调度会造成 T2 的结果是 30，显然不是可序列化的。
2PL
2PL，two-phase locking，两阶段封锁协议。
为了确保可串行化，所以引入两阶段锁。
将事务的获取锁和释放锁分成了增长(growing)和缩减(shrinking)两个不同的阶段
增长阶段：每个事务请求所有需要的锁资源，此阶段不允许释放任何锁
缩减阶段：事务进入释放锁的阶段，不允许再对资源进行加锁
2PL 是能够保证冲突可串行化的，所以能满足可串行化。可以看到下面调度的事务执行，结果和串行化执行结果是一样的。
但是如果 T1 的回滚了，则导致 T2 也必须回滚，不然就产生脏读。
所以如上所说，虽然保证了可串行化，但不满足可恢复性，故而不能避免级联回滚。
S2PL
为了避免上面的问题，所以很多现代数据库使用 S2PL 或 SS2PL 来实现并发控制。
strict two-phase locking 严格两阶段封锁。
除了封锁满足两阶段封锁条件之外，还要求持有的排它锁必须在事务提交后才能释放。这个要求保证未提交事务所写的任何数据在该事务提交之前均以排它方式加锁，从而能够避免级联回滚。
遵循严格封锁调度有两个特性
符合 ACA 的也符合 strictness，因为由于锁的存在无法读取或修改其他未提交事务修改的值
是可串行化的
可以看到下面的例子，只有当 T1 Commit 后，才会释放 B 的写锁，所以 T2 要等到 T1 Commit 后，才能获取到 B 的读锁；假设 T1 回滚，也不会造成 T2 回滚，这样就避免了级联回滚了。
SS2PL
强严格两阶段锁，strong strict two-phase locking，也称为 rigorous 2PL。
除了封锁满足两阶段之外，还要求事务提交之前不得释放任何锁。
SS2PL 降低了并发度，但带来的好处是
不像 S2PL 需要跟踪每个事务的锁的阶段，整个事务提交前都是两阶段增长阶段，提交后才是缩减阶段，这样实现起来就很简单了
且保证了提交顺序，CO(commitment ordering)，以后再聊 CO
隔离级别
我们再看看如何基于锁并发控制实现不同的隔离级别
S 表示操作前加锁，操作后释放锁
C 表示操作前加锁，提交后释放锁
通过这些锁的策略，则可以通过锁来实现各种隔离级别。
例如读已提交：写操作在提交后再释放，这样就阻塞读请求了，从而避免读到未提交的数据。
多版本并发控制
multi-version concurrency control (MVCC) 是一个比较宽泛的概念，不仅仅指并发控制。
核心思想是对每个对象的修改都会产生一个新的版本，可以读取任意存在的版本，对所有对象进行版本的管理控制。
这样的好处是修改操作和读历史版本的读操作各自不影响对方，可以并行操作。
对于数据库操作冲突来说，读写冲突（快照）是可以通过 MVCC 机制来避免的，而写写冲突则可以通过加锁的方式来避免并发修改，从而保证正确性。
设计 MVCC 的几个主要的考虑方向:
版本存储：version storage
垃圾回收：garbage collection
索引管理：index management
版本存储
数据库中更新一条记录，就会对这条记录产生一个新的版本，通过指针将不同的版本记录链接起来，组成版本链。这样，数据库就可以通过版本链找到不同版本的记录。
版本的组织方式有以下几种
append-only storage 追加方式：新版本直接追加写入到同一个表空间中
time-travel storage 时间线方式：老版本单独存储在一个表空间中
delta storage 增量存储方式：只存储修改部分的数据，而不是整个元组
元组（tuple）：指的是数据库存储引擎中的一条有版本信息的记录。
追加方式
append-only storage
版本链的指向顺序有两种方式
老版本的指针指向新版本记录 oldest-to-newest(O2N)
新版本的指针指向老版本记录 newest-to-oldest(N2O)
O2N
生成新版本时，将老版本的指针指向新版本，所以访问这个新记录，需要遍历老记录，这样就会产生读放大，且生成新纪录时需要更新老记录的指针。
N2O
生成新版本时，将新版本的指针指向老版本，所以访问某个版本的记录时，需要从新记录开始遍历到指定版本。
图来源于论文：《An Empirical Evaluation of In-Memory Multi-Version Concurrency Control》
时间线方式
time-travel storage
将老版本直接 copy 到 time-travel 表，新版本写入主表，新版本指向老版本。
索引指向主表即可，通过主表中最新版本的指针去遍历老版本。
time-travel 也是 append-only 的存储方式，只是新老版本在不同的表空间中。这种方式有利于回收老版本记录，但同时产生了写放大。
增量存储方式
delta storage
只存储修改部分的数据，而不是整个 tuple。由于不需要 copy 整个 tuple，所以更快速。而读取的时候需要组装数据，所以更慢。
垃圾回收
当所有运行中的事务都不会再读取到一条记录的某个版本时，则这个版本是可回收的。
如所有运行的事务中，最小可见的版本号是 11，如果一条记录的最新版本号是 6，那么这条记录的小于 6 的版本都是可以回收的。
一般有两种回收方式
tuple-level 元组级别：以元组为粒度进行回收过期记录。
transaction-level 事务级别：以事务为粒度回收过期记录。
元组级别的回收
两种回收方式
后台清理的方式 background vacuuming：后台线程定期进行清理
合作式回收 cooperative cleaning：工作线程来清理
后台清理
Vacuum 线程扫描到版本比他 TS 小的 tuple，vacuum 的 TS 应该选择比现在 running 最小的 transactions 还小的 TS。
TS 为自增版本号，每个事务启动时分配一个此 TS 作为其可见性判断。
合作式回收
工作线程执行事务操作时，扫描到过期不可见的版本记录则直接删除，这样就不再需要单独的后台线程来定期清理了，但如果某条记录一直没有被事务扫描到，则永远无法被清理。
混合式
使用合作式回收，然而定期再用后台清理方式，来避免有的数据没有被读取则无法回收的问题。
事务级别的回收
事务维护一个读集合和写集合，分别存储其读到的记录和创建的记录，当事务结束后，再从两个集合中找出对于运行中事务不再可见的记录，将他们删除掉。
索引管理
索引管理是指数据库中的索引，如何指向实际的主表数据？
有两种方式
逻辑指针 logical pointer
物理指针 physical pointer
逻辑指针
索引指向一个"中间指针"即逻辑指针，这个中间指针再指向主表存储的元组的位置(某个页面的某个位置)，如图所示。
这种方式对于写比较友好，例如，如果更新某条记录，则这条记录相关的所有索引都不需要更新，只需要更新"中间指针"指向新的元组的位置即可。
但是存在读放大问题，所有索引访问数据都需要先访问"中间指针"，再跳转到实际数据存储位置。
MySQL InnoDB 就是使用逻辑指针的方式，所有索引都指向主键，通过主键再去访问真实的数据。
物理指针
所有索引都指向主表存储的元组的真实位置。
这种方式和逻辑指针刚好相反，对于读比较友好，索引指向元组的实际位置，直接就可以访问到元组，无需通过中间指针进行跳转。
但不利于写，如果更新了某条记录的位置，则相关的索引都需要更新，造成写放大。
PostgreSQL 使用这种方式，所以更新记录时成本较高。
隔离级别
MVCC 不是单独可以使用的技术，需要配合其他并发控制技术一起来实现不同的隔离级别，如 S2PL。
那我们来看看 MVCC+S2PL 如何实现不同的隔离级别。
事务号
数据有多个版本由不同的版本号区分，这种版本号就是一个事务号，是一个单调递增的数字。
将事务分成两种类型：只读事务和更新事务。
如果是只读事务：则在事务开始时获取一个事务号，读取数据时，就读取比这个事务号小的版本号的数据。这种读取是不用加锁的。
如果是更新事务：
读操作：获取共享锁，读取最新版本的值
写操作：获取排它锁，为写的数据创建一个新版本，版本号为无穷大(版本号类型的最大值，当然实际数据库很少这样实现的，考虑到崩溃恢复和持久化，实际数据库实现的版本控制和可见性判断远比这复杂，属于工程上的优化，目的是一样的)，这样其他事务根据其版本号就无法读取到这条记录，提交时，重新获取事务号，将此写入的数据的版本号改为此事务的事务号+1。
所以 MVCC 天然就不会读取到未提交数据。
读已提交
每次读都重新获取一次快照，读取最新已提交数据。
可重复读
第一次执行读操作时生成快照，后面的读都以此快照进行读取，这样每次读取的版本都是一样的。
如果是SELECT ... FOR UPDATE或 DML 语句，需要用排它锁锁住需要读写操作的数据直到数据结束。
可串行化
可串行化用 SS2PL 来实现。
这样，通过 MVCC+S2PL 实现了数据库的不同隔离级别。
基于可串行化快照隔离的并发控制
快照
快照 snapshot
数据库中数据和状态的某一版本（可以认为只要哪怕有一个数据修改，数据库就会产生一个新版本）。
快照隔离
快照隔离 snapshot isolation
snapshot isolation is a guarantee that all reads made in a transaction will see a consistent snapshot of the database (in practice it reads the last committed values that existed at the time it started), and the transaction itself will successfully commit only if no updates it has made conflict with any concurrent updates made since that snapshot.
事务像是被"隔离"起来了，对同一数据的操作互相不影响；快照隔离只是一种技术，而不是隔离级别，
快照隔离（后面同一写成 SI）技术是 MVCC 技术的一种实现，所以使用 SI 的读操作，读到的同一份快照的数据一定是一样的。SI 读取的是数据的某一快照，所以不会发生读写冲突或写读冲突。这样就避免了幻读异常，不可重复读，脏读，但是 SI 无法阻止写偏序，所以 SI 并不是可串行化的。
由于 SI 是 MVCC 的一种实现，所以避免异常的实现和前面的 MVCC 的一样，但是没有锁的保护，所以会产生写偏斜异常。
对于 SI 来说，T1 和 T2 读取的都是某一个快照 v11 的值，所以if (x+y)>0就会成立，T1 将 x 改成 0，T2 将 y 改成 0，这样就造成 x+y=0 了，违反了约束。在串行调度下，不管 T1 先执行还是 T2 先执行，都不会出现这种结果。这种异常被称为写偏序(write skew)。
为了解决 write skew 问题，所以就出现了可序列化的快照隔离技术 serializable snapshot isolation(SSI)。
可序列化的快照隔离技术
serializable snapshot isolation(SSI)
既然 write skew 是读写冲突的一种类型，那么避免或者检测读写冲突就可以解决 write skew 问题。
理论基础
三种依赖关系
《Generialized isolation level definitions》定义三种依赖关系
写读依赖(write-depends)：T1--wr-->T2，T1 写数据项 X 的一个版本，T2 读取这个版本，意味着 T1 先于 T2 执行
写写依赖(read-depends)：T1--ww-->T2，T1 写 X 的一个版本，T2 再写一个新版本覆盖 T1 写的版本，意味着 T1 需要先于 T2 执行
读写依赖(anti-depends)：rw-dependency 或 rw-conflicts，Ti 先读了 X 的一个版本 Xi，而 Tj 修改了 X 值，产生一个新版本 Xj，所以是先读后写，属于 wr 的反向依赖
检测写偏序的理论基础的两篇论文，说明读写冲突行为之间的逻辑关系
《weak consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions》：定义了读写依赖，通过读写依赖表明不可串行化必须是多版本可串行化图(MVSG multivertion serialization graphc)存在两条读写依赖边形成的环。
《Making snapshot isolation serializable》：定义读写依赖的扩展形式，表明写偏序发生时，两条读写依赖的边是相邻的。
DSG direct serialization graph
在并发事务之间，根据事务之间的三种关系，画出一幅有向事务关系图，表明事务操作数据时的前后关系，读写操作对新版本值的依赖关系。
事务 T1, T2, T3 执行如下
DSG 图如下
《marking snapshot isolation serializable》中证明了，如果调度不是可序列化的，那么 DSG 必然存在由两条连续的 rw-dependency 边形成的环，且这两边边在两个并发事务中。
Suppose H is a multiversion history produced under Snapshot Isolation that is not serializable. Then there is at least one cycle in the serialization graph DSG(H), and we claim that in every cycle there are three consecutive transactions Ti.1, Ti..2, Ti.3 (where it is possible that Ti.1 and Ti.3 are the same transaction) such that Ti.1 and Ti.2 are concurrent, with an edge Ti.1 --> Ti.2, and Ti.2 and Ti.3 are concurrent with an edge Ti.2 --> Ti.3.
any cycle must have two rw-dependency edges that occur consecutively, and further, each of these edges is between two concurrent transactions.
dangerous structures
然而要找出 DSG 中是否有环，成本是相当高的，所以论文定义了存在一种危险结构(dangerous structures)，只要在 SDG(static dependency graph)图中存在这种危险结构，就会在 DSG 图中可能存在环，危险结构是出现环的必要非充分条件。同时得出结论，一个 SI 调度的 SDA 不存在这种危险结构，这个调度就是可序列化的 SI。
《marking snapshot isolation serializable》对 dangerous structure 的定义如下
Definition 3.5 (Dangerous Structures). We say that the static dependency graph SDG(A) has a dangerous structure if it contains nodes P, Q and R (some of which may not be distinct) such that:(a) There is a vulnerable anti-dependency edge from R to P(b) There is a vulnerable anti-dependency edge from P to Q(c) Either Q = R or else there is a path in the graph from Q to R; that is, (Q, R) is in the reflexive transitive closure of the edge relationship.
其使用 SDG 图的概念，为了更容易理解，我们直接看《serializable isolation for snapshot database》，论文对这种结论进行了补充，且给出了 SSI 相关算法的实现。
将 rw 分成两种情况
读操作读取的不是最新的值：产生 rw 依赖。读取的是某快照，所以互相不阻塞。
读操作在写操作之前发生：可能产生 rw 依赖。读取数据需要加 SIREAD 锁，写时就会检查是否有 SIREAD 锁，有则代表有 rw 依赖。
DSG 中(MVSG)，存在一个 pivot 节点（事务），这个节点有两条边（入边，出边），如果存在这个节点，则存在 dangerous structure，则可能导致形成环。只要回滚此节点，则会打破环的形成，就可以确保调度是可串行化的。 这样虽然导致了回滚率增加，但是不需要再找出环，只需找出此 pivot 节点，从而效率大大提高了。
所以这种危险结构是形成环的必要非充分条件。
如下图，Tpivot 存在入边和出边，所以产生了危险结构，就可能形成环(如果图中点虚线存在)，这个时候，我们只需要回滚 Tpivot 就破坏了这种结构。
SSI
SSI 在 SI 的基础上，增加一些其他判断和操作来实现 SSI 技术。
数据库需要为每个事务维护两个 boolean 值，
T.inConflict ： 此值指示是否存在 rw-dependency 从其他事务指向事务 T
T.outConflict ： 指示是否存在 rw-dependency 从事务 T 指向其他事务
如果 T.inConflict 和 T.outConflict 都是 true，既有入边也有出边，则代表此调度可能是非可串行化的。
Write lock
写锁避免了事务并发执行的写写冲突，遵循 SS2PL 协议。
SIREAD lock
事务读取了某个版本的数据后，则会在此数据上加上 SIREAD 锁。SIREAD 锁不阻塞写锁，仅仅是一种标志，代表访问此数据。
事务开始
事务开始时，我们将事务的 inConflict 和 outConflict 都设置为 false。
读操作
T 不应该读到（在 T 开始时还没有完成提交的事务）但在 T 结束前已经提交的事务才会生成新的 T 读不到的版本。
写操作
提交
事务提交后他的 SIREAD 不释放，是因为提交后事务也会影响其他正在运行的事务。直到所有这些事务都提交后才可以释放。
所以，可以看出 SSI 是一种乐观的实现方式，通过事务执行操作时来检测事务之间的依赖关系，如果读写不构成危险结构，则读写可以并发执行，如果构成，则以回滚 pivot 事务为代价来避免读写冲突。这样就实现了可串行化。
隔离级别
在 RC 和 RR 隔离级别下，SSI 和 SS2PL+MVCC 实现几乎一样。但在可串行化下，SSI 本质上是使用 MVCC+行级锁+SIREAD 来实现可串行化的。
SS2PL+MVCC vs SSI
MVCC 技术避免了读写冲突，让读读，读写（快照读）可以并发的执行，但仅限制于只读事务与其他事务可以并发；而非快照读写冲突是无法避免的，这个时候就需要 S2PL 来避免冲突，保证事务的可串行化。
所以很多数据库就是通过这种 MVCC+S2PL 技术来实现其事务的可串行化。例如 MySQL 的 InnoDB。然而这种方式是悲观的，有的读写冲突是不会造成异常的，有的却会引起写偏斜等异常，S2PL 无法进行区分，所以就降低了事务的并发执行。
而 PostgreSQL 则是通过 SSI 来实现其事务的可串行化执行，SSI 是乐观的实现方式，读写操作时进行检测，如果存在危险结构则可能造成异常，回滚其 pivot 事务即可，这种方式可以允许一定的读写并发执行，所以相对于 MVCC+S2PL 的方式性能更为优异。
例如，对于下面的两个事务，
T1 读取了 x，而 T2 修改了 x，所以T1 -- rw --> T2，有读写依赖，
而 T2 读取了 z，如果没有其他并发事务修改 z，则 T2 不会与其他事务产生 rw 依赖，则 T2 不会 pivot 事务，对于这种情况，SSI 是运行并发执行的，而 S2PL 由于读写冲突，是不允许并发执行的。所以，从这点看，SSI 的并发度更高。
而论文对 SI、SS2PL 和 SSI 的并发度测试结果，也证明了 SSI 的性能远优异于 S2PL。
最后
并发控制的实现技术非常多，还有基于时间戳的并发控制，基于有效性检查的并发控制等等，但是大多数 RDBMS 还是基于上面两种技术，也是相对较为主流的实现方案。
本文主要系统性的讲了并发控制相关的理论，然而数据库在工程上的实现是非常复杂的，如 PostgreSQL 就对锁做了很多优化，还有 SSI 等等。
我阅读了很多并发控制和事务相关的论文、书籍和资料，不断思考和总结写出本文，希望能给大家带来帮助。如有错误之处，欢迎指正。
主要阅读参考的资料如下：
《concurrency control and recovery in database systems》
《generalized isolation level definitions》
《making snapshot isolation serializable》
《serializable Isolation for Snapshot Databases》
《数据库事务处理的艺术》
《postgresql 技术内幕：事务处理深度探索》
《database system implementation》
《database system concepts》
版权声明: 本文为 InfoQ 作者【楚】的原创文章。
原文链接:【http://xie.infoq.cn/article/8a9f7aac17fa7a4d286d9a999】。文章转载请联系作者。
还未添加个人签名 2018.06.12 加入
还未添加个人简介
评论