UCB CS186 Fall 2024 — 数据库内核阅读路线

待复核

是什么

这是加州伯克利 CS186 2024 秋季数据库课的阅读路线速记：把「会写 SQL」的人带到「能做存储/并发/恢复设计决策」的层面。日常类比：你会开车（SQL），这门课教你看导航（查询器）和发动机（页、索引、日志）——知道何时加档、何时降速，避免在高峰路段硬踩油门。

路线按五层展开：磁盘页 → 索引 → 执行 → 并发 → 崩溃恢复。读表不是论文全集，而是「先建立共同词汇，再按作业把每一层动手做一遍」的地图。

为什么重要

不理解这张读表，下面这些事都没法解释：

为什么同一条 SQL，换引擎后延迟差一个数量级（B+Tree vs LSM 写放大不同）
为什么「读到旧数据」有时合法、有时是 bug（隔离级别与可见性规则）
为什么 crash 后数据没丢，但恢复要跑几分钟（WAL 与 checkpoint 边界）
为什么索引、日志、buffer manager 交界最容易出事故（三层各自正确仍可能整体错）

核心要点

页与索引像书架：磁盘按 Page（固定大小块，常 4–16KB）读写；B+Tree 像带目录的书架——叶子有序且常串成链表，范围扫描友好。二级索引只存「定位器」（tuple locator），还要回表取完整行。类比：目录告诉你哪一层哪一格，还得再走一趟拿书。
并发像排队规则：2PL（两阶段锁）先拿锁再干活、结束才放——安全但热点会堵；MVCC（多版本）让读看旧快照、写造新版本——读写少互堵，但长事务会堆「过期版本」要回收。类比：2PL 是单间更衣室；MVCC 是每人拿一份复印件。
恢复与执行分家：ARIES 是崩溃恢复框架（分析日志 → 重做 → 撤销），靠 WAL（Write-Ahead Logging：先写日志再改页）和 LSN（Log Sequence Number，日志序号）保证重放幂等；它不是锁协议，不要和 2PL/MVCC 混谈。执行侧：连接顺序与代价模型决定计划，统计信息过期会选错索引。类比：ARIES 是黑匣子回放；优化器是按油耗选路线。

实践案例

案例 1：账本区间查询加联合索引

-- 慢：只有主键，按账户扫再过滤日期
SELECT * FROM ledger WHERE acct_id = 42 AND ts BETWEEN '2024-01-01' AND '2024-01-31';
-- 快：联合索引让范围变成顺序叶扫描
CREATE INDEX idx_ledger_acct_ts ON ledger(acct_id, ts);

逐部分解释：

谓词是「等值 + 范围」→ 最左前缀 (acct_id, ts) 能吃满
B+Tree 叶子按键有序，扫描变成顺序读，少随机 I/O
若 checkpoint 很久没做，crash 后重放 WAL 仍可能很久——索引加速查询，不缩短恢复

案例 2：热点库存更新缩短事务

-- 坏：长事务里又读又算又写，行锁/版本拖很久
BEGIN; SELECT qty FROM stock WHERE id=1 FOR UPDATE; /* 调外部定价 API */ UPDATE stock SET qty=qty-1 WHERE id=1; COMMIT;
-- 好：先算完，再开短事务只改一行
-- price = call_pricing_api(...);
BEGIN; UPDATE stock SET qty=qty-1 WHERE id=1 AND qty>0; COMMIT;

逐部分解释：

热点行上长事务 → 2PL 下队列化，MVCC 下版本雪崩
把外部 I/O 移出事务，持锁/持快照窗口缩到毫秒级
qty>0 把业务约束放进单条更新，减少往返

案例 3：批量导入要测「中断+重启」

# 伪配置：小事务批量 + 定期 checkpoint
batch_size = 1000
wal_flush = every_commit
checkpoint_every = 30s
# 测试：导入到一半 kill -9，再启动看能否恢复到一致点

逐部分解释：

大批量仍按小事务提交，避免单事务 WAL 膨胀
checkpoint 绑定 LSN：刷脏页并记下「重做从哪开始」
只测「跑完」不够；必须测进程被杀后重启是否还能一致

踩过的坑

把 B+Tree 当万能：写密集、点查为主时 LSM 往往更合适；B+Tree 强在范围读与稳定延迟，不是所有负载的默认解。
只做功能测、不做 crash-replay：没杀进程重放 WAL，就发现不了「以为提交了其实丢了」的恢复洞。
把并发只当成「加什么锁」：真实痛点常是隔离级别与版本可见性（脏读、不可重复读、写偏斜）。
索引越多越快：每次写入要维护所有二级索引；读快了、写与空间可能整体变慢。

适用 vs 不适用场景

适用：

已会 SQL，想进 storage / query planner（约一学期课量）
自研或深度调优单机库，数据从 GB 级往上、在意 p99 与恢复 RTO
要搭内部「数据库内核」技术雷达或课程大纲
面试/oncall 需要能画清「页 → 索引 → 锁/版本 → WAL」一张图

不适用：

只用托管库、只改连接串（直接看云厂商文档）
完全不关心事务/一致性的只读展示页
要在几天内上线的轻应用原型（先托管，别先造引擎）
需要分布式共识 / 跨机复制细节时（本课主轴仍是单机内核；另读 Raft 等）

历史小故事（可跳过）

传统课以 B+Tree + 2PL 为主轴；ARIES（1992 前后工业实践成文）把恢复讲成可教的算法。
2010 年代后 MVCC、LSM 进入主流课表，补上「读多写少」与「写密集」两条线。
CS186 把讲义与作业内核强绑定，常被当作「一门课浓缩版数据库红宝书」。
云数据库把页、日志、优化器拆成可观测服务，课里每一层都能在生产找到对应团队。
Fall 2024 读表仍强调：先把单机正确性（锁/版本 + WAL）吃透，再谈分布式扩展。

学到什么

瓶颈常在边界：日志 / 缓冲 / 并发交界，不在单个「聪明算法」。
读表的价值是统一语言：同事说 B+Tree split，团队听得懂。
并发与恢复都是对「时间」建模：谁先看见、crash 后谁还算数。
性能要在代价模型与数据分布上一起看，单点调优不够。
好的数据库能力来自「读得懂结构图与日志」，而不只是「会写更多 SQL」。

关联

database-internals —— 数据库内部机制总览
b-tree —— B-Tree / B+Tree 及变种
mvcc —— 多版本并发控制
aries —— 崩溃恢复框架
query-optimizer —— 查询计划与代价模型
storage-engine —— 存储引擎实现边界
lock-management —— 锁管理与隔离边界

反向链接

（暂无反向链接）

UCB CS186 Fall 2024 — 数据库内核阅读路线

是什么

为什么重要

核心要点

实践案例

案例 1：账本区间查询加联合索引

案例 2：热点库存更新缩短事务

案例 3：批量导入要测「中断+重启」

踩过的坑

适用 vs 不适用场景

历史小故事（可跳过）

学到什么

延伸阅读

关联

反向链接