Snapshot Isolation(1) - 理论算法

💡 事务隔离机制为多个事务同时执行提供并发控制。不同的并发控制级别涉及到正确性以及性能之前的权衡。Snapshot Isolation是常用的一种并发控制，其能够在保证正确性的同时兼具更好的并发性能，被用于各类数据库。本系列文章作为读书笔记，旨在整理各类Snapshot Isolation算法以及实现。

本文作为该系列的第一章，旨在探讨各类Snapshot Isolation的理论算法思路以及其对正确性的保证。

Snapshot Isolation

A Critique of Snapshot Isolation、A Critique of ANSI SQL Isolation Levels均对Snapshot Isolation的基础实现进行了总结，该算法核心是通过检测write-write conflict以避免lost update。

比如对于该场景：两个事务 T1 和 T2，分别用于给张三存入50块钱和100块钱，两者对应的SQL为

// TXA
SELECT balance FROM accounts; // return 100
UPDATE accounts SET balance = 100 + 50 = 150 WHERE name = 'ZhangSan';
// TXB
SELECT balance FROM accounts; // return 100
UPDATE accounts SET balance = 100 + 100 = 200 WHERE name = 'ZhangSan';

若没有检测write-write conflict，则最终结果错误。Snapshot Isolation的检测算法如下：

  1. 每个事务包含一个start timestamp和commit timestamp，start timestamp决定了事务可见的数据范围，commit timestamp决定了事务写入数据的时间戳。
  2. 对于两个事务txni和txnj，若以下两个条件同时为真，则判定为发生write-write conflict，需要abort两个事务中的其中一个
    1. Spatial overlap: 两个事务写同一个行
    2. Temporal overlap: Ts(txni) < Tc(txnj ) and Ts(txnj ) < Tc(txni)

正确性

  • 该算法是否为Serializability的充分条件

    否，该算法存在Write Skew问题，即其允许执行序列r1[x] r2[y] w1[y] w2[x] c1 c2

  • 该算法是否为Serializability的必要条件

    否，对于以上的银行转账Lost Update例子，其可以表达为执行序列r1[x] r2[x] w2[x] w1[x] c1 c2 ，如果对其稍加修改r1[x] w2[x] w1[x] c1 c2 （事务2 blindly write x），该序列会触发算法的write write conflict detection，但是该序列实际符合Serializability(等价于r1[x] w1[x] c1 w2[x] c2 )

Serializable Isolation for Snapshot Databases

根据以上的正确性分析，Snapshot Isolation无法满足Serializable。Making snapshot isolation serializable对构成Serializable的理论条件通过冲突图进行了分析：并行之间的事务构成图，如果两个事务并行访问同一个数据，且其中一个访问动作为写，则两个事务之间构成冲突。存在四种冲突(conflict)：

  • 读写冲突(rw)
  • 写读冲突(wr)
  • 写写冲突(ww)

如果并行事务之间构成的冲突图为无环图，则对应的事务执行等价于某种Serializable Execution。该理论是后续各类数据库产品提供Serializable Snapshot Isolation的基础。

根据该理论，一个朴素的Serializable Snapshot Isolation算法是在每次访问操作时记录相应的边，维护一个冲突图，并且不断运行寻找环的算法。然而该算法性能较低，难以应用于实际。

Serializable Isolation for Snapshot Databases对以上的算法进行了改进，其观察到：

  • Snapshot Isolation本身阻止了write-write conflict、write-read conflict，因此运行过程中无需检测对应产生的边。
  • 当Snapshot Isolation出现违背Serializable的情况时，构成环的并行事务之间必定存在两条连续的rw conflict边。（必要不充分条件

基于以上观察，其提出了一种能够在数据库运行过程中快速confliect detection的算法，大致过程是：在事务读操作时通过锁记录一个读时间戳，根据该时间戳，之后的写操作都会检查并记录是否存在rw conflict，若一个事务既构成一个rw conflict的读事务，又构成另一个rw conflict的写事务，则表示出现两条连续的rw conflict边，则系统会abrot掉连续边中的transcation。

Write-Snapshot Isolation

