Eswaran 1976 — 串行化与谓词锁的源头

是什么

这篇 1976 年的论文回答一个看似简单的问题：多个人同时改一个数据库，怎么算”改对了”？ 它给出的答案叫串行化（serializability）——只要并发执行的最终结果等价于”某种一个一个排队执行”的结果，就算对。

日常类比：一群人合编一份共享 Excel。最稳的做法是排队，一人改完下一个再来；但太慢。允许大家同时编辑，怎么保证不出乱子？这篇论文说：“只要事后能找到一种排队顺序让结果跟你们并发改的结果一模一样，就 OK。”

换句话说：并发可以乱跑，只要外人看不出来就算合格。这条标准既能容忍并发提速，又给”合格”画了清晰的红线。

围绕这条标准，论文还顺手定义了事务（transaction）、两阶段锁（2PL）、谓词锁（predicate lock）。它是后来 40 年所有”事务隔离级别”讨论的源头。

为什么重要

不理解这篇，下面这些事都没法解释：

为什么数据库教材必讲 ACID 中的 I（Isolation），所有讨论都从这里出发
为什么 PostgreSQL / MySQL 都有”可串行化”这个最严级别——名字直接来自这里
为什么并发控制学了一大堆术语（脏读 / 不可重复读 / 幻读），背后只有一个真目标
为什么 Spanner、CockroachDB 推销自己时第一句话都是”Strict Serializable”
为什么”幻影问题”作为一个独立现象被人反复提起——它就是这篇定义出来的

核心要点

论文把”并发执行该长什么样”拆成 三个层面：

事务是原子单位：一组读写要么全做、要么全不做。类比：去 ATM 取钱——“扣余额”和”吐钞票”必须捆在一起，不允许只做一半。
串行化是正确性标准：N 个事务并发跑，只要存在一种串行顺序（T1→T2→T3 或 T2→T1→T3 ……）能产生相同结果，就算正确。类比：菜端上桌后，能解释成”先炒 A 再炒 B”或”先炒 B 再炒 A”都行，但不能解释成”两道菜各炒了一半”。
两阶段锁（2PL）保证串行化：每个事务先只加锁不放锁（生长期），到某一刻停止加锁、然后只放锁不加锁（收缩期）。论文证明：所有事务遵守这个纪律 → 任何并发调度都串行化。

加上谓词锁——锁不是锁某条记录，而是锁”满足某个条件的所有记录”——四件套就齐了。

实践案例

案例 1：什么调度算”串行化”

两个事务转账：

T1: 读 A → 写 A-100 → 读 B → 写 B+100
T2: 读 A → 写 A-50  → 读 C → 写 C+50

并发交错跑出某个最终状态。问：这个状态合法吗？答：如果它等于 “T1 全做完再做 T2” 或 “T2 全做完再做 T1” 的结果，就合法。两个串行顺序里有一个对得上即可。

注意”串行化”不挑串行顺序——只要存在任何一个能解释结果的顺序就行。这个”存在性”思想后来被推广成”调度图无环”的形式化判定。

案例 2：2PL 怎么落地

T1: lock(A) → 读 A → 写 A → lock(B) → 读 B → 写 B → unlock(A) → unlock(B)
        ↑↑ 生长期：只加锁                    ↑↑ 收缩期：只放锁

只要 T1 不在放过锁之后再去加新锁，并发跑也安全。反例：

T1: lock(A) → 写 A → unlock(A) → lock(B) → 写 B → unlock(B)

这里 T1 释放 A 后又加新锁——违反 2PL，可能出现 T2 看到中间不一致状态。

案例 3：谓词锁解决”幻影”

-- T1 想确认"工资 > 10000 的员工有几人"
SELECT COUNT(*) FROM emp WHERE salary > 10000;
-- T2 同时插入一条 salary=12000 的新员工
INSERT INTO emp VALUES ('alice', 12000);

记录锁锁不住”还不存在的记录”。论文提议：T1 不锁某些行，而是锁住谓词 salary > 10000；T2 想插的记录满足这个谓词 → 冲突，必须等。这就是 predicate lock，解决了”幻影读”问题。

逐部分解释：

普通行锁锁的是”现存这条记录”——T1 锁不到”将来才会存在的 alice”
谓词锁锁的是”满足条件的整片空间”——空间里还没有的元素将来插入时也会被拦下
代价：判断两个谓词是否冲突很贵（需要做布尔逻辑求交），所以工业界基本退化成”索引区间锁”近似

踩过的坑

