Lec 10 索引并发控制

0. 学习地图

这讲的核心问题只有一个：如何让多个 worker 同时访问同一个索引，又不把数据结构弄坏？

结构 / 场景	难点	常见解决方式
Hash Table 查找 / 插入	多个线程会竞争同一个 bucket	按表 / 页 / 槽位加 latch
B+Tree 查找 / 更新	遍历可能和 split / merge 并发发生	Latch crabbing / coupling
叶子页范围扫描	遍历不再是严格自顶向下	sibling latch 需要 no-wait 协议

复杂度速查

记号：

n = 索引中的 entry 数
f = B+Tree 的有效 fanout
h = 树高，因此 h = O(\log_f n)

结构 / 操作	期望复杂度	最坏情况 / 关键注意点
Hash table lookup	`O(1)`	极端冲突下可能到 `O(n)`
Hash table insert	均摊 `O(1)`	resize 需要全局协调
B+Tree 点查	`O(h) = O(\log_f n)`	每层都要拿一次 latch
B+Tree 插入 / 删除	常见情况 `O(h)`	split / merge 最多可向上级联 `O(h)` 层
叶子页范围扫描	`O(h + \#leaf\_pages\_touched)`	no-wait 失败会导致重试

1. 正确性：Locks vs. Latches

DBMS 里的并发正确性有两个层面：

逻辑正确性（Logical correctness）：worker 能不能看到它应该看到的数据。
物理正确性（Physical correctness）：数据结构内部表示是否仍然合法。

这讲讨论的是 latch，不是事务层的 lock。

维度	Locks	Latches
保护对象	数据库的逻辑内容	DBMS 的内存数据结构
持有者	事务	worker / 线程
持有时间	整个事务期间	一次操作的临界区
模式	shared / exclusive / intention 等	通常只有 read / write
死锁处理	检测与回滚	主要靠编码纪律避免

Latch 模式

Read latch：允许多个 reader 同时持有。
Write latch：独占访问，不能与任何读写并存。

2. Latch 的设计目标与实现

设计目标

一个好的 latch 应该：

占用元数据小
在无竞争时足够快
尽量分散管理
避免昂贵的系统调用

常见实现

Test-and-Set Spin Latch

无竞争时非常快。
通常只需要一个原子指令。
竞争激烈时会不停自旋，带来缓存抖动。
不够 cache-friendly，也不够 OS-friendly。

Compare-and-Swap（CAS）

很多 latch 的基础原语是 CAS：

比较内存位置 M 是否等于期望值 V
如果相等，就写入新值 V'
否则失败并重试或退让

Blocking OS Mutex

编程模型简单。
高竞争下比纯自旋更稳妥。
但 lock / unlock 成本更高，可能需要进入内核。

Reader-Writer Latch

支持多 reader 并发。
很适合树结构中的读遍历。
代价是更多元数据和队列管理。
还要处理 reader / writer 饥饿问题。

3. Hash Table 的 Latching

Hash table 的并发控制相对简单，原因是：

worker 的访问路径更单一
通常一次只会碰一个 page 或 slot
访问方向更统一，因此更不容易死锁

如果需要 resize，通常会在整个表上拿一个 global write latch。

不同粒度

方案	思路	优点	代价
Global latch	整个表共用一个 latch	最简单	并发度最差
Page / block latch	每个页 / bucket block 一个 latch	实现与并发较平衡	热页会形成竞争
Slot latch	每个 slot 一个 latch	并发度最高	元数据和管理成本更高

实践结论

想要实现简单，就用更粗粒度。
热 bucket 多的时候，用 page/slot latch 更合适。
resize 要尽量少做，因为它往往意味着全局临界区。

4. 为什么 B+Tree 更难

B+Tree 并发访问同时要处理两类问题：

两个 worker 同时修改同一个节点
一个 worker 在遍历，另一个 worker 正在 split / merge

第二类问题决定了 B+Tree 的 latch 协议要比 hash table 精细得多。

5. Latch Crabbing / Coupling

标准做法是 latch crabbing：

先锁住 parent。
再锁住 child。
如果 child 已经“安全”，就释放 parent。

Safe Node

所谓 safe node，就是本次更新不会引起结构变化的节点：

插入时：节点不会 split。
删除时：节点不会 merge / underflow。

