前言

在了解 TinyKV 中提到的 badger 过程中学习到 LSM-Tree，故此记录

什么是 LSM-Tree

LSM-Tree 全称为 Log-Structured Merge-Tree，日志结构合并树，下文简称 LSM-Tree。LSM-Tree 的架构分为内存部分和有序的磁盘部分，内存部分实现高速写，有序的硬盘实现高效查，整体架构如下图中 LevelDB 所示。

现代LSM-Tree架构图

LSM-Tree 的思想是：借助于内存和日志文件将写入过程分为时间上不前后相连的两步，写入是只顺序写入磁盘的日志文件和内存，等系统空闲时再将内存中数据写入到磁盘。这样在处理写入请求时就省去了磁盘寻道、转动磁头的时间。

LSM-Tree 有以下几个特点：

LSM-Tree特点

LSM-Tree 工作原理

LSM-tree 核心是将写入操作与合并操作分离，通过将数据写入日志文件和内存缓存，然后定期进行合并操作来提高写入和查询的性能。

LSM-Tree 写入

LSM-Tree 写入操作分为两步，分别执行，具体步骤如下：

  1. 第一步为写入操作
    1. 写入日志文件（Write-Ahead Log, WAL）：当有新的 key-value 需要写入时，首先将其追加到顺序写的日志文件中。这个操作称为预写日志（Write-Ahead Logging），它可以确保数据的持久性和一致性。
    2. 写入内存缓存（MemTable）：同时将新的 key-value 写入内存中的数据结构，通常是跳表或红黑树等有序数据结构。内存缓存可以快速响应读取操作，并且具有较高的写入性能。
  2. 第二步为定期合并
    1. 内存与磁盘的合并（MemTable to SSTable）：当内存缓存达到一定大小或者其他触发条件满足时，将内存缓存中的 key-value 写入到磁盘上的 SSTable 文件中。即在 MemTable 满时将其转为 Immutable MemTable，同时构建新的 MemTable，保证向内存写 MemTable 和向磁盘写新的 SSTable 可以同时进行。
    2. SSTable 的合并：当 SSTable 数量到达阈值时，进行合并。合并操作将多个 SSTable 文件进行合并，消除重复的 key 和删除的 key，并生成新的 SSTable 文件。合并操作可以基于时间、文件大小或其他条件进行触发和控制。

LSM-Tree 的一些特性：在执行 Update 和 Delete 操作时并不会真正去操作 SSTable 中的数据，如果在 MemTable 中已有记录则直接执行修改操作（用新的覆盖旧的），否则直接写入，有点类似于追加写入。由于读取时自上而下读取，自然会先读取到新的数据。在进行 SSTable 合并时也是利用时间戳去进行操作。

可以从下面这张图直观感受 LSM-Tree 写入过程：

LSM-Tree Write

LSM-Tree 查找

LSM-Tree 的查找分为三步，首先是查找内存，不中再查硬盘，具体步骤如下所示；

  1. 先查内存中的 MemTable，如果命中则返回；
  2. 再查 Immutable MemTable，如果命中则返回；
  3. 最后查硬盘，依次从 L0 层的 SSTable 文件开始，逐层遍历。首先对每个 SSTable 对应的布隆过滤器进行过滤，如果判定为在该 SSTable 中，则查询该 SSTable 的索引表，索引表 key 有序，所以是二分查找。如果找到对应的 key，则根据偏移值获取数据返回；如果未找到对应的 key，则对下一个 SSTable 重复该过程。

LSM-Tree Search

三大组件

MemTable

MemTable 是内存中的数据结构，存储近期更新的记录值，因此可以采用一些有序集合来存储，比如跳表、红黑树都是非常不错的选择，整体来说，MemTable 相对比较简单，采用的数据结构也比较常见。

Immutable MemTable

Immutable MemTable，可以理解成不可变表。它是因 MemTable 存储容量达到阈值后转变而来，所以采用的数据结构和 MemTable 一样。引入 Immutable MemTable 作为一种中间结构，避免 MemTable 的读写冲突竞争，保证对 MemTable 的写入和向磁盘写入 SSTable 同时进行，从而提高系统性能。

SSTable

