LSM 树读写放大问题及 KV 分离技术解析

本文作者为中国移动云能力中心大数据团队软件开发工程师周翔宇，文章首先分析 B+树磁盘随机写问题，引出 LSM 树并分析其结构、读写流程、Compaction 策略以及在 HBase 中的具体实现。其次，分析 LSM 树读写放大的根本原因，以及学术界如何通过 KV 分离技术来优化 Compact 导致的写放大。最后，分析 KV 分离技术在 HBase MOB 和 TiDB Titan 项目中的具体落地。

1、背景

LSM 树（Log-Structured Merge-Tree），因其独特的数据组织方式（Log-Structured）和需要在后台不断合并（Merge）的维护方式而得名。又因其磁盘顺序写的模式，从而取代 B+Tree，被广泛应用于 HBase、Cassandra、LevelDB、RocksDB 和 TiDB 等写密集型 KV 数据库和存储引擎上。

在认识 LSM 树之前，首先回顾一下被主流关系型数据库广泛采用的索引结构：B+Tree。B+Tree 是一种多路平衡查找树，为了降低树的高度，非叶子节点只存放索引数据，叶子节点存放所有数据和指向相邻节点的指针。由于叶子节点通过指针相连，且所有叶子节点到根节点的距离基本相同，因而具有高效的范围查询和稳定的查找效率，以及具有较小的读放大和空间放大。然而，B+Tree 采用磁盘随机读写方式，且以磁盘数据页作为最小的读写单元。随着数据大量插入，导致叶子节点不断分裂，最终导致逻辑连续的数据存放到不同物理磁盘块位置，产生大量的读随机 I/O，从而导致范围查询效率下降和读放大。此外，当更新一条数据时，B+Tree 采用原地更新方式（in-place update），整个叶子节点对应的数据页都要读取和写回，带来了额外的读写放大。因此，磁盘随机读写成为 B+Tree 的瓶颈，使其适用于读多写少的场景。

随着 Google BigTable 的公开和 HBase、Cassandra 等 NoSQL 开源数据库的落地，LSM 树才真正大规模的进入了学术界和工业界的视野。LSM 树实际上并非是一种具体的数据结构，而是一种具备“顺序追加”、“多层数据结构”和“定期合并”等特性数据处理逻辑，将离散的随机写转化为批量的顺序写，减少了磁盘寻道时间提高了写入性能，适用于写密集型应用。

2、LSM 树和 HBase 中的应用

LSM 树结构上是一种横跨内存和磁盘，且包含多颗子树的索引结构，并在内存达到阈值时启动树合并。LSM 树中 C0（MemTable）是一颗常驻内存中还未刷盘、原地更新的查找树，MemTable 内部 KV 对有序存储，便于快速持久化到 SSTable 上。C1 - CX（SSTable）是磁盘中只追加（append-only）的 B-Tree，每个 SSTable 包含多个存储数据的文件 segment，每个 segment 内部都是有序的，但不同 segment 之间没有顺序关系。随着数据的不断写入，SSTable 和 segment 数量不断增加，当 Ci 超过固定大小后，采用 Merge Sort 的方式写入到 Ci+1 层，该过程也称为 Merge 或者 Compact。

LSM 树根据 SSTable 中每层 Run 数量的不同，将 Compaction 策略划分为两大类：Tiering 和 Leveling。论文中对于 Run 的概念比较抽象，可以理解每个 Run 里 KV 对具有 key 有序（sorted）和 key 不重叠（non-overlapping）两个特点。

Tiering：每层可能有 N 个重叠的 sorted Runs，当上一层的 sorted Runs 要 merge 下来时，不会和当前层重叠的 sorted Runs 马上合并，而是等到当前层空间不足时，才会合并，然后再 merge 到下一层。Tiering 这种策略适用于写密集型（Write-Intensive）应用，具有较低的写放大，但是读放大和空间放大较高。由于所有上层数据直接追加写入下层，写放大比较低。但是每层都有多个 Run，且多个 Run 中的数据可以重叠，点查询需要由上到下遍历每一个 Run，读放大较严重。业界采用 Tiering 作为 Compaction 策略的有 BigTable、HBase、Cassandra 和 InfluxDB 等 KV 数据库。

