LSM树原理探究

B+树随着mysql Innodb引擎的广泛推广越来越被大家所熟知，而前不久我在研究Raft算法时，偶然发现了一种和B+树类似的数据结构——LSM树（Log-Structured-Merge-Tree 日志结构合并树），它是Google发表的论文 Big Table 中提到的一种很有趣的文件组织数据结构， 现如今已经被运用在很多工业界的产品之中了：HBase、Cassandra、LevelDB、RocksDB等等。今天就来研究研究LSM树的原理。

LSM树定义

LSM树（Log-Structured-Merge-Tree）和B+树类似，它们被设计出来都是为了更好地将数据存储到大容量磁盘中。相对于B+树，LSM树拥有更好的随机写性能。在下面的一个ACM的报告中可以看到：

磁盘顺序写的性能有些颠覆我们的常识的，在上面的例子中，磁盘顺序写的吞吐量甚至能够超过内存随即写的吞吐量。而LSM树正是利用了这一点，它通过将磁盘随机写操作转化为顺序写操作，从而将随机写操作的吞吐量提高了好几个数量级。那么它是如何转换的呢？下面我们先来看看它的基本思想。

LSM树的基本思想

LSM树会将所有的数据插入、修改、删除等操作保存在内存之中，当此类操作达到一定的数据量后，再批量地写入到磁盘当中。而在写入磁盘时，会和以前的数据做合并。在合并过程中，并不会像B+树一样，在原数据的位置上修改，而是直接插入新的数据，从而避免了随机写。

LSM树的结构

LSM树的结构是横跨内存和磁盘的，包含memtable、immutable memtable、SSTable等多个部分。

memtable

顾名思义，memtable是在内存中的数据结构，用以保存最近的一些更新操作，当写数据到memtable中时，会先通过WAL的方式备份到磁盘中，以防数据因为内存掉电而丢失。

预写式日志（Write-ahead logging，缩写 WAL）是关系数据库系统中用于提供原子性和持久性（ACID属性中的两个）的一系列技术。在使用WAL的系统中，所有的修改在提交之前都要先写入log文件中。

memtable可以使用跳跃表或者搜索树等数据结构来组织数据以保持数据的有序性。当memtable达到一定的数据量后，memtable会转化成为immutable memtable，同时会创建一个新的memtable来处理新的数据。

immutable memtable

顾名思义，immutable memtable在内存中是不可修改的数据结构，它是将memtable转变为SSTable的一种中间状态。目的是为了在转存过程中不阻塞写操作。写操作可以由新的memtable处理，而不用因为锁住memtable而等待。

SSTable

SSTable(Sorted String Table)即为有序键值对集合，是LSM树组在磁盘中的数据的结构。如果SSTable比较大的时候，还可以根据键的值建立一个索引来加速SSTable的查询。下图是一个简单的SSTable结构示意：

memtable中的数据最终都会被转化为SSTable并保存在磁盘中，后续还会有相应的SSTable日志合并操作，也是LSM树结构的重点。

最终LSM树的结构可以由下图简单表示：

LSM树的增删改查

上面介绍了LSM的基本思想和结构，下面来看看它们是怎么配合起来完成一个数据系统最常见的CRUD流程。

写入操作

写操作首先需要通过WAL将数据写入到磁盘Log中，防止数据丢失，然后数据会被写入到内存的memtable中，这样一次写操作即已经完成了，只需要1次磁盘IO，再加1次内存操作。相较于B+树的多次磁盘随机IO，大大提高了效率。随后这些在memtable中的数据会被批量的合并到磁盘中的SSTable当中，将随机写变为了顺序写。

删除操作

当有删除操作时，并不需要像B+树一样，在磁盘中的找到相应的数据后再删除，只需要在memtable中插入一条数据当作标志，如 delKey:1933 ，当读操作读到memtable中的这个标志时，就会知道这个key已被删除。随后在日志合并中，这条被删除的数据会在合并的过程中一起被删除。

更新操作

更新操作和000删除操作类似，都是只操作memtable，写入一个标志，随后真正的更新操作被延迟在合并时一并完成。

查询操作

查询操作相较于B+树就会很慢了，读操作需要依次读取memtable、immutable memtable、SSTable0、SSTable1......。需要反序地遍历所有的集合，又因为写入顺序和合并顺序的缘故，序号小的集合中的数据一定会比序号大的集合中的数据新。所以在这个反序遍历的过程中一旦匹配到了要读取的数据，那么一定是最新的数据，只要返回该数据即可。但是如果一个数据的确不在所有的数据集合中，则会白白得遍历一遍。

读操作看上去比较笨拙，所幸可以通过布隆过滤器来加速读操作。当布隆过滤器显示相应的SSTable中没有要读取的数据时，就跳过该SSTable。

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

还有上面提到的索引文件，也可以加速读操作。

合并操作

由前面的增删改查操作来看，合并操作是LSM树最重要的操作。

合并操作有两个主要的作用：

1. 合并内存中的数据到磁盘中。
2. 由于将内存数据合并到磁盘当中会产生大量的小的集合，并且更新和删除操作会产生大量的冗余数据，通过合并操作可以减少集合中的冗余数据并降低读操作时线性扫描的耗时。

目前广泛使用的有两种合并策略，size-tiered策略和leveled策略

size-tiered策略

size-tiered策略是HBase采用的合并策略，具体内容是当某个规模的集合达到一定的数量时，将这些集合合并为一个大的集合。比如有5个50个数据的集合，那么就将他们合并为一个250个数据的集合。这种策略有一个缺点是当集合达到一定的数据量后，合并操作会变得十分的耗时。

leveled策略

leveled策略是LevelDB和RocksDB采用的合并策略，size-tiered策略因为会产生大数据量的集合，所以会造成突发的IO和CPU资源的消耗，所以leveled策略使用了分层的数据结构来代替原来的大数据集合。

leveled策略将集合的大小限制在一个小的范围内如5MB，而且将集合划分为不同的层级。每一个层级的集合总大小是固定且递增的。如第一层为50MB，第二层为500MB...。当某一层的数据集合大小达到上限时，就会从这一层中选出一个文件和下一层合并，或者直接提升到下一层。如果在合并过程中发现了数据冲突，则丢弃下一层的数据，因为低层的数据总是更新的。

同时leveled策略会限制，除第一层外。其他的每一层的键值都不会重复。这是通过合并时剔除冗余数据实现的，以此来加速在同一层内数据的线性扫描速度。

RocksDB Compaction实例