LSM-Tree 存储模型常常被应用于 KV 存储引擎，通过将大量的随机写转化为顺序写，从而达到提升数据写入的性能，与此同时也带来了读取数据性能低下的问题，更加适用于写远大于读的应用场景，RocksDB 采用 LSM Tree 数据结构，在保证写入数据的性能同时兼顾数据查询性能。

LSM Tree 数据结构

LSM-Tree 全称是 Log Structured Merge Tree，是一种分层、有序、面向磁盘的数据结构，其核心思想是充分了利用磁盘批量的顺序写要远比随机写性能高出很多的特性。对数据的操作均采用追加方式，不进行删除和更新，有舍才有得，该结构的设计大大提升了写性能，同时降低了读取的性能，因而适用于写多读少的场景。

我们以向 LSM-Tree 插入一条数据为例，了解数据是如何被写入的。假设我们实现：PUT foo bar，将 Key 为 foo，Value 设置为 bar。该操作首先被写入磁盘的 WAL(Write Ahead Log，预写 Log)日志中，该操作用于故障恢复，如果出现系统宕机，可以将内存中来不及写入磁盘的数据进行恢复，这一步确保了数据写入的可靠性。

然后，将这个数据直接写入到内存中的 MemTable（并不去判断该 Key 是否存在），之后便可以回复用户写入成功。很显然，内存是有限的，不可能无限制地写入数据。MemTable 有一个固定的大小，一般是 32M，当 MemTable 写满之后，被转换为 Immutable MemTable(只读的 MemTable)，之后创建一个空的 MemTable 继续写入数据。使用 Immutable Memtable，避免了将 MemTable 中的内容序列化到磁盘阻塞写操作。

此时，有一个后台线程会不停地将 Immutable MemTable 复制到磁盘中并释放内存，每个 Immutable MemTable 对应于磁盘中的 SSTable。这些 SSTable 文件，虽然每个文件中的 Key 是有序的，但是文件之间是完全无序的，还是没法查找。SSTable 巧妙地采用了 分层合并机制 来解决乱序的问题：

SSTable 被分为很多层，越往上层，文件越少，越往底层，文件越多。每一层的容量都有一个固定的上限，一般来说，下一层的容量是上一层的 10 倍。当某一层写满了，就会触发后台线程往下一层合并，数据合并到下一层之后，本层的 SSTable 文件就可以删除掉了。合并的过程也是排序的过程，除了 Level 0 以外，每一层内的文件都是有序的，文件内的 KV 也是有序的，便于查找了。

合并步骤也就是 Major Compaction，这个阶段会真正的清除掉被标记删除掉的数据以及多版本数据的合并，避免浪费空间，由于 SSTable 都是有序的，我们可以直接采用 Merge Sort 进行高效合并。

可见，该存储实现利用 WAL 确保数据写入的可靠性，只进行数据的追加不更新数据的特性，只要数据写入 WAL 和 MemTable 便认为数据写入成功，充分利用顺序写入提升写入的性能，同时利用分层合并机制来提升数据查询的性能。

了解到这里，也许我们会有疑问，只进行数据追加，那么对于用户删除数据和更新数据的操作，该怎么处理，接下来，我们了解一下，常见的数据操作是如何实现的。

常见数据操作

以常见数据的更删改查为例，展示 LSM Tree 对数据操作的过程，加深对底层数据操作的理解。

写入数据

写入操作相当快速的，只需要在 WAL 文件中顺序写入当次操作的内容，成功之后将该数据写入 MemTable 中即可认为写入成功。

读取数据

同样地，采用分层查找的方式。首先到内存的 MemTable 和 Immutable MemTable 查找，之后到磁盘的 SSTable 的每层进行查找，只要找到了便可以直接返回。因为数据是按照这个路径进行追加的，因此可以认为按照这个路径查找到的最新的数据就是我们想要的结果。

这样的查找方式有可能由于需要多次进行内存和文件的查找才可以找到符合条件的 Key，但是这个分层结构形成了一个天然的优势：越是被经常读写的热数据，就越靠上，对这样的 Key 查找就越快。

读取优化

在实际的项目中，通常可以对读取操作进行进一步的优化：

• 在内存中缓存 SSTable 文件的 Key，采用布隆滤波器来避免一些无谓的查找，来加速查找。

• 例如 LevelDB 中的 Mainfest 文件，它记录了 SSTable 文件的一些关键信息，例如 Level 层数，文件名，最小 key 值，最大 key 值等，这个文件通常不会太大，可以放入内存中，可以帮助快速定位到要查询的 SSTable 文件，避免频繁读取。

更新数据

实际上并不存在更新数据的操作，更新数据和写入数据一样，也是向其中插入数据。很显然，在整个 LSM Tree 中可能会同时存在多个 key 值相同的数据，只有合并 SSTable 文件的时候，才会将旧的值删除。而在数据读取时，总是从 Level 0 层的 SSTable 开始查找，而低层的 SSTable 比高层的 SSTable 新，因而用户总是可以读取到最新的数据。

删除数据

删除数据也不是立即将数据从文件中删除，而是记录下对这个 key 的删除操作标记，只有当合并 SSTable 文件时才会真正的删除。

实际应用

LevelDB，HBase，Google BigTable，Cassandra，InfluxDB 都是采用 LSM Tree 存储模型，Flink 的 State 就是采用的是 RocksDB KV 的存储，还有包括 MongoDB、Cassandra 等等也都在开发基于 RocksDB 的存储引擎。

参考资料

1. RocksDB：不丢数据的高性能 KV 存储
   

2. LSM Tree 学习笔记——MemTable通常用 SkipList 来实现
   

3. 深入理解什么是LSM-Tree