Snapshot Isolation(2) - InnoDB, PostgreSQL
本文主要讨论MySQL，PostgreSQL与Snapshot Isolation的相关实现，包括：
- InnoDB Repeatable Read Isolation的MVCC+2PL的并发控制算法实现
- Serializable Isolation for Snapshot Databases提出Serializable Snapshot Isolation(SSI)的算法以及其在InnoDB上的实现
- PostgreSQL的SSI实现
InnoDB
InnoDB提供Repeatable Read隔离级别（类似于Snapshot Isolation但实际存在差别的），实现方式是MVCC+2PL，该算法与基于时间戳的并发控制算法不同：
InnoDB中每个事务会有一个全局唯一的trx_id，其会维护一个max_trx_id，表示当前未分配的最小trx_id，若新的事务创建，则将其设置为新事务对应的trx_id并递增。
新事务创建后，若其为读写事务，则将自身trx_id加入到全局活跃读写事务链表，同时赋值该链表并构造ReadView用于判断普通读操作的可见性。
事务提交时，其首先将事务中获取到的锁释放（2PL），之后将自身的trx_id从全局活跃读写事务链表删除。
对于普通读操作，即Consistent Nonlocking Reads，其会基于ReadView判断数据的可见性，ReadView的结构如下图所示：
- up_limit_id表示ReadView创建时活跃读写事务中的最小trx_id，若行数据携带的trx_id < up_limit_id，则数据对当前事务可见。
- low_limit_id表示ReadView创建时最小未分配的trx_id，若行数据携带的trx_id > low_limit_id，则表示数据属于该事务创建后的新事务，则数据对当前事务不可见
- 若数据携带的trx_id位于up_limit_id与low_limit_id之间：
- 若其能够在ReadView中链表中找到，除非trx_id是自己本身，否则表示该数据属于与该事务并行运行的活跃事务，对当前事务不见
- 若无法找到，表示在ReadView创建时，该事务已经进行了提交（将自身删除出活跃链表），因此数据对当前事务可见。
对于写操作或者上锁的读操作（如
SELECT FOR UPDATE），其会直接作用在最新数据，并且加锁直至commit阶段后再释放，保证并行事务运行中不会出现write-write conflict
💡 InnoDB的ReadView机制与理论算法中通过timestamp判断可读性不同，其通过trx_id来对数据进行标识，虽然trx_id是递增创建，但是trx_id之间的顺序并不代表事务commit顺序。
这种实现并不满足Snapshot Isolation要求，虽然其通过2PL防止了write-write conflict的出现，但是无法阻止Lost Update的现象，比如对于以下事务执行：虽然txn2的update语句不会与txn1的update语句并行执行（会被写锁阻塞），但是在txn1 commit之后，txn1会释放写锁，之后txn2的update语句得以运行，在InnoDB的读写事务中，读操作会基于事务启动时的快照，而写操作则总是作用于最新数据，因此txn2的update结果会将txn1的update结果覆盖，且其结果是基于txn1之前的快照结果，因此无法等价于txn1 txn2的顺序执行结果。
// txn1
SELECT COUNT FROM t;
update .. based on count
// txn2
SELECT COUNT FROM t;
update .. based on count
txn1 commit
txn2 commit
💡 这里的问题本质是txn1与txn2相互构成了rw-conflict，形成了循环。SSI可以检测出来？
SSI on InnoDB
Serializable Isolation for Snapshot Databases提出Serializable Snapshot Isolation(SSI)在论文中描述了一种在InnoDB上的实现。
SI on InnoDB
为了在InnoDB上支持SSI，该论文首先在InnoDB上支持SI。其采用一种first-committer-wins算法，修改思路大致为在获取写锁时检查对应行是否在事务启动后有一个新的提交，若有则将事务abort掉。
SSI on InnoDB
SSI算法的思路是检测并行运行的事务之间rw conflict，某个事务同时具有一条rw conflict的出边以及入边，则表示两个连续的rw conflict，是一种dangerours structure，需要中止边上的事务。
SSI的commit伪代码如下：
- SSI通过在事务存储两个标志位：inConflict和outConflict表示该事务是否包含rw conflict的出边和入边。
- commit时在停止事务后若检测到两个标志位同时为true，则abort自己。该操作需要原子，因为读写操作也会检查一个事务的标志位是否同时为true，若为true且该事务已经commit，则会abort自身。
- commit结束后需要保留自身，因为可能存在与该事务并行的其他事务，需要等待至所有与该事务并行的事务都提交了再进行回收。当事务作为最老的活跃事务提交，则会检查比该事务更老的挂起事务是否能够进行回收。
function commit(T):
atomically:
// 标记事务 T 不再运行
T.running = false
// 防止中间有其他事务因为查看到该事务已经结束而abort，需要原子
if T.inConflict and T.outConflict:
abort(T)
return "UNSAFE_ERROR"
// 调用现有 SI (Serializable Isolation) 的提交逻辑，
// 但不释放 SIREAD 锁
execute_existing_SI_commit(T, keep_SIREAD_locks = true)
// 如果 T 持有任何 SIREAD 锁
if T.holds_SIREAD_locks:
// 挂起事务 T，但保留 SIREAD 锁
suspend_transaction(T)
// 如果 T 是最老的活跃事务
if T.is_oldest_active_transaction:
// 清理所有比当前活跃事务更老的挂起事务（且没有与运行中事务并行）
cleanup_suspended_transactions()
rw conflict的发生与真实发生的时间无关，比如可能存在：
- txn1,txn2同时创建，两者基于同一个快照，txn1读a，txn2写a，txn2提交，此时两者构成rw conflict，read先发生，write后发生
- txn1,txn2同时创建，txn2写a，txn2提交，txn1读a，此时两者构成rw conflict，write先发生，read后发生。
SSI总是在rw conflict发生的后者进行记录，因此其需要在read，write操作都进行判断和记录：
读操作会首先通过SIREAD锁记录，之后检查是否存在写操作与当前读操作构成冲突，有两种情况：
正在进行写的事务，通过检查execlusive锁
已经写完数据的事务，通过检查是否存在更新版本的数据
若存在更新版本的数据且其已经提交了，若该事务同时inConflict和outConflict为true，则只能abort自身了
写操作则主要检查SIREAD锁，若满足以下条件之一，则表示存在并行事务与当前事务构成rw conflict
上锁的事务正在运行
上锁的事务已经提交，当其提交时间比当前事务的开始时间大
同理若该事务已经提交且其inConflict和outConflict为true，则只能abort自身了
function read(T, x):
// Acquire SIREAD lock on x
acquire_lock(key=x, owner=T, mode=SIREAD)
// Check for conflicting EXCLUSIVE locks
if exists_conflicting_exclusive_lock(x):
wl.owner.inConflict = true
T.outConflict = true
// Proceed with existing SI read logic
existing_SI_read_logic(T, x)
// Handle new versions of x
for each version xNew of x newer than what T read:
atomically:
if xNew.creator is committed and xNew.creator.outConflict:
abort(T)
return UNSAFE_ERROR
xNew.creator.inConflict = true
T.outConflict = true
function write(T, x, xNew):
// Acquire EXCLUSIVE lock on x
acquire_lock(key=x, owner=T, mode=EXCLUSIVE)
// Check for conflicting SIREAD locks
for each conflicting SIREAD lock rl on x:
if rl.owner.running or commit_time(rl.owner) > begin_time(T):
atomically:
if rl.owner is committed and rl.owner.inConflict:
abort(T)
return UNSAFE_ERROR
rl.owner.outConflict = true
T.inConflict = true
// Proceed with existing SI write logic
existing_SI_write_logic(T, x, xNew)
SSI on PostgreSQL
SI on PostgreSQL
PostgreSQL的Repeatable Read实现了标准的Snapshot Isolation：
- 对于读操作，其可见性判断规则与InnoDB类似
- 对于写操作，其会上锁，但看到数据版本与快照一致，且其应用了First updater wins规则避免了Lost Update。对于一个数据，txn1修改的同时会上锁，后续并行事务的修改会被阻塞：
- 若txn1 commit，则被阻塞事务会被通知事务失败
- 若txn1 abort，则被阻塞事务可将修改作用至快照版本上
SSI on PostgreSQL
Serializable Snapshot Isolation in PostgreSQL在PostgreSQL上实现了SSI，讨论一下其中提到的优化。
Read-Only Optimizations
PostgreSQL SSI针对只读事务进行了优化，其主要基于以下定理：
- 存在txn1→txn2→txn3的dangerous structure且txn1为只读事务，若其涉及到冲突循环，则txn3一定为在txn1开始前的已经commit。
该定理证明不难，因为txn1是只读事务，因此其只能与txn3构成wr conflict。
首先可以直接利用该定理其加强检测避免不必要的false-positive abort，其次PostgreSQL利用其提出了Safe Snapshot，如果一个只读事务被判断为Safe Snapshot，表示其永远不会导致冲突图循环，则可以直接作为SI的运行，避免记录SIREAD锁等开销。
判定原理很简单，当一个只读事务txn1启动或运行时，如果其能够检测不存在txn2→txn3结构，则可以标记为Safe Snapshot。如下图，当只读事务启动时，其可以记录记录前commit的事务以及时间上与其并行的正在运行事务，若在运行过程中，所有并行运行事务commit且没有引入rw conflict，表示不存在txn2→txn3结果，该只读事务可以标记了Safe Snapshot。
对于长时间运行且涉及到读取大量数据的事务，将其运行在Safe Snapshot模式可以极大减少SSI带来的开销，因此PostgreSQL提供了Deferrable Transactions，其确保一个只读事务在Safe Snapshot模式运行：只读事务启动后，会不断检测自己是否可以为Safe Snapshot，若存在txn2→txn3结构，则重启事务，直到为Safe Snapshot再开始运行。
Ref && Related
论文：
- A Critique of ANSI SQL Isolation Levels
- Serializable Isolation for Snapshot Databases
- Serializable Snapshot Isolation in PostgreSQL
MySQL相关：
- mysql-8.0正确性分析
- MySQL Repeatable-Read 的一些误解
- 关于 MySQL Repeatable Read Isolation 常见的三个误区
- MySQL · 引擎特性 · InnoDB 事务系统
SSI相关：