概要介绍LSM树

LSM(Log Structured Merged Tree)树一般用在写多读少的场景，比如日志类型的数据，是HBase、 Cassandra、 LevelDB、 RocksDB 以及 ClickHouse MergeTree 等流行的 NoSQL 数据库的底层数据结构

核心思想

• WAL保证数据持久性
• 数据写入内存，达到阈值后再批量写入磁盘
• 数据的所有操作：增删改全部作为顺序写，追加写的方式，大大提升写入性能
• 顺序追加写会形成很多无用的数据，需要异步实现数据压缩和整理

核心原理

这张经典图片来自 Flink PMC 的 Stefan Richter 在Flink Forward 2018演讲的PPT

typical LSM backed system

SSTable (Sorted String Table)

LSM-Tree的优点和缺点

与B-tree系列数据结构相比，LSM的写性能提升10作用倍，读性能降低10倍左右（但是使用布隆过滤器Bloom Filter可以改进读性能，特别是针对不存在的key的读取性能的改进）

写入流程

• 写入WAL（Write Ahead Logging）保证数据持久性
• 写入Active MemTable
• 如果Active MemTable写满，则变成Immutable MemTable，再一步写入到磁盘中的SSTable，同时生成一个新的Active MemTable
• 更新索引
• 更新布隆过滤器

读取流程

• 读取MemTable，如果读取到则返回
• 读取布隆过滤器，如果没有，则返回
• 如果布隆过滤器存在，则使用索引定位SSTable
• 如果索引不存在，则返回空值
• 如果存在则加载索引值对应的SSTable，读取指定的值

数据合并流程

因为LSM都是追加写入SSTable，哪怕是删除操作都是追加一个标识，所以经过一段时间的操作后，就会存在很多重复的key以及被删除的key，所以还需要进行数据合并，减少资源占用以及提供查询性能

参考

• Log Structured Merge Trees
• Understanding LSM Trees: What Powers Write-Heavy Databases
• LSM 树详解
• 平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了
• 一文了解数据库索引：哈希、B-Tree 与 LSM
• 深入理解什么是LSM-Tree
• 日志结构的合并树 The Log-Structured Merge-Tree
• LSM-tree vs B-tree