mirai2cs

DDIA 第 4 章学习复盘（上）：从两个 bash 函数推导出 LSM ​

创建时间：2026-07-12；最近更新：2026-07-12

这是我读《数据密集型应用系统设计》（DDIA）第 4 章前半部分的学习复盘。

本章内容主要讨论的是"数据存储中读与写的权衡"。这篇文章会从一个只有两行代码的"数据库"出发，遇到问题解决问题，最后推出 LSM-tree （一些工业级存储引擎的核心结构）。叙述顺序可能与原文略有差异。

LSM-Tree（Log-Structured Merge-Tree，日志结构合并树）：不频繁地在磁盘原位置修改数据，而是先追加写、再在后台合并整理。

从零开始：两个函数的数据库 ​

如果从零开始实现最简单的一个键值对的文件数据库，只需要两个函数，一个写入，一个读取。

bash
db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

我们暂且简单地选择尾追加作为写入的方式。

好处：

  • 实现简单
  • 写入较快，更新一个 key，只是在末尾多写一条新记录

但代价立刻显现出来——

问题01：脏数据如何清理

既然永远只往末尾追加，旧数据就永远不会被修改。如果只是少数几个 key 的频繁修改，可能存在大量的垃圾历史值堆在文件内，而实际我们只关心最后更新的值。

问题02：读取操作比较费时

当前场景下需要整个文件读一遍——因为即使在前面查到了，后续数据中也可能出现同样的 key 去更新 value 值，所以中途命中也不能停，此时复杂度为 O(n)。

当前问题清单：问题01、问题02

对于数据库而言，查询是频繁且非常重要的操作。特别是数量级上来的情况，我们无法接受每次查询需要 O(n) 的时间，希望解决"问题02"。

那么如何加速查询呢？我们可以在内存里维护一个哈希表：key → 该 key 最新值在文件中的字节偏移量。查询时先查表拿到偏移量，直接 seek 过去读，不用再扫全文件。

为什么放内存而不放磁盘？因为磁盘上的哈希表性能很差：大量随机 I/O、扩容代价高、哈希冲突处理繁琐——这条路基本走不通。

这个方案引入了几个新问题：

问题03：重启要重建

哈希表在内存中，也就意味着没有持久化存储，每次系统的重启都意味着哈希表的重建，依然需要走一遍事实表。对于大量数据的情况，重建可能非常耗时，这里会存在性能问题。这是存储于内存带来第一个问题。

我联想到曾经工作中遇到的一个场景：有的系统在对接口进行性能测试之前会提前请求几次接口作为预热，提前把需要的缓存建好，这样测起来更接近真实情况——和这里"重启后要重建索引才恢复速度"是一个道理。

问题04：内存装不下。

内存很好用，但是比较贵，容量也较小，全部用来存储大量不同的 key 值往往不符合实际。即使预算充足，性价比也太低了。这是存储于内存带来第二个问题。

问题05：没有范围查询。

哈希表能接受的输入是单个 key，没有批量查询。对于范围查询这种情况，依然需要把范围中的每一个 key 作为输入值进行一次查询，依然是性能问题。这不是存储于内存带来的问题，是哈希表存储带来的问题。

当前问题清单：问题01、问题03、问题04、问题05

对"问题05"深入分析——哈希为什么只能以单个 key 作为查询？那就需要看看哈希本身的原理："牺牲有序，换来高效的单点查询"。数值相邻的 key 可能散落在内存的各个角落，无法快速定位到相邻的 key。

那就把相邻的 key 放在一起呗？排序。SSTable 出现了。

SSTable (Sorted String Table) ：一个按 Key 排序、写入后基本不再修改的磁盘文件

排序带来一个哈希给不了的保证：如果 key 存在，它必然位于字典序上夹住它的两个已知 key 之间。这意味着索引不需要记住每一个 key——每隔几 KB 分一个块，只记每块的第一个 key。

