问题

先引入两个概念：读偏序、写偏序
读偏序：在一个读事务执行期间，另一个事务的写破坏了自己的读约束
写偏序：两个写事务并发期间，都满足了自己的约束，但两个事务提交的结果却破坏了彼此的约束
可串行化隔离级别（SSI）主要解的是写偏序问题，或者更通俗地讲，解的是两个事务串行执行结果与并行执行结果不一致问题。
举例：一个表有 1，2 两行数据，事务 t1 update 1 -> 2，并发事务 t2 update 2 -> 1，则串行执行有两种可能结果：

t1 -> t2 表中数据为 2，2 （t1 读 t2 的写结果并做写操作）
t2 -> t1 表中数据为 1，1 （t）
但并发执行的结果可能是 2，1。
当发现这种串行化冲突时（两个事务串行执行结果与并行执行结果不一致），SSI 级别会检测这种冲突，并让其中一个事务回滚

解串行化问题的理论

三种读写依赖关系

在并发写的场景下存在以下三种依赖关系，其中 mvcc 保证了 ww 、wr 依赖不冲突，但保证不了 rw 不冲突：
写写依赖（ww）：当存在同一个对象上 t1 -> t2 t1 先读写，t2 后读写时（t2 写写依赖 t1），不导致冲突
写读依赖（wr）：当存在同一个对象上 t1- > t2 t1 先读写，t2 后读时（t2 写读依赖 t1），不导致冲突
读写依赖（rw）：当存在同一个对象上 t1 -> t2 t1 先读，t2 后写时（t2 读写依赖 t1），可能导致冲突
第三种依赖导致冲突发生时，一定存在 t1-> t2 -> t3 这样的序列，比如最简单上面问题中的例子： t1 （rw）-> t2 （rw）-> t1 这种序列，t1 读到 1， t2 写 2->1，t1 再写 1->2 时未将 2->1 改为 2 -> 1 -> 2，这时 t0 提交，t1 再提交，就达不到 t1 把所有1 改为 2 的目的（同样 t2 读不到 t1 写的 2，它只将 2->1，没有1 ->2->1，达不到2全改为1的目的）， t1 (rw)-> t2 (rw)-> t3 这种序列叫 危险结构（a (rw)-> b 指的是 b 依赖 a，a 是读，b 是写，b 读写依赖 a）。

但出现 t0 读写依赖 t1 读写依赖 t2 时不一定会冲突，比如 t0 -> t1 -> t2，t0 只读不写，而在 t0 拿 snapshot 时 t2 还未提交，那么 t0 就应该读不到 t2 的结果，这时并不冲突。

读写依赖和危险结构的检测

对于读写依赖的检测，需要在读时和写时都做判断：
读时，检查有没有更新版本数据，如果有就存在 rw 依赖。
写时，检查有没有读操作做过的 SIREAD 标记，如果有就存在 rw 依赖。
为了让后续读写能检查到 rw 依赖，需要在事务上做个标记，t1 (rw)-> t2 时，在 t1 上标记 outConflict = true，t2 上标记 inConflict = true
在检查到 rw 依赖时，要判断是否存在危险结构，如果存在，就需要终止自己这个事务：

如果读时发现 tself (rw)-> t2，且 t2 已经提交了，并且有 t3 读写依赖了 t2（ t2 (rw)-> t3）则 abort 掉自己（因为 t2 已经 commit，不可能再 abort t2）
如果写时发现 t1 (rw)-> tself（t1 上有 SIREAD标记），且 t1 已经提交了，并且 t1 读写依赖了 t0 （t0 (rw)->t1）则 abort 掉自己（因为 t1 已经 commit，不可能再 abort t1）

在事务提交时，如果发现 t1 (rw)->tself (rw)-> t2，则 tself 也要 abort

危险结构检查总结

读时检查 tself (rw)-> t1 (rw)-> t2
写时检查 t1 (rw)-> t2 (rw)-> tself
提交时检查 t1 (rw)-> tself (rw)-> t2

pg 的理论优化

1、当 t1 是只读事务时，t1->t2->t3 t3 已经提交后t1 才获取 snapshot，才可能成环（因为它是只读的，能成环一定是读到了已经提交事务的写入），t3 未提交不会成环
2、引入 BEGIN TRANSACTION READ ONLY, DEFERRABLE 命令，可以让这个只读事务拿快照锁定事务区间以后等所有并行事务都结束才真执行。如果这个区间中又出现了rw依赖，则要重拿快照，重新锁定区间，这样保证了没有并行事务。

pg 的 SSI 实现

pg 引入谓词锁概念，对应于理论中的 SIREAD 锁
谓词锁有三种级别行级 -> 页级 -> 表级。
默认条件下，当一个页上有两个行级谓词锁时，就升级为页谓词锁，当表上有32个页锁或行锁时，就升级为表谓词锁。
谓词锁的事务状态存在 SERIALIZABLEXACT 状态体中，在事务提交后依然存在，当SLRU 满时，无法再添加事务状态时，会触发 summary，清理很老的 SERIALIZABLEXACT，老的已提交事务共用 OldCommittedSxact 这个结构体，下文中 tsummary 就表示这些已提交的事务。

读操作

对于读操作，对于安全快照，自己只读，t2 之后没有事务，或它们都在自己获取 snapshot 之后，则不会冲突。
当发现 t2 写在自己 tself 之后 (tself (rw)-> t2)，则比较：

tself 回滚的情况

1、自己不是只读，且有 tself->t2->t3 则可能构成危险结构
2、自己是只读，且 t3集合中最小的commit事务（或 tsummary）在自己获取快照前提交，则构成危险结构
3、无论自己是否只读，如果存在 t1（或 tsummary）->tself-> t2，则构成危险结构

t2 回滚的情况

1、tself->t2->tsummary，且 t2 未提交则标记 t2 DOOMED（t2 在 precommit 时会发现并回滚），如果t2 提交了，则回滚自己

写操作

tself 回滚的场景

1、t1-> tself -> t2 t2 已经提交，或属于 summary 事务
2、t2 在 prepare 提交阶段，t1 和 tself 要么没提交，要么提交在 t2 之后，这时如果 t1 是写则冲突，t1 是读但获取快照在 t2 提交之后也冲突
3、t0 -> t1 -> tself，t0 未提交或在 tself 之后提交，这时t0 是写事务，则冲突，t0 是读事务但获取快照比 tself 晚，则冲突