A Critique of Snapshot Isolation该文观察到，Snapshot Isolation既不构成Serializable的充分条件，也不构成其必要条件（即上文的正确性分析），其提出了另外一种Serializable Snapshot Isolation的算法，即Write-Snapshot Isolation算法，其核心思想是检测事务之间的read-write conflict，而不是write-write conflict，算法如下：

对于两个事务txni和txnj，若以下两个条件同时为真，则判定为发生read-write conflict，需要abort两个事务中的其中一个:

  1. Spatial overlap: 事务txni读，事务txnj写同一行
  2. Temporal overlap: Ts(txni) < Tc(txnj) < Tc(txni) ，即事务运行过程中，读集合被修改过

与Serializable Isolation for Snapshot Databases的SSI相比，该文主要强调其算法能够避免write-write conflict detection，减少由于write-write conflict带来的false positive abort。（然而其read write conflict检测条件看起来比SSI更加宽松，是否会有更高false positive?

同时，从实现上该算法相比于Serializable Isolation for Snapshot Databases也更为简单，理论上只需要在事务运行过程维护读集合，commit时进行对比即可。（在实际运行中维护的数据量和对比工作是否会有更高开销？

正确性

  • 该算法是否为Serializability的充分条件

    是（分析TODO）

  • 该算法是否为Serializability的必要条件

    否，因此该算法存在false positive abort

SSI of CockroachDB

💡 CockroachDB声称受到了Write Snapshot Isolation的启发，但从官方的实现上看其SSI实现是一种新的思路，感觉false positive abort率会更低？欢迎指正。

CRDB的SSI算法理论也是从冲突图理论出发，然而其算法与上面讨论的两种SSI算法不同，上面两种的思路更像是：直接避免某种边的出现以避免环的出现。而CRDB的思路是通过时间戳为事务排序，总是允许时间戳小的事务指向时间戳大的事务的边，反之则不允许，通过这种方法保证冲突图总是无环图。具体而言，当存在t1，t2，且start_ts(t1) < start_ts(t2)，需要避免以下边的出现：

  • write - read

    • 这里出现的情况是t1读到了t2写的内容，由于t1的开始时间戳比t2小，因此MVCC的实现下这里不可能会发生。

  • read - write

    构成这类边有两种情况：

    • t2读后t1写。这里CRDB的处理思路参考了WSI，其记录了读集合，写操作会查看读集合是否具有比当前时间戳更大的记录，若有则abort事务。
    • t1写，t2再MVCC读，由于MVCC下，t2读不到t1内容，因此本质上也构成了这种边。为了避免这种情况，CRDB使用了名为strict schedule的方法避免，本质是t1写后会留下“锁”，若t2读时看到，则通过一系列规则abort到两个中的某个事务。另外一种解法是阻塞t2直到t1 commit，但由于CRDB提供了optimistic的并发控制，因此没有采用这种解法。

  • write - write

    通过“写锁”记录避免

Summary

本文总结了SI、SSI、WSI、SSI of CockroachDB的基本算法并且讨论了背后相关的形式化定义和正确性。

几类SSI算法的核心都是从冲突图理论出发，通过各种观察到的性质以保证运行过程不会出现图成环。

后续文章会阅读具体的工业界实现，学习实际运行中的算法实现和优化。

Ref && Related

定义相关

  1. A Critique of ANSI SQL Isolation
  2. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions
  3. Generalized Isolation Level Definitions

Serializable Snapshot Isolation(SSI):

  1. Making snapshot isolation serializable
  2. Serializable Isolation for Snapshot Databases
  3. A Critique of Snapshot Isolation

Blog：

  1. https://justinjaffray.com/what-does-write-skew-look-like/
  2. SIGMOD'08 | Serializable Snapshot Isolation
  3. EuroSys12 | Write-Snapshot Isolation
  4. https://www.infoq.cn/article/history_transaction_histories
  5. https://www.cockroachlabs.com/blog/serializable-lockless-distributed-isolation-cockroachdb/

https://github.com/ept/hermitage?tab=readme-ov-file

#Database #Transaction