可串行化

可串行化把交错历史投影成事务之间的先后约束：只要存在某个串行次序能产生相同观测效果，并发执行就没有暴露不可解释的中间状态。冲突可串行化用读写冲突构造 precedence graph，环表示事务先后要求自相矛盾。它允许所选串行次序违背现实完成时间，所以与严格可串行化不同。

设初始 $x=0$，调度为 r1(x)->0; r2(x)->0; w1(x,1); w2(x,1); c1; c2。两个事务都想把读值加一。由 $r_1$ 先于 $w_2$ 得 $T_1\to T_2$，由 $r_2$ 先于 $w_1$ 得 $T_2\to T_1$，形成环；任一串行执行都应最终得到 2，而该调度得到 1。环直接指出两个事务都试图排在对方之前。

再看 blind write：w1(x,1); w2(x,2); w1(x,3); c2; c1 没有任何读，最终写者为 $T_1$，所以与串行次序 $T_2,T_1$ 视图等价。但第一次 $w_1$ 产生 $T_1\to T_2$，第二次 $w_1$ 又产生 $T_2\to T_1$，它不冲突可串行化。两种判据的差别不是图算法出错，而是采用的等价关系不同。

可串行化还不自动给出恢复性。例如 w1(x,1); r2(x)->1; c2; a1 的冲突图只有 $T_1\to T_2$，但读者已提交后写者中止，仍然是不可恢复的调度。串行等价、提交依赖与持久性需要分别证明。严格可串行化另外要求保留不重叠事务的实时先后。

冲突约束无环时，其传递闭包构成严格偏序理路偏序Partial order · Partially ordered set满足自反、反对称和传递性的关系。；拓扑排序把它扩展为串行全序。两阶段锁与时间戳排序可直接约束该图，MVCC理路多版本并发控制Multiversion concurrency control · MVCC · 多版本并发控制机制通过保留多个已提交版本和显式可见性规则协调事务读写的并发控制框架。则保存多个版本并用可见谓词选择读版本；它是一类实现机制，不是可串行化的同义词。

乐观并发验证理路乐观并发验证Optimistic concurrency control · OCC · 串行提交验证以固定快照和私有写集执行事务，在一个原子步骤内验证所有外部读再发布，证明按提交顺序的串行见证并暴露拆开验证的竞态。提供另一种可逐事件执行的充分机制：事务先在固定快照上计算，在一个原子入口内核对全部外部读依据并发布私有写，成功事务按提交顺序得到串行见证。检查与发布若拆开，两笔旧决定都可能获准；允许盲写按提交序覆盖也不等于采用SI的写写提交规则。

快照隔离理路快照隔离Snapshot isolation · SI让事务读取开始时一致快照，并以先提交者获胜规则排除并发同项写入的隔离级别。让事务读取开始时的一致快照，并以 first-committer-wins 排除并发同项写入，却允许 write skew：两个事务读取对方将覆盖的旧版本、分别写不同数据项时，会形成双向读写反依赖环。完整历史与约束违反由 SI 专页承接，本页保留串行等价与图无环判据。

与线性一致性理路线性一致性Linearizability每次操作可放置在调用与返回之间的单点，使历史等价于满足实时顺序的顺序规范。一样尊重非重叠事务实时顺序的版本称为严格可串行化；原子提交、持久性和可恢复性仍需日志与两阶段提交理路两阶段提交Two-phase commit · 2PC协调者先收集准备结果再统一决定提交或中止的原子提交协议。等独立协议。