浅析分布式系统之体系结构 - 事务与隔离级别（多对象、多操作）下篇
中间隔离级别（Intermediate Isolation Levels）
对于实现隔离级别 PL-2（读、写操作均不能保证足够的一致性（例如：反向直接依赖相关的一致性））数据存储系统相对相对实现隔离级别 PL-3（读、写操作都可以保证足够的一致性）系统来说可以实现的一致性的保证有较大的差距，但是其性能和后者相比有极大的提高。为了弥补这两者之间的差距，提出了一类隔离程度位于这两着之间的隔离级别即中间隔离级别(Intermediate Isolation Levels)，从而取得两者之间的平衡。
隔离级别 PL-2+（Isolation Level PL-2+）
这里情况在实践中很常见，例如：电子商务中的库存情况和订单状态，银行账户信息的查询等等。很多时候，开发人员开开发应用程序的时候使用 ASNI-92 的 read commited（读已提交）作为事务的隔离级别来保证系统在这些场景下的一致性。然而，考虑如下事务记录历史：
图 14 上面的事务历史记录无法保证业务约束 x + y >0 ，因为事务 T1 执行后 x+y=-110
图 15 上面的事务历史记录的产生的 DSG（H）中的循序并不局限于两个事务，而是是在在 3 个事务之间产生的。
通过上面的例子可以发现隔离级别 PL-2 并不足以完整实现系统所需的一致性，因此需要对于隔离级别 PL-2 进行加强。隔离级别 PL-2+是对于隔离级别 PL-2 最弱的一类加强。隔离级别 PL-2+适用于数据存储仅需保证当客户端来读取相应的结果的时候其观察到的数据存储系统状态是一致的，且无需隔离级别 PL-3 的场景。假设当应用程序定义的完整约束条件是正确的则在其相关事务提交后数据存储系统的状态仍会保持一致。而且，当应用程序含有更新操作的事务 T1 对于数据存储系统状态的观察符合正确的完整性约束并且这个事务能够单独运行直至完成，那么可以假设即使它改变了已提交的数据存储系统状态，整个系统包含应用程序状态的完整性约束在事务 Ti 提交后仍会继续保持。在这样的系统当中为了避免上面的场景，系统需要实现基础一致性。基础一致性这个概念由 Weihl 提出。如果某个事务 Tj 其读操作得到的结果乃是由多个已经提交事务组成的子集的进行一系列执行后得到结果，且这些事务中的每一个更新事务其并发执行得到的事务历史记录的步骤与按照顺序执行得到事务历史记录中的步骤相同一致，则可以认为系统实现了基础一致性。按照的基础一致定义，若按照序列执行的多个已经提交的更新事务的结果总是保证一致性的，则可以保证某个事务 Tj 对于数据存储系统的各次观察都是一致的。事务 Tj 不能从任意的事务组成的集合当中读取结果，它必须从已经组成一个执行序列的事务集合当中读取结果，且它必须看到这个序列每一步对应的每一个已经提交的事务的更新带来的变化。实现基础一致性的关键在于让系统中的事务避免对于其他与之有依赖关系的事务更新察觉的丢失（Missing Transaction Updates）。事务更新察觉的丢失（Missing Transaction Updates）：即某一个事务 Tj 对于其所读取的某个数据对象的版本 xj 由于事务 Tj 的这个读操作完成之后执行的另外一个事务 Tk 的对于同一个数据对象的写入操作变成了过时版本（版本 xj << xk）这个情况未能察觉。
无依赖丢失（No-Depend-Misses）
通过对于事务之间关系进行分析便可以发现，只要保证无依赖丢失（No-Depend-Misses），即事务 Tj 对于事务 Tk 有任何正向依赖关系，事务 Tj 能够避免对于事务 Ti 更新察觉的丢失，便可以避免事务更新察觉的丢失。而 PL-3 隔离级别能够保证无依赖丢失（包含正向，反向）【Chan，Gray】，所以通过将其限制的相应条件进行放宽，即在隔离级别 PL-2+在排除场景 G1 的基础上加入了排除 G1-single 情景，从而达到相同的效果。
排斥场景：G1，G1-single
G1-single
当基于事务历史记录中产生的 DSG(H)图中包含一个含有反向依赖关系的有向环，且这个环有且只有一个反向依赖有向边（Single Anti-dependency Cycles），则这个事务历史记录包含场景 G1-single。例如前文在隔离级别 PL-3 中描述过的事务历史记录 H0（图 11）便是包含了场景 G1-single，故而不符合隔离级别 PL-2+。通过排除 G-single，系统可以保证无依赖丢失（排除了所有反向依赖的情况）。
隔离级别 PL-2+可以排除幻读（幻读包含一个反向依赖），但是无法完全避免由于更新数据而引起的数据存储状态的不一致，例如常见的 write-skew 的问题（见下面的事务历史记录）便无法排除。
图 16 由于反向依赖的循环问题造成的 write-skew 的问题，由多于一个反向依赖有向边组成环，直接反向依赖的各自的写操作更改了对应的不同的数据对象，说明 PL-2+无需从一个完整的包含所有事物的改变的状态中读取数据，而是允许从一个包含所有过去已经观察到的事物（各个事物观察可能不同，所以状态也可能不同）的更新的状态中去读取数据。
客户端角度: 对于应用程序来说隔离级别 PL-2+十分适用于只读事务以及程序员能够对于会对数据存储系统一致性产生影响的写操作进行控制的场景（例如，读多写少的电商产品展示和低频交易场景）。由于 PL-2+需要事务了解所有其他事务对于系统产生的改变，从这个角度来说 PL-2+维护了系统的因果一致性。
隔离级别 PL-CS（稳定游标（Isolation Level Cursor Stability））
游标类似于指针是一种用于引用特定的数据对象的技术，它可以指定查询结果集中的任何位置，然后允许用户对指定位置的数据进行处理。大部分商业化数据存储系统（数据库）都会提供通过使用游标来保证一致性解决方案这便是著名的稳定游标（Cursor Stability）[Dat90]。稳定游标利用游标来引用事务正在访问的一个特定（例如当前）数据对象，一个事务中可以有多个游标，当一个事务 Ti 通过一个游标访问了一个数据对象，则可以无需立即释放读锁（如同 REPEATABLE READ）而是保持这个读锁直到这个游标被移除或者事务进行提交。当这个事务对于数据进行了更新，则这个锁升级位写锁。由于可以对某个数据对象一直持有读锁，所以可以排除更新丢失的情况（别的事务要更新这个对象则必须通知当前的事务释放读锁）。稳定游标也没有任何和时间方面相关的限制。
在隔离级别 PL-3 中的事务历史记录 H0 中（详细见事务（多对象、多操作）上篇）出现了两个事务 T1 和 T2 都对于单个数据对象 x 进行更新且 T2 的更新发生了丢失的情况。
图 17 在使用稳定游标的系统中这类情景无法出现，因为事务 T1 由于可以通过游标持有对于数据对象 x 的读锁，所以事务 T2 无法对于 x 进行任何修正（即 w2(x2, 26)这一步无法执行）除非事务 T1 事务提交完毕或者主动将游标移除以后才可执行。由于是通过游标引用对于特定的数据对象发生效果，所以可以对于 DSG（H）做一些小小的特化，即有向边不是针对所有数据对象而且通过给有向边打上针对单个数据对象的相应标签，来形成所谓的标签有向图（Labeled DSG（H），LDSG）。
排斥场景：G1，G1-cursor(x) Labeled Single Anti-dependency Cycles
G1-cursor(x) Labeled Single Anti-dependency Cycles
当基于事务历史记录中产生的 LDSG(H)图中包含一个含有反向依赖关系以及一个或多个写依赖的有向环，这个环每个有向边都带有相应标签，同时其有且只有一个反向依赖有向边，则这个事务历史记录包含场景 G1-cursor(x) Labeled Single Anti-dependency Cycles。由于排斥 G1，G1-cursor(x) Labeled Single Anti-dependency Cycles，所以在实现稳定游标的系统中上面的例子中的事务历史记录 H0 是不能被允许出现的。
客户端角度: 对于应用程序来说隔离级别 PL-CS 保证了当数据对象中的某一个数据项（数据行）被一个进程、线程改变之后当这个进程的事务没有提交之前，这个数据项不能被其他进程或线程读取。同时，它也确保每个可更改游标的当前行不会被另一个应用程序进程更改。如果脱离了游标的范围，在工作单元（unit of work pattern）期间读取的数据对象可由另一个应用程序进程更改（游标已经释放）。
隔离级别 PL-2L （Isolation Level PL-2L （基于锁的 PL-2））
早期 ANSI-92 时代数据存储系统一般都基于锁机制(通过长写锁与短读锁结合使用)实现读已提交（READ COMMITTED)隔离级别。由于锁机制提供的一致性保证要强于对于读已提交（READ COMMITTED) 所需保证的一致性，所以 Adya 的隔离级别专门基于锁的机制的特殊性给出了对应的隔离级别 PL-2L。这样的话，当应用程序进行相应的数据存储系统平台迁移的时候（特别是从老旧平台迁移到新平台，许多新的系统并不使用悲观锁机制实现读已提交而是使用其他优化的并发控制方式，例如乐观锁），可以让程序员能够对于老数据平台与新数据平台在读已提交（READ COMMITTED)实现上的微妙不同有所察觉，并对于已有代码做出相应的修正从而使系统继续工作下去。
锁单调性（lock-monotonicity property）
实现基于锁的 PL-2L 隔离级别的数据存储系统需要实现锁单调性（lock-monotonicity property），所谓锁单调性（lock-monotonicity property）是指若事务历史记录中存在一个事务 Ti 的事件 ri（xj）（即事务 Ti 读取了由事务 Tj 写入的数据对象版本 xj），在此事件发生后之后，数据存储系统会保证 事务 Ti 会观察到另外一个和事务 Ti 有读依赖关系的事务 Tj 以及其所依赖的所有其他事务的操作对系统的影响（例如：状态更新）。如果这个系统的事务历史记录中的每条记录有一个数据编号，则事务 Ti 在执行时看到的记录的编号必须是单调递增的。由于是基于锁实现，所以系统中的事务 Ti 试图去读取某个数据对象 xj 之时，需要使用短读锁来获取相应的访问权限，由于锁的互斥性，如果事务 Tj 是最后修正数据对象 x 并给出了 xj 的事务，则事务 Tj 已经提交，否则事务 Tj 会一直持有这个锁，从而使事务 Ti 无法执行读取操作，而且 Tj 依赖任何其他的事务也必须都提交完毕。
排斥场景：G1，G-monotonic
G-monotonic
当基于事务历史记录中产生的 USG(H，Ti)图中包含一个含有反向依赖关系（这个代表反向依赖的有向边由读取事件 ri(xj)或者谓词查询，例如 ri(Dept=Sales: x1; y2))到到其他的事务 Tk）以及任何数量的顺序或者依赖有向边，则认为这个事务历史记录包含场景 G-monotonic，并且无法实现单调读（Monotonic Reads）。通过排除场景 G-monotonic,系统可以实现锁单调性（lock-monotonicity property）。
展开序列化图（Unfolded Serialization Graph or USG）
和其他隔离级别类似，隔离级别 PL-2L 也通过对于 DSG(H)进行相应的调整来体现相应的隔离级别的特殊性。隔离级别 PL-2L 使用的是展开序列化图（Unfolded Serialization Graph or USG）。由于锁与某个事务 Ti 的某个读操作相挂钩，因此可以用 USG（H，Ti）来标识某个事务 Ti 的历史记录对应的 USG 图。和 DSG 图一致，USG 图也保留所有的已经提交的事务作为节点（除了事务 Ti），由于事务 Ti 要和相应锁关联，所以会将事务 Ti 拆分为多个节点，每个节点代表这个事务相应的读、写操作各自对应的事件。USG 图中的有向边则表示事务 Ti 相关的读、写事件的关系。以如下事务历史记录 H2L 为例：
图 18 对于要实现锁单调性（lock-monotonicity property）的数据存储系统来说，当事务历史记录中的某个事务 Ti 有读取事件 ri(xj) 或者谓词查询，例如 ri(Dept=Sales: x1; y2) 存在，则数据存储系统会将锁与这个读取事件相挂钩。在 USG 图中会将事务 Ti 涉及的操作分解为多个事件，同时基于其他事务与事务 Ti 的内部的读操作对应的读取事件 ri(xj)或者 (或者谓词查询，例如 ri(Dept=Sales: x1; y2))根据相关的依赖关系类型添加相应的有向边。对于事务 Ti 涉及的事件如果是连续事件则依据 Ti 中的顺序由有向边连接，方向为由先发生的事件指向后发生的事件。由此可以看出上述的事务历史记录 H2L 由于含有环所以不符合隔离级别 PL-2L。
如下事务历史记录 Hm 符合隔离级别 PL-2L
图 19
因为只定义了锁和某个读事件挂钩（锁单调性和某个操作相关（锁通过某个操作与某个数据对象关联）)，但是没有指定哪一个读事件（也无法指定），所以锁可以是任意一个读事件关联。由此操作发生（读事件产生）的时机就显得比较重要。例如：事务 Ti 修正数据对象 x 与 y，即使实现了锁单调仍旧会出现事务 Tj 读取了事务 Ti 已经修正过的版本 xi 以及事务 Ti 还没来的及修正的版本 y 的情况。这是因为如果 Tj 在读取 xi 之前读取了 y，而读锁是和读取数据对象 x 的操作相关联的，这样就无法通过这个读锁来保证在事务 Tj 读取数据对象 y 的时候 Ti 已经提交，进而也无法保证数据对象 y 的版本是最新的被 Ti 的写操作修正过的最新版本。由此可以看出锁单调性属性比隔离级别 PL-2+的无依赖丢失（No-Depend-Misses）要弱一些，并且不能保证 Tj 观察到一致的数据库状态;因为无依赖丢失属性和操作的时机无关，它可以确保无论事务 Tj 何时读取 xi，事务 Tj 都不会错过事务 Ti 的影响。所以隔离级别 PL-2L 虽然排除了 G-monotonic，但是并不能彻底排除事务 Ti 读操作对于其他事务的写操作更新状态的丢失。上面的事务历史记录 Hm 中，虽然通过锁与读事件 r3(x2,2)关联，从而实现了在事务 T3 在 r3 事件发生后不会忽略事务 T2 的和 x 数据对象相关的写操作写入的值， 但是其仍旧已经忽略了事务 T2 的写入事件 w2(y2,2)。这种情况在隔离级别 PL-2+中是不会出现的，因为场景 G1-singl 包含了所有包含单个反向依赖成环的情景，而 G-monotonic 只能算作其子集，所以隔离级别 PL-2+和锁的时机无关，只要事务 T3 对事务 T2 有依赖，则隔离级别 PL-2+不允许事务 T3 错过事务 T2 的造成的系统状态的变化。
在隔离级别 PL-2L 之下，当读事件是谓词查询（例如 ri(Dept=Sales: x1; y2)），由于读事件关联的锁所涉及的数据对象不是单个数据对象而是谓词匹配成功的所有对象，如此系统可以保证如下基于谓词的读操作的一致性：
1）如果事务 Ti 基于谓词的读取操作察觉到某一个事务 Tj 造成的系统状态变化，它会观察到事务 Ti 造成的完整影响以及 Ti 依赖的所有事务造成的影响。在极端情况下，当事务 Ti 只包含一个读操作时，而这个读操作涉及所有的系统的所有数据对象，事务 Ti 将会观察到一致的数据库状态，即得到隔离级别 PL-2+（因为，只有一个读事件，所以在这种情况下和时机无关，这样就等于保证了保证无依赖丢失（No-Depend-Misses），即所有的事务 Tj 造成的变化都会被事务 Ti 察觉）。
2）当系统保证基于谓词的读取操作的原子性并且基于锁的实现隔离级别，则由于每个基于谓词的读取操作是在获得谓词读锁之后执行的，所以可以都视作以隔离级别 PL-3 事务执行。
第二个一致性保证比第一个保证更强。
客户端角度: 对客户端引用程序来说，隔离级别 PL-2L 最常用在一些使用锁实现各隔离等级的老旧系统中。在某些业务情景之下，当系统业务的代码需其某个读操作事件发生之后得到信息是不变的则这个隔离级别 PL-2L 也很有用。
隔离级别 PL-SI（Isolation Level Snapshot Isolation）（快照隔离））
在 Adya 的定义当中，当一个事务 Ti 开始执行（例如：从第一个操作事件开始算起（start(Ti)）），系统便为这个事务选择了一个起始点 si，并以此为基准点来确定这个事务的起始点和其他事务的提交（终点）(c(Ti)=commit(Ti)或 abort(Ti))之间的先后顺序关系。 尽管为了方便起见一般都选择为某个较早的点（可以是任意的之前的点），事务 Ti 的起始点的确定实则往往随着业务需求而定，而不是一定是事务 Ti 启动时距离这个事务 Ti 最近的位于其他事务的提交（结束）点之后的那个点作为起始点。例如：如果当业务需要所有其他事务对于系统的更新都不能为事务 Ti 所察觉，则 Ti 的起始点必然选择在其他任何事务提交之前。
定义：Adya 从快照条件下的读/写操作两方面来对于快照隔离（Snapshot Isolation）进行定义与描述，并且 Adya 的定义去除了对于实现相关的部分，仅针对事务历史记录中各个事务起始和结束之间关系本身：
快照读：若事务 Ti 执行的所有读取都发生在其起点，当事务 Ti 的读事件 ri(xj) 在事务历史记录 H 当中记录，则事务 Ti 和任意另外一个事务 Tj 之间只会有两类情况（定义中的 " 表示的是时间先后顺序（time-precedes order）概念），
1）只有事务 Ti 和事务 Tj，则事务 Tj 的提交事件 cj 在事务 Ti 的起始事件之前发生(cj<t si)
2）当事务 Ti 和事务 Tj 之外有另外一个事务 Tk 发生，且事务 Tk 有事件 wk(xk) 也在事务历史记录 H 当中记录，则
事务 Ti 的起始点在事务 Tk 的提交点之前 （si <t ck）或者
事务 Tk 的结束点在事务 Ti 的起始点之前（ck <t si）同时数据对象的版本 xk 在 xj 之前。
快照写：如果有并发事务发生即 事务 Ti 和事务 Tj 同时运行，则不允许事务 Ti 和事务 Tj 不能同时修正同一个数据对象。也就是说如果事务 Ti 和事务 Tj 的事件 wi(xi)和事件 wj(xj)都被同时记录在事务历史记录 H 中,则事务 Ti 和事务 Tj 必定是串行运行（ci <t sj 或者 cj<t si）。
图 20 图中第一部分说明快照读的第二类情况的（1）情况，后面两个部分说明（2）情况。通过保证若事务 Ti 读取了事务 Tj 的信息，则 cj 与 si 之间不存在事务 k 的提交（ck），来确保事件 ri(xj)的准确性不会发生更新丢失（防止由于反向依赖造成这种情况）。
时间先后顺序（time-precedes order）
由于事务历史记录中的事务的事件顺序无法确认事务的起始点和提交点之间关系，事务的历史记录 H 上的事务的顺序是基于时间先后顺序（time-precedes order）的偏序（时间先后顺序基于事务历史记录（如版本记录，操作记录）对其中各个事务开始与结束之间先后关系等进行判断而不是基于操作的时间戳）：
同一个事务之内，当事务 Ti 的起始点 si 在这个事务的提交点 ci 之前则可以记录为（si <t ci）（因果一致性，不考虑并发，非全序）
不同的事务之间，即系统涉及的所有的事务 Ti 以及事务 Tj 来说，如果存储系统的调度选择某个事务 Tj 的开始点 sj 的顺序在事务 Ti 的提交 ci 点之后则可以记录为（ci <t sj）反之则为（sj <t ci）（可通过快照读里面的定义中的读事件进行判定）
事务的历史记录上的事务的顺序是基于时间先后顺序（time-precedes order）的偏序，所以事务记录的先后顺序和事件的实际发生时间没有完整的一一对应关系（否则就是全序记录），故而仅凭事务历史记录中的事件顺序无法确定不同事务之间的各个起始点和提交之间的关系。如下的例子:
尽管在事务历史记录中，事件 w3(z3) 记录在 r2(z0)之前，且事务 T3 的提交事件记录在在事务 T2 的起始点 r2(x1)事件之前，实则数据版本的顺序以及事务 T2 的事件 r2(z0)（C3 肯定没有发生）说明系统在时间先于顺序当中并没有选择 s2 排在 C3 之后。
另外，如果将时间先后顺序和一个唯一的物理时间关联，即时间先后顺序和各个事务的物理发生时间一致，则客户端应用系统可以得到高于 PL-2+ 甚至 PL-3 的一致性保证。因为时间先后顺序一旦和各个事务的物理发生时间一致，则事务 Ti 必然会读取到在 Ti 的实时起始时间之前的所有的已经提交的事务对于系统造成的更新。
并发事务（Concurrent Transactions）
当事务 Ti 的起始时间小于与事务 Tj 的结束时间（ sj <t ci)
图 21 并发事务的认定和 si 和 sj 之间，tci 以及 tcj 之间的先后关系无关
启动依赖（Start-Depends）：如果事务 Tj 的结束点在事务 Ti 的起始点之前（cj ）则可以认为事务的 Tj 对于事务 Ti 有启动依赖（Start-Depends）关系。
开始排序序列图（Start-ordered Serialization Graph，SSG(H））：基于启动依赖可以将 DSG（H）稍作改变成为 SSG(H) 。SSG 保留和 DSG 图一样的节点以及有向边并包含启动依赖关系信息（有向边上加入“s”）一起作为有向边。如下为一个符合快照隔离的事务历史记录：
图 22 虽然符合快照隔离，由事务 T3 的起始点事件 r3(x1,1)可以看出，事务 T1 在事务 T3 之前提交，而事务 T2 的提交点必然在事务 T3 的起始点之后，所以事务 T2 对事务 T3 是反向依赖关系，事务 T3 无法观察到事务 T2 对于数据对象 x 的更新。
排斥场景：G-SIa: Interference，G-SIb: Missed Effects
G-SIa: 干扰（Interference）
当一个事务历史记录产生的 SSG(H）图包含事务 Tj 对于事务 Ti 有直接读/写依赖，但是没有启动依赖关系则说明 SSG(H）图包含 G-SIa。没有启动依赖关系就没有对于并发事务造成的干扰的保护，即在并发事物之间有读/写依赖。
G-SIb: 丢失效果（ Missed Effects）.
当一个事务历史记录产生的 SSG(H）图包含一个含有反向依赖关系的有向环则说明 SSG(H）图包含 G-SIb。通过由反向依赖以及一个启动依赖有向边组成的有向环可以判断事务 Ti 是否会丢失在 Ti 起始点之前已经提交的事务的更新。
G-SIb 由于包含额外的启动依赖限制因此比 G1-single 更强一点（和一致性的强弱定义类似限制越严格越强）。
从客户端角度：快照隔离（Snapshot Isolation）和 PL-3 相比，其只能保证事务 Ti 所有的操作必须从相同的状态 s 读取到信息， 但是快照隔离无法保证事务 T 在执行后的得到一个状态 t 的父状态（即 t 状态的紧靠的前一个状态）是状态 s，即状态 s（快照）不能保证和状态 t 之间没有任何其他状态存在。
如下图所示：
图 23 符合快照读的定义事务 Ti 的起始点在事务 Tk 的提交点之前 （si （snapshot(Ti) ≤ start(Ti)） 然而状态 t 的父状态并不是状态 s 而是状态 k。
基于快照的隔离的协议 （snapshot-based protocols）
由于不同的需求与使用场景，如果以 Adya 的快照隔离（Snapshot Isolation）定义作为基础，将快照隔离（Snapshot Isolation）相应的约束做相应的调整则可以得到多个不同的强度的基于快照的隔离。
从客户端的角度可以从 3 个维度来观察这些基于快照的隔离的协议的不同：
1）时间维度，不同的协议所使用的时间戳是基于逻辑时间还是基于物理时间
2）不同的协议是否允许使用过期的快照（快照是否包含在某个事务开始时间之前提交的所有事务的变化）
3）状态的完整性，即快照的是包含数据存储系统的完整状态还是只需符合因果一致性即可。
1.隔离级别 PL-ANSI （ANSI Snapshot Isolation（ANSI 快照隔离））/
隔离级别 PL-GSI （Generalized Snapshot Isolation (GSI)（一般快照隔离））/
隔离级别 Clock-SI （Clock-Snapshot Isolation（时钟快照隔离））
隔离级别 PL-ANSI 快照隔离：
由 Berenson 提出[Berenson et al]的是最初始的也是最广为人知的快照隔离定义。一个基于 ANSI 快照隔离运行的事务 Ti，其总是从在某一个（逻辑）时刻----初始时间戳（start-timestamp）生成的由已经提交了的数据组成的快照中读取数据。 （换句话说，产生快照的初始时间戳即为可以在事务的开始时刻，这个初始时间戳可以等于事务第一次读操作的时间也可以是其之前的任意一个逻辑时刻生成（ss(Ti)（snapshot(Ti)) ≤ si（start(Ti)） < ci（end(Ti)）））。由此其他事务在这个事务 T1 的初始时间戳之后的更新操作由于无法影响这个快照而无法被事务 T1 所察觉。当事务 T1 需要提交时会设置一个提交时间戳（commit-timestamp）并提交。若事务 Ti 需要提交时，有另外一个并发事务（Concurrent Transactions）T2（即事务 T2 的初始时间戳和提交时间戳和事务 T1 的初始时间戳和提交时间戳有重叠）已经对于事务 T1 需要更新的数据对象进行了更新并已经提交，则依据先来先得的原则（即第一个提交的事务赢）的仲裁原则来停止事务 T1 的提交从而防止更新的丢失。ANSI 快照隔离和 Adya 的快照隔离的定义最大的不同在于，Adya 是基于时间先后顺序（time-precedes order）的偏序来判断各个事务之间的关系和时间戳没有直接关系，ANSI 快照隔离定义更偏向于事务的操作相关，要求相关的操作有基于时间戳的一个全序排序，因此比 Adya 的快照隔离的定义更强。为了不阻塞事务的读取操作以提升系统执行效率，ANSI 快照隔离允许事务使用过期的快照，只要其可以维护从初始时间戳开始的快照数据即可。
隔离级别 PL-GSI（一般快照隔离 Generalized Snapshot Isolation (GSI)）：
Elnikety,Fernando 等人基于 ANSI 快照隔离允许读过期快照的特质将快照隔离应用在了分布式多副本系统提出了一般快照隔离（Generalized Snapshot Isolation (GSI)）。一般快照隔离的也需要所有操作基于时间戳组成一个全序并利用 ANSI 快照隔离定义中允许使用过期的快照（即 snapshot(Ti)这一点。其允许所读取的 commit(Tj)的值不一定是最新的，commit(Tj)的时间戳不是事务历史记录中所有的提交操作中时间戳最大的），并且也继续保留了某些要求事务读取的数据必须是来自最新快照的隔离种类中的许多属性。 尽管和保证 PL-3（序列化）等级隔离相比所能提供的一致性较弱。然而，通过允许客户端从系统的不同的副本中得到相应的快照，可以减少相应的系统读操作以及写操作的阻塞与取消，提高系统的运行效率。一般快照隔离（Generalized Snapshot Isolation (GSI)）相对 ANSI 快照隔离更加明确的定义了相关的操作（一般快照隔离也是基于事务历史记录中操作的时间戳的全序排序），并基于这些概念重新定义了 ANSI 快照隔离：
snapshot(Ti): 事务所基于的快照的生成时间戳
start(Ti): 事务的开始时间（第一个操作时间戳）
commit(Ti): 事务的提交时间（提交操作时间戳）
abort(Ti): 事务取消时间（取消操作时间戳）
end(Ti): 事务结束时间（commit(Ti)或者 abort(Ti)）（等同于提交或取消时间戳）
一般快照隔离从读与提交两方面进行定义：
读：当事务 Ti 的读事件 ri(xj) 在事务历史记录 H 当中记录（即事物 Ti 对于事物 Tj 有读依赖），则事务 Ti 和任意另外一个事务 Tj 之间只会有两类情况
1）只有事务 Ti 和事务 Tj，则事务 Tj 的提交事件 commit(Tj)在事务 Ti 的快照的生成时间 snapshot(Ti)之前发生（commit(Tj) < snapshot(Ti)）
2）当事务 Ti 和事务 Tj 之外有另外一个事务 Tk 发生，且事务 Tk 有事件 wk(xk) 也在事务历史记录 H 当中记录，则事物 Tk 的提交点不能在事物 Tj 的提交点和事物 Ti 的起始点之间（保证事物 Tk 的提交能够包括为事物 Ti 所观察到），即：
事务 Ti 的起始点在事务 Tk 的提交点之前 （snapshot(Ti) < commit(Tk)）或
事务 Tk 的提交点在事务 Tj 的提交点之前（commit(Tk) < commit(Tj)）。
提交：任意两个事务 Ti、Tj，当事务 Ti 提交时，事务 Ti 和事务 Tj 相互不能有影响（impact），即这两个事务的更新涉及的数据集合不能有交集，且事务 Ti 从产生快照和提交的整个时间段内不能存在事务 Tj 的提交操作的事件的时间戳。（即 snapshot(Ti) < commit(Tj) < commit(Ti)）。
由于一般快照隔离仍旧无法避免 write skew 等问题，因此一般快照隔离和 ANSI 快照隔离一样只能只能提供与 PL-3 隔离等相比相对较弱的一致性保证。由于事务可能观察到一些“旧”快照，为保证提交更新事务的正确性，系统对于每一次的更新事务必须像之前的已经提交的事务一样根据最近提交的事务的写操作涉及的写入集合检查其写入集合。因此为了保证系统的一致性，又基于更高的一致性保证即序列化（PL-3）提出了相应的动态检查规则：若任意两个事务 i、j，事务 Ti 从产生快照和提交的整个时间段内存在事务 Tj 的提交操作的事件的时间戳（snapshot(Ti) < commit(Tj) < commit(Ti)） ，则事务 Ti 的读操作涉及的数据集合和事务 Tj 的写操作涉及的数据集合必须没有交集。通过这个规则可以保证实现一般快照隔离的系统生成的事务历史记录是序列化的，但是因为涉及对于读操作的集合的检查对比，所以会带来不小的性能惩罚。为此又提出了对应的静态检查条件 ：任意两个更新事务 Ti 与 Tj 的写操作的涉及的数据集合有交集或者任意两个事务 Ti 与 Tj 的任意读写操作的涉及的数据集合不能有任何交集（writeset(Ti) ∩ writeset(Tj) <> ∅∨( readset(Ti) ∩ writeset(Tj) = ∅∧writeset(Ti) ∩ readset(Tj) = ∅)）。符合这个条件的系统的任意两个更新事务由于写操作涉及的数据集合没有交集且符合 GSI 的定义所以必然是串行的，而对于读写操作来说由于保证所涉及的数据集合是没有交集的，所以两者之间没有直接依赖关系。
隔离级别 PL-Clock-SI （时钟快照隔离 Clock-Snapshot Isolation）：
Jiaqing Du 等人从时间维度去中心化角度出发，将 ANSI 和物理时钟相结合，通过使用分布式系统各个分区（副本）服务器的本地时钟而不是中央时钟的办法来在分布式系统中高效的实现 ANSI 快照隔离。假设实现时钟快照隔离的分布式系统的将数据分区存放，且各个服务器的本地时钟是通过 Network Time Protocol (NTP)进行相应的同步并将时钟同步偏差绝对值控制在有限范围内。由于要实现 ANSI 快照隔离，其所有快照的数据必须包含且仅包含所有先于 snapshot(Ti)已经提交 Commit 的事务的数据，所有事务的提交操作都会产生一个基于提交时间戳标示的新快照，并能够构成一个全序关系。这个系统同时要保证并发事务之间不能有写写冲突（定义类似 GSI 的提交的定义）否则取消相应的更新事务。由于和物理时钟关联，并且是分区存储数据，这便涉及到数据远程提交到其他分区的可能，故而将数据提交分为本地和远程两类，本地提交和一般操作没有区别，而将数据远程的事务执行分为 Prepared 或者 Committing 两个阶段（使用 2PC 提交），每个阶段都会有相应的本地时间戳，同时考虑会有时钟同步偏差的情况。
采用时钟快照隔离的系统需实现如下几点：
分区因读取操作产生快照时，直接从本地时钟获取相应的时间戳 snapshot(Ti)
读：读取操作的时间戳取所在的分区的本地的时钟产生的时间戳 snapshot(Ti)，当这个读取操作需要远程读取另外一个分区上面的数据，这个时间戳大于负责提交事务所在的分区（假设数据所在的分区和读取操作不在同一个分区，读取操作是一个远程操作）的本地的时钟产生的时间戳，则读取操作在远处的分区上的会先等待直到两者的时钟同步偏差消除。然后，若另一个分区上有事务进行提交，则继续等待直到这个分区上的事物的提交操作两个阶段产生的时间戳都小于读取操作的时间戳且提交操作状态为已经提交，则可开始读取操作并读取小于 snapshot(Ti)的最新提交操作所提供的数据。这里的为时钟同步偏差消除产生的延迟是为了保证快照包含最近提交操作的更新的数据。
提交：如果单分区内部本地提交（单个分区之内）可以使用本地时钟作为提交时间戳直接提交，并对于同一时间段内并发事务写操作涉及的数据集合在本地就地进行是否有重合（写写冲突）检查，如果没有会互相有影响的事物则进行提交。如果需要远程提交，则进行基于 2PC 协议的远程分布式事务提交，选择最大的准备阶段时间戳作为提交时间戳进行 2PC 提交；为了保证基于提交时间戳排序是全序，光有时间戳由于会出现重复无法区分，因此每个分区在执行 2PC 准备阶段时各自会添加自己分区的 id，并需要在每一个执行写操作的分区的本地进行和单个分区相同的检查。
图 24 对于时间同步偏差和提交操作延迟造成的创建快照延迟
时钟快照隔离也允许使用“旧”快照，这个快照允许的延迟时间范围从 0（快照时刻保持最新数据）到以下两个数据的最大值之间（系统最大延迟之内前的数据）。
（1）将事务同步提交到稳定持久化完毕所需的时间加上一个往返网络延迟
（2）分区节点之间最大时钟偏差减去两个分区之间的单向网络延迟
隔离级别 PL-StrongSI（Isolation Level Strong Snapshot Isolation （强快照隔离））
强快照隔离（Strong Snapshot Isolation）：符合强快照隔离的事务的历史记录 H，首先要求历史记录 H 中的每一对已经提交的事务（事务 Ti 和事务 Tj）符合 ANSI 快照隔离（Snapshot Isolation）定义。再次，事务历史记录 H 中的每一对已经提交的事务（事务 Ti 和事务 Tj），若事务 Tj 的提交操作发生在事务 Tj 的第一个操作之前，则事件 cj 的时间戳小于事务 Ti 的第一个操作的事件 si 的时间戳（即 commit(Tj) 快照隔离无法保证这一点，因为快照可以是开始之前的任意一点而不是和事务实际的执行时间（物理时间），即可以 snapshot(Ti)强快照隔离的系统需要基于时间（物理时间）维持事务之间的一个全序排列，其要求任意一对事务都有先后关系（事务 Tj 起始点在 Ti 提交之后开始），且基于时间的进行先后排序，则最新提交的事务 Tj 的 commit(T)操作时间戳会大于系统发布的任何现有开始或提交时间戳，同时系统也会包装事务 Tj 会观察到包含事务 Ti 的更新在内的数据存储系统的全部状态。要实现上述要求一个事务的所有操作完全与其他事务隔离，强快照隔离和严格序列化一样基于物理时间进行事物顺序的全序定义，从而可以提供 PL-3 甚至严格序列化的一致性保证。
隔离级别 PL-Strong SSI （Strong Session Snapshot Isolation（强会话快照隔离））/
隔离级别 PL-Prefix-consistent SI （Prefix-consistent Snapshot Isolation 前置一致性快照隔离）
由于强快照隔离要求整个数据存储系统都维持所有事务的统一的前后顺序，对于实现这个隔离级别的系统的性能来说影响过大。为此，可以放宽对于维持事务统一的顺序范围的限制，将维持所有事务的统一的顺序维持在会话范围（对于分布式系统来说数据存储系统往往有多个客户端并产生多个会话），并且系统会对于每一个和事务关联的会话给与一个编码 LH (T)。在强会话快照隔离中事务的历史记录 H，首先要求历史记录 H 中的每一对已经提交的且会话编码一致的事务（LH（Ti）=LH（Tj))在会话范围内符合基础快照隔离（Snapshot Isolation）定义。再次，事务 Tj 的提交事件 cj 在事务 Ti 的起始事件 si 之前发生（即 cj < si）。所以，虽然强会话快照隔离放松了在数据存储系统层面的一部分强制限制，对单个客户端而言其限制并没有本质的变化：和强快照隔离一样，事务只能从基于时间维度的在这个事务起始点之前的完全完成的状态中读取数据，而不能从在提交（结束）的实时时间点在事务起始点之后的事务当中读取数据，同时系统在会话范围其仍要维持一个昂贵的全序。如果每一个事务都是一个会话，即一个会话里面只有一个事务，则强会话快照隔离等同于基本的快照隔离（Snapshot Isolation）。若将会话等同于一个工作流，便可以将强会话快照隔离也同样应用到分布式系统中，并基于 GSI 衍生出前缀一致性快照隔离（Prefix-consistent Snapshot Isolation）。前置一致性快照隔离保证在一个工作流（会话）当中，任意两个事务 Tj，Ti，若事务 Tj 的提交在事务 Ti 的起始点 start(Ti)（非 snapshot(Ti)）之前，则事务 Ti 的快照必须包含事务 j 的更新信息（即若 commit(Tj) < start(Ti)则 commit(Tj) 事务 Ti 和事务 Tj 之间有读依赖，说明不存在另外一个事务 Tk，其 commit(Tk)在[commit(Tj), start(Ti)]之间。而在事务提交时，则这两个事务之间在数据和时间维度不存任何交集。通过使用前缀一致性快照隔离，可以使分布式系统中也实现强会话快照隔离所能保证的正确性。
隔离级别 PL-PSI（Parallel Snapshot Isolation PSI（平行快照隔离））
平行快照隔离 由 Sovran 等人从分布式存储系统使用业务场景出发，通过在系统整体层面放松由于 ANSI 快照隔离所需要的对于整个系统快照而需要系统保持所有提交操作维持全序的要求而提出的一种较弱的快照隔离。平行快照隔离为了增加多地域大型分布式数据存储系统的伸缩性而允许不同的地域的分区节点按照不同的顺序提交。PSI 允许一个事物在不同的地域节点上有不同的提交时间，由此各个地域节点上的组成的事物历史记录上记录的操作事件顺序是不同的。一个事物在每个节点上有一个提交时间，它先从本地开始提交然后扩散到各个远程节点 。
采用平行快照隔离的系统需要实现如下几点：
节点快照读：自事务开始时，所有操作都在各自事务的所在原初站点在这个事务开始时依据最新提交的版本产生的快照读取数据。（假设分叉都已经解决）
提交：任意两个事物之间没有相互影响（参考 GSI 的定义），即没有写写冲突。若两个事物在某个节点有了并发造成了相互影响则必须进行分叉（disjoint）
全节点提交保证因果一致性：若在任意一个节点事物 Ti 的提交顺序在事物 Tj 的开始时间之前，则在任何其他节点都要保证这个顺序。
平行快照隔离由于允许在不同的分区节点进行提交进而造成的各个节点数据的不一致即分叉。分叉分为两类：短分叉（Short fork）与长分叉（long fork）两者的区别在于短分叉在多个节点上各有一个事物执行，整体为并发执行的几个事物提交结束后会立即进行融合（merge）而长分叉则需要较长的时间且每个节点上有多个事物顺序执行，整体为并发执行等各个节点的事物都执行完毕后进行融合。
平行快照隔离与其他隔离类型的比较如下：
图 25 PSI 允许分叉(ref:Transactional storage for geo-replicated systems)
由上面的各类快照隔离可以发现对于大型分布式数据存储系统来说，通过对于时间维度（否维持统一的全序），快照是否最新以及状态完整性范围等方面的妥协与权衡，从而使各类快照隔离在多副本与去中心化架构的分布式系统上实现成为可能，并能够在实际的应用场景上在保证系统所需的正确性的前提下提升了系统整体执行效率。然而，各家对于快照隔离各个操作以及对应的事件以及时间的定位并没有统一，这里以 Adya 的定义为基础，以 GSI 的定义为参照对各种快照隔离进行了一个大致介绍。
隔离级别 PL-FCV（Forward Consistent View（向前一致视图））
向前一致视图放宽了 Adya 快照隔离对于快照读在多个事物并发场景下的一部分限制。
排斥场景：G1，G-SIb: Missed Effects
由于允许 G-SIa，所以当多个事物并发时允许这些事物之间有依赖关系，事物 Ti 允许观察到在其起始点之后的其他事物提交的更新，即所谓的超过起始点“向前”读取。这些读取只允许从能够一致的数据存储状态上观察数据。由于 G-SIb 比 G-single 更严格（G-SIb 不允许反向依赖与启动依赖组成的有向环），因此 PL-FCV 要强于 PL-2+。
客户端视角：向前一致视图适用于某些应用系统的并发写操作较多，且数据存储系统能够保证数据一致的场景下来提升应用系统的整体性能。
隔离级别 PL-3U（PL-3U，Update Serializability(更新序列化 ))
很多系统中只读事物的数量远多于写入事物（例如：web 网站等），所以这类系统若维持所有操作都在 PL-3 等级的隔离代价过于高昂。例如：降低对于读操作的隔离等级到 PL-2+对于不少系统往往就足够了。通过降低只读事物的等级，只保证所有的更新事物的提交是可序列化，变得到更新序列化 PL-3U。
更新序列化 PL-3U 需要实现如下的条件：
无更新冲突丢失：若事物 Ti 依赖于事物 Tj，则与事物 Tj 以及其所依赖以及反向依赖（由于包含反向依赖因此比只包含依赖的无依赖丢失更强）的所有的相关事物的更新应该为事物 Ti 察觉到。
排斥场景：G1，G-updagte
G-updagte：当一个事物历史记录中产生的 DSG(H)图由这个历史记录所有的更新事物（只读事物可以缺失）以及某一个事物 Ti，且这个图中包含了一个或多个反向依赖有向边组成的环。
Hn3U: r1(S0, O) w1(X1, 50) w1(Y1, 50) c1 r2(S0, Open) w2(X2, 55) w2(Y2, 55) c2 w3(S3, Close) c3 rr(S3, Close) rr(X1, 50) rr(Y1, 50) cq [S0<<S3, X1 <<X2, Y1 <<Y2]
图 26 当有 2 个事物包括只读事物 Tr 事物 T3 之前都读取了数据 x1 与 y1 则说明事物 Tr 和事物 T2 之间存在反向依赖，而事物 T1 与事物 T2 由于都读取了数据 S0，故而与事物 T3 有反向依赖。由于由 2 个反向依赖组成有向环，所以 PL-2+允许这个事物历史记录，而 PL-3U 则由于排斥场景 G-updagte 而不允许产生这个事物历史记录。同时，PL-3U 和 PL-3 比较由于 PL-3U 没有要求包含所有的读事物，所以有些在 PL-3 隔离级别 DSG 图中会由多余一个读事物（2 个只读或更多）和更新事物组成的有向环，在 PL-3U 隔离基本形成的 DSG 图中由于某些只读事物没有包括而无法形成环。如此，这类情况就会造成系统并不是完全符合序列化隔离级别的。若数据存储的系统的客户端将这些只读事物都执行并直接进行相互比较将会发现事物的执行顺序会不一致。不过 PL-3U 隔离级别只在这类情况下会出现不一致，在其他情况下都是符合 PL-3 的隔离级别的。
从客户端角度：PL-3U（Snapshot Isolation）和 PL-3 相比，只需要对于某些特殊场景下的只读事物进行特殊处理即可（若有需要）。
隔离级别之间的相互关系
强于 PL-2 隔离级别（Intermediate Isolation Levels）汇总
参考文献：
https://pmg.csail.mit.edu/papers/adya-phd.pdf
A Critique of ANSI SQL Isolation Levels MSR-TR-95-51.PDF (microsoft.com)
Seeing is believing: a client-centric specification of database isolation | the morning paper
Generalized Isolation Level Definitions http://www.cs.cornell.edu/lorenzo/papers/Crooks17Seeing.pdf
https://pmg.csail.mit.edu/papers/icde00.pdf
Transactional storage for geo-replicated systems
Daudjee, K., and Salem, K. Lazy database replication with snapshot isolation
Clock-SI: Snapshot Isolation for Partitioned Data Stores Using Loosely Synchronized Clocks
Seeing is Believing: A Client-Centric Specification of Database Isolation
Database Replication Using Generalized Snapshot Isolation
https://www.geeksforgeeks.org/concurrency-control-in-dbms/?ref=lbp
版权声明: 本文为 InfoQ 作者【snlfsnef】的原创文章。
原文链接:【http://xie.infoq.cn/article/3ae697a8c4432f068fa3d3bdf】。文章转载请联系作者。
还未添加个人签名 2008.04.20 加入
20年软件开发经验，长期关注软件工程，软件开发方法学，软件设计与分布式系统
评论