Leveling：每层有且只有一个 sorted Run，当上一层的 sorted Run 要 merge 下来时，会马上和当前层的 sorted Run 合并。Leveling 这种策略适用于读密集型（Read-Intensive 应用），具有较低的读放大和空间放大，但写放大较高。由于每层只有一个 Run，这个 Run 中的 KV 对不存在 Key 重叠，因此降低了读放大和空间放大，但是点查询仍然有可能会遍历所有的 Run，而范围查询必然会遍历所有的 Run。Leveling 上层与下层 merge 的过程有可能涉及到上下层所有的数据，造成上层 Run 全量重写到下层中，导致写放大较高，但是由于每个 Run 可以分为多个 partition(SSTable)，因此可以节约部分临时空间。业界采用 Leveling 作为 Compaction 策略的有 LevelDB、RocksDB 等 KV 数据库。

LSM 树在 HBase 的实现中，MemStore 和 StoreFile 分别对应 C0 和 C1 - CX。数据写入时，首先会写到内存中的 MemStore，当达到一定阀值之后，flush（顺序写）到磁盘，形成新的 StoreFile，最后多个 StoreFile 又会进行 Compact。HBase MemStore 内部维护了一个 ConcurrentSkipListMap 的数据结构，跳表是一种查找、插入和删除高效的内存数据结构，其底层采用有序链表存储，方便数据插入。在底层节点之上构建多层不同的稀疏索引，加速节点的查询定位。当内存数据源源不断 flush 到磁盘后，为了减少读数据 seek 操作次数，HBase 支持 Major Compaction 和 Minor Compaction 策略，所有的 HFile 或者选择多个 HFile 进行异步多路归并成一个 HFile 文件。

为了提升 LSM 树 SSTable 的随机读性能，HBase 在 HFile 中引入了 Bloom Filter，对应 HFile 中的 Bloom index block。通过 Bloom Filter，HBase 以牺牲少量的空间代价，换来读取数据时非常快速地确定是否存在某条数据，从而进一步提升磁盘随机读效率。

3、LSM 树读写放大问题分析及放大优化 

LSM 树的读放大主要来源于读操作需要从 C0~Ck（自顶向下）一层一层查找，直到找到目标数据。这个过程可能需要不止一次 I/O，特别是对于范围查询，读放大非常明显。LSM 树的空间放大主要是由于所有数据写入采用非原地更新的追加方式，过期或者删除的数据不会马上从磁盘上清理掉。因此，采用 LSM 树思想的 KV 数据库的实现中，通常需要启用后台线程周期检查或者手动 flush 等方式触发 Compaction 来减少读放大（减少 SSTable 文件数量）和空间放大（清理过期数据），但也因此带来了严重的写放大问题。下图是 PebblesDB 论文中测试了几款主流 KV 数据库的写放大系数对比：

其中，RocksDB 写放大系数高达 42 倍，LevelDB 也高达 27 倍。写放大意味着对磁盘更多的读写，造成数据库系统写入性能的频繁抖动。如果采用 SSD 作为持久化存储，由于 SSD 具有不支持覆盖写、必须先擦除后写入和使用寿命低的特性，写放大问题对 SSD 也是灾难性的。因此，LSM 树的写放大就成了学术界各大顶会顶刊和工业届亟需研究的问题。

目前，LSM 树优化方向主要有写放大、Merge 操作、二级索引和硬件层面等方向。下文着重分析 KV 分离技术，KV 分离技术核心思想是 LSM 树 Compaction 过程中不需要重写 value。对于 KV 对中 value 较大的情况，能够大大减少无效 I/O，降低写放大。同时，LSM 树不存储 value，体积更小，一个 SSTable 文件存储更多的 key，可以更充分的 Cache 到内存中，有利于减少读 LSM 树的 I/O。