2PL 是充分但不必要：遵守 2PL 一定串行化，反过来不一定。也就是说有些调度本身串行化，2PL 却拒绝它——为简单和可判定付出的代价。
2PL 会死锁：两个事务互相等对方的锁是经典死锁。论文承认这点，提议用超时或检测来打破。后来这成了所有 2PL 数据库的标配苦差。
谓词锁理论好看，实现非常贵：判断”两个谓词是否冲突”等价于布尔可满足性（SAT），一般是 NP-hard。所以工业界普遍退化成更粗的”键范围锁 / 索引区间锁”近似它。
混淆”一致性”和”串行化”：论文里”consistency”指数据满足应用约束（比如余额≥0），“serializability”指调度合法。后人常把两者搅在一起，吵架时定义不一样就鸡同鸭讲。

适用 vs 不适用场景

适用：

OLTP 数据库（PostgreSQL / MySQL / Oracle / SQL Server）默认就用 2PL 或它的变种
短事务、读写比适中、强一致性要求的系统（银行 / 订单 / 库存）
需要严格 ACID 的场景
教学场景下作为”正确性的第一原理”——比直接上 MVCC 好讲得多

不适用：

高并发只读分析（OLAP）→ 用 MVCC + 快照隔离更划算
跨地域分布式 → 单纯 2PL 太慢，需要 Paxos / Raft 协调
最终一致性可接受的场景 → 用 crdt-json / Dynamo 风格系统
长事务（数小时）→ 持锁太久阻塞别人，改用 Saga / 补偿事务
移动端 / 边缘断网协作 → CRDT 或 Operational Transform 路线更合适

历史小故事（可跳过）

1971 前后：IBM 圣何塞实验室在做 System R（关系数据库的第一个原型）。Jim Gray 等人在解决”多用户并发改同一个表”问题，发现没有清晰的正确性定义。
1976 年：Eswaran、Gray、Lorie、Traiger 把团队几年里的内部讨论写成 9 页论文发到 CACM，定义了串行化、2PL、谓词锁。这是事务理论的”创世纪”。
1981 年：Jim Gray 在《The Transaction Concept》里把这套思想推广到操作系统、网络协议——事务从”数据库专属”变成通用计算抽象。Gray 后来因此拿了图灵奖。
1990s：Phil Bernstein 等人把串行化的形式化做完整（冲突可串行化、视图可串行化），写进所有数据库教材。Berenson 等人 1995 又给”中间隔离级别”做了清晰定义。
2008 起：Spanner 把这套搬到全球分布式，靠 TrueTime 实现 External Consistency（比串行化更强）。Calvin、CockroachDB、FoundationDB 等也各自给出现代版回答。

学到什么

正确性需要先被定义——没有”串行化”这个概念之前，并发控制是工程拼凑；定义出来之后，所有方法都被迫向它对齐
理论标准 vs 工程协议是两码事：串行化是目标，2PL 是达成它的一种方法。后来还有 OCC、MVCC、Timestamp Ordering 多种协议，目标都是它
简化往往牺牲完整性：2PL 会拒绝一些其实合法的调度，但因此变得简单可证
预见未来：谓词锁理论上完美却工程上贵，最后被退化到”索引范围锁”。研究里常见这种”理想 → 近似”的演化轨迹
一篇 9 页论文可以塑造一整门学科：现代数据库教材”事务”一章的骨架，几乎全部来自这篇

关联

codd-1970 —— 关系模型给”事务在改什么”提供了清晰的对象
ingres-1976 —— 同年 Berkeley 关系数据库实现，靠这套并发理论才能多用户跑
paxos —— 分布式版本的”如何让所有节点同意一个顺序”，本质也是串行化
spanner —— 用 TrueTime 把串行化推到全球尺度，目标更严的 External Consistency
crdt-json —— 走另一条路：放弃强一致性，换并发友好与最终一致性
lamport-1978 —— 逻辑时钟提供了”事件顺序”的抽象，与串行化理论互补
hoare-logic —— 串行执行的正确性证明工具，和并发正确性形成对照

反向链接

aries-1992 —— ARIES 1992 — 数据库崩溃后怎么把账目对回来
bernstein-1981-cc —— Bernstein 1981 并发控制综述 — 把分布式数据库的 20+ 算法整成两条主线
codd-1970 —— Codd 1970 — 关系模型奠基
crdt-json —— CRDT JSON — 协同编辑 JSON 数据结构
gray-1981-transaction —— Gray 1981 — 把”事务”提升为通用抽象
hoare-logic —— Hoare Logic — 把”程序对不对”变成”数学证明对不对”
ingres-1976 —— INGRES 1976 — Berkeley 平行实现的关系数据库
lamport-1978 —— Lamport 1978 — 分布式系统里没有”绝对的同时”
paxos —— Paxos — 分布式共识算法
spanner —— Spanner — 全球分布式 SQL 数据库