LSM树如何实现高速写入

可视化演示

展示LSM树从MemTable内存写入、SSTable刷盘到Compaction层级合并的全流程，通过模式切换理解随机写转顺序写的核心机制。

写入瓶颈背景

想象一座藏书满到溢出的图书馆。管理员要求每来一本新书，必须立刻按编号插回书架的正确位置。可书架几乎满了，插一本新书意味着把后面一整排书全部往外挪一格，几百本书跟着移动，手臂酸、耗时长。数据库中的 B+ 树就像这座图书馆：叶子节点是书架，插入一条记录要定位叶子，节点满了还要分裂、向上调整父节点指针。在磁盘上，这种工作方式对应着随机写——磁头像搬运工一样反复寻道，每挪一次要花费数毫秒甚至十几毫秒。

这里的关键差距在于：机械硬盘的顺序写带宽可达每秒上百 MB，而随机写每秒只能完成几百次小 I/O。假设一次随机写要 10ms 寻道，1 万次随机写就要 100 秒；但如果把 1 万条小数据合并成一次顺序写，只需几十毫秒。两者差距可达一两个数量级。存储引擎的设计者们意识到：谁能把随机写凑成顺序写，谁就赢了。

$$\text{随机写耗时} \approx T_{\text{寻道}} + \frac{\text{数据量}}{\text{带宽}} \quad \gg \quad \text{顺序写耗时} \approx \frac{\text{数据量}}{\text{带宽}}$$

1. 随机写耗时：一次随机写入磁盘的总开销 = 磁头寻道时间 + 旋转等待 + 实际传输数据的时间。

$$T_{\text{寻道}} + \frac{\text{数据量}}{\text{带宽}}$$

2. 远大于符号：\gg 表示左边远大于右边，强调随机写比顺序写慢得多。

$$\gg$$

3. 顺序写耗时：数据连续摆放，磁头几乎不用移动，耗时主要就是传输时间。

$$\frac{\text{数据量}}{\text{带宽}}$$

所以 LSM 树的发明者换了个思路：既然每次插书都要挪书架，那不如把新书全部堆在门口（内存），攒够一批后按编号排好，一次性推进仓库（磁盘）。这种“先记账、后整理”的模式，把数据库从“每步都严格排好”的教条主义，解放成了“分批入库、事后整理”的实用主义。

MemTable缓冲

新包裹到达快递仓库后，并不直接上货架，而是先放到前台登记台。工人们只需要把包裹往登记台上一放，随手按编号排个序——这个动作在内存里完成，快如闪电。这个登记台就是 LSM 树的 MemTable（内存表）。它通常用跳表（Skip List）实现：一种多层级链表，可以在内存中高效地保持 Key 有序，插入和查找的期望复杂度都是 \\(O(\log n)\\)，比数组插入动辄移动整个区间要灵活得多。

你可能会问：数据只放内存，断电不就全丢了吗？仓库的解决办法是：每来一件包裹，先在签到簿上记一笔（WAL，Write-Ahead Log，预写日志），再放登记台。这本签到簿按顺序追加写在磁盘上，写着“编号 X 的包裹已签收”。哪怕内存断电蒸发，重启后照着签到簿就能把包裹重新唤回。WAL 是顺序追加写，速度极快，它用极小的代价换来了不丢数据的保证。

$$\text{Cost}_{\text{MemTable 操作}} = O(\log n)$$

1. 操作代价：Cost 表示一次插入或查询需要的比较/移动次数。

$$\text{Cost}_{\text{MemTable 操作}}$$

2. 大 O 记号：O 用于描述算法耗时的增长趋势，忽略常数项。

$$O$$

3. 对数复杂度：\log n 表示耗时与数据量的对数成正比。n 是内存中数据条数。

$$\log n$$

有了登记台和签到簿，写入流程变成：先写 WAL（顺序写磁盘）→ 再写 MemTable（内存操作）→ 返回成功。两次都是廉价操作，所以单条写入的延迟极低，而且多条写入可以在内存里自然“攒批”——这为后面整批刷盘创造了条件。登记台看似只是临时堆放，实则是整个 LSM 快写体系的发动机。

SSTable落盘

登记台再快也有容量上限。当包裹堆到一定数量，仓库就会启动“封箱流程”：把登记台上的所有包裹按编号彻底排好序，封进一个标注好编号范围的包裹箱，然后让工人扛着这箱包裹，放到仓库的指定货区。这个动作在存储引擎里叫 flush（刷盘）：先把 MemTable 冻结为不可变（Immutable）状态，不再接收新写入，然后由后台线程把它整体写成一个 SSTable 文件。

