数据库写得太慢？不是磁盘的锅，是你在“随机写“——LSM-Tree 用写放大换写吞吐的账本

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

数据库写得太慢？不是磁盘的锅，是你在"随机写"——LSM-Tree 用写放大换写吞吐的账本

先讲一个看起来矛盾的现象：同样是往磁盘上写 1 GB 数据，顺序写能跑到每秒几百 MB，可你要是随机地东写一块、西写一块，吞吐能掉两个数量级。这不是玄学，是磁盘的物理脾气。

问题来了：数据库索引天生是"随机"的——新插入的 key 落在 B+ 树的哪个叶子页，得靠查找才知道，而查找要寻道。于是关系型数据库的写入，一直是背着"随机 I/O"这个包袱在跑。

有一类存储引擎干脆掀了桌子：我全顺序写，随机的事交给后台慢慢收拾。这就是 LSM-Tree（Log-Structured Merge-Tree，日志结构合并树）。LevelDB、RocksDB、Cassandra、HBase，全是这个思路。

为什么随机写慢、顺序写快

机械硬盘（HDD）写入前，磁头要先"寻道"（seek）到目标磁道，再等盘片转到正确扇区（rotational latency）。一次随机写，大头的时间花在这两个机械动作上。顺序写则是一次寻道、一路往下刷，磁头几乎不用动。

固态硬盘（SSD）没有机械动作，但它有自己的坑：写之前要先擦除整块，而且有"写放大"——写 4 KB 的逻辑数据，底层可能要擦写一个 256 KB 的块。乱序的小块随机写，会把 SSD 的擦除搞得频繁又浪费，寿命和性能一起掉。

所以无论 HDD 还是 SSD，把随机写变成顺序写，都是实打实的优化。

B+ 树的困境

关系型数据库（MySQL InnoDB 等）用 B+ 树做索引，读很快：树高很低，3 层就能索引上亿条数据，一次点查几次磁盘 IO 就到叶子页。但写就没那么爽了：

B+ 树是"读优化"的结构，它把写入的成本摊在了一次次的随机 I/O 上。读多写少的 OLTP 场景无所谓，但遇到写多读少的负载——日志、时序数据、消息流、埋点——B+ 树就顶不住了。

LSM 的核心：写内存，然后顺序刷盘

LSM-Tree 换了个思路，把写入拆成两段：

第一段，写内存。 新写入先进一个内存里的有序结构 MemTable（一般是跳表或红黑树）。同时为了防宕机丢数据，先顺序追加到 WAL（预写日志）——注意这个追加也是顺序写。到这里，写入的"热路径"就结束了，速度极快。

第二段，刷盘。 等 MemTable 涨到一定大小（比如 64 MB），把它整个顺序写成一个不可变的文件，叫 SSTable（Sorted String Table）。因为 MemTable 里本来就是有序的，直接顺序刷出去就行，磁盘全程不用寻道。

看出来没有：写入路径上没有任何随机 I/O。这就是 LSM 写吞吐高的全部秘密——把随机写延后、转换成顺序写。

读怎么办：多查几个文件，拿布隆过滤器兜底

天下没有免费的午餐。既然数据散落在"一个 MemTable + 若干 SSTable"里，读一个 key 就得挨个找：先查 MemTable，再按新旧顺序查每个 SSTable。SSTable 越多，读越慢。这就是 读放大（read amplification）。

两个手段缓解：

• 每个 SSTable 自带索引（稀疏索引 + 布隆过滤器）。布隆过滤器能在 O(1) 时间告诉你"这个 key 大概率不在这块文件里"，把绝大多数无效查询直接挡掉，避免翻遍所有 SSTable。
• 合并（compaction）：后台线程把多个小的、有重叠的 SSTable 合并成更大的、有序的 SSTable，把同一 key 的旧版本清掉。文件少了，读放大就下来了。

布隆过滤器这步很关键。LSM 的读放大能不能被接受，一半靠 compaction，一半靠布隆过滤器把"不存在的 key"这种最坏情况挡住。

Compaction 的两条路线，和那笔账

Compaction 是 LSM 最微妙的工程决策，分两大流派，对应三种"放大"的取舍。

Tiered（分层平铺，Cassandra、HBase）：同一层允许有多个 SSTable，攒到一定数量就把它们合并成一个更大的。写放大低（每条数据平均只被重写几次），但读放大高（一层里一堆文件都要查）、空间放大高（旧版本清理不及时）。

Leveled（层级金字塔，LevelDB、RocksDB）：每层是"一组无重叠的有序 SSTable"，层与层之间大小差一个倍数（典型是 10 倍）。L0 满了就往下层合并，把数据"推"进金字塔。读放大低（每层最多查一两个文件）、空间放大低，但写放大高。

写放大这笔账，Leveled 的策略下可以粗略估一下：设相邻层大小比是 T（比如 10），一条数据从 L0 一路被推到最底层，几乎每一层都要被重写一次（合并时把它搬进下一层），所以写放大量级大致是 O(T × 层数)，实际测出来 10 到 30 倍很常见。Tiered 的写放大则接近 O(1) 到个位数。

于是有了那个著名的 RUM 猜想（Read / Update / Memory 三者不可兼得）：读放大、写放大、空间放大，你最多压住两个，总要牺牲一个。

• 要写快 → Tiered，接受读慢、占空间。
• 要读快、省空间 → Leveled，接受写放大高。

RocksDB 默认走 Leveled，但允许你按负载调成 Tiered 或混合，本质就是在这三个放大之间挪预算。

为什么它值得你了解

LSM-Tree 已经不只是"某个数据库的内部实现"，它撑起了整个现代基础设施的写入层：RocksDB 是 TiKV、CockroachDB、Flink、很多消息队列的存储底座，Cassandra/HBase 是大数据列存的标配，连 Kafka 的日志分段、LevelDB 内嵌在 Chrome 里存浏览数据，背后都是"顺序写 + 后台合并"这一套哲学。

理解它，你就能看懂一堆看似不相干的东西：为什么 Kafka 追加写能这么快，为什么有些时序数据库写入量惊人但偶尔查询会抖一下，为什么 RocksDB 的调参参数里"compaction"占了一半。它们都是同一笔账的不同记法。

和 408 的关系（延伸）

B+ 树是 408 数据结构、以及数据库索引的必考点，本博客之前专门拆过它为什么是索引的“天选之子”（数据库索引为什么用 B+ 树，而不是更“聪明”的二叉树？——答案不在算法，在磁盘）。LSM-Tree 是 B+ 树在"写密集"场景下的一个工业级对手，属于延伸/进阶内容，不在 408 考纲内，但理解"为什么有人愿意牺牲读来换写"，恰恰是吃透 B+ 树设计动机的反面教材——考纲内的 B+ 树是"读优化的有序树"，考纲外的 LSM 是"写优化的有序树"，对照着看，两边都更透了。

所以下次再有人问"为什么我的数据库写得这么慢"，先别急着加机器。问问自己：你是在顺序写，还是在随机写？如果是后者，要么换数据结构，要么像 LSM 一样，把随机延后、把顺序提前。存储引擎的世界里，没有更快的磁盘，只有更聪明的写顺序。

LSM-Tree 说到底还是棵"合并树"，树结构、跳表、布隆过滤器这些底子都是数据结构的范畴。想补这块，推荐 B站【408实验室】的《数据结构》。