LSM树探秘：原生分布式数据库的存储引擎

LSM树探秘：原生分布式数据库的存储引擎

LSM树，即Log-Structured-Merge-Tree（日志合并树），是一种分层、有序、面向内存+磁盘的数据结构，其核心思想是磁盘批量的顺序写速度要远比随机写性能高出很多。这一特性使得LSM树在原生分布式数据库的存储引擎中得到了广泛应用。

一、出现背景

传统集中式数据库使用的数据结构主要是B+树。每次写操作不仅要执行写请求写入的记录，还要对B+树执行必要的元数据更新，这涉及到B+树中节点的移动、拆分或合并。每次写入B+树结构时，都是磁盘的随机IO写操作。因此，在面对海量数据读写的场景下，随机写的性能瓶颈愈发明显。此外，不建议对表创建较多的索引，因为每个索引都是一棵B+树，每次写入都需要维护所有的B+树。

LSM树的概念则来源于谷歌的“BigTable”论文。在大数据领域，谷歌发布的大名鼎鼎的“三驾马车”论文（GFS、MapReduce、BigTable）给大数据领域带来了无数的灵感，LSM树就是其中之一。

二、LSM树的特性

LSM树将数据存储限制为只能进行追加操作，而数据存储只是一个包含完全有序的键值对的“日志”，排序顺序由键决定。LSM树首先将大量写入缓存在内存，当积攒到一定程度后，将它们批量写入文件中，一次I/O可以进行多条数据的写入，充分利用每一次I/O。

LSM树整体上不是一个单一的数据结构，而是结合了多个数据结构，利用了存储层次结构中不同存储设备的响应时间。由于只进行追加，它在提供高写入率的同时，还能通过在内存中维护的索引提供低成本读。与执行in-place更新的基于B+树的存储引擎相比，LSM树有助于避免随机I/O。

三、行业应用

1. 分布式数据库：如Hbase、Apache Cassandra、LevelDB、RocksDB、ClickHouse MergeTree等NoSQL数据库都使用LSM树来处理大规模的分布式数据存储和查询，以提供高吞吐量和低延迟的数据访问。国内知名的分布式数据库Oceanbase、Tidb（基于RocksDB）也是使用LSM树。

2. 日志存储：由于LSM树对写入操作具有高效的支持，它在日志存储场景中表现出色。例如，用于处理日志数据的系统，如ELK（Elasticsearch, Logstash, Kibana）使用LSM树来快速地写入和检索大量的日志事件。

3. 分布式文件系统：一些分布式文件系统，如Hadoop的HDFS和Google的GFS，使用LSM-Tree来管理文件系统的元数据，例如文件和目录信息。这样可以提供高效的元数据访问和更新操作。

4. 时间序列数据：由于LSM树对写入操作的高效支持和时间序列数据的特性相符，它在时间序列数据存储和分析中被广泛使用。这包括物联网（IoT）应用、日志分析、金融数据等领域。

四、LSM树的组成部分

现代LSM树包含了三个部分：MemTable、Immutable MemTable、SSTable。前两个位于内存，最后一个位于磁盘中。

1. MemTable：是LSM树在内存中的数据结构，只用于保存最新的数据，按照Key有序地组织这些数据。存在内存中的数据会因为断电而丢失，这一点和传统集中式数据库是一样的。WAL（Write Ahead Log）即事务的所有修改在提交之前要先写入log文件中，当有新数据写入时，首先将数据记录在WAL Log中，用作故障恢复，然后将数据写入内存的MemTable中。

2. Immutable MemTable：当MemTable达到一定大小后，会转化为Immutable MemTable。Immutable MemTable是将MemTable转为磁盘上的SSTable的一种中间状态。在转化过程中，写操作由新的MemTable处理，过程中不阻塞数据更新操作。

3. SSTable：是LSM树在磁盘中持久化存储的数据结构，它是一个有序的键值对文件。后台线程会将Immutable MemTable写入到磁盘中形成一个新的SSTable文件，并随后销毁Immutable MemTable。LSM树不会修改已存在的SSTable，LSM在修改数据时会直接在MemTable中写入新版本的数据，并等待MemTable落盘形成新的SSTable。

五、LSM树的增删改查

我们以RocksDB为例来介绍LSM树的增删改查操作。

