简介

Log Structured Merge Tree，下面简称 LSM。

2006年，Google 发表了 BigTable 的论文。这篇论文提到 BigTable 单机上所使用的数据结构就是 LSM。

目前，LSM 被很多存储产品作为存储结构，比如 Apache HBase, Apache Cassandra, MongoDB 的 Wired Tiger 存储引擎, LevelDB 存储引擎, RocksDB 存储引擎等。

简单地说，LSM 的设计目标是提供比传统的 B+ 树更好的写性能。LSM 通过将磁盘的随机写转化为顺序写来提高写性能 ，而付出的代价就是牺牲部分读性能、写放大（B+树同样有写放大的问题）。

LSM 相比 B+ 树能提高写性能的本质原因是：外存——无论磁盘还是 SSD，其随机读写都要慢于顺序读写。

优化写性能

如果我们对写性能特别敏感，我们最好怎么做？—— Append Only：所有写操作都是将数据添加到文件末尾。这样做的写性能是最好的，大约等于磁盘的理论速度（200 ~ 300 MB/s）。但是 Append Only 的方式带来的问题是：

• 读操作不方便。
• 很难支持范围操作。
• 需要垃圾回收（合并过期数据）。

所以，纯粹的 Append Only 方式只能适用于一些简单的场景：

• 数据库的 WAL。
• 能知道明确的 offset，比如 Bitcask。

优化读性能

如果我们对读性能特别敏感，一般我们有两种方式：

• 有序存储，比如 B+ 树，SkipList 等。
• Hash 存储 —— 不支持范围操作，适用范围有限。

读写性能的权衡

如何获得（接近） Append Only 的写性能，而又能拥有不错的读性能呢？

以 LevelDB 为代表的 LSM 存储引擎给出了一个参考答案。注意，LevelDB 实现的是优化后的 LSM，原始的 LSM 可以参考论文。下面的讨论主要以 LevelDB 为例子。

LevelDB 的写操作主要由两步组成：

1. 写日志并持久化（Append Only）。
2. Apply 到内存中的 memtable（SkipList）。

所以，LevelDB 的写速度非常快。

memtable 写“满”后，会转换为 immutable memtable，然后被后台线程 compaction 成按 Key 有序存储的 sst 文件（顺序写）。由于 sst 文件会有多个，所以 LevelDB 的读操作可能会有多次磁盘 IO（LevelDB 通过 table cache、block cache 和 bloom filter 等优化措施来减少读操作的磁盘 IO 次数）。

总结

基于 LSM 数据结构的 LevelDB 的适用场景：

• 写请求多。
• 写性能（吞吐+延迟）要求高。

参考文档

• SSTable and Log Structured Storage: LevelDB
• Log Structured Merge Trees