Appearance
事务与并发控制
概念
上一章解决了"怎么找得快"。可数据库不只是给人看的，它还被人同时改。
看一个具体的场景：账户 x 里有 100 元、y 里有 200 元，T1 要把 x 的 50 元转给 y，T2 在另一头统计"x + y 一共多少钱"。T1 做了四步：读 x、写 x（减 50）、读 y、写 y（加 50）。
如果 T2 正好在第三步之后、第四步之前把两个数读走，它读到的是 x = 50、y = 200 —— 总额变成 250，凭空少了 50 元。
这 50 元没有消失，它只是被看到了一个中间状态。这种错误不是"算错了"，是"看到了不该看到的东西"。
于是需要一样东西来定义"什么算一次完整的操作"：
事务（transaction）是一组要么全部生效、要么全部不生效的数据库操作。
它要保证四件事，合称 ACID：
| 字母 | 名字 | 一句话 |
|---|---|---|
| A | 原子性 Atomicity | 全做或全不做，没有"做了一半" |
| C | 一致性 Consistency | 约束在事务前后都成立（转账前后总额不变） |
| I | 隔离性 Isolation | 并发执行的结果，等价于某个串行顺序的结果 |
| D | 持久性 Durability | 一旦提交，断电也不丢 |
原理
一、ACID 各自靠谁实现
这四条不是并列的四个模块，它们对应四套不同的机制：
| 特性 | 主要实现手段 |
|---|---|
| 原子性 | undo 日志（回滚：把改过的值改回去） |
| 持久性 | redo 日志（重做：把没落盘的操作重放一遍） |
| 隔离性 | 锁（悲观）+ MVCC（乐观，读不加锁） |
| 一致性 | 不是某个机制，而是前三者的结果——加上业务自己的约束 |
最后一条常被误解：一致性不是数据库单方面能保证的。它要求"转账前后总额相等"这类规则由应用或约束来写，数据库只负责让 A、I、D 成立。
二、并发会出四种错
按严重程度从重到轻：
| 异常 | 现象 | 例子 |
|---|---|---|
| 丢失更新 | 两个事务改同一个值，后写的覆盖了先写的 | 两人同时读到 100，各加 10，最后是 110 而不是 120 |
| 脏读 | 读到了别人还没提交的数据 | 读到 T1 写完但回滚掉的值 |
| 不可重复读 | 同一事务里同一条记录读两次，值不一样 | 第一次读 100，第二次读 110（中间别人改了） |
| 幻读 | 同一事务里同一个范围查两次，行数不一样 | 第一次查出 3 行，第二次多出 1 行 |
关键在于"读的是不是同一个东西"：
- 不可重复读：同一行的值变了。
- 幻读：多出了新行，或者少了行。
- 丢失更新和脏读：都与"写"有关，一个覆盖、一个读未提交。
三、隔离级别：把四种错分级容忍
隔离越强越安全，但并发度越低。标准（SQL:92）给四档：
| 隔离级别 | 脏读 | 不可重复读 | 幻读 |
|---|---|---|---|
| 读未提交（RU） | 可能 | 可能 | 可能 |
| 读已提交（RC） | 不可能 | 可能 | 可能 |
| 可重复读（RR） | 不可能 | 不可能 | 可能 |
| 可串行化（Serializable） | 不可能 | 不可能 | 不可能 |
读这张表的正确方式是看"每一档消灭了哪一个并发的错"：RD 消除脏读，RR 再消除不可重复读，Serializable 再消除幻读。
一条实践补充：这张表给的是下限。MySQL 的 InnoDB 在 RR 级别上，用 MVCC 让"快照读"看不到新行，又用间隙锁（next-key lock）挡住插入，实际上把幻读也挡掉了。所以"标准说 RR 有幻读"与"MySQL 的 RR 没幻读"并不矛盾——一个说的是最低承诺，一个说的是实际实现。
四、封锁：共享锁与排他锁
| 锁 | 记法 | 允许别人做什么 | 用于 |
|---|---|---|---|
| 共享锁 | S 锁（读锁） | 别人可以再加 S 锁，不能加 X 锁 | 读 |
| 排他锁 | X 锁（写锁） | 什么都不许加 | 写 |
相容矩阵（横为已持有、竖为请求）：
| 已有 \ 请求 | S | X |
|---|---|---|
| 无 | 可 | 可 |
| S | 可 | 不可 |
| X | 不可 | 不可 |
规律一句话：读读相容，其余全排。
五、两段锁协议（2PL）
光有 S/X 锁还不够——加锁解锁的时机也会影响结果。两段锁协议规定的就是这个时机：
- 生长阶段（growing）：只能加锁，不能解锁。
- 收缩阶段（shrinking）：只能解锁，不能再加锁。
- 加锁和解锁的分界点就是"拿到最后一把锁的那一刻"。
2PL 是可串行化的充分条件——只要每个事务都遵守 2PL，结果一定等价于某个串行执行。但它有代价：
- 不保证不死锁。T1 先锁 x 再锁 y、T2 先锁 y 再锁 x，两边各持一把互等 → 循环等待，与 死锁 里的四个必要条件完全对上。
- 并发度被压低：锁越晚放，别人越要等。
（还有个 严格 2PL：事务结束前不释放任何锁。它更强，能顺带避免"级联回滚"。）
六、可串行化判定：优先图
"结果等价于某个串行顺序"是可以机械判定的，方法叫冲突可串行化：
- 列出调度里所有操作的先后。
- 找冲突对：来自不同事务、操作同一个对象、且至少有一个是写。
- 每个冲突对连一条边：先执行的指向后执行的。
- 得到优先图。图无环 ⟺ 该调度冲突可串行化；图有环就不可串行化。
判环就是拓扑排序能不能走完全部结点——和 Warshall 传递闭包 说的是同一件事。
七、MVCC：让"读"不加锁
如果读也要加锁，读多写少的系统会被拖垮。MVCC（多版本并发控制）的思路是：给每行保留多个历史版本，读的时候挑一个"该看到"的版本，不用加锁。
两个必须分清的概念：
| 快照读 | 当前读 | |
|---|---|---|
| 读什么 | 事务开始（或语句开始）时的快照 | 最新已提交的版本 |
| 加锁吗 | 不加锁 | 加锁（SELECT ... FOR UPDATE / LOCK IN SHARE MODE） |
| 谁在用 | 普通 SELECT | UPDATE / DELETE / 加锁查询 |
一个 SELECT 读到的是哪个版本，取决于这个事务的 Read View（读视图）。这就是 RR 级别下"同一个 SELECT 在事务里读两次结果一样"的机制来源。
八、日志：undo 与 redo，以及 WAL
| 日志 | 存什么 | 用来 |
|---|---|---|
| undo 日志 | "这个值原来是多少" | 回滚（原子性）；同时给 MVCC 提供旧版本 |
| redo 日志 | "这个值改成了多少" | 重做（持久性），崩溃恢复时重放 |
WAL（Write-Ahead Logging，先写日志）是一条铁律：
数据页落盘之前，必须先把对应的 redo 日志落盘。
为什么？因为顺序写日志比随机写数据页快得多。事务提交时只要保证日志已落盘就够了，数据页可以慢慢刷回去；万一崩了，重放日志即可。"提交很快"这个体验，本质上是用"先写日志"换来的。
示例
例 1：用优先图判定一个调度（C）
#include <stdio.h>
/* 一个操作：事务号（0 = T1，1 = T2）、对象号（0 = x，1 = y）、是不是写 */
typedef struct { int t, obj, is_w; } Op;
/* 三个调度，都是 6 个操作 */
static Op A[] = {{0,0,0}, {0,0,1}, {0,1,0}, {1,0,0}, {1,1,0}, {0,1,1}};
static Op B[] = {{0,0,0}, {1,0,0}, {0,0,1}, {0,1,0}, {0,1,1}, {1,1,0}};
static Op C[] = {{0,0,0}, {0,0,1}, {0,1,0}, {0,1,1}, {1,0,0}, {1,1,0}};
/* 冲突对连边：不同事务 + 同对象 + 至少一个写 */
static int build(Op *s, int n, int e[2][2]) {
int cnt = 0;
e[0][0] = e[0][1] = e[1][0] = e[1][1] = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (s[i].obj == s[j].obj && s[i].t != s[j].t
&& (s[i].is_w || s[j].is_w)) {
if (!e[s[i].t][s[j].t]) { e[s[i].t][s[j].t] = 1; cnt++; }
}
return cnt;
}
/* Warshall 求传递闭包；对角线出现 1 就说明有环 */
static int cyclic(int e[2][2]) {
int r[2][2];
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) r[i][j] = e[i][j];
for (int k = 0; k < 2; k++)
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
if (r[i][k] && r[k][j]) r[i][j] = 1;
return r[0][0] || r[1][1];
}
static void judge(const char *name, Op *s, int n) {
int e[2][2];
int cnt = build(s, n, e);
printf(" %-12s 冲突边 %d 条（", name, cnt);
int first = 1;
if (e[0][1]) { printf("T1->T2"); first = 0; }
if (e[1][0]) { if (!first) printf(", "); printf("T2->T1"); first = 0; }
if (first) printf("无");
printf("）-> %s\n", cyclic(e) ? "不可串行化（优先图成环）"
: "可串行化（优先图无环）");
}
int main(void) {
printf("交叉执行的两个事务能不能等价于串行？\n");
judge("交错 A", A, 6);
judge("交错 B", B, 6);
judge("T1 整段先跑", C, 6);
printf(" 判据：优先图有环 <=> 该调度不等价于任何一个串行执行。\n");
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
交叉执行的两个事务能不能等价于串行？
交错 A 冲突边 2 条（T1->T2, T2->T1）-> 不可串行化（优先图成环）
交错 B 冲突边 2 条（T1->T2, T2->T1）-> 不可串行化（优先图成环）
T1 整段先跑 冲突边 1 条（T1->T2）-> 可串行化（优先图无环）
判据：优先图有环 <=> 该调度不等价于任何一个串行执行。读法：交错 A 与交错 B 都出现了 T1→T2 和 T2→T1 两条边，成环——说明它们都"两边都想当前面的"，谁也串不成。
例 2：枚举全部交错，看错误从哪冒出来（Python）
C 段只判断"可不可串行化"，但它没说不可串行化的调度到底会算错成什么样。这是另一条路：把 15 种合法交错全跑一遍，用真实数值看结果。
def dw(s):
"""显示宽度：中文算 2 列"""
return sum(2 if ord(c) > 0x2000 else 1 for c in str(s))
def pad(s, w):
return str(s) + " " * max(0, w - dw(str(s)))
def table(head, rows, gap=2):
data = [[str(c) for c in r] for r in rows]
w = [max([dw(head[i])] + [dw(r[i]) for r in data]) + gap for i in range(len(head))]
print(" " + "".join(pad(head[i], w[i]) for i in range(len(head))))
for r in data:
print(" " + "".join(pad(r[i], w[i]) for i in range(len(head))))
def interleavings(progs):
"""枚举所有满足各事务程序序的交错"""
names = list(progs)
out = []
def rec(pc, path):
if all(pc[n] == len(progs[n]) for n in names):
out.append(list(path))
return
for n in names:
if pc[n] < len(progs[n]):
pc[n] += 1
path.append(progs[n][pc[n] - 1])
rec(pc, path)
path.pop()
pc[n] -= 1
rec({n: 0 for n in names}, [])
return out
def conflicts(sched):
"""冲突对 -> 优先图的边（同对象、至少一个写、不同事务、有先后）"""
edges = set()
for i in range(len(sched)):
for j in range(i + 1, len(sched)):
ti, oi, a = sched[i]
tj, oj, b = sched[j]
if oi == oj and ti != tj and (a == "W" or b == "W"):
edges.add((ti, tj))
return edges
def has_cycle(nodes, edges):
"""优先图有环 <=> 拓扑排序排不完所有结点"""
succ = {n: set() for n in nodes}
indeg = {n: 0 for n in nodes}
for a, b in edges:
if b not in succ[a]:
succ[a].add(b)
indeg[b] += 1
ready = sorted(n for n in nodes if indeg[n] == 0)
seen = 0
while ready:
n = ready.pop(0)
seen += 1
for m in sorted(succ[n]):
indeg[m] -= 1
if indeg[m] == 0:
ready.append(m)
ready.sort()
return seen != len(nodes)
X0, Y0, AMT = 100, 200, 50
PROG = {
"T1": [("T1", "x", "R"), ("T1", "x", "W"), ("T1", "y", "R"), ("T1", "y", "W")],
"T2": [("T2", "x", "R"), ("T2", "y", "R")],
}
def run(sched):
mem, reg = {"x": X0, "y": Y0}, {}
for t, obj, op in sched:
if op == "R":
reg[(t, obj)] = mem[obj]
else:
mem[obj] = reg[(t, obj)] + (AMT if obj == "y" else -AMT)
return mem, reg[("T2", "x")] + reg[("T2", "y")]
scheds = interleavings(PROG)
print("=== 1. 全部合法交错里，T2 读到的总额是多少 ===")
print(" 初始 x=%d, y=%d，总额应为 %d；合法交错共 %d 种"
% (X0, Y0, X0 + Y0, len(scheds)))
cnt = {}
for s in scheds:
cnt[run(s)[1]] = cnt.get(run(s)[1], 0) + 1
for total in sorted(cnt):
print(" 读到总额 %-4d 的交错有 %2d 种%s"
% (total, cnt[total], " <-- 算错了" if total != X0 + Y0 else " <-- 正确"))
print()
print("=== 2. 两个算错的交错，逐步展开 ===")
bads = [s for s in scheds if run(s)[1] != X0 + Y0]
pick = [bads[0], [s for s in bads if run(s)[1] == X0 + Y0 + AMT][0]]
for s in pick:
mem, reg = {"x": X0, "y": Y0}, {}
for t, obj, op in s:
if op == "R":
reg[(t, obj)] = mem[obj]
print(" %s 读 %s -> %d" % (t, obj, mem[obj]))
else:
mem[obj] = reg[(t, obj)] + (AMT if obj == "y" else -AMT)
print(" %s 写 %s = %d" % (t, obj, mem[obj]))
print(" -> T2 求和 = %d，正确值是 %d" % (run(s)[1], X0 + Y0))
print()
print("=== 3. 优先图（冲突可串行化判定） ===")
rows = []
for name, s in [("交错 A（上面第 1 个）", pick[0]), ("交错 B（上面第 2 个）", pick[1]),
("T1 整段跑完再跑 T2", [("T1", "x", "R"), ("T1", "x", "W"),
("T1", "y", "R"), ("T1", "y", "W"),
("T2", "x", "R"), ("T2", "y", "R")])]:
e = sorted(conflicts(s))
cyc = has_cycle(["T1", "T2"], e)
rows.append([name, "，".join("%s→%s" % (a, b) for a, b in e),
"有环" if cyc else "无环", "不可串行化" if cyc else "可串行化"])
table(["交错", "优先图的边", "环", "结论"], rows)
print()
print("=== 4. 两段锁（2PL）：把抢锁也画出来 ===")
print(" 约定：只画写事务要的排他锁 X；T1 全程要用到 x 与 y")
locks, held, rows = {"x": None, "y": None}, [], []
plan = [("T1", "R", "x"), ("T1", "W", "x"), ("T1", "R", "y"), ("T1", "W", "y"),
("T2", "R", "x"), ("T2", "R", "y"), ("T1", "U", "x"), ("T1", "U", "y")]
for t, op, obj in plan:
if op == "U":
act, note = "释放 X 锁", "收缩阶段"
locks[obj] = None
held = [k for k in held if k != obj]
elif locks[obj] is None:
act, note = "申请 X 锁 -> 成功", "生长阶段"
locks[obj] = t
held.append(obj)
elif locks[obj] == t:
act, note = "已持有 X 锁", "同一事务不必重复申请"
else:
act, note = "等 %s 释放" % locks[obj], "阻塞，不是空转"
rows.append([t, "%s(%s)" % (op, obj), act, ",".join(held) if held else "-", note])
table(["事务", "操作", "锁动作", "此刻持有", "所处阶段"], rows)
print()
print(" 生长阶段只加锁（T1 的四步 R/W + T2 的两个 R），收缩阶段只解锁（T1 的两个 U）。")
print(" 2PL 保证的是结果可串行化，不保证不死锁：")
print(" 若 T1 先锁 x 再锁 y、T2 先锁 y 再锁 x，两边各持一把互等，就成环")
print(" —— 这与 /os/16-deadlock.md 说的循环等待是同一件事。")
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
=== 1. 全部合法交错里，T2 读到的总额是多少 ===
初始 x=100, y=200，总额应为 300；合法交错共 15 种
读到总额 250 的交错有 3 种 <-- 算错了
读到总额 300 的交错有 10 种 <-- 正确
读到总额 350 的交错有 2 种 <-- 算错了
=== 2. 两个算错的交错，逐步展开 ===
T1 读 x -> 100
T1 写 x = 50
T1 读 y -> 200
T2 读 x -> 50
T2 读 y -> 200
T1 写 y = 250
-> T2 求和 = 250，正确值是 300
T1 读 x -> 100
T2 读 x -> 100
T1 写 x = 50
T1 读 y -> 200
T1 写 y = 250
T2 读 y -> 250
-> T2 求和 = 350，正确值是 300
=== 3. 优先图（冲突可串行化判定） ===
交错 优先图的边 环 结论
交错 A（上面第 1 个） T1→T2，T2→T1 有环 不可串行化
交错 B（上面第 2 个） T1→T2，T2→T1 有环 不可串行化
T1 整段跑完再跑 T2 T1→T2 无环 可串行化
=== 4. 两段锁（2PL）：把抢锁也画出来 ===
约定：只画写事务要的排他锁 X；T1 全程要用到 x 与 y
事务 操作 锁动作 此刻持有 所处阶段
T1 R(x) 申请 X 锁 -> 成功 x 生长阶段
T1 W(x) 已持有 X 锁 x 同一事务不必重复申请
T1 R(y) 申请 X 锁 -> 成功 x,y 生长阶段
T1 W(y) 已持有 X 锁 x,y 同一事务不必重复申请
T2 R(x) 等 T1 释放 x,y 阻塞，不是空转
T2 R(y) 等 T1 释放 x,y 阻塞，不是空转
T1 U(x) 释放 X 锁 y 收缩阶段
T1 U(y) 释放 X 锁 - 收缩阶段
生长阶段只加锁（T1 的四步 R/W + T2 的两个 R），收缩阶段只解锁（T1 的两个 U）。
2PL 保证的是结果可串行化，不保证不死锁：
若 T1 先锁 x 再锁 y、T2 先锁 y 再锁 x，两边各持一把互等，就成环
—— 这与 /os/16-deadlock.md 说的循环等待是同一件事。四条结论：
- 15 种交错里只有 10 种是对的：3 种读到 250、2 种读到 350。"并发执行有 1/3 的概率算错" 这句话，比"并发会有问题"具体得多。
- 两种错的方向相反：250 是读到了"x 已扣、y 未加"；350 是读到了"x 未扣、y 已加"。同一个中间状态，从两头看都能出错。
- 两个错掉的交错都被优先图抓了出来：它们各自含
T1→T2与T2→T1两条边，成环；而"T1 整段跑完再跑 T2"只有一条边，无环。 - 2PL 把错误挡在门外，代价摆在明面上：T2 的两个读全程在等。隔离是靠让别人等换来的，这就是隔离级别越高并发越低的根源。
考点
考点
1. ACID 与实现手段的对应（必须能对上号）
| 特性 | 手段 |
|---|---|
| 原子性 A | undo 日志（回滚） |
| 持久性 D | redo 日志（重做） |
| 隔离性 I | 锁 + MVCC |
| 一致性 C | 前三者的结果 + 业务约束（不是单独机制） |
2. 四类异常与四级隔离的对照
| 隔离级别 | 脏读 | 不可重复读 | 幻读 |
|---|---|---|---|
| 读未提交 RU | 可能 | 可能 | 可能 |
| 读已提交 RC | 不可能 | 可能 | 可能 |
| 可重复读 RR | 不可能 | 不可能 | 可能（标准下限） |
| 可串行化 | 不可能 | 不可能 | 不可能 |
不可重复读 vs 幻读：前者是同一行的值变了，后者是同一个范围里多出/少了行。
3. 锁相容矩阵
读读相容，其余全排。 S 与 S 可共存，S 与 X、X 与 X 都不行。
4. 两段锁（2PL）
- 生长阶段只加锁，收缩阶段只解锁。
- 是"可串行化"的充分条件，不是必要条件（有些可串行化调度不满足 2PL）。
- 不保证不死锁——只保证"死锁了也不会算错"。
- 严格 2PL：事务结束前不释放任何锁（避免级联回滚）。
5. 冲突可串行化的三步判定
① 找冲突对（不同事务 + 同对象 + 至少一个写）；② 按先后连边；③ 看优先图有没有环（拓扑排序 / Warshall 传递闭包）。
6. 快照读与当前读
| 快照读 | 当前读 | |
|---|---|---|
| 加锁 | 不加 | 加 |
| 语句 | 普通 SELECT | UPDATE / DELETE / FOR UPDATE |
MVCC 只对快照读免锁——UPDATE 一定读到最新已提交版本。
7. WAL 与崩溃恢复
数据页落盘前，redo 日志必须先落盘。 提交时只保证日志落盘就够了。崩溃后：redo 重放已提交的，undo 回滚未提交的。
8. 易错点清单
- 认为隔离级别是"四级台阶，越高越好"：越高并发越低，实践中 RC 用得非常广。
- 认为 2PL 能避免死锁：不能，它只是把"结果错"换成了"可能卡住"。
- 把"可串行化"与"串行执行"画等号：可串行化说的是"等价于某个串行顺序"，物理上仍并行。
- 混淆"不可重复读"与"幻读"：一个是值变了，一个是行数变了。
- 以为 MVCC 让所有读都不加锁：当前读要加锁。
- 弄反 undo / redo 的用途：undo 管回滚，redo 管重做。
- 忽略"标准说 RR 有幻读"这个措辞：它说的是下限，不是实现。
小结
- 事务是"全做或全不做"的一组操作；ACID 里 A 靠 undo、D 靠 redo、I 靠锁与 MVCC，C 是三者加起来的结果。
- 并发会带来丢失更新、脏读、不可重复读、幻读四种错；四级隔离级别就是"容忍其中哪几种"的分档。
- 可串行化可以机械判定：连冲突图，看有没有环。
- 隔离不是免费的：2PL 让并发度下降，还可能死锁；MVCC 用多版本把"读"从锁里解放出来。
- WAL 是性能与安全的交换点：先写日志，提交就快，崩了能重放。
回到主线：这一章讲的"资源共享 + 并发访问 + 加锁等待"，正是 操作系统 里那套同步互斥机制的应用层版本——信号量换成了锁，临界区换成了事务，P/V 的等待队列换成了锁等待队列。区别只有一处：数据库要保证的是"结果等价于串行"，而不只是"不互相踩"。
到这里，"单台机器上怎么把数据管好"讲完了。下一章换个方向：一台机器不够用了怎么办——并行与多核。
下一篇：并行与多核
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。