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

原创手机用户0271 2023-11-20

425

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

—

背景

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树实际上并非是一种具体的数据结构，而是一种具备“顺序追加”、“多层数据结构”和“定期合并”等特性数据处理逻辑，将离散的随机写转化为批量的顺序写，减少了磁盘寻道时间提高了写入性能，适用于写密集型应用。

—

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以牺牲少量的空间代价，换来读取数据时非常快速地确定是否存在某条数据，从而进一步提升磁盘随机读效率。

—

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时间。

—

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重写）。

—

总结

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

附：参考文献

The Log-Structured Merge-Tree (LSM-Tree)
LSM based Storage Techniques: A Survey
PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees
WiscKey：Separating Keys from Values in SSD-conscious Storage
HashKV: Enabling Efficient Updates in KV Storage via Hashing
HBase MOB官方设计文档
tikv/titan: A RocksDB plugin for key-value separation, inspired by WiscKey
Titan的设计与实现

- END -

关于本周文章如果大家有疑问，或者有其他感兴趣的大数据内容，欢迎大家在评论区留言，后续会持续分享大数据领域的干货知识~

elakehouse