LSM

可视化演示

存储背景：为何后厨需要"白板哲学"

想象一个没有白板的餐厅后厨。每接到一道菜，大厨都要立刻翻开那本几十斤重的菜品档案册，在正确位置插入新内容。档案册放在仓库最里面，翻一次要跑一个来回，磁头在盘片间跳来跳去——这就是"随机写"。机械硬盘一次随机写大约需要 5~10 毫秒，而顺序写一块数据只要 50~100 微秒，差距接近一百倍：

核心架构：白板、底单、菜单册三件套

一个高效的后厨，需要三件东西配合：一块给服务员临时记菜名的白板，一本防止白板被擦掉后无法对账的登记底单，以及一排排整理好的菜单册。LSM 的架构恰好也是这三件套。

MemTable 是白板。它是一张驻留在内存中的有序表，通常用跳表（SkipList）实现。新数据像在白板上写粉笔字一样飞快插入，内部始终按键排序。白板容量有限，默认几 MB 到几十 MB，写满了就要揭下来换新板。

WAL 是登记底单（Write-Ahead Log，预写日志）。每次写入在动白板之前，先在一本流水账上追加一行。如果半夜停电白板被擦掉，第二天照着底单就能把所有菜名抄回来。底单是顺序追加的，几乎不消耗时间。

SSTable 是菜单册（Sorted String Table）。它是一组磁盘上的有序键值文件，一旦生成就只读不改，内部键已排好序，并附带快速定位的索引和布隆过滤器。对应到后厨，就是那本印刷精美、按菜名拼音排列、还带目录的终极档案。

三者分工恰如后厨的"快、稳、全"：白板快，底单稳，菜单册全。任何写入都先落在白板和底单上，慢慢沉淀成菜单册；任何读取都要先看白板，再翻最新的菜单册——这就引出了下一节的写入路径。

写入路径：先写白板，攒满再装订

当服务员报来一道新菜"宫保鸡丁"，后厨的标准动作是：先在登记底单上快速记一行"12:30 宫保鸡丁"，再把菜名写到白板上。注意顺序——先写底单，再写白板。这样就算下一秒停电，底单还在，菜不会丢。

流程对应 LSM 写入路径四步走：第一步，写入请求先追加到 WAL；第二步，数据插入内存中的 MemTable；第三步，当 MemTable 到达阈值（例如 4MB），它被"冻结"成只读的不可变版本，同时新开一块空白板继续接单；第四步，后台线程把冻结的 MemTable 一次性刷成 SSTable 落到磁盘，这个过程叫 flush（刷盘）。

这套流程的最大收益，是把"频繁小写"变成"批量大写"。如果 n 条数据直接随机落盘，需要 n 次随机写；而 LSM 攒满一批才刷一次盘，刷盘次数近似为：

Compaction：打烊后整理菜单册

白板一张张揭下来装订成册，菜单册越堆越多。顾客想找"宫保鸡丁"，可能要翻五本册子；有些旧册子里的做法已被新册子覆盖，还占着地方。于是后厨每晚打烊后要做一件重要的事：把同类菜单合并成一本精编大目录，删掉过期菜谱，腾出空间——这就是 Compaction（合并压缩）。

LSM 最常见的合并策略有两种。Leveled Compaction（分层合并） 把数据划分为 L0、L1、L2……多个层级，每层容量大约是下一层的十分之一。当某层数据超阈值，后台线程就和下一层做一次归并，把数据下推。这种策略读路径短、读放大低，但合并频繁，写放大高。

Tiered Compaction（分代合并） 则相反：容量相近的 SSTable 先凑成一组，同组数量达到阈值才一次性合并成一个大文件。它写放大更低，但读放大更高——同层的散落文件更多。RocksDB 等引擎允许按场景切换或混合使用。

合并虽然发生在后台，但并非无偿：合并时重写数据，会让实际写入磁盘的数据量超过应用写入量，这个倍数称为"写放大"（Write Amplification）。调优 LSM 的过程，本质上就是在写放大、读放大、空间放大三个指标之间反复权衡。

读路径优化：给菜单册配封面索引

白板哲学带来高吞吐，却给读添了麻烦：查一道菜，要先看白板，再看最新几本菜单册，逐层翻找。如果盲目翻遍所有册子，就是 LSM 的"读放大"——一次查询可能触发多次磁盘 IO。后厨的办法是：每本菜单册封面印一张"菜名速查表"。

这张速查表就是 布隆过滤器（Bloom Filter）。它把册子里的菜名映射到一个位数组上，查询时先过速查表：表上说"没有"，那就一定没有，不必翻册子；表上说"有"，才真正翻开确认。它可能"谎报有"（误判），但绝不会"漏报有"。这个不对称特性完美契合读路径。