如果一个节点最多能容纳 m 个 key，那么常见教材里的 safe 条件可以写成：

\[ \text{Insert safe} \iff \text{occupancy} < m \]

\[ \text{Delete safe} \iff \text{occupancy} > \left\lceil \frac{m}{2} \right\rceil \]

真实系统里可能会用 merge threshold 代替“半满”规则，但本质相同：safe 就是 这一步不会触发结构变化。

查找协议

对于 Find：

从 root 开始。
给 child 加 read latch。
释放 parent。
重复直到 leaf。

这样 reader 不需要一直把整条路径都锁住。

复杂度：

\[ O(h) = O(\log_f n) \]

因为 worker 只会走一条 root-to-leaf 路径。

插入 / 删除协议

对于写操作：

从 root 往下，按需获取 write latch。
到达 child 后判断它是否 safe。
如果 child safe，就释放祖先节点上的 latch。
只保留那些对 split / merge 仍然必要的 latch。

这是更保守但最稳妥的版本。

常见情况下它的复杂度仍然是：

\[ O(h) \]

但最坏情况下，split / merge 可以一路级联到 root，因此结构修改本身也可能达到 O(h)。

6. 更好的 B+Tree Latching

课上专门指出一个瓶颈：很多更新一开始就会对 root 加 write latch。

但现实里，大多数 insert / delete 其实只改 leaf，并不会真的触发 split / merge。

乐观协议

因此可以采用两阶段思路：

先像查找一样，用 read latch 一路往下。
到叶子后再获取 / 升级成 write latch。
如果 leaf 是 safe 的，就直接完成。
如果 leaf 不 safe，就释放并重启，改用保守的写锁协议。

这样能明显减少 root write latch 的争用。

可以把乐观协议理解成：

常见情况：只走一次 root-to-leaf，约 O(h)
猜错时：先走一次读路径，再重走一次写路径，渐进复杂度仍是 O(h)，但路径代价大约接近 2h

7. 叶子页扫描

前面的遍历都是 自顶向下。但 range scan 会从一个 leaf 横向走到 sibling。

这会带来新问题：

T1 可能在删除时持有某个 leaf 的 write latch
T2 可能持有 read latch，并想横向走到 sibling
如果 sibling latch 只能傻等，就可能形成死锁

必须遵守的规则

leaf sibling 的 latch 获取必须支持 no-wait 模式。

如果拿不到下一个 sibling 的 latch：

不能无限等待
应该重启、放弃，或者按数据结构允许的方式恢复

因为 latch 一般不像 lock 那样有完整的死锁检测与恢复机制。

如果第一次定位之后还要继续横向扫描 k 个 leaf page，那么代价大致是：

\[ O(h + k) \]

这里还没有把 no-wait 失败后的重试算进去。

8. 代价总结

操作	Latch 模式	路径 / 时间代价	主要风险
Hash table lookup	page/slot latch	期望 `O(1)`	hot bucket 竞争
B+Tree search	自顶向下 read latch	`O(\log_f n)`	只要不横向走，一般不会死锁
B+Tree insert/delete	保守 crabbing	常见情况 `O(\log_f n)`	split / merge 级联
B+Tree insert/delete	先乐观再回退	常见情况 `O(\log_f n)`	leaf 不 safe 时需要重启
Leaf range scan	read latch + no-wait sibling	`O(\log_f n + k)`	如果允许等待 sibling，会死锁

9. Write-Set 纪律

对于 B+Tree 写操作，worker 会维护一个私有的 write-set 来记录本次修改过的节点。

修改过的节点上的 write latch 要一直持有到操作结束。
不能把“做了一半”的结构更新暴露给别的线程。
如果后续拿不到需要的 write latch，就根据 write-set 回滚，并释放全部 latch。

这是把“物理正确性”真正落实到代码里的关键规则。

10. 最终总结

Latch 负责保护物理结构，lock 负责保护逻辑数据。
Hash table 的并发控制更简单，因为访问模式更规则。
B+Tree 的核心协议是 latch crabbing，关键概念是 safe node。
乐观树遍历很重要，否则 root write latch 很快会成为瓶颈。
范围扫描必须使用 no-wait sibling 协议，否则迟早会遇到死锁。