学术界在 KV 分离技术的研究中，简单分析奠基性的 WiscKey 和 HashKV 方案。WiscKey 提出一种对 SSD 优化的基于 LSM 树的存储引擎设计，核心流程是 LSM 树节点只存放二元组<key, offset>，当数据插入时原始数据的 value 写到一个 append-only 文件中（vLog），然后将 key 插入到 LSM 树节点中。由于原始数据的剥离，LSM 树节点大幅减少，相应的读写放大、空间放大和 SSD 损耗都有所减小。由于数据文件的尺寸小了，所需 IO 数量也就少了对应的查询速度有所提高。当很多记录被删除（或者被更新）之后，只需要删除 LSM 树节点中的数据，存储在 append-only 文件中的原始数据需要定期垃圾回收。Wisckey 的设计思路适用于 value 相对较大的情况下有助于减少写放大，本质上只是将 LSM 树的写放大问题转嫁到了 vLog 中，而 vLog 中的数据读写和垃圾回收仍存在较大的性能开销。HashKV 在 Wisckey 基础上针对 vLog 的读写和垃圾回收优化，提出了 circular 特性的 vLog、数据分片和冷热分离等方面的改进，减少 vLog 数据 GC 时间。

4、HBase 和 TiDB 中 KV 分离技术实现

学术界的顶会顶刊发表了很多优秀的数据结构和 KV 分离方案来优化写放大问题，实验场景下数据对比也较为出色。然而，由于业界负载和实际业务数据更为复杂，业界 KV 分离技术成熟产品并不多。下面简单分析一下应用较为广泛的开源产品 HBase MOB（Medium Object）和 TiDB Titan 如何实现了 KV 分离技术的应用。

HBase 2.0 版本引入了列族级别的 MOB 功能，改善了对中等大小值的低延迟读写能力，支持 MOB 阈值可配，对客户端完全透明，为 HBase 对象存储提供了一体化解决方案。由于 HBase 最理想场景是存储 Metadata，对于 MOB（1~10MB）、LOB（>10MB）写入时，触发频繁的 flush、Compaction 和 Region 分裂，导致 HBase 集群读写延迟和长期处于 RIT 状态。

HBase MOB 方案中 Metadata 和 MOB 数据同时写入 Memstore，当 Memstore 中数据 flush 到磁盘时，将 Metadata 存放到常规的 StoreFile 形式，MOB 数据则以 HFile 格式直接存储到 HDFS 上，使得 MOB 移出普通 Region 的管理来避免 Region Split 和 Compaction 操作。然而，数据仍然先写入 Memstore，决定了写入数据量不能太大，否则一次写入可能会撑爆 Memstore，造成 OOM 或者 Full GC。此外，为了避免 HDFS 上存在许多 MOB 小文件，HBase MOB 支持更为简单的 Compaction 方式，默认按天合并压缩。HBase MOB Compaction 只对小文件进行压缩，而对大文件不进行严格的压缩，避免对大文件的无限压缩使得写放大更具可预测性。

TiDB 数据存储使用 RocksDB 作为底层数据存储架构，而 Titan 作为 RocksDB 插件提供的高性能 KV 存储引擎，其主要设计灵感来源于 WiscKey，通过 KV 分离技术降低写放大。Titan 在数据写入操作中类似于 HBase MOB，也是先写入 WAL，在 MemTable flush 到磁盘时，通过 TitanTableBuilder 来判断当前 value 大小是否符合分离阈值，如果 value size >= min_blob_size 则将 value 分离到 BlobFile，并生成 index 写入 SSTable；如果 value size < min_blob_size 则将 value 直接写入 SSTable。BlobFile 中包含了有序存储的 KV 对，KV 对按单个记录压缩。对于过期或者待删除数据，LSM 树采用 Compation 方式删除，而对于分离出 LSM 树的 BlobFile，需要垃圾回收来减少 KV 分离导致的空间放大。Titan 支持两种垃圾回收方式：Regular GC（普通垃圾回收）或者 Level Merge（在 LSM 树 Compaction 时候同时进行 BlobFile 重写）。

5、总结

LSM 树的 KV 分离技术有效缓解了 Compaction 操作对 value 的不断重写，减小了写放大。但于此同时，带来其他的开销，比如空间放大、读路径变长等。LSM 树读放大、写放大和空间放大，三者就像 CAP 定理一样，需要根据用户实际业务负载，做好权衡和取舍。