LSM-Tree LevelDB与RocksDB存储引擎

可视化演示

展示LSM-Tree写入路径（WAL→MemTable→SSTable分层）与Compaction策略对比（Leveled vs Size-tiered），理解LevelDB/RocksDB的高写入吞吐量设计。

存储架构三件套

小林的前台桌上摆着三样法宝：一本厚厚的“借还登记台账”、一张宽敞的“新书速递桌”、以及书库里成排的大书架。每本书到馆，她先在台账上记一笔，再放到速递桌上供读者取阅，桌子放不下时才搬到书库书架上。这套制度的最大好处是：读者还书不需要立刻插回书架，前台接书、登记、上桌三步就完事，速度快得飞起。数据库世界的 LSM-Tree 也遵循同样的逻辑——WAL 就是台账，MemTable 就是速递桌，SSTable 就是书架。

MemTable 是常驻内存的有序表，底层通常用跳表（Skip List）实现。所有写请求先在这里落一脚，由于内存操作极快，写入吞吐自然就高。但内存毕竟是“速递桌”，容量有限、还怕断电，于是有了 WAL（Write-Ahead Log，预写日志）：每次写 MemTable 前，先把这条记录以追加方式顺序写入磁盘日志文件，一旦机器崩溃，重启后靠 WAL 就能把速递桌上的书“复原”。当 MemTable 攒到阈值，它会被转成不可变的 Immutable MemTable，后台再刷成磁盘文件——这就是 SSTable（Sorted String Table，有序字符串表）。SSTable 一经写出就永不再改，只能通过合并产生新文件来更新，这就是“书架上的书不能改，只能重新整理一版”的道理。

这三件套的分工清晰地映射到硬件上：MemTable 用内存（快但易失），WAL 用磁盘顺序区（慢但持久），SSTable 用磁盘随机读区（容量大）。内存当“前台”、磁盘当“库房”的双存储介质设计，让 LSM-Tree 既能享受内存的速度，又能拥有磁盘的容量——小林自豪地说，这就叫“前台快接单，库房装得下”。

写入流程四步走

想象一下图书馆的还书高峰：读者排着队，每人都要还两三本书。如果按老办法把书逐本插回书架，队伍能排到门口。小林的做法是：先快速登记台账，把书往速递桌上一放，读者转身就走；等桌子满了，保洁阿姨再把整桌书推到书库上架。四个动作——登记、放桌、换桌、上架——完美对应 LSM-Tree 的写入四步。

第一步，顺序写 WAL。把写入记录以追加（append）方式写进日志文件末尾。磁盘顺序写的速度远超随机写，因为磁头不用反复寻道，这就像台账本越写越厚，笔尖始终在最后一页，从不翻回前面。第二步，写 MemTable。在跳表里插入一条有序记录，纯内存操作，微秒级完成。第三步，满了转不可变。MemTable 达到阈值后，立刻冻结成只读的 Immutable MemTable，同时新开一张空表继续接客——好比前台桌子满了就换一张备用桌。第四步，后台刷盘成 SSTable。后台线程把 Immutable MemTable 的内容按键排序后写成 SSTable 文件，写完后 WAL 中对应记录即可安全删除。

这个流程最精妙之处在于：用户请求等到的只是 WAL 追加 + 内存写入两步，真正的磁盘整理全部被“延迟”到后台。LevelDB 还提供 WriteBatch，把多条写请求合并成一批提交，一次 fsync 刷一批数据，进一步摊薄日志落盘成本。这一优化俗称 Group Commit（组提交），就像小林把十个读者的还书登记一口气写到台账上，而不是每本都停顿一次。

四步流程环环相扣，核心哲学是“前台快速应答，后台慢慢整理”。小林发现，自从用了这套流程，读者排队时间缩短了 80%，代价只是整理库房时多走几步路——这笔账，图书馆愿意付。

分层存储金字塔

书库不是一个大平层，而是分成了好几层：一楼是刚上架还没来得及细分的“临时推车区”，二楼是按大类排好的正式书架，三楼、四楼面积更大、书架也更整齐。每往下一层，能容纳的书量就翻十倍。这个金字塔结构，正是 LSM-Tree 的分层设计。

第 0 层（L0）的特殊之处在于：文件之间没有任何全局顺序可言，新刷盘的 SSTable 直接堆在 L0，彼此 key 范围可以重叠——就像临时推车上的书，谁先到就摞谁上面。而从 L1 开始，每一层内部的所有 SSTable 共同构成一个全局有序的键空间，文件之间互不重叠，而且每层覆盖的 key 范围恰好拼成完整全集。为什么要这么设计？因为“完全有序”能大幅降低查询和合并的复杂度：查某个 key 时，每层最多只需读一个文件；合并时也能像归并排序一样顺滑地合并两份有序表。