SSTable 全称 Sorted String Table（有序字符串表），它最关键的特性是内部按键有序、生成后不可修改。正因如此，刷盘过程可以一路顺序追加写磁盘，磁头从头走到尾，没有丝毫回头——这就是“新箱子永远只往最上层摞”的磁盘版本。新的写入请求会立刻使用新的 MemTable，旧表变成文件后不再变化，读写互不干扰。

$$\text{第 } k \text{ 层容量 } S_k = S_0 \times R^k$$

1. S_k：第 k 层可容纳的数据总量，例如 L1 层的总容量。

$$S_k$$

2. S_0：第 0 层（最浅层）的基础容量，由单次刷盘的 MemTable 大小决定。

$$S_0$$

3. 容量放大因子 R：每向下移一层，容量放大 R 倍，通常取 10 左右。

$$R$$

4. k 次幂：S_0 乘以 R 的 k 次方——层数越深，容量指数级膨胀。

$$R^k$$

于是磁盘上的数据呈现出层次感：L0 层零星摆着刚刷下来的小箱子，L1、L2 层则是整理过的中箱和大箱。分层让“新数据永远在最上面、旧数据沉在下面”成为一种物理秩序，而这套秩序正是 Compaction 表演的舞台。

Compaction合并

仓库开久了，问题来了：相同编号的包裹可能散落在好几个箱子里，有的箱子贴着作废标签，有的内容重复。查找越来越费劲，空间越来越浪费。于是仓库安排了一位整理工，定期把几个小箱子倒出来，按编号重新归并为一个大箱子——这个过程就是 Compaction（压实/合并）。

Compaction 的触发时机通常看阈值：比如 L0 层的箱子数量超过 4 个，就触发一次合并；合并结果推入 L1，若 L1 又超过容量上限，就继续向 L2 合并。合并算法本质是多路归并：同时打开多个 SSTable，像流水线一样比较各个文件的当前 Key，挑最小的输出到新文件，遇到重复 Key 保留最新版本。这个“新版本覆盖旧版本”的规则，让更新操作也能延迟到合并时才落地。

$$\text{Write Amplification（写放大）} = \frac{\text{实际写入磁盘的数据量}}{\text{真实新增的数据量}}$$

1. 写放大：合并在后台重写数据文件，导致实际落盘量超过净新增量，这个倍数就是写放大。

$$\text{Write Amplification}$$

2. 分子：包括新写入数据和所有合并重写的老数据——磁盘实际消耗的总 I/O。

$$\text{实际写入磁盘的数据量}$$

3. 分母：用户真正提交的新数据总量。

$$\text{真实新增的数据量}$$

整理工的付出是值得的：合并后箱子更少、更大，查找时可以跳过更多文件，存储空间也得到回收。但代价是额外的磁盘 I/O——写放大。LSM 树的设计本质是在写放大、读放大、空间放大三者之间拧螺丝：层数多一层，读更慢；合并勤一点，写放大更高；合并懒一点，空间占用上涨。优秀的存储引擎正是在这三把刀之间走钢丝。

读放大优化

在仓库里找一件包裹，直觉做法是从最新的箱子往前翻——因为新版本总比旧版本新。但 LSM 的层数一多，“从最新到最旧倒着翻”就变成了噩梦：最坏情况下要把每一层的每一个箱子的封面都拆开看一眼，这就是读放大（Read Amplification）。读放大的规模 = 层数 × 每层平均箱子数。相比 B+ 树从根走到叶子的 3~4 次 I/O，LSM 的读放大可以轻松到几十倍。

仓库的解决办法是：给每个箱子贴一张快查贴纸（布隆过滤器，Bloom Filter）。贴纸的原理很巧妙——数据写入箱子时，用 k 个哈希函数把 Key 映射到位数组的 k 个位置上，全部涂黑；查询时同样算 k 个位置，只要有一个没被涂黑，就说明“这个 Key 肯定不在箱子里”。它允许偶尔误判（说“在”其实不在），但绝不漏判（说“不在”就一定不在）。

$$P_{\text{误判}} \approx \left(1 - e^{-\frac{kn}{m}}\right)^k$$

1. 误判率 P：布隆过滤器“误报存在”的概率，记作 P。

$$P_{\text{误判}}$$

