1. LSM Tree介绍

1.1 概念

​B+树读效率高而写效率差；log型文件操作写效率高而读效率差；因此要在排序和log型文件操作之间做个折中，于是就引入了log-structed merge tree模型，通过名称可以看出LSM既有日志型的文件操作，提升写效率，又在每个sstable中排序，保证了查询效率

主要发展阶段如下：

• LSM-tree起源于 1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》，后续发展如下：
• FAST’16 的《WiscKey: Separating Keys from Values in SSD-conscious Storage》
• PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees（SOSP 2017）

LSM-tree 是专门为 key-value 存储系统设计的，key-value 类型的存储系统最主要的就两个核心功能，put（k，v）：写入一个（k，v），get（k）：给定一个 k 查找 v。

LSM-tree 最大的特点就是写入速度快，主要利用了磁盘的顺序写，pk掉了需要随机写入的 B-tree

下图是 LSM-tree 的组成部分，是一个多层结构，就更一个树一样，上小下大。

首先是内存的 C0 层，保存了所有最近写入的 （k，v），这个内存结构是有序的，并且可以随时原地更新，同时支持随时查询。剩下的 C1 到 Ck 层都在磁盘上，每一层都是一个在 key 上有序的结构。

写入流程：追加到写前日志（Write Ahead Log，也就是真正写入之前记录的日志）中，接下来在内存中构建一颗有序的小树，随着小树的逐渐增大，达到一定阈值时会flush到磁盘上，多次flush之后会形成多个数据存储文件，后台线程会按照配置自动将多个文件合并成一个（compact)，此时多颗小树就会被合并成一棵大树。

查询流程：在写入流程中可以看到，最新的数据在 C0 层，最老的数据在 Ck 层，所以查询也是先查 C0 层，如果没有要查的 k，再查 C1，逐层查

LSM树本质是在读写之间取得平衡，LSM树不像B+树一样是一棵完整的大树，一棵LSM树就是一个个B+树合起来。
​​​

1.2 LSM Tree优化方式

1. Bloom filter: 经过布隆过滤器，能以少许的空间代价，换来在读取数据时快速地肯定是否存在某条数据，效率进一步提高，如HBase每一个HFile中的HFile中的Bloom index block
2. compact: compact的作用是:
   • 合并文件
   • 清除过期，多余版本的数据
   • 提高读数据的效率
     这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了

2 LSM Tree的应用

LSM Tree在NoSQL、NewSQL及存储引擎中普遍应用，见下图：

2.1 HBase

HBase存储应用LSM主要设计思想如下：
数据写入流程：

• 因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLog
• MemStore上的树达到一定大小之后，需要flush到HRegion磁盘中（一般是Hadoop DataNode），这样MemStore就变成了DataNode上的磁盘文件StoreFile
• HRegionServer定期对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树，来增强读性能。

数据读取流程：
首先搜索BlockCache,再搜索MemStore,如果不在MemStore中，则到storefile中寻找。

数据删除流程：
不会去删除磁盘上的数据，而是为数据添加一个删除标记。在随后的major compaction中，被删除的数据和删除标记才会真的被删除。

2.2 RocksDB

LSM Tree 被分成三种文件，第一种是内存中的两个 memtable，一个是正常的接收写入请求的 memtable，一个是不可修改的immutable memtable，另外一部分是磁盘上的 SStable （Sorted String Table），有序字符串表，这个有序的字符串就是数据的 key。

SStable 一共有七层（L0 到 L6）。下一层的总大小限制是上一层的 10 倍

读写流程如下图：
​​

2.3 Mongo

Mongo 从3.0开始，包含了支持B+和LSM的 Wired Tiger引擎