**LSM Tree（Log-Structured Merge Tree）是一种对高并发写数据非常友好的键值存储模型，同时兼顾了查询效率。**LSMTree是我们下面将要介绍的NoSQL数据库所依赖的核心数据结构，例如BigTable.、HBase、 Cassandra、TiDB 等。

1.9.1 LSM Tree 的原理

LSM Tree的有效性基于一个结论：**磁盘或内存的顺序读/写数据性能远高于随机读/写数据性能。**这个结论不仅对传统的机械硬盘成立，对SSD硬盘同样成立。

顺序读/写和随机读/写的区别：

• 顺序读/写：按照文件中数据的顺序有序地进行读/写操作。例如，向某磁盘文件的尾部追加数据就是一种典型的顺序写操作。
• 随机读/写：它不遵循文件中数据的先后顺序进行数据的读取与写入。

**LSM Tree模型的思想就是在磁盘上用顺序读/写代替了随机读/写，充分发挥磁盘的读/写性能优势。**LSM Tree模型主要包括如下几个组成部分。

• MemTable
• Immutable MemTable
• SSTable

（1）MemTable

**MemTable是一种内存中的结构，用于保存SSTable最近更新的数据，并且按照数据Key的字典序将数据有序地组织起来。**LSM Tree模型并不限定MemTable的具体实现方式，只要保证数据有序、读/写效率高即可，红黑树、跳跃表等数据结构都是实现MemTable的适当选择。

LSM Tree模型接收到写数据请求后会直接在MemTable中处理，针对新增、修改、删除类型的写请求分别会执行不同的逻辑。

• 新增数据：直接将数据插入MemTable中。
• 修改数据：如果在MemTable中存在此数据Key，则直接修改；否则，将数据插入MemTable中。
• 删除数据：LSM Tree模型不删除数据，而是将数据状态标记为tombstone（墓碑），表示此数据已被删除。可见，删除数据的流程与修改数据的流程类似。如果在MemTable中存在此数据Key，则将数据状态修改为tombstone；否则，将携带tombstone状态的数据插入MemTable中。

由于最近更新的数据都被保存在内存中，而内存是易失性存储，所以通常使用预写日志（Write-Ahead Log，WAL）的方式保证数据的可靠性——在数据修改命令被提交到MemTable之前，先追加记录到磁盘上的WAL文件中。

（2）Immutable MemTable

当MemTable中存储的数据达到一定大小（默认为32MB）时，MemTable会变成只读的Immutable MemTable，后台线程将它持久化为基于磁盘的SSTable文件。为了不影响写数据请求的处理，LSM Tree会新建一个空白的MemTable接管工作。

（3）SSTable

LSM Tree将数据持久化到磁盘后的结构称为SSTable（Sorted String Table）。顾名思义，SSTable保存了基于数据Key按照字典序排序后的数据集合，它是一种持久化的、有序且不可变的键值对存储结构。数据Key、Value被连续地存储在SSTable文件中，同时在文件的尾部存储数据Key在文件中位置的偏移量并将其作为稀疏索引，用于提高在SSTable中查找某数据Key的速度。图1-40展示了 SSTable的结构。

当MemTable达到一定的大小后，它最终会被刷写到磁盘中变成SSTable文件，所以在不同的SSTable中可能存在相同的数据Key。**对于某个特定的数据，在最新的SSTable中存储的对应记录才是它的最新值，其他SSTable中的对应记录都是冗余数据。**这会浪费存储空间。所以，LSM Tree会周期性地对SSTable进行合并操作，通过将多个SSTable合并为更大的SSTable来清除冗余记录。

LSM Tree使用Level划分SSTable文件，Level N的SSTable文件会经过合并操作下沉到Level N+1, Immutable MemTable被持久化成的SSTable文件处于Level 0。合并操作的主要策略是 Leveled Compaction Strategy（LCS），此策略保证：

• 所有Level的SSTable文件大小均一致，默认为160MB；
• 每个Level会限制此层内所有SSTable文件的总大小，层级越高，限制的阈值越大，如Level 1的文件总大小为10GB，Level 2的文件总大小为100GB等；
• 不仅单个SSTable的内部数据有序,而且同一 Level内的SSTable之间也是有序的。

当Level N的文件总大小达到阈值时，会触发LCS的合并操作：在Level N中选择一个SSTable和Level N+1中与其数据Key有交集的SSTable进行合并，合并结果是生成若干新的SSTable，且它们各自的大小都不超过160MB，这些SSTable文件下沉到LevelN+1。如果Level N+1的文件总大小也达到阈值，则继续执行同样的合并操作，直到某一层的文件总大小在限制的阈值内，或者到达最后一层。

图1-41简单描述了合并操作过程。假设Level 1的SSTable文件总大小超过阈值，那么Level 1中的1个SSTable选择Level 2中与它有交集的2个SSTable进行合并，生成了 3个新的SSTable。

