LSM Tree 101

前言

在现代互联网系统中，海量数据的高效写入和查询是数据库系统设计的核心目标之一。特别是写多读少或写入密集型的场景中，传统B-Tree类结构难以胜任。**LSM Tree（Log-Structured Merge Tree）**作为一种写入友好型数据结构，已经广泛应用于数据库、键值存储和时间序列系统中。

定义

Wiki 定义如下：

A Log-Structured Merge-tree (LSM tree) is a data structure that is designed to provide high performance for write-intensive applications by converting random writes into sequential ones using a multi-tiered structure of components.

简单来说：LSM Tree 是一种将写操作转化为顺序写入的树形数据结构，通过分层合并提升写入性能。

工作原理

一句话：将写入数据先缓存在内存中，定期顺序写入磁盘并分层合并，提升写入效率。

基本流程如下：

写入首先进入内存表（如 MemTable）；
内存表写满后持久化为磁盘 SSTable（Sorted String Table）；
多个 SSTable 定期进行合并（Compaction）；
查询操作先查内存表，再查 Bloom Filter、SSTable；
删除操作使用“标记删除”，在合并过程中真正清除。

属性与指标

LSM Tree 的核心关注指标：

写放大（Write Amplification） 多层合并操作可能导致同一条数据写多次。
读放大（Read Amplification） 查询需要遍历多层SSTable，依赖 Bloom Filter 缓解。
空间放大（Space Amplification） 多版本数据和未清除的删除标记带来额外存储开销。
压缩策略（Compaction Policy） 包括 Size-Tiered、Levelled、Hybrid 多种策略。
延迟稳定性（Write/Read Latency） 压缩过程可能阻塞写入或造成读延迟抖动。
吞吐性能（Throughput） 顺序写和批量合并大幅提升系统吞吐。
适应性 可根据应用调整层级、压缩频率、内存比例等参数。

类型

压缩策略（Compaction Strategies）

Size-Tiered Compaction（STCS） 多个同层段文件积累到阈值后批量合并。写效率高，但读放大严重。
Levelled Compaction（LCS） 每层容量递增，每次只合并相邻层，读性能更优但写放大较高。
Hybrid Compaction 结合 STCS 和 LCS，适用于特殊负载特征。

存储组件

MemTable（内存表） 接受所有写入请求，通常是跳表、红黑树等结构。
Immutable MemTable MemTable 写满后冻结，等待 flush 到磁盘。
SSTable（Sorted String Table） 持久化的只读文件，按键排序，包含数据块与索引块。
WAL（Write-Ahead Log） 所有写入先记录日志，崩溃后恢复使用。
Bloom Filter 每个 SSTable 携带，快速判断 key 是否可能存在，避免不必要读取。
Compaction 后台进程合并、排序和清理过期数据。

应用场景

LSM Tree 在以下场景中表现优异：

写密集型数据库 如 OLTP 系统、高并发写入日志系统。
键值存储引擎 RocksDB、LevelDB、WiredTiger 等。
时序数据库 如 InfluxDB、TimescaleDB、VictoriaMetrics 等。
分布式数据库与大数据平台 如 Apache HBase、Apache Cassandra、TiKV 等。
搜索引擎与消息系统 如 Elasticsearch（Lucene）、Apache Pulsar（BookKeeper WAL）。

常用产品实现

采用 LSM Tree 结构的代表产品：

RocksDB Facebook 推出的高性能嵌入式数据库，支持多种压缩策略。
LevelDB Google 开源，RocksDB 前身，轻量、嵌入式存储。
Apache Cassandra 分布式 NoSQL，底层存储采用 LSM Tree。
Apache HBase Hadoop 生态的列式存储系统，基于 HFile（SSTable）+ MemStore。
WiredTiger MongoDB 默认存储引擎，自 MongoDB 3.2 起采用 LSM。
TiKV 分布式事务型 KV 数据库，采用 RocksDB 作为底层引擎。
InfluxDB 时序数据库，采用自定义的 TSM（Time-Structured Merge Tree）。

LSM tree 101

文章目录