1.3.2 写多读少：基于LSM派系的存储引擎

大部分读者或多或少都会听过LevelDB或者RocksDB这两个非常著名的项目，这两个项目就是基于LSM Tree存储引擎构建的。那为什么本小节的标题不是LSM Tree存储引擎而是LSM派系存储引擎呢？接下来为读者解答这个问题。

其实LSM这类组件是为了解决互联网中大量的写场景而出现的，其中最著名的莫过于LSM树了。之所以说LSM是一类组件，主要原因是它的目标是提升大量写场景下的写性能。早期磁盘的随机读/写性能非常低，但是对于需要存储大量数据，并且对数据安全要求非常高的场景，又不得不选择HDD来存储数据，这就出现了难题。选择用磁盘存储就会面临性能问题，而不用磁盘存储又解决不了实际问题。在这样的背景下，人们最终还是选择了用磁盘存储数据。机械磁盘的随机读/写速度确实慢，这一点毋庸置疑，但顺序读/写的性能要远远好于随机读/写。于是人们开始朝着顺序读/写这个方向前进，最终一种新的技术方案就出现了，即LSM类存储引擎。LSM类存储引擎充分利用磁盘的顺序写来保证性能，既保持了持久性又提升了写性能。因此，笔者认为LSM其实是一种思想，它主要表达的是通过顺序写磁盘来解决大量写这类问题。这种思想不仅在数据库这个领域有很多应用，而且在大数据领域使用的消息队列中也有着广泛的应用。

从LSM在内存层中维护的数据是否实时落盘，LSM派系的存储引擎分为以下两类。

❑ 数据同步落盘类：原生满足数据持久性。

❑ 数据异步落盘类：数据持久性通过预写WAL日志来保证。

这两类各自有一些项目在使用。数据同步落盘类的LSM存储引擎以LSM Hash模型为主，这种模型的实现中以Bitcask最为出名。Bitcask是NoSQL数据库Riak内部的存储引擎。而数据异步落盘类组件最经典的是LSM Tree模型和LSM Array模型。LSM Tree的典型实现有Google研发的LevelDB，以及Facebook基于LevelDB改进的RocksDB，还有大数据领域的HBase、Cassandra、InfluxDB、ElasticSearch等知名项目。而LSM Array实现的组件有开源项目Moss等。LSM Tree和LSM Array的区别在于，它们在内存中存储数据的数据结构是树类（跳表、红黑树、B树等）结构还是数组结构。

和同步落盘相比较，异步落盘模型虽然复杂一些，但它能为系统提供更强大的功能。例如通过异步落盘可在内存中将数据排好序再落盘，这样原生的数据存储就是有序的，这在有序查询的场景下更为通用。而同步落盘则只能简单地追加写数据，数据的有序访问只能依靠它维护的索引来实现，灵活性相对低一些。

LSM派系的存储引擎的共同点都是充分利用顺序写磁盘进而处理大量写操作的场景，只是LSM Tree在业界用得最为广泛。下面以LSM Tree为例介绍它的基本原理。典型的LSM Tree架构如图1-7所示。

图1-7 LSM Tree架构

以经典的三层架构来介绍LSM Tree。

在内存层中，LSM Tree主要由MemTable和ImmuMemTable构成。二者的区别在于，当MemTable中数据写满（达到设定的最大阈值）后，它就会将当前的MemTable设置成只读，该MemTable就变成了ImmuMemTable。之后重新创建一个新的MemTable来继续处理新的写请求。MemTable是内存中实现的一个有序的数据结构，通常采用红黑树、B树、跳表等数据结构来实现。

磁盘层由多层SSTable（Sorted String Table）文件构成。这些SSTable文件有些是由内存中的ImmuMemTable定期落盘形成的，有些则是在后续过程中压缩数据后生成的。存储在磁盘上的SSTable会定期进行数据的合并，以减少SSTable的数目，提升空间利用率和读性能。有些系统把数据的合并称为数据压缩，本质上是通过合并相同k的数据以减少重复的数据条目。最主要的压缩策略有分层压缩和分级压缩。以分层压缩为例，层数越大，存储的数据越多，数据越旧，层数小的合并后的数据会迁移到下一层级。下面简单介绍一下LSM Tree存储引擎的读/写过程。

对于LSM Tree而言，它处理写操作的主要过程如下：当存储引擎接收到写请求时，首先会将数据记录一份到WAL日志文件中以保证数据的持久性，写完WAL日志后，紧接着它会将该条数据写入内存的MemTable模块中，当数据写入MemTable完成后这一次写操作就完成了，可以响应给客户端了。

对于读请求而言，LSM Tree在处理时的流程如下：在接收到一个读请求后，LSM Tree会首先从内存的MemTable中读取数据，如果没读到再从ImmuMemTable中读取数据，如果还没读取到则会从磁盘的SSTable文件中读取，依次从低层级向高层级读取。一旦读取到数据就停止读取过程，然后返回给客户端。从本质上来说，LSM Tree由于是追加写数据的，因此读取时只需要逆序读取最新的数据即可，也就是说，它的数据读取过程是一个倒序读取的逻辑。把握了这一点就比较好理解了。

此外，LSM Tree系统后台有专门的线程完成一些异步任务。例如，内存层只读的ImmuMemTable中维护的数据会定期被后台线程写入磁盘中形成SSTable文件，这个过程为Minor Compact。再比如，每一层的SSTable数目一般都是有限制的，当超过限制后异步线程会进行层与层之间的数据压缩，这个过程称为Major Compact。压缩是LSM Tree的重点内容，后面会有专门的章节进行详细介绍，此处不再赘述。

本节只是说明LSM Tree是什么以及做什么的，关于LSM Tree为什么由MemTable、ImmuMemTable、SSTable这几部分构成，为什么这样设计，以及压缩方式等核心内容，会在后面详细介绍。