2. 参数 k、n、m：k 个哈希函数；n 个已插入的 Key；m 个 bit 的位数组。

$$k, n, m$$

3. \frac{kn}{m}：每个 bit 被命中的平均次数，决定了某一位为 0 的概率。

$$\frac{kn}{m}$$

4. k 次方：k 个哈希位置全部冲突的概率——这正是误判的来源。

$$\left(1 - e^{-\frac{kn}{m}}\right)^k$$

贴上快查贴纸后，查询一个 Key：先扫 L0 最上面几个箱子的贴纸，说“不在”就跳过；说“在”才真正打开箱子找。绝大多数不存在的 Key 会被一张贴纸拦住，只需一次内存位运算，完全不用碰磁盘。配合块缓存（Block Cache）把热数据留在内存里，LSM 的读性能虽然还是不如 B+ 树，但已经足够应对绝大多数业务场景——毕竟它换来了惊人的写吞吐。

删除与更新

快递单填错了怎么办？你没法拆开已经封好的箱子把包裹拿出来——箱子是封死的。快递仓库的做法是：在箱子上贴一张醒目的作废标签，注明“编号 X 作废”，照常把箱子放进仓库。客户来取件时，看到作废标签，就回复“这个包裹没了”。在 LSM 树里，这张作废标签叫墓碑（Tombstone）：删除操作并不去磁盘删数据，而是写入一条特殊标记 key -> tombstone。

这种设计看似笨拙，实则是大智慧。更新也一样：新版本直接写入 MemTable，旧版本留在地下层躺着。真正的物理删除发生在Compaction 整理时——当合并程序遇到墓碑标记，就知道该 Key 的旧版本可以全部丢弃；当遇到同一个 Key 的多个版本，只保留最新一个。于是，被“作废”的数据像落叶一样在一次次合并中被扫出仓库，空间得以回收。

$$\text{Tombstone} + \text{Key}_{\text{old}} \xrightarrow{\text{Compaction}} \varnothing$$

1. Tombstone（墓碑）：删除时写入的特殊占位标记，表示该 Key 已逻辑删除。

$$\text{Tombstone}$$

2. Key 的旧版本：历史上写入的旧数据，一直静静躺在深层的 SSTable 里。

$$\text{Key}_{\text{old}}$$

3. 合并箭头：只有当 Compaction 扫描到这两者时，清理动作才会发生。

$$\xrightarrow{\text{Compaction}}$$

4. 空集符号：表示该 Key 的全部痕迹被彻底清除，物理空间被回收。

$$\varnothing$$

有趣的是，墓碑本身也有副作用：如果删除一个不存在的 Key，墓碑会一直存活到合并被清除，占用空间。好在工程上可以给墓碑加时间戳，到期自动丢弃。这套“延迟删除”机制让 LSM 在写密集场景下如鱼得水——删除不再是一次昂贵的磁盘操作，而是一条便宜的追加记录，完美绕开了传统 B+ 树“删除要改写文件”的痛点。

开源应用

这套仓库管理术一经问世，立刻被各家“大仓库”采用。Google 的 LevelDB 是教科书级实现，用 C++ 写就；Meta 在它基础上强化了并发与性能，推出 RocksDB，成为业界最流行的嵌入式 KV 存储引擎之一。为什么 AI 和分布式系统如此偏爱它？因为它们的写请求太疯狂了——点击日志、监控指标、特征数据，每秒几十万次写入，传统 B+ 树根本扛不住。

分布式数据库是 LSM 的最大受益者。TiKV（TiDB 的存储层）用 RocksDB 作为单节点引擎，上层做分布式事务，底层靠 LSM 的高写入吞吐支撑 OLTP 场景；HBase 的 HFile 同样源自 LSM 思想；Cassandra 更是将 LSM 与分布式哈希天然结合。可以说，现代“写多读少”的互联网基础设施，绕不开 LSM 的影子。

$$\text{总代价} = \alpha \times \text{写放大} + \beta \times \text{读放大} + \gamma \times \text{空间放大}$$

1. 总代价：存储引擎在运行中的综合开销，是调优要最小化的目标函数。

$$\text{总代价}$$

2. 三个放大项：写放大、读放大、空间放大，此消彼长。

$$\text{写放大} + \text{读放大} + \text{空间放大}$$

3. 权重系数：\alpha、\beta、\gamma 表示业务对三者的敏感度——写多场景让 \alpha 大，读多场景让 \beta 大。