SSTable 是 LSM-Tree 的核心，主要是用于数据在磁盘上的持久化存储，存储一些按照 key 有序排列的键值对组成的 segment。另外，为了加快查询速度，通常需要给 SSTable 创建索引，索引存储在 SSTable 的尾部，用于帮助快速查找特定的 segment。索引表在我们操作系统非常常见，像文件管理和存储中都用到了索引表。类似于我们操作系统中的索引表，SSTable 也用一张存储表记录了 SSTable 存储的每个元素的位置。引入索引表后，当从 SSTable 中取数据的时候，不用把整个 SSTable 读进内存了，而是只需要读进非常小的索引表即可，极大减少了 IO 成本。同时索引的 key 是有序的，所以查找时二分查找方式也非常快。

LSM-Tree SSTable

布隆过滤器

为了进一步减少数据查询时的磁盘 IO 和提高查询速度，LSM-Tree 引入了布隆过滤器。利用布隆过滤器，对所要查询的数据进行一个初步判读。每个 SSTable 都有个布隆过滤器，如果布隆过滤器判定为没有，则改 SSTable 中一定不存在改数据；如果布隆过滤器判定为有，则改数据很可能存在于该 SSTable 中，这是再将索引表加载进内存，进行进一步的查找确认。如果找到则返回；如果未找到，则再匹配下一个 SSTable 的布隆过滤器。

布隆过滤器结构如下所示：

LSM-Tree 布隆过滤器

LSM-Tree 优点与缺点

优点：写入快（增、删、改速度非常快），写吞吐量极大：写入时仅写入内存和顺序写入磁盘上的日志，不用关心是否写入磁盘。

缺点：

  1. 查询较慢，相比于 B + 树，查询速度较慢
  2. 范围查找能力较差
  3. 查询不存在的数据会进行全表扫描，非常慢

总结 —— 我的理解

LSM 利用内存写入速度远大于磁盘写入和磁盘批量顺序写的速度要远比随机写性能高出很多的特性，设计出这个结构。写入时分别写入 MemTable 和 WAL 中，利用红黑树保证 MemTable 写入时的有序性，同时写入 WAL 防止内存崩溃。在 MemTable 满时将其转为 Immutable MemTable，同时构建新的 MemTable，保证向内存写 MemTable 和向磁盘写新的 SSTable 可以同时进行。如此以来，外部向 LSM-Tree 中写入数据时分为两步，第一步向 MemTable 写入数据和向 WAL 写入日志，第二步实际向磁盘写入数据并调整内部多级 Level SSTable，如此两步操作大大提高了写入效率。在 LSM-Tree 中执行读操作时，读取顺序为：MemTable -> Immutable MemTable -> L0 -> … -> LN, 以这种方式逐层向下进行搜索，读取操作有两个特点：其一便是越靠近上层的数据越新，也就是说自上向下读取到的第一个数据便是当前有效数据；其二便是每个 SSTable（包括 MemTable）内部有序，能够使用二分查找的方式加快搜索效率。但是这种查找方式存在读放大问题，如果数据较旧，读取的层数可能较多，随着层数增加，读的范围会越来越大，导致读取速度降低。如此便有了优化策略 —— 布隆过滤，在向 MemTable 中写入时，利用哈希表对 key 进行映射，存在便映射为 1，这样在搜索时便可以利用 key 进行哈希判断是否不存在了（如果为 0 可以保证肯定不存在，为 1 可能存在 —— 哈希映射问题），从而加快搜索效率。

写在最后

LSM-Tree 的应用还是非常广的，特别是在数据量特别大、写入特别多的数据库中，目前基于 LSM 实现的数据库有：LevelDB，RocksDB，Hbase，Cassandra，ClinkHouse 等。

我目前了解的 badger 数据库便是使用的是 LSM-Tree，但是做了一些优化，将 WAl Log 改为了 Value Log，同时将 Key-Value 分离存储。LSM-Tree 里面存储的是一个 Key 以及 Value 的地址，Value 本身以 WAL 方式 append 到 Value Log 文件中。这样做有两个优势：由于 LSM-Tree 做 Compaction 时不需要重写 Value（每个 Value 大小相同），大大减小了写放大。同时 LSM-Tree 更小，一个 Block 能存储更多的 key，也会相应的降低读放大，能缓存的 Key 以及 Value 地址也更多，缓存命中率更高。

bagerDB

各家数据库优化好像也不太一样，具体我也没多了解，以后有机会会去多学习学习。

参考文献