LSM-Tree存储引擎设计：从RocksDB到TiDB的实战原理

为什么写多读少场景都用LSM-Tree

B+树是关系型数据库的经典索引结构，但在写入密集型场景中面临严重的写放大(CoW B+树可能达到100x)。2006年Google发表的Bigtable论文公开了LSM-Tree（Log-Structured Merge Tree）在云规模数据库中的应用，此后LevelDB、RocksDB、HBase、Cassandra、TiKV等系统纷纷采用。LSM-Tree以顺序写+延迟合并的方式，将随机写转换为顺序写，写放大可控制在10x以内。

一、LSM-Tree核心架构

LSM-Tree是多层的顺序写结构，核心思想是：将随机写转化为顺序写，将合并操作推迟并合并批处理。

• MemTable：内存中的写缓冲区，使用SkipList或B+树实现有序KV。默认64MB，写满后转为Immutable MemTable
• Immutable MemTable：只读内存表，将被flush到磁盘成为SSTable
• WAL (Write-Ahead Log)：预写日志，防止MemTable数据丢失
• SSTable：Sorted String Table，磁盘上有序KV文件，不可变(Immutability)
• Level分层：Level 0 → Level 1 → Level 2 ... 逐层合并，每层容量成倍增长

二、读写路径详解

写入路径:

1. 写入WAL (顺序追加ms级)
2. 写入SkipList MemTable (内存操作ns级)
3. MemTable满 → 转为Immutable → 异步flush为L0 SSTable
4. 后台Compaction: L0→L1→L2 逐层合并归并排序

读取路径:

1. MemTable查找 (最新数据)
2. Immutable MemTable查找
3. Level 0 SST (可能有重叠，全部查找)
4. Level 1+ SST (无重叠，每层一个)
5. Bloom Filter 过滤不存在的SST，加速判断

读路径的多级查找是LSM-Tree的读写trade-off本质：牺牲一定的读性能换取极高的写吞吐。

三、Compaction策略对比

Compaction是LSM-Tree的后台核心操作，合并SST文件并清理过期数据。不同数据库选择了不同的策略：

四、RocksDB：工业级LSM-Tune可调参数

RocksDB是Facebook维护的嵌入式KV存储引擎，是LSM-Tree最工程化的实现。关键可调参数：

• Target File Size：Level 1 SST文件默认64MB，Level N文件默认64MB * 10^(N-1)
• Level Compaction Dynamic Level Bytes：自动计算层级容量比例（推荐开启）
• Subcompactions：将Compaction拆分为多个子任务并行执行
• Blob (Titan)：大value分离存储，显著降低写放大

性能调优典型方向：

• 写密集 → 增大Level 0 file数限制，使用Tiering/Blob
• 读密集 → 增大Block Cache，启用Bloom Filter
• 混合负载 → Level Compaction Dynamic Level Bytes，自动适应

五、TiKV：分布式LSM-Tree的分层架构

TiDB的存储层TiKV采用RocksDB作为底层引擎，在分布式层面做了大量优化：

• Region分片：数据按Key Range切分为~100MB的Region
• Raft Replication：每个Region有3-5个副本，强一致
• Coprocessor：下推到存储节点执行过滤/聚合
• Titan引擎：TiKV内嵌的Titan存储引擎，大value分离降低写放大

典型配置：16核CPU、64GB内存、NVMe SSD存储集群可支撑百万QPS级别的TPCC读写。

六、理论前沿: Key-Value分离与分布式LSM

SILK (SIGMOD 2021) 提出将Key和Value分离存储：在Compaction阶段只移动和排序Key（小的metadata），Value存在单独的vLog中。这能将Leveled Compaction的写放大从30x降低到5x，代价是Value查询会因为LSM层数增多而变慢。

WiscKey (FAST 2017) 是更早的KV分离方案，证明了KV分离在写密集场景的巨大收益。Titan引擎就是WiscKey思想在RocksDB生态的工业实现。

七、总结

LSM-Tree是现代分布式存储系统的基石数据结构——从嵌入式LevelDB到云原生HBase/TiKV，从单机KV到分布式NewSQL。理解LSM-Tree的读/写路径、Compaction策略和写放大权衡，是深入理解数据库内核的第一步。

写入优化的顺序更新、不可变SSTable、分层合并——这些设计思想也逐渐影响到了数据湖(Iceberg/Hudi)、日志系统(Kafka/LinkedIn Brooklin)等非KV存储系统。LSM-Tree已经超越了数据结构本身，成为一种通用的"无缝写入+后台整理"设计模式。

参考资料

• O'Neil et al. (1996) - The Log-Structured Merge-Tree (LSM-Tree)
• Facebook RocksDB Wiki - github.com/facebook/rocksdb
• Dong et al. (2017) - Optimizing Space Amplification in RocksDB (SILK)
• Lu et al. (2017) - WiscKey: Separating Keys from Values
• TiDB Blog - TiKV Architecture and Titan Engine