可串行化

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

若 $T_1$ 写 x 后 $T_2$ 读 x，产生边 $T_1\to T_2$；若又有另一个对象导致 $T_2\to T_1$，形成环，调度不冲突可串行化。可串行化不自动保证事务按现实时间顺序出现；严格可串行化还要求尊重非重叠事务的实时先后。它也不独自保证可恢复性、无级联回滚或持久性。

若 precedence graph 无环，任一拓扑序都给出一个冲突等价的串行调度。反之，blind write 可能使某历史在 view 意义下可串行化，却因保守的写写冲突边而不冲突可串行化；因此常用的无环判据刻画的是 conflict serializability，而不是所有可能的可串行化定义。

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

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

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