专业书籍精读 · Database Internals · 第 7 章
Database Internals · Ch 7 · Alex Petrov · 2019
你发一条消息、点一次赞、让手表记一次心跳，这些数据最后都要落到某个数据库里。前几章讲的存法像改字典：翻到那一页，涂掉旧的，写上新的。这一章讲一种完全相反的脾气——记流水账：永远只在本子最后一行往下写，从不回头改一个字。
你管一家小店的账。改字典派：每个客户一页，余额变了就翻到他那页擦掉重写，查账方便，但一天要翻上千次页。流水账派：笔就没抬过，「张三 +100」「李四 −30」「张三 +50」一行行往下记，快得离谱；代价是想知道张三现在有多少钱，得从头翻一遍，看到好几条只认日期最新的那条。
硬盘有个朴素的脾气：一路往下写，快；东一榔头西一棒子地找地方写，慢——差的不是一点，是几十上百倍。而「改字典」偏偏是后一种：改一个数字就得去它所在的那一页，那些页散落在盘的各个角落。对写得特别多的活儿（聊天记录、传感器读数、日志、点赞），这就是瓶颈。
还有个小机灵：每本册子封面贴一张速查条，能一眼告诉你「本册肯定没有张三」，省掉大量白翻。
它并没有让写变便宜，只是把「立刻付」改成了「先赊着、后台分期还」——同一条数据在整理时会被反复搬好几遍，盘上还同时躺着它的好几个版本。写多读少、写完就不太改的活儿（日志、监控指标、消息），流水账派完胜；要反复精确查、要按顺序翻一整段的，改字典派仍然更合适。
日志结构存储的聪明之处，就是把「回头改」换成「往后追加 + 事后归并」。写快了，但代价一分没少，只是记在「查得多翻几本」「盘上多占几份」「后台一直在整理」这三笔账上。
想进到具体机制、记号和示意图？ → 切到精读版
你以为日志结构存储（log-structured storage）是「写得快」的魔法，其实它只做了一笔交易：把「原地随机改」换成「顺序追加 + 事后归并」。省下的写代价一分没有消失，全部记在读放大与空间放大的账上，由后台的合并（compaction）分期偿还。
本章是第一部分「存储引擎」的收官章。第 2–6 章讲的是 B-Tree 谱系：有序、原地更新；第 6 章的写时复制（copy-on-write）与 Bw-Tree 已在往「别原地改」挪，这一章把这条路走到底——完全不原地改，只追加。它对应现实中 LevelDB / RocksDB / Cassandra / HBase 这一整支写优化存储。往下就进第二部分：分布式系统。
问题出在 B-Tree 的写路径。把一个 8 字节的计数器加一，它要整页读进内存（页通常 4KB–16KB）、改掉那 8 个字节、再整页写回；为了崩溃安全，改之前还得先往 WAL 写一遍。8 字节的逻辑写变成几十 KB 的物理写，而且这些页散落在文件各处，写是随机的。
随机与顺序差多少？机械盘随机 IOPS 常在 100–200 量级，顺序带宽却轻松上 100MB/s；固态盘没有磁头，但闪存「只能整块擦除」让随机小写同样要多付代价。差的是两三个数量级。于是写密集负载——时序指标、日志、聊天消息、社交计数——都先在写路径上撞墙：不是 CPU 不够，是盘被逼着做它最不擅长的事。本章的赌注很直接：把所有写都变成顺序追加，读和空间的代价另想办法补。
LSM-tree（log-structured merge-tree，日志结构合并树）把存储拆成两种性格相反的部件：内存里那张表可变——就是 memtable，来一条写就插一条，天然有序；磁盘上那些表全部不可变——memtable 写满即冻结，后台一次性顺序写出成一个 SSTable，此后一个字节都不再改。
崩溃安全靠 WAL：写请求先追加 WAL 再进 memtable；崩了就重放，等 memtable 成功刷成 SSTable，对应 WAL 段即可丢弃。整条写路径上磁盘只做两件事：追加 WAL、顺序写出 SSTable——没有一次原地修改。
文件不可变，「改」和「删」只能换个说法。更新＝写一条新版本，旧版本仍躺在更老的 SSTable 里；删除＝写一条墓碑（tombstone）——书里形容成一张「休眠证书（dormant certificate）」：它不删任何东西，只宣告「从此刻起，此键作废」。
由此有个反直觉结论：在 LSM 里删数据，磁盘占用会先变大，真回收要等合并碾过去。而墓碑自己什么时候能删是个必须小心的判断：只要还有更老的 SSTable 可能藏着这个键的旧值，墓碑就得留着；提前扔掉，旧值就会重新冒出来——数据「复活」。Cassandra 的 gc_grace_seconds（默认十天）就是为此留的安全期。
写简单了，读就复杂了。一个键可能同时出现在 memtable 和多个 SSTable 里，于是一次读要做两件事。归并迭代（merge-iteration）——各 SSTable 内部有序但彼此键区间可能重叠，用一个优先队列（最小堆）做 K 路归并：每次从各表游标挑出最小的键、输出后推进那一路，只需每表一个游标就能拉成一条全局有序流。调和（reconciliation）——同一个键归并出好几条时，按时间戳 / 纪元（epoch）取最新；若最新的是墓碑，就当不存在。「谁新听谁的」这条规矩，是整套设计能自洽的地基。
最坏情况一次点查要摸遍所有 SSTable，这就是读放大。第一道墙是布隆过滤器：每个 SSTable 配一个，若干哈希函数把键映射到一个位数组，只要有一位是 0 就说明键肯定不在这个文件里，整个跳过；全是 1 也只能说「可能在」。代价是内存与假阳性率的直接交换——RocksDB 的对照是 9.9 bit/键约 1% 假阳性。一亿个键按 10 bit 也才 ~125MB 内存，挡掉 99% 的无效文件读，极其划算。但它只对点查有效，范围扫描帮不上忙。
不合并会怎样？SSTable 无限增多，读放大线性恶化；被覆盖的旧版本与墓碑永远占着盘。所以后台一直在做同一件事：读进若干 SSTable → 归并 → 调和 → 丢掉过期版本与到期墓碑 → 写出新文件 → 删掉旧的。妙处在于不可变性让合并异常好写：输入有序就是顺序读，输出新文件就是顺序写，全程不必对数据加锁——第 5 章 B-Tree 恢复要对付的并发与半写页问题，被结构本身消解了一大半。
合并策略是本章最该记住的选型点，主流三种：
10 倍。LevelDB 文档给得很具体：日志攒到约 4MB 转成一个 SSTable，L0 超过 4 个文件即触发合并，第 L 层上限 10^L MB。好处是每层最多命中一个文件，代价是同一条数据在层间被反复重写。4 个）尺寸相近的 SSTable 就合成更大的一个。写放大低得多，但一个键可能散在很多张表里；大表合并时新旧并存，磁盘可能被临时撑到近两倍。账本到这里可以合上了：衡量一个存储引擎就看读放大、写放大、空间放大三个数，而三者不可能同时最优，只能选两个。这就是本章引用的 RUM 猜想（Athanassoulis 等，EDBT 2016）：Read、Update、Memory 三项开销，压低其二必然抬高其三。B-Tree 站在读优化角——读放大接近 1、空间省，但写放大高；LSM 站在写优化角——写路径全顺序，但读要归并、盘上留多份。合并策略则是在 LSM 内部继续微调这三者的配比。
日志结构不一定要排序。Bitcask（Riak 的存储引擎）走到极端：磁盘上就是一串纯追加、完全不排序的数据文件，内存里一张叫 keydir 的哈希表记录每个键当前的值在哪个文件的哪个偏移。于是任何一次读都是「查一次内存哈希 + 一次磁盘定位读」；代价同样直白：所有键必须常驻内存，且不支持范围扫描。WiscKey 是折中派：键值分离——键连同一个指针留在 LSM 树里，值单独写进追加式的 vLog，合并只搬键不搬值，写放大骤降，范围扫描则退化成对 vLog 的大量随机读。判据很清楚：值越大，键值分离越划算。
最后一节最有「数据库内幕」的味道：你的日志底下还压着别人的日志。文件系统本身可能就是日志结构的；固态盘的 FTL 更是——闪存只能整块擦、按页写，所以它从不原地改，而是换个空页写、把旧页标记无效、事后回收。要命的是各层写放大相乘而非相加：LSM 合并重写 10 遍，FTL 回收再放大若干倍，最终落到闪存颗粒的写入量可能是逻辑写的几十倍；更麻烦的是各层垃圾回收彼此不知情——数据库刚判定一批数据作废，FTL 可能正把它们搬到新块上。书里给的方向是把栈压平：绕过文件系统与 FTL 直接管理裸闪存。道理是通用的——「顺序写」这个前提，在你看不见的下层可能根本不成立。
先给个场景当锚：某物联网平台 50 万台设备每 10 秒上报一次，稳定 5 万 写/秒，查询几乎全是「某设备最近 24 小时的曲线」，数据 30 天后过期。这种负载下 B-Tree 先在写路径上崩——几十字节的点写要拖动几 KB 的页且随机；换成 LSM 写全部顺序化，再配 TWCS 让整批过期数据整个文件删掉。反过来，账户余额表读多写少、要频繁按主键范围对账，B-Tree 依然更省心。
表 1 · LSM-tree vs B-tree（本章与第 2–6 章的正面对照）
| LSM-tree（本章） | B-tree（第 2–6 章） | |
|---|---|---|
| 磁盘写形态 | 纯顺序追加，从不原地改 | 原地更新，页级随机写 |
| 写放大 | 来自后台合并，分层策略常 >10 倍 | 来自页级重写 + WAL 双写 |
| 读放大 | 可能摸多个 SSTable，靠布隆过滤器压住 | 约 3–4 次页读到底，稳定 |
| 空间放大 | 高——旧版本与墓碑等合并才回收 | 低，但有页内碎片 |
| 延迟稳定性 | 后台合并与前台抢 IO，有写停顿抖动 | 更平稳 |
| 适合 | 写密集、写完少改：时序、日志、消息、计数 | 读密集、更新分散、要严格范围扫描 |
表 2 · 三种合并策略怎么选（括号内为各系统官方文档给出的默认值）
| 分层 leveled | 按大小分组 size-tiered | 时间窗口 TWCS | |
|---|---|---|---|
| 触发条件 | 某层容量超限（层比约 10×） | 攒够 N 个同尺寸表（默认 4） | 时间窗口结束 |
| 读放大 | 低——每层最多一个文件 | 高——一个键可能散在多表 | 低（通常只落一两个窗口） |
| 写放大 | 高——RocksDB 称「常大于 10」 | 低 | 低 |
| 空间放大 | 低（Cassandra 称约需 10% 余量） | 高——大表合并时磁盘可能临时翻倍 | 低——整桶过期整桶删 |
| 选它当且仅当 | 读多写少、磁盘紧张 | 写多读少、磁盘富余 | 时序 + TTL，数据基本按时间到达 |
表 3 · 有序 vs 无序：日志结构的第二个分岔
| 有序 LSM | Bitcask（无序） | WiscKey（键值分离） | |
|---|---|---|---|
| 点查 | 可能多表 + 布隆过滤器 | 内存哈希 + 一次定位读 | 查 LSM 拿指针，再读一次 vLog |
| 范围扫描 | 支持，且高效 | 不支持 | 支持但要大量随机读 vLog |
| 内存要求 | 索引 + 布隆过滤器 | 全部键常驻内存 | 只存键，比全量 LSM 省 |
| 写放大 | 合并搬键也搬值，最高 | 低 | 低——合并只搬键 |
这一章的分量在于：你今天用到的写优化存储，几乎全是它的实例。源头是 Google 的 Bigtable（OSDI 2006）确立的 memtable + SSTable + 合并骨架；LevelDB 把它变成人人能读的实现；Meta 从 LevelDB fork 出 RocksDB，此后它成了被到处嵌入的存储底座——MyRocks、TiKV、CockroachDB 的 Pebble、各种流处理的状态存储；Cassandra / HBase / ScyllaDB 是同源的另一支。
落到日常决策，它给的是一组能直接开口讲的判据：选型时问「读写比多少、值多大、要不要范围扫描」，出问题时问「现在疼的是读放大、写放大还是空间放大」。面试问「LSM 为什么写快」，标准答案不是「因为顺序写」，而是「它把随机写换成了顺序写，代价推迟到合并里付」——后半句才是区分度。
4.9 bit/键 ≈ 10%、9.9 bit/键 ≈ 1%、15.5 bit/键 ≈ 0.1%，用途是「减少 Get 与 Seek 带来的 IO、CPU 与块缓存扰动」。RocksDB Wiki · Bloom Filter ↗4MB 转成 SSTable、L0 超 4 个文件触发合并、第 L 层上限 10^L MB、输出按 2MB 切分，并估「最坏一次合并约 0.5 秒」——本章的分层结构在这里是代码级可核对的事实。LevelDB · doc/impl.md ↗gc_grace_seconds」，且墓碑必须与数据同目录，以免丢盘时「数据被复活」。Cassandra Docs · Compaction Overview ↗① 全部交易只有一笔：把「原地随机改」换成「顺序追加 + 事后归并」——代价没消失，只是推迟到合并里付。
② 结构：一张可变内存表（memtable，常用跳表）+ 一堆不可变磁盘表（SSTable）+ 一份 WAL 兜底；磁盘上没有一次原地修改。
③ 更新即追加新版本，删除即写墓碑——删数据会让磁盘先变大，真回收要等合并。
④ 读做两件事：K 路归并把多来源拉成有序流，再按时间戳调和取最新；墓碑压过更老的值。
⑤ 布隆过滤器是读放大的第一道墙：只对点查有效、只能否定不能肯定；约 10 bit/键换 1% 假阳性。
⑥ 合并是命根子：不可变性让它顺序读、顺序写、几乎无锁。三种策略——分层（读优、写放大 >10）、按大小分组（写优、读与空间变差）、时间窗口（时序 + TTL，整桶到期整桶删）。
⑦ RUM 猜想：读、更新、空间三种开销最多同时压住两个。B-Tree 占读优化角，LSM 占写优化角。
⑧ 日志结构不必有序：Bitcask 换到「一次定位读」，代价是全部键常驻内存且不能范围扫描；WiscKey 用键值分离让合并只搬键，值越大越划算。
⑨ 日志栈叠：文件系统与 FTL 自己也是日志结构，各层写放大相乘、垃圾回收互不知情——「顺序写」这个前提在下层未必成立。
⑩ 口诀：写多读少、写完少改 → LSM；读多、要范围扫描、磁盘紧张 → B-Tree；出问题先分清疼的是读放大、写放大还是空间放大。