误判率 p 与位数组长度 m、哈希函数个数 k、已插入元素数 n 的关系为：

工程实现：LevelDB 与 RocksDB 的后厨风格

同一套"白板哲学"，落地到不同餐厅会有完全不同的风格。LevelDB 是 Google 打造的原版后厨：简洁、克制、单线程合并，适合在单机环境提供稳定的基础 KV 能力。它只有最基本的 MemTable、SSTable、Compaction，像一家只做几道招牌菜的小馆子，可靠但扩展性有限。

RocksDB 则是 Facebook 在 LevelDB 基础上改造的中央厨房。它引入多线程 Compaction，合并任务可并行执行，后厨不再被单次大合并卡死；支持列族（Column Family），一本菜单册可以分成多个分区独立管理；支持多种压缩算法（Snappy、Zstd、LZ4），磁盘空间利用率更高，吞吐和灵活性大幅提升。

实际调优中几个参数最常被关注：write_buffer_size 决定白板多大——调的过大，刷盘和后续合并的体积会变大，反而引发更长的停顿；max_background_jobs 控制后台合并线程数；block_cache 大小直接决定热数据命中率。调优就像调整后厨备菜流程：菜太多就加人手，白板太小就换大板，但每一步都在读写放大之间做取舍。

选择哪家取决于场景：轻量嵌入式场景选 LevelDB，高并发、高可用、需要弹性调优的场景选 RocksDB——它也因此成为 TiKV、Flink 状态后端等众多系统的存储底座。

生产应用：白板哲学撑起的分布式大厦

单个后厨的白板哲学，放大到连锁餐饮集团，就成了分布式系统的高吞吐基石。LSM 几乎垄断了写密集场景的存储底座。

在 KV 存储领域，HBase、Cassandra、TiKV 的底层都用 LSM 引擎。以 TiKV 为例，它为 TiDB 提供分布式事务键值存储，RocksDB 就是它的存储引擎。电商订单写入、时序指标采集、用户行为日志——这些每秒几十万次写入的场景，传统 B+ 树很快会被随机写拖垮，而 LSM 的批量顺序写能轻松顶住。

在 消息系统领域，Kafka 的日志存储同样借鉴了 LSM 的核心思想——所有消息只追加不修改，写入全部走顺序 IO。它虽然不是严格的 LSM-Tree，但"用顺序写换吞吐"的哲学同出一源。消息队列的高吞吐，追根溯源和 LSM 是同一个老师教的。

生产环境使用 LSM 引擎，最常踩的坑是 Compaction 风暴：大量数据合并触发时，瞬间占满 IO 和 CPU，读写延迟飙升。经验做法是提前规划 Compaction 时间窗口、限制后台合并带宽、监控 write stall 指标。理解了白板-菜单册模型，这类故障的排查思路就很清晰——不是菜有问题，是打烊后整理册子的动作把路堵了。

AI 应用场景

Python 演示

import osimport tempfile  class SimpleLSM:    ""“极简 LSM-Tree 演示引擎：MemTable + WAL + SSTable + Compaction”""     def init(self, mem_threshold=5, data_dir=None):        self._memtable = {}        self.sstables = []        self.mem_threshold = mem_threshold        self.data_dir = data_dir or tempfile.mkdtemp()        self._wal_path = os.path.join(self.data_dir, "wal.log")        self._wal = open(self._wal_path, "a", encoding="utf-8")     def put(self, key, value):        # 第一步：追加 WAL（登记底单）        self._wal.write("%s=%s\n" % (key, value))        self._wal.flush()        # 第二步：写入 MemTable（白板）        self._memtable[key] = value        if len(self._memtable) >= self.mem_threshold:            self.flush()     def flush(self):        # 第三步：冻结 MemTable，按键排序生成 SSTable        table = dict(sorted(self._memtable.items()))        self.sstables.append(table)        self._memtable = {}     def get(self, key):        # 第四步：先查白板，再倒序查最新菜单册        if key in self._memtable:            return self._memtable[key]        for table in reversed(self.sstables):            if key in table:                return table[key]        return None     def compact(self):        # 第五步：合并所有 SSTable，去重保留最新值        merged = {}        for table in self.sstables:            merged.update(table)        self.sstables = [dict(sorted(merged.items()))]     def close(self):        self._wal.close()  if name == "main":    db = SimpleLSM(mem_threshold=5)    for i in range(20):        db.put("key-%02d" % i, "value-%d" % i)    print(“SSTable 数量：”, len(db.sstables))    print(“查询 key-03：”, db.get("key-03"))    db.put("key-03", "updated")    print(“覆盖后查询 key-03：”, db.get("key-03"))    db.compact()    print(“合并后 SSTable 数量：”, len(db.sstables))    print(“合并后 key-03：”, db.get("key-03"))    db.close()

常见误区

面试题