每天学一个算法--LSM-Tree（Log-Structured Merge Tree）

教案 24LSM-TreeLog-Structured Merge Tree · 工程级一、问题模型为什么需要 LSM-Tree设有一个存储系统需要支持高吞吐写入write-heavy大规模数据磁盘存储可接受的读取性能传统结构B-Tree的核心问题写入会导致随机 I/O频繁磁盘修改核心矛盾写入希望顺序写快 读取希望随机查快 LSM-Tree 的目标用“顺序写 延迟整理”来优化写性能二、核心思想必须精确理解所有写入先进入内存再批量写入磁盘磁盘数据通过“分层 合并”逐步整理。结构组成1️⃣ 内存层MemTable有序结构通常跳表 / 红黑树所有写入先进入这里2️⃣ 磁盘层SSTable不可修改immutable按 key 排序一旦写入不再更新三、写入流程精确步骤Step 1写入 MemTableput(key, value) → 插入内存结构Step 2MemTable 满flush → 写入磁盘生成一个SSTable有序文件Step 3多层结构形成Level 0 Level 1 Level 2 ...四、读取流程关键查找顺序1. MemTable 2. Level 0多个文件 3. Level 1 4. Level 2 ... 每一层都需要查五、问题读会变慢因为数据分散在多个文件中六、解决方案1Bloom Filter你刚学过的每个 SSTable 配一个 Bloom Filter判断key 是否可能存在 大幅减少磁盘查找次数七、核心机制Compaction合并为什么需要合并否则SSTable 越来越多 → 查询变慢Compaction 做什么多个有序文件 → 合并 → 新文件 本质就是外部排序 多路归并你刚学的八、两种 Compaction 策略重点1️⃣ Leveling分层式特点每层数据量指数增长每层 key 范围不重叠优点查询快缺点写放大高频繁重写数据2️⃣ Tiering分组式特点每层允许多个重叠文件到一定数量再合并优点写入更快缺点查询慢九、核心指标必须掌握1️⃣ 写放大Write Amplification一个数据被写多少次Leveling高Tiering低2️⃣ 读放大Read Amplification查询需要读多少文件Leveling低Tiering高3️⃣ 空间放大Space Amplification重复数据占用空间十、删除操作重要LSM-Tree 不直接删除写入一个“删除标记”Tombstone在 Compaction 时 真正删除十一、整体结构示意MemTable ↓ flush Level 0多个文件 ↓ compaction Level 1更大 ↓ Level 2 ...十二、与前面算法的关系体系串联组件来源算法SSTable排序Compaction外部排序Bloom Filter概率结构查询二分查找 你之前学的东西全用上了十三、真实系统应用1️⃣ LevelDBGoogle2️⃣ RocksDBFacebook3️⃣ Cassandra分布式数据库4️⃣ HBase大数据十四、本质总结严肃表达LSM-Tree 通过将写操作缓存在内存中并顺序写入磁盘同时利用多层有序文件与归并机制将随机写转化为顺序写从而在大规模数据场景下显著提升写入性能其代价是通过增加读放大与写放大在查询与维护成本之间进行权衡。 这一节的真正意义你现在已经不只是“学算法”而是在理解算法 → 数据结构 → 系统设计