1. 写操作（增删改）：LSM树的数据更新是日志式的，修改数据时直接追加一条新记录（为被修改数据创建一个新版本），而使用B+树的传统集中式数据库则需要找到数据在磁盘上的位置，并在原地进行修改。LSM树的写入就是写入一个键值对，写入时会直接将键值对写入到内存中的MemTable。LSM的删除也是为数据打上一个墓碑标志，并不会做我们通常理解上的delete操作。

   先写WAL（Write Ahead Log）预写日志，再写入内存MemTable。

   写入数据量到达大小限制时，MemTable转变成immutable MemTable（不可变）。

   重启开一个新的MemTable。

   将immutable MemTable刷到磁盘上形成SST文件，该immutable MemTable销毁。

   WAL中数据都持久化到SST file之后，会被删除。

每一层都会切分成多个SST文件，每个SST文件都是键值对文件。达到一定阈值后，向下一层做Compact。用于去除相同key的多条记录。当我们对一个key进行多次update/delete时，RocksDB会产生多条记录。虽然定期合并可以有效的清除无效数据，缩短读取路径提升查询效率，提高磁盘利用空间，但Compaction操作是非常消耗CPU和磁盘IO的。

1. 查操作：因为最新的数据总是先写入MemTable，所以在读取数据时首先要读取MemTable，然后从新到旧搜索SSTable，找到的第一个版本就是该Key的最新版本。根据局部性原理，刚写入的数据很有可能被马上读取。因此，MemTable在充当写缓存之外也是一个有效的读缓存。为了提高读取效率，SSTable通常配有BloomFilter（布隆过滤器）和索引来快速判断其中是否包含某个Key以及快速定位它的位置。因为读取过程中需要查询多个SSTable文件，因此理论上LSM树的读取效率低于使用B+树的传统集中式数据库。

六、LSM树的优缺点

1. 优点：具有较高的写入性能和压缩存储，适用于写多读少或写入速度较快的场景。通过将写入操作集中在内存和顺序写的日志文件中，可以获得较高的写入吞吐量。查询可以通过内存缓存和有序的SSTable文件，进行快速定位和检索键值对。

2. 缺点：读放大。如读取操作可能需要扫描多个SSTable文件，导致查询性能不如B-tree等结构稳定。此外，合并操作可能会引起较长的停顿时间，影响读写性能，对于实时性要求较高的系统可能会有影响。

3. 对比B+树：在LSM树上进行一次数据更新不需要磁盘访问，在内存即可完成，速度远快于B+树。当数据访问以写操作为主，而读操作则集中在最近写入的数据上时，使用LSM树可以极大程度地减少磁盘的访问次数，加快访问速度。LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。极端的说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。

七、LSM树的设计原则

LSM树的设计原则主要包括以下几点：

• 先内存再磁盘：利用内存的高速读写能力，将写入操作集中在内存中，然后再批量写入磁盘。
• 内存原地更新：在内存中，数据可以直接进行原地更新，提高写入效率。
• 磁盘追加更新：在磁盘上，数据只能进行追加操作，避免随机写操作带来的性能瓶颈。
• 归并保留新值：通过合并操作，保留最新的数据版本，同时清除无效数据。

LSM树的设计出发点是追加式更新的内存或磁盘操作意味着顺序写入，执行效率比较高。同时，引入内存MemTable作为读和写的缓冲，因为直接读写磁盘效率会比较差。但内存中不可能无限制的放所有数据，所以在内存中的数据必须有一个大小限制，超出限制的数据需要写入磁盘文件（SSTable）。

SSTable会有多层的原因是为了将I/O的开销最小化。追加式的操作导致一个数据存在多个版本，既无效占用了大量磁盘空间，还有导致查询需要遍历太多数据，影响查询效率，所以要做合并和压缩，把这些冗余数据都舍弃掉。假设只有一个SSTable，因为MemTable在不断写入，查询操作也一直在扫描，完全没法做Compact。上述的问题在分层的结构下可以得到很好的缓解，本质上来说就是将一次性的大量I/O开销分摊到了多层当中，并且在在多层的这些I/O也不是完全同步的。这样一来某个时刻下的I/O开销会小很多，相应带来write stall写停顿的延迟与次数也会有所减少。

综上所述，LSM树作为一种高效的存储引擎，在原生分布式数据库中得到了广泛应用。通过了解其出现背景、特性、行业应用以及增删改查操作等