悠悠楠杉
网站页面
什么是LSM树？LSM树的层次结构，lsm树原理
08/24
从磁盘随机写入的瓶颈说起
2006年谷歌发布BigTable论文时，传统B+树结构面临着一个致命瓶颈：当数据量超过内存容量时，频繁的磁盘随机写入会导致性能断崖式下跌。正是这个背景下，Patrick O'Neil等人提出的LSM树结构，犹如一把精巧的手术刀，精准切中了现代存储系统的痛点。
LSM树的三层核心结构
1. MemTable（内存缓冲区）
所有写操作首先进入这个完全驻留内存的跳表结构，其写入速度可达每秒百万级操作。就像写字时先用的草稿纸，MemTable允许系统在内存中快速完成数据变更，著名的LevelDB在此环节采用跳表（SkipList）实现，平均时间复杂度控制在O(log n)。
2. Immutable MemTable（不可变内存表）
当MemTable达到阈值（通常5-10MB），会原地冻结为只读状态，同时创建新的MemTable接管写入。这个设计巧妙地分离了读写路径，避免了锁竞争。如同餐厅备餐时的双砧板机制，一块处理新食材时，另一块正在进行装盘。
3. SSTable（磁盘存储层）
冻结的MemTable通过后台线程刷盘生成Sorted String Table（SSTable），这些文件具有两个关键特性：
- 按键有序排列（类似B+树的叶子节点）
- 不可修改的特性（只支持追加写入）
层次化存储的精妙设计
成熟的LSM实现（如RocksDB）通常采用多层SSTable结构：
- Level 0：直接由Immutable MemTable转化而来，允许键范围重叠
- Level 1~N：每层容量呈指数增长（通常10倍关系），通过compaction过程实现数据归并
这种设计像极了图书馆的藏书系统：新书先放在入口展台（L0），定期整理到分类书架（L1），最终归档到密集书库（L2+）。其中关键的compaction过程，本质上是一种多路归并排序的磁盘实现。
Compaction的平衡艺术
LSM树最精妙的部分莫过于其compaction策略：
- 大小分级策略（Size-Tiered）：Cassandra采用的方案，当小文件达到一定数量时合并为大文件
- 分层策略（Leveled）：LevelDB/RocksDB的方案，保证除L0外每层数据无重叠
- 混合策略：现代系统常根据数据冷热采用不同策略
这种设计带来了显著的写入放大效应（通常5-10倍），但通过顺序IO的高吞吐弥补了这一缺陷。就像快递公司的分拣中心，虽然需要多次搬运包裹，但流水线作业的整体效率远高于单独派送。
现实世界的优化实践
工业级实现中常见的增强手段包括：
1. 布隆过滤器：加速SSTable的键存在性判断
2. 前缀压缩：减少磁盘存储空间
3. 并行Compaction：RocksDB的多线程处理
4. 延迟Compaction：TiDB的写间歇期优化
这些优化使得LSM树在SSD时代依然保持着强大生命力，从MongoDB的WiredTiger引擎到InfluxDB的TSM结构，都能看到其思想变种。