容量增长遵循等比规律：若 L0 基准容量为 C0，那么第 i 层的容量是 C0 乘以放大因子 T 的 i 次方，LevelDB 中 T 取 10。也就是说，L1 容量是 L0 的 10 倍，L2 是 100 倍，L3 是 1000 倍。这就像楼越往下空间越大，因为下层要承接上层所有合并下来的数据，还要保留足够余量让合并“有地方倒腾”。

层数也不能无限增加。级别越多，读路径要检查的层就越多，合并的战线也拉得越长，所以工程上通常限制总层数，并让 L0 容量尽量小、深层容量尽量大。小林管这叫“塔尖要小，塔基要稳”——顶层快速周转，底层海量沉淀，中间的每一层都像书架上的隔板，把混乱逐级沉降为秩序。

压缩策略双雄会

书架不会自己变整齐，需要有人定期整理。整理的方式有两种流派：LevelDB 的“逐层精整型”和 Cassandra/HBase 常用的“攒箱封箱型”。小林把这两种策略比作两种整理习惯：一种是每天下班后把推车上的书逐本归位到正式书架，并顺手清掉内容重复的旧版本；另一种是等小箱子攒够一大箱后，直接封箱贴上标签送进库房，省去频繁倒腾。

Leveled Compaction（分层合并）是 LevelDB 的默认策略。当 L0 的文件数超过阈值（通常 4 个），就挑出与某个 L0 文件 key 范围重叠的 L1 文件，与之一并合并成新的 L1 文件；新文件若超出 L1 容量上限，再向下层滚动合并。这个过程像“冒泡”：数据逐层下沉，每次合并都清理掉过期数据和墓碑标记。它保证每一层内部严格有序，读放大小，但代价是同一份数据可能被反复重写多次——这就是写放大的来源。

Size-tiered Compaction（按大小分层合并）则完全不同：不做逐层精整，而是把大小相近的 SSTable 归为一组，攒够数量后一次性合并成一个更大的文件。这就像小箱子不急着拆箱上架，而是攒够 10 箱后封成一大箱再进库。它的写放大极小（数据最多被搬动几次），写入吞吐更高；但读放大和空间放大明显——找一本书可能要翻遍好几只大箱子，而且合并前同一 key 的多个版本同时占着空间。

对时序日志这类“写完几乎不读”的场景，Tiered 是更优解；对需要频繁点查的在线业务，Leveled 的严格有序更合适。小林最后总结：整理书架没有万能方案，要么多花力气保持整齐（Leveled），要么少收拾但找书费劲（Tiered）——图书馆要按读者习惯选策略，数据库要按读写比例做取舍。

读取优化组合拳

读者来找一本《AI 入门》，小林会先扫一眼新书速递桌（MemTable），没有再去楼下的临时推车区找（L0），再往下每一层书架各看一个位置（L1 及以上）。因为每层有序，每层只需定位一个文件，读路径清晰。但如果每层都真的翻一遍文件，磁盘 IO 次数太多——这就是“读放大”：一次 Get 最多可能触发 MemTable 一次查找、L0 每个文件一次检查、以及每层各一次磁盘读，累计起来能产生上十次 IO。

为了治读放大，第一件武器就是 Bloom Filter（布隆过滤器），可以把它想象成每层书架门口挂着的一本“查书便签机”：把书名列成位图指纹，问它“这本书在不在这层”，它回答“不在”就绝对正确，回答“在”却可能偶尔误报。查询时先问便签机，如果它说“不在”，这一层直接跳过，省下整个文件的磁盘 IO。第二件武器是 block cache（块缓存），SSTable 在磁盘上是按 4KB~64KB 分块的，热数据块缓存在内存里，重复读同一块就不用再去磁盘。第三件武器是前缀压缩与索引：SSTable 文件头部维护稀疏索引，二分定位 key 所在数据块，再配合布隆、缓存、索引三层过滤，把一次点查的 IO 次数压到 1~2 次。

布隆过滤器本身也有学问：位数组越长、哈希函数个数越合适，误判率越低，但占用内存也越大。工程上通常把误判率控制在 1% 左右，作为“存在性判断”的性价比最优解。

有了便签机、缓存和索引这三件套，读放大从“每层都翻箱”变成“每层先问一句”。小林笑着说，这就是为什么读者在这么大的图书馆里找书，平均只需要打开一个抽屉——存储引擎把“多问多翻”优化成了“先问后翻、问完不翻”。

引擎对比与进化

LevelDB 是 Google 工程师 Jeff Dean 设计的单机 KV 存储引擎，开图书馆基础制度的先河；RocksDB 则是 Facebook 基于 LevelDB 的“集团化改造”，把总馆制度复制到多分馆、多员工的大型图书馆网络。两者同宗同源，但 RocksDB 在工程能力上做了大量升级。