$$\alpha, \beta, \gamma$$

今天的 LSM 早已不是单纯的数据结构，而是一套成熟的工程哲学。当你面临“每秒百万级写入、数据不丢、还能按序扫出来”的需求时，选择 RocksDB 或 TiKV 这类 LSM 系存储，就是在聘请那位经验丰富的仓库整理工——它或许不算完美的读书人，但绝对是顶级的搬货工人。

AI 应用场景

Python 演示

import hashlibimport os  class MemTable:    def __init__(self, limit=8):        self.data = {}        self.limit = limit     def put(self, key, value):        self.data[key] = value     def is_full(self):        return len(self.data) >= self.limit     def freeze(self):        items = sorted(self.data.items())        self.data.clear()        return items  class BloomFilter:    def __init__(self, size=256, k=3):        self.bits = [False] * size        self.size = size        self.k = k     def _hash(self, key, i):        raw = hashlib.md5("{}-{}".format(key, i).encode()).hexdigest()        return int(raw, 16) % self.size     def add(self, key):        for i in range(self.k):            self.bits[self._hash(key, i)] = True     def may_contain(self, key):        for i in range(self.k):            if not self.bits[self._hash(key, i)]:                return False        return True  class SSTable:    def __init__(self, path, items):        self.path = path        self.bloom = BloomFilter()        self.items = {}        for k, v in items:            self.items[k] = v            self.bloom.add(k)        with open(path, "w", encoding="utf-8") as f:            for k, v in items:                line = "{}\t{}\n".format(k, "TOMBSTONE" if v is None else v)                f.write(line)     def get(self, key):        if not self.bloom.may_contain(key):            return None, False        if key in self.items:            return self.items[key], True        return None, True  class LSM:    def __init__(self, root="lsm_demo", limit=8, levels=3):        self.root = root        self.mem = MemTable(limit)        self.levels = [[] for _ in range(levels)]        self.seq = 0        os.makedirs(root, exist_ok=True)     def put(self, key, value):        self.mem.put(key, value)        if self.mem.is_full():            self._flush()     def delete(self, key):        self.mem.put(key, None)     def _flush(self):        path = os.path.join(self.root, "sst_{}.sst".format(self.seq))        self.seq += 1        table = SSTable(path, self.mem.freeze())        self.levels[0].append(table)        if len(self.levels[0]) >= 3:            self._compact(0)     def _compact(self, level):        merged = {}        for table in self.levels[level]:            for k, v in table.items.items():                merged[k] = v        alive = [(k, v) for k, v in sorted(merged.items()) if v is not None]        target = level + 1 if level + 1 < len(self.levels) else level        for table in self.levels[level]:            os.remove(table.path)        self.levels[level] = []        path = os.path.join(self.root, "sst_{}.sst".format(self.seq))        self.seq += 1        new_table = SSTable(path, alive)        self.levels[target].append(new_table)        if len(self.levels[target]) >= 3 and target < len(self.levels) - 1:            self._compact(target)     def get(self, key):        if key in self.mem.data:            return self.mem.data[key]        for tables in self.levels:            for table in tables:                val, found = table.get(key)                if found:                    return val        return None  if __name__ == "__main__":    db = LSM()    for i in range(30):        db.put("user:{}".format(i), "value-{}".format(i))    print("查询 user:5 ->", db.get("user:5"))    db.delete("user:5")    print("删除后查询 user:5 ->", db.get("user:5"))    print("查询 user:6 ->", db.get("user:6"))    print("SSTable 文件数 ->", len(os.listdir("lsm_demo")))

1. items = sorted(self.data.items())冻结 MemTable 时先按键排序，保证刷盘出的 SSTable 内部有序。
2. self.levels[0].append(table)新刷出的 SSTable 直接追加到 L0 层，磁盘写入天然顺序化。
3. if len(self.levels[0]) >= 3:达到阈值立即触发 Compaction，控制 L0 文件数量，抑制读放大。
4. merged[k] = v合并时用字典按键去重，后写入的版本自动覆盖旧版本，实现“最新版本胜出”。
5. alive = [(k, v) for k, v in sorted(merged.items()) if v is not None]过滤掉墓碑（None 值），物理删除真正发生。
6. if not self.bloom.may_contain(key):布隆过滤器说“没有”就直接跳过整个文件，省去一次磁盘读。
7. db = LSM()一个迷你数据库实例，内部自包含内存表、分层文件和合并逻辑。

常见误区

面试题