这3个SSTable被归入Level 2。我们发现Level 2的文件总大小也超过阈值，于是Level 2中的某个SSTable与Level 3中有交集的3个SSTable继续合并操作，生成一个新的SSTable被归入Level 3，如图1-42所示。

由于Level 0的SSTable文件来自Immutable MemTable，所以这些SSTable之间可能有数据Key重叠。但是经过合并操作，Level 1~N每一层的SSTable之间就不会有数据Key重叠了，一个数据Key在某一层至多存在一次。

我们可以轻易地发现，层级越低，数据越新。如果某数据存在于Level 1、Level 3、Level 5，那么Level 1对应的数据值是最新的。

1.9.2 读/写数据的流程

LSM Tree处理客户端的写数据请求的流程如下所述，如图1-43所示。

1. 将写数据信息记录到WAL文件中。
2. 在MemTable中写入数据，此时就可以将响应数据返回给客户端。
3. 当MemTable中存储的数据大小达到阈值时，将其变为Immutable MemTable，新的MemTable继续对外提供服务。
4. Immutable MemTable被持久化为SSTable文件，处于Level 0。
5. 如果Level 0的SSTable文件大小达到阈值，则执行合并操作，Level 0的SSTable文件逐渐下沉到Level 1。
6. 以此类推，如果Levels的SSTable文件大小达到阈值，则继续通过合并操作将SSTable文件下沉到Level N+1。

在LSM Tree中查找数据时，按照数据值的新旧程度，查找顺序为MemTable、Immutable MemTable、Level 0 SSTable、Level 1 SSTable，直到Level N SSTable。LSM Tree处理客户端的读数据请求，当然也要保证读取到数据最新值，其流程如下。

1. 在MemTable中查找数据。
2. 如果未找到数据，则在Immutable MemTable中继续查找。
3. 如果未找到数据，则在Level 0最新的SSTable文件中查找。
4. 如果在Level 0的所有SSTable文件中都找不到数据，则继续在Level 1查找。
5. 以此类推，直到在某一层找到数据，或者在最后一层也未找到数据。

总结

什么是LSM Tree呢？

• LSM Tree（Log-Structured Merge Tree）是一种对高并发写数据非常友好的键值存储模型，同时兼顾了查询效率。

LSM Tree有效性是基于什么得到的？

• 磁盘或内存的顺序读/写数据性能远高于随机读/写数据性能。

顺序读/写和随机读/写的区别：

• 顺序读/写：按照文件中数据的顺序有序地进行读/写操作。例如，向某磁盘文件的尾部追加数据就是一种典型的顺序写操作。
• 随机读/写：它不遵循文件中数据的先后顺序进行数据的读取与写入。

LSM Tree模型的核心思想？

• 在磁盘上用顺序读/写代替了随机读/写，充分发挥磁盘的读/写性能优势。

什么是MemTable呢？

• MemTable是一种内存中的结构，用于保存SSTable最近更新的数据，并且按照数据Key的字典序将数据有序地组织起来。

MemTable针对新增、修改、删除类型的写请求分别会执行不同的逻辑？

• 新增数据：直接将数据插入MemTable中。
• 修改数据：如果在MemTable中存在此数据Key，则直接修改；否则，将数据插入MemTable中。
• 删除数据：LSM Tree模型不删除数据，而是将数据状态标记为tombstone（墓碑），表示此数据已被删除。可见，删除数据的流程与修改数据的流程类似。如果在MemTable中存在此数据Key，则将数据状态修改为tombstone；否则，将携带tombstone状态的数据插入MemTable中。

什么是SSTable呢？

• LSM Tree将数据持久化到磁盘后的结构称为SSTable（Sorted String Table）。
• SSTable保存了基于数据Key按照字典序排序后的数据集合，它是一种持久化的、有序且不可变的键值对存储结构。
• 数据Key、Value被连续地存储在SSTable文件中，同时在文件的尾部存储数据Key在文件中位置的偏移量并将其作为稀疏索引，用于提高在SSTable中查找某数据Key的速度。

LSM Tree处理客户端的写数据请求的流程？

1. 将写数据信息记录到WAL文件中。
2. 在MemTable中写入数据，此时就可以将响应数据返回给客户端。
3. 当MemTable中存储的数据大小达到阈值时，将其变为Immutable MemTable，新的MemTable继续对外提供服务。
4. Immutable MemTable被持久化为SSTable文件，处于Level 0。
5. 如果Level 0的SSTable文件大小达到阈值，则执行合并操作，Level 0的SSTable文件逐渐下沉到Level 1。
6. 以此类推，如果Levels的SSTable文件大小达到阈值，则继续通过合并操作将SSTable文件下沉到Level N+1。

LSM Tree处理客户端的读数据请求的流程？

1. 在MemTable中查找数据。
2. 如果未找到数据，则在Immutable MemTable中继续查找。
3. 如果未找到数据，则在Level 0最新的SSTable文件中查找。
4. 如果在Level 0的所有SSTable文件中都找不到数据，则继续在Level 1查找。
5. 以此类推，直到在某一层找到数据，或者在最后一层也未找到数据。