比如索引里只有 handbag（偏移 1024）和 handsome（偏移 4096），要找 handiwork，直接 seek 到 1024 顺序扫几 KB 即可。这就是稀疏索引。其实字典就是这个结构：页眉只标本页第一个词，翻到大致位置再顺着找。"问题05"解决。

注意这一步顺手把"问题04"一起解决了：索引不用记全量，内存压力骤降。

但使用 SSTable 排序引来了新麻烦：

问题06：写的太慢

排序后文件追加非常痛苦。SSTable 写完即不可变，往中间插入一个 key，唯一的办法是把整个文件重写一遍。我们最初的出发点"追加写入快"荡然无存。

类似数组的插入

当前问题清单：问题01、问题03、问题06

那有没有插进去我就不用管顺序、自带排序的数据结构呢？有的。过去经验告诉我，Java 中的 TreeMap 就可以，插入自带排序。在书中，这个内存结构的标准称呼叫做 memtable。

为了尽可能节省内存，下一步就是设定一个指定大小：内存中存到一定数据量，整体写入文件成为一个段（segment），内存里只需在段清单上登记一下新来了几号段。段文件只可新增，不可修改。

但 memtable 在内存里，断电就没了。兜底方案还是追加写入：每次写入 memtable 的同时，顺手追加一份到磁盘上的日志文件。这个日志不排序也无所谓，它唯一的用途是崩溃后重放、把 memtable 恢复出来；memtable 一旦成功写成段文件，对应那段日志就可以扔了。它防的不是错误操作，而是没落盘的数据消失。"问题03"解决。

到这里，这套"memtable 内存缓冲 + 不可变段文件 + 日志兜底"的组合，就是 LSM 的主体了。

当前问题清单：问题01

LSM 顺手把挂了一路的"问题01"也收掉了：脏数据如何清理？

后台的 压实（compaction） 过程把多个段归并成一个新段，同一个 key 只抄最新的值过去，旧值不被抄、就地蒸发。归并的方式和归并排序的合并步骤一样：各段本来就有序，并排看第一个 key，最小的抄进输出。一次只需看每段当前一条，几乎不占内存。

删除数据。段文件不可修改，那怎么删除一个 key？答案是墓碑（tombstone）：删除也当成一次写入，追加一条"此 key 已删"的标记。它为什么有效？因为读取顺序是：内存（memtable）优先，然后从新段查到旧段，命中即停。墓碑比旧值更新，会先被命中——也就是我如果给这个 key 声明了墓碑，更旧的值就不用看了。

Steam 的卸载游戏——数据还在那儿，只是被标记为了垃圾，等待后续清理回收。这个比喻大体成立，但有一处方向要注意：旧值在合并时是正常被丢弃的，真正要多活一阵的反而是墓碑本身——它必须一路传播到最旧的段，确认身后再没有更老的版本可能"诈尸"，才能真的删除。也就是：值先死，碑后拆。

当前问题清单：NULL

其实还有一个 LSM 引入但自己已经解决的问题，可以继续看看：

问题07：查不存在的 key 很慢

最后一个问题：查一个不存在的 key，得把所有段翻一遍才能死心，太慢了。

解法是给每个段配一个布隆过滤器——一小段位图。建段时把每个 key 哈希成几个数字，把位图对应位置置 1；查询时对目标 key 做同样的哈希，检查那几位：

  • 只要有一位是 0，这个 key 绝对不在这个段里，直接跳过；
  • 全是 1 也只是"可能在"（可能是别的 key 碰巧凑齐了这几位，即假阳性），要进段核实。

它回答的不是"在哪"，只是"在不在"，而且错误是单向的：它的"不在"一定是"真不在"，它的"在"可能是"假在"。

当前问题清单：NULL

本篇的问题清单清空了，下篇将会介绍 LSM 的对手—— B 树，以及两者的读写较量。

如果内容有错，欢迎指出，一起讨论。