LevelDB 的特点可以概括为“简单而优雅”：单线程后台合并，内存表只有一个，写路径清晰，代码量小，非常适合嵌入式场景。但它也有先天局限：单线程 Compaction 在面对海量写入时容易成为瓶颈，写入稍快就会出现“写停顿”（Write Stall）——好比图书馆只有小林一个整理员，前台收书太快，书堆到天花板，只能暂停接客。

RocksDB 针对这些短板逐一开刀。第一，列族（Column Family）：把一个大库拆成多个独立命名空间，每个列族有自己的 MemTable 和 SSTable，相当于图书馆开了多个分馆，互不干扰。第二，多线程并行 Compaction：合并任务可以拆成多个子任务交给线程池并行执行，整理效率成倍提升。第三，合并算子（Merge Operator）：新增“直接在书页上加更正签”的能力，不用把整本书拿出来重写，适合计数器、JSON 字段更新这类高频小更新。此外还有自适应层数调整、前缀布隆过滤器、Cuckoo 哈希等改进，以及更细粒度的配置项，让用户能把写放大、读放大、空间放大调到适合自己业务的平衡点。

选型建议也很直白：如果只是嵌入式单机小数据量，LevelDB 的轻量是优点；如果是大数据、高并发、需要列族隔离或多线程合并的生产环境，RocksDB 几乎是标配。小林最后感叹：LevelDB 是一本写得很好的教科书，而 RocksDB 是把教科书变成了一座能应对百万读者的大图书馆——读懂了前者，你就能理解后者的每一个设计意图。

AI 应用场景

Python 演示

import hashlib class BloomFilter:    def __init__(self, size=1024, hashes=3):        self.size = size        self.hashes = hashes        self.bits = 0     def _hash(self, key, i):        return int(hashlib.md5((str(i) + str(key)).encode()).hexdigest(), 16) % self.size     def add(self, key):        for i in range(self.hashes):            self.bits |= (1 << self._hash(key, i))     def might_contain(self, key):        for i in range(self.hashes):            if not (self.bits & (1 << self._hash(key, i))):                return False        return True  class SSTable:    def __init__(self, data, seq):        self.seq = seq        self.data = sorted(data.items())        self.bloom = BloomFilter()        for k, _ in self.data:            self.bloom.add(k)     def get(self, key):        if not self.bloom.might_contain(key):            return None        for k, v in self.data:            if k == key:                return v        return None  class LSMTree:    def __init__(self, mem_limit=3):        self.mem = {}        self.wal = []        self.sstables = []        self.mem_limit = mem_limit        self.seq = 0     def write(self, key, value):        self.mem[key] = value        self.wal.append((key, value))        if len(self.mem) >= self.mem_limit:            self._flush()     def _flush(self):        self.seq += 1        self.sstables.append(SSTable(self.mem, self.seq))        self.wal.clear()        self.mem = {}        self._maybe_compact()     def _maybe_compact(self):        if len(self.sstables) < 3:            return        merged = {}        for t in sorted(self.sstables, key=lambda x: x.seq):            for k, v in t.data:                merged[k] = v        self.sstables = [SSTable(merged, self.seq)]     def get(self, key):        if key in self.mem:            return self.mem[key]        for t in reversed(self.sstables):            v = t.get(key)            if v is not None:                return v        return None  if __name__ == '__main__':    lsm = LSMTree()    for i in range(9):        lsm.write('key%d' % i, i)    print(lsm.get('key5'))    print(lsm.get('missing'))    print('SSTable数量:', len(lsm.sstables))

1. self.bits |= (1 << self._hash(key, i))布隆过滤器用按位或把 k 个哈希位标记为 1，对应“在便签机上记下这本书的指纹”。
2. if not (self.bits & (1 << self._hash(key, i)))按位与检查发现任一位为 0，就说明该 key 必然不在本层，直接跳过整个 SSTable 的磁盘读。
3. self.data = sorted(data.items())刷盘时把内存表按键排序，生成不可变的有序 SSTable，这是后续合并和二分查找的基础。
4. self.wal.append((key, value))先写 WAL 日志再写内存表，模拟“台账先行”的崩溃恢复机制。
5. if len(self.mem) >= self.mem_limitMemTable 达到阈值触发 flush，模拟“新书桌满了就上架”。
6. for k, v in t.data: merged[k] = v合并时用字典覆盖语义保留最新版本，后写入的值自然覆盖旧值，等价于 Compaction 清理重复 key。
7. for t in reversed(self.sstables)查询时从最新生成的 SSTable 倒序遍历，因为新版本总是排在后面。

常见误区

面试题