[FAST'21] REMIX

REMIX: Efficient Range Query for LSM-trees

作者： Wenshao Zhong, Chen Chen, and Xingbo Wu, University of Illinois at Chicago;

Song Jiang, University of Texas at Arlington

论文概要

LSM-tree 的强大写入性能使得很多知名的 KV 存储都选择了它作为底层实现，比如 LevelDB、RocksDB 等。但在充分利用磁盘顺序写入提高写入性能的同时，它的查询效率也受到了比较大的影响，一次查询往往需要访问多个 table 文件。对于点查还可以通过 bloom filter 来做缓存，避免无意义的访问，但范围查询却很难避免。

本文的主要工作就是对 LSM-tree 的范围查询性能进行优化。作者为 LSM-tree 设计了一种高效的索引，在保证写性能不下降的情况下，通过利用较少的额外存储开销记录下数据的全局有序视图（globally sorted view），有效地提升了查询性能。

Compaction

Buffer 数据构造 mem table，顺序写入持久化为不可变的 sorted table，LSM-tree 通过这两个过程实现了高效的顺序写入，但随着时间迁移，也会不断积累大量的 table 文件，使得查询必须访问更多的文件，降低性能。

为了解决低效查询的问题，LSM-tree 都引入了 compaction 机制，通过整合零散的文件，删除数据的历史版本（GC），使得整体数据保持在尽可能新的状态，进而减少查询时接触到无效数据的可能性，提升性能。

图1

Leveled compaction 和 Tiered compaction 是两种基础的策略，同时也是读/写性能上的折衷：

  • Leveled compaction：compaction 频率相对较高，查询性能好但写放大严重，即牺牲写优化读。

  • Tiered compaction：通过增加每个 level 中允许并存的 run 数量，降低 compaction 频率，减小了写放大，但查询时需要同时访问更多的 run，查询性能较差，即牺牲读优化写。

本文目标是实现写最优的同时优化查询性能，所以选择的是 tiered compaction，下文如未强调都默认为该策略。

LSM-Tree范围查询

不管是哪种 compaction 策略，范围查询的数据都可能分布在内存或是以及多个 run 中，所以 LSM-Tree 进行范围查询是一个归并的过程。

  1. 在每个 run 内用二分得到首个大于等于 begin key 的位置，作为该 run 的初始化 cursor。

  2. 利用最小堆维护这些 cursor。

  3. 每次 pop 堆顶 cursor 对应的数据，然后得到新的堆顶，直到堆顶 key 大于 end key。

显然，这个过程会涉及到较多的 key 比较（最小堆维护），并且必须访问所有 run，即使该 run 上没有符合要求的数据。由于 tiered compaction 每一层可能有多个 run，所以对基于它的 LSM-tree 进行范围查询时，同时访问的 run 会更多，查询性能也更差。

图2

REMIX

Design Based on Sorted View

事实上，在做范围查询的过程中，实际上已经在多个 run 之间构造了一个全局的有序视图（sorted view）。但在大部分 LSM-tree 实现中，这个视图都是用时构造，查询结束后即进行释放，重复构造过程中产生了很多计算/IO 开销，导致查询性能很差。

LSM-tree run 的基础属性之一是不变性（immutability），而在底层 table 不变的情况下，基于 run 构造的 sorted view 同样继承了这一特性。因此，如果能够将 sorted view 高效地存储下来，那么它天然就是多个 run 的索引，能够有效地加速查询。 本文提出的 REMIX 正是基于此思路。

图3

REMIX 将 sorted view 涉及到的 key range 按照顺序划分为多个 segment，每个 segment 内保存一个 anchor key，记录该 segment 内最小的 key。

此外，每个 segment 内还维护了 cursor offsets 和 run selectors 两个信息。Cursor offsets 记录了每个 run 中首个大于等于 anchor key 的 key offset，比如 11 这个 segment，run 1,2,3 首个大于等于该值的 key 是 11, 17, 31（offset 1, 2, 1）。Run selectors 顺序记录了 segment 内每个 key 所在的 run 序号，以 71 这个 segment 为例，71, 73, 79 分别在 run 0, 1, 0 中。

假设点查 17，基于 REMIX 可以进行如下的查询过程：

  1. 通过 anchor key 二分查找，定位到 17 落在第二个 segment 的 key range 内。

  2. 由于 cursor offsets 代表着各个 run 中首个大于等于 anchor 的 key，17 > 11，所以直接将它作为各个 run 的初始 cursor，即 (1, 2, 1)。

  3. 将当前 pointer 设置为 run selectors 中的第一个，即 run 0，相当于原先的最小堆 top。

  4. 从 pointer 指向的 run 开始比较，11 (run 0) < 17，所以推进 run 0 的 cursor，即 offsets 变为 (2, 2, 1)。同时，run selectors 也向前推进，由 run0 切换至 run1，表示下一个需要访问的是 run1 在 cursor offsets 中对应的 key，即 run1 中下标为 2 的 key（17）。

  5. 查询结束。

范围查询过程：不断地根据 run selectors 调整访问的 run 及 offset，并结合与 end key 的比较结果，即可将点查过程扩展为范围查询。

但从上面的查询过程可知，segment 内查询是从 anchor key 开始，这个过程还是可能会产生不必要的比较和 run 访问。这和 segment 内的 key 数量有关，如果数量多，顺序查询性能差，但存储效率高（只用存储 anchor key），反之 anchor key 会变多，存储开销大。

因此，本文针对 segment 内的查询做了额外的优化。

Search in a Segment

二分查找

Segment 是对 sorted view 的切分，所以在每个 segment 内，它所维护的 key 之间也是有序的，所以对它也进行二分查找也是很自然的想法。但与 segment 间基于 anchor key 进行查询不同的是，每个 segment 内仅维护了一个 key，所以无法借助 key 比较来查询。

图4

本文借助了 run selectors 来进行二分查询，但由于 selector 仅记录了该 key 归属的 run，并不确定是该 run 中的哪一个 key，所以此处还计算了一份 occurrences 来辅助定位。该值表示的是当前 selector 所在的 run 在 segment 内是第一次出现，通过该 run 的 cursor offset 加上 selector 对应的 occurrence 值，即可得到它在该 run 中对应 key 的下标。

以上图 16 个 selector、查询 41 为例（假设 cursor offset 都是 0）：

  • 访问第 8 个 selector，通过 selector 和 occurrence 确认该 key 为 run3 的第 4 个 key（43），>41，所以向左查询。

  • 访问第 4 个 selector，run2 第一个 key（17），<41，向右查询。

  • 不断二分，最终查询到 41 为 run3 的第 3 个 key。

显然，不管是基于 selectors 的二分还是基于 occurrences 快速跳过 run 内元素，都能有效地减小 key 之间的比较次数，降低计算的开销。

I/O优化

这个优化比较朴素，因为数据都是 block 形式存储的，在通过二分定位到某个 key 时，与它同 block 的数据也会被加载上来，此时在该 block 内的数据做一次小范围的查询，看看是否可以减少一下后续二分的 range。

以查询 79 为例：

  • 访问第 8 个 selector，通过 selector 和 occurrence 确认该 key 为 run3 的第 4 个 key（43），<79，向右查询。

  • 43 属于 run3，83 可能也被同时读取，83>79，所以可以减少 upper bound，进而按照二分计算，下一个被访问的是 run0，绕过了对 run1（73）的访问。

    但这个其实也可能有 bad case，加入查询 73，本来第二次访问 run1 就查询到了，而由于此优化，额外访问了 run0。

简单地小结一下，相对于传统的范围查询，REMIX：

  • 通过全局的二分查找（segment 间基于 anchor key、segment 内基于 selectors），有效地减少了定位一个 key 时的复杂度。传统方式 M * logN，REMIX logMN。

  • Run selectors 可以帮助 REMIX 在查询时快速地在不同 run 的 key 间顺序推进，不用维护最小堆，也就避免了在每次 pop 时通过 key 比较进行重排，降低了计算开销。

  • 基于 anchor key 的二分也使得查询过程有机会跳过一些无需访问的 run，以先前的图片为例，如果一次点查询基于 anchor 二分的结果是第三个 segment，那么本次查询只需要访问 run2 即可完成。

存储开销

REMIX 本质上就是索引，因此也是典型的空间换时间，所以引入它所带来的额外存储开销是否能够接受也是必须考虑的。

本文对不同 workload 不同配置（segment 大小、是否开启 bloom filter、key/value 平均大小）下的情况都进行了较为详细的评估，结果如下表（最差情况下约 10% 的膨胀）。此处不再展开，细节大家可以参考下原文 3.4。

表1

RemixDB

图5

作者基于 REMIX 实现的一个 KV 存储，由于 workload 往往具有很强的空间分布特性，RemixDB 使用了 partitioned store layout 以降低 compaction 的开销。

Partitioned store layout 和分布式存储中基于 partition 划分数据的思想类似，将不同 key range 的数据分布到不同的 partition，从而每个 partition 可以独立地进行 compaction，相互之间不产生影响。RemixDB 中的每个 partition 都可以视为传统 tiered compaction LSM-tree 里的一个 level，即其中包含多个 run，此外为该 partition 内的所有 run 维护了一个 REMIX 索引。

关于 RemixDB，论文中还分别介绍了以下几个方面，这里仅简单地描述一下，对细节感兴趣的同学可以查看下原文。

  • 文件结构设计：主要介绍了如何尽可能高效地存储，包括特殊 bit 的设定。

  • Compaction：主要介绍了 RemixDB 和 compaction 相关的一些操作，核心点在于 compaction 策略（比如降低新文件数量，减少 REMIX rebuild）、partition split 策略。

  • REMIX 重建：主要策略是读 I/O 限制、尽可能复用 REMIX 文件中未修改部分（不变性）。

性能测试

测试配置：

  • CPU：2 Intel Xeon Silver 4210（2 20C）

  • Mem: 64GB

  • Linux (v5.8.7)

  • 文件系统：ext4 on 960G Intel 905P Optane PCIe SSD

我的思考

参考文献

PreviousFAST 2021 overviewNext[FAST'21] D2FQ

Last updated

Was this helpful?