Day 47 Hard Storage Engine B-tree / LSM WAL / MVCC

数据库内部与存储引擎 — 一次读写在盘上到底发生了什么Database Internals & Storage Engines: B-tree vs LSM, WAL & Crash Recovery, MVCC, Query Optimizer

问题场景 + 需求约束

你在为一个交易/账本系统选底层存储引擎：订单表写入峰值 10 万 QPS，点查（按订单号）5 万 QPS，单表数据量增长到 10 TB+，宕机后必须零数据丢失恢复（RPO=0），且大量并发读写不能互相阻塞。摆在面前的问题不是「用 MySQL 还是 Postgres」这种表层选择，而是：这些数据库内部的存储引擎，凭什么保证一次 UPDATE 既快又不丢、还能被别的事务同时读到一致快照？

要回答这个，必须打开数据库这个黑盒，看清四件事：数据在盘上怎么组织（B-tree vs LSM）、崩溃了怎么不丢（WAL）、并发读写怎么不打架（MVCC）、一条 SQL 怎么被翻译成最优的盘上访问（优化器）。这也是设计存储密集型系统、以及面试架构师岗位的分水岭。

高层架构（存储引擎剖面）

graph TD
    SQL["SQL 查询"] --> PARSE["Parser + Planner
基于代价的优化器"]
    PARSE --> EXEC["Executor
Access Method 接口"]
    EXEC --> AM{"存储引擎"}
    AM -->|读多| BT["B+Tree
InnoDB / Postgres"]
    AM -->|写多| LSM["LSM-Tree
RocksDB / Cassandra"]

    BT --> BP["Buffer Pool
页缓存 · 脏页"]
    LSM --> MEM["MemTable
内存有序表"]

    WRITE["写路径"] -.先写.-> WAL[("WAL / redo log
顺序追加")]
    BP -->|checkpoint 刷脏页| DISK[("数据文件
heap / SSTable")]
    MEM -->|flush + compaction| DISK
    WAL -.崩溃恢复 redo/undo.-> BP

    classDef q fill:#1a2530,stroke:#64c8ff,color:#e8eef5
    classDef eng fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef dur fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    class SQL,PARSE,EXEC q
    class BT,LSM,BP,MEM eng
    class WAL,DISK dur

核心不变量：任何数据落地前，先写 WAL（顺序 IO）；数据结构本身决定读/写/空间放大三者的取舍

关键技术点

1. B-tree vs LSM-tree — 读放大与写放大不可兼得

原理：磁盘（尤其机械盘和 SSD）的顺序写远快于随机写。B+Tree 把数据原地（in-place）组织成有序的页，查找 O(log n) 且每次点查只读一个叶子页——读友好；但更新一行要把对应页读进来、改、再写回，是随机写，且一页只改几字节也要整页刷盘（写放大）。LSM-Tree 反过来：写只追加到内存 MemTable，满了就顺序 flush 成不可变的 SSTable，后台再 compaction 合并——把随机写变成顺序写，写吞吐极高；代价是一个 key 可能散落在多层 SSTable，点查要查多层（读放大），靠 Bloom Filter 缓解。

Trade-off（RUM 三角：Read / Update / Memory 放大，最多优化两个）：

B+Tree：✅ 读放大低、范围扫描快、原地更新省空间；❌ 写放大高（页级刷盘 + WAL 双写）、随机写、写入抖动。适合读多写少、点查/范围混合的 OLTP。
LSM-Tree：✅ 写放大低（顺序写）、压缩率高（不可变文件好压）、省空间；❌ 读放大高、compaction 抢 IO 造成延迟毛刺、空间瞬时翻倍。适合写多、时序/日志/KV。
关键洞察（Mark Callaghan）：read / write / space amplification 三者至少牺牲一个，没有银弹。选引擎=选你能承受哪种放大。

# LSM 点查：从新到旧逐层找，Bloom Filter 先挡掉不存在的层
def lsm_get(key):
    if v := memtable.get(key):           # ① 内存最新
        return None if v is TOMBSTONE else v
    for sst in sstables_newest_to_oldest():   # ② L0→Ln 逐层
        if not sst.bloom.might_contain(key):  # 假阳性率 ~1%
            continue                          # 绝大多数层被跳过
        if v := sst.get(key):                 # 命中则返回（删除是墓碑）
            return None if v is TOMBSTONE else v
    return None
# 写：只 append，删除也是「写一个墓碑」，真正回收在 compaction

现实案例：

MySQL InnoDB：经典 B+Tree，主键即聚簇索引，二级索引存主键值（回表）。默认 OLTP 引擎。
RocksDB（Facebook）：LSM 引擎，被 MyRocks、TiKV、CockroachDB、Kafka Streams 当底座。RocksDB wiki 详述 leveled/universal compaction。
Cassandra / HBase：LSM，为高写入吞吐设计，时序与宽表场景标配。
Uber：因 Postgres 的写放大/复制成本，迁到 MySQL/InnoDB——同是 B-tree 家族，索引结构差异决定写成本。

2. WAL 与崩溃恢复 — 先写日志，才敢改数据

原理：数据页在内存 buffer pool 里被改成「脏页」，若此时宕机、脏页还没落盘，数据就丢了。WAL（Write-Ahead Logging）的铁律：任何对数据页的修改，其 redo 日志必须先顺序写入磁盘并 fsync，才允许脏页刷盘。这样崩溃后重放 WAL 就能重建内存中丢失的修改。顺序写 WAL 也顺便把「多个随机写」摊销成「一次顺序写 + 异步刷脏页」，反而提速。工业标准是 ARIES 算法：三阶段恢复——Analysis（找出崩溃时的脏页和活跃事务）、Redo（重放到崩溃瞬间的状态，含未提交事务）、Undo（回滚未提交事务），配合 LSN、checkpoint、CLR 保证幂等可重入。

Trade-off（持久性 vs 延迟，取决于 fsync 时机）：

每事务 fsync（如 innodb_flush_log_at_trx_commit=1）：✅ RPO=0、真持久；❌ 每次 commit 一次磁盘同步，延迟高、吞吐受限。
组提交 group commit：✅ 攒一批事务一次 fsync，吞吐×10；❌ 尾部事务多等几毫秒。几乎所有生产库默认开启。
放松（=2 / async）：✅ 极快；❌ 崩溃丢最近 ~1s 已提交事务。账本绝不能用，缓存型可以。

# 提交时的 WAL 顺序（简化）
def commit(txn):
    lsn = wal.append(txn.redo_records)   # ① 顺序追加 redo（还含 undo 信息）
    wal.fsync_up_to(lsn)                 # ② 强制落盘 —— 这一步返回后才算「已提交」
    mark_committed(txn)                  # ③ 现在才回复客户端 OK
    # 脏页稍后由 checkpoint 异步刷；崩溃则靠 redo 重放补回

现实案例：

PostgreSQL：WAL + checkpoint，pg_wal 目录即日志；物理复制、PITR 全靠它。
InnoDB：redo log（物理，恢复用）+ undo log（逻辑，MVCC/回滚用）双日志，group commit 默认开。
RocksDB：MemTable 前也有 WAL，flush 成功后对应 WAL 才可删。
ARIES（IBM，Mohan 等）：几乎所有关系库崩溃恢复的理论蓝本。

3. MVCC — 读不阻塞写，写不阻塞读

原理：如果读写都靠锁互斥，一个长事务的读会把写全堵死。MVCC（多版本并发控制）让每次更新不覆盖旧行而是产生一个新版本，每行带创建/删除的事务时间戳（xmin/xmax）。事务开始时拿一个快照，读取时只看「对我可见」的版本——于是读永远不加锁、看到一致快照，写也不用等读。这就是 REPEATABLE READ / Snapshot Isolation 的实现基础。代价是旧版本会堆积，必须回收：Postgres 靠 VACUUM 清理死元组，InnoDB 靠 purge 线程清理 undo。

Trade-off（旧版本放哪 → 决定写放大与回收痛点）：

Postgres 式（新版本写在堆表里）：✅ 回滚快、旧版本原地；❌ 每次更新要更新该行的所有索引（新元组新位置）→ 写放大严重；死元组多 → VACUUM 压力、表膨胀。HOT 更新可缓解（不改索引列时旧新版本同页、不动索引）。
InnoDB 式（旧版本进 undo log，主表原地更新）：✅ 只更新被改列的索引、写放大低；❌ 长事务导致 undo 链变长，历史版本重建（read view 回溯）变慢，purge 跟不上会撑爆 undo 表空间。
纯锁（无 MVCC）：✅ 实现简单；❌ 读写互斥，OLTP 并发直接崩。

# 可见性判断（Postgres 风格，简化）
def visible(tuple, snapshot):
    # 创建该版本的事务已提交，且在我的快照之前
    if not committed_before(tuple.xmin, snapshot):
        return False
    # 该版本未被删除，或删除它的事务对我不可见
    if tuple.xmax and committed_before(tuple.xmax, snapshot):
        return False
    return True
# 读只扫版本链挑「可见」的那个，全程不加锁

现实案例：

PostgreSQL：堆表多版本 + VACUUM；「长事务阻塞 VACUUM 导致表膨胀」是经典生产事故。
MySQL InnoDB：undo log 重建历史版本，read view 决定可见性。
Oracle：undo segment + SCN，「ORA-01555 snapshot too old」即历史版本被覆盖。
CockroachDB / Spanner：MVCC + 时间戳，把版本时间戳和分布式一致性结合。

4. 索引内部与查询优化器 — 一条 SQL 的最优盘上路径

原理：同一条 SELECT ... WHERE a=? AND b>? 可以有多种执行方式：全表扫、走 a 的索引再过滤、走复合索引 (a,b) 直接定位。基于代价的优化器（CBO）用统计信息（直方图、distinct 值数、行数）估算每种方案要读多少页、结果集多大，选代价最小的。索引本身是 B+Tree：聚簇索引叶子存整行，二级索引叶子存主键（需回表），覆盖索引让查询列全在索引里、免回表。选择性（selectivity）是关键——低选择性列（如性别）走索引反而更慢。

Trade-off：

更多索引：✅ 读快、支持覆盖查询；❌ 每个索引都要随写维护 → 写放大、占空间。Postgres 更新还要动全部索引。
复合索引顺序 (a,b) vs (b,a)：✅ 最左前缀匹配决定能否用上；❌ 选错顺序索引形同虚设，范围列要放最后。
CBO 依赖统计：✅ 自适应最优计划；❌ 统计过期 → 选错计划（把该走索引的走成全表扫），需定期 ANALYZE。

-- 用 EXPLAIN 看优化器到底怎么走
EXPLAIN ANALYZE
SELECT order_id, amount FROM orders
WHERE user_id = 42 AND created_at > '2026-01-01';
-- 期望: Index Scan using idx_user_created (user_id, created_at)
-- 若见 Seq Scan + Filter → 统计过期或选择性误判, 先 ANALYZE orders;
-- 复合索引 (user_id, created_at): user_id 等值在前, 范围列在后

现实案例：

PostgreSQL：CBO + EXPLAIN (ANALYZE, BUFFERS)，直方图统计存 pg_statistic。
MySQL：8.0 起支持直方图与不可见索引（先建后灰度启用）。
CockroachDB / TiDB：分布式 CBO，还要估算跨节点数据分布与网络代价。
「隐式类型转换致索引失效」：字符串列传数字、函数包裹列（WHERE date(t)=...）都会让索引用不上，是最高频线上慢查询。

扩展与优化（增长后怎么办）

写扛不住：读多写少继续 B-tree + 加读副本；写吞吐瓶颈考虑换 LSM 引擎（MyRocks / TiKV），用顺序写换随机写。
单机 10TB 到顶：分片（见 Day 4），每片仍是独立存储引擎；跨片查询交给上层。
compaction 抖动：LSM 限速 compaction、分离热冷层、用 universal compaction 降写放大（换更高空间放大）。
VACUUM / purge 跟不上：拆分长事务、调 autovacuum 激进度、监控表膨胀率与 undo 长度。
WAL 成瓶颈：组提交 + 更快的 WAL 盘（独立 NVMe）；异地灾备用 WAL 流式复制（物理复制 / CDC）。

常见陷阱 + 面试追问

1. 「LSM 一定比 B-tree 快」？ 错。LSM 只在写密集时赢；点查多、范围扫多、读延迟敏感的场景，B-tree 的低读放大更优。选引擎先看读写比。

2. 关了 fsync 换吞吐？ innodb_flush_log_at_trx_commit=2 或 synchronous_commit=off 会在崩溃时丢已回复 OK 的事务。账本/支付绝不能碰，这是 RPO≠0。

3. Postgres 更新很慢 / 表越来越大？ 多半是 MVCC 死元组堆积 + 每次更新动全部索引。长事务阻塞 VACUUM 是头号元凶。

4. 建了索引却没用上？ 最左前缀不匹配、列被函数/隐式转换包裹、选择性太低、统计过期——用 EXPLAIN 验证而不是猜。

面试高频追问：①「为什么顺序写比随机写快，SSD 上还成立吗？」②「WAL 里既有 redo 又有 undo，各自作用？ARIES 三阶段？」③「MVCC 下两个事务同时更新同一行会怎样（写写冲突/first-committer-wins）？」④「聚簇索引 vs 二级索引，回表是什么，覆盖索引怎么避免？」⑤「Snapshot Isolation 能防住哪些异常，防不住什么（write skew）？」

深入资源

《Designing Data-Intensive Applications》第 3 章（Kleppmann）：B-tree vs LSM、WAL、存储引擎权衡的最佳入门。
《Database Internals》（Alex Petrov）：B+Tree、LSM、ARIES、并发控制的系统性深挖。
Mark Callaghan · Small Datum：read/write/space amplification「三选二」的权威分析。
RocksDB Wiki：LSM 引擎、compaction 策略、Bloom Filter 的工程细节。
Uber Engineering: Postgres→MySQL：MVCC 写放大与索引架构差异的真实案例。

深入思考（点击展开答案）

1. SSD 时代随机写已经不慢了，为什么 LSM「顺序写」的优势仍然成立？

表面看 SSD 随机 IOPS 很高，但优势没消失，原因在写放大与 SSD 内部机制：

SSD 有自己的 FTL 和擦除块：闪存以「页」写、以更大的「块」擦除，随机小写会触发内部 GC 和读-改-写，放大对闪存的物理写入（device-level write amp），加速磨损。顺序大写对 FTL 友好得多。
B-tree 的页级写放大：改几字节要刷整个 16KB 页，还要写 WAL——一次逻辑写变成多次物理写。LSM 把多个改动攒成一个大顺序块，摊薄单位写成本。
但 LSM 有 compaction 写放大：数据要被反复合并重写多次（leveled 可达 10×+）。所以「LSM 一定省写」不绝对——省的是前台随机写，代价是后台顺序重写。

结论：SSD 缩小了差距，但没抹平；真正要比的是端到端写放大和延迟毛刺，而非单纯 IOPS。

2. 一个跑了 3 小时的分析事务，导致 Postgres 主库磁盘暴涨、写变慢。机理链条是什么？

这是 MVCC + VACUUM 的经典连锁：

长事务持有一个老快照，VACUUM不敢回收任何「可能对这个老快照仍可见」的死元组——哪怕它们对所有新事务都早已不可见。
于是 UPDATE/DELETE 产生的死元组持续堆积，表和索引不断膨胀（bloat），占盘暴涨。
表变大 → 顺序扫和索引扫要读更多页 → buffer pool 命中率下降 → IO 升高、查询变慢。
膨胀还拖累后续 VACUUM 本身（要扫更多页），形成恶性循环。

修法：拆分/限时长事务（idle_in_transaction_session_timeout）、把分析查询放只读副本、监控 pg_stat_activity 里的 xact_start 和最老快照年龄、必要时 VACUUM FULL 或 pg_repack 回收空间。这也是「OLTP 和 OLAP 要分库」的底层理由之一。

3. Snapshot Isolation 看似很强，但它防不住 write skew。举个真实例子，怎么修？

经典例子——医院值班：约束是「任何时刻至少 1 名医生值班」。当前 Alice、Bob 都在值班。两人同时点「我请假」：

各自事务的快照都看到「有 2 人值班」→ 都判断「减到 1 人仍满足约束」→ 都提交。
结果0 人值班，约束被破坏。两个事务改的是不同的行（各自那条值班记录），所以没有写写冲突，SI 放行。

这就是 write skew：两事务基于同一份读快照做决策，各改各的，合起来违反了跨行不变量。

修法：①Serializable Snapshot Isolation（SSI）——Postgres 的 SERIALIZABLE 会检测读写依赖环并中止一个事务。②显式加锁物化冲突——SELECT ... FOR UPDATE 锁住相关行，或对「值班人数」这个聚合加一把锁/一行计数器，把隐式冲突变成显式写写冲突。

4. 为什么二级索引通常存「主键值」而不是「行的物理地址」？各自代价？

两种设计真实存在，取舍相反：

存主键值（InnoDB 式）：二级索引叶子 → 主键 → 再查聚簇索引拿整行（回表）。好处是行在聚簇索引里位置变动（页分裂、MVCC 更新）时，二级索引不用改，只要主键不变。代价是每次二级索引查询多一次 B+Tree 查找。
存物理地址（Postgres 的 ctid / heap-only 思路）：索引直接指到堆里的物理位置，查得快、免回表。但行一旦移动位置（MVCC 每次更新产生新元组、在新位置），所有二级索引都得更新指针——这正是 Postgres 更新写放大的根源。HOT 更新就是为了在「不改索引列」时让新版本留在同页、避免动索引。

本质是「间接层放哪」的取舍：主键间接层换来更新时索引稳定（写省），物理地址换来读时少一跳（读省）——又一次 read/write 放大的对立。

5. 崩溃恢复时，WAL 里为什么要重放「未提交」事务的修改，再回滚它们？直接跳过不行吗？

不行，这正是 ARIES「先 Redo 全部、再 Undo 未提交」设计的精妙之处，核心是幂等与状态一致：

为什么先 redo 未提交的：崩溃瞬间，磁盘上的数据页处于任意中间状态——可能已经刷了某个未提交事务的部分脏页，也可能没刷。ARIES 采用「repeating history」：先把 WAL 无差别重放到崩溃那一刻的精确状态（含未提交改动），让内存/磁盘状态确定可知，Undo 才有稳定的起点。
为什么再 undo：重放后,未提交事务的修改也在了,必须按 undo 信息逐条回滚,恢复到「仿佛这些事务从没发生」。
为什么幂等：恢复过程本身可能再次崩溃。每页有 LSN 记录「已应用到哪」，redo 时只对 page.LSN < record.LSN 的才重放；undo 写 CLR（补偿日志记录）记录回滚进度。于是恢复可以反复重启而不出错。

「跳过未提交的」听起来省事，但你根本无法知道磁盘上哪些未提交改动已经落盘——不重放到已知状态，就没有安全的回滚基线。

← 回到 index