< 返回主菜单

通过形状编码构建LSM-Tree全局范围过滤器—GRF

2024-07-02

Innovation Highlights

       提出了一种全局范围过滤器结构Global Range Filter (GRF)来减少查询过滤器的时间开销。在不产生额外内存开销的情况下将全局过滤器支持了范围查询,通过形状编码来保证查询结果在并发场景下的正确性。

Achievements Summary

通过形状编码构建LSM-Tree全局范围过滤器—GRF

       LSM-Tree是一种非常常见的键值对数据存储引擎。LSM-Tree在磁盘上维护多个排序数组,牺牲了部分查询性能来换取高效的写入性能。随着数据量的扩大以及排序数组个数的增加,查询这些过滤器的时间逐渐变成了性能瓶颈。过往工作通过建立全局过滤器,减少过滤器查询次数的方式来降低这一瓶颈。但是过往的全局过滤器往往无法加速范围查询,同时在并发查询的场景下会产生正确性的问题。

5.png

图1. 全局过滤器的多版本并发控制(MVCC)问题

       张焕晨团队提出了一种全局范围过滤器结构(GRF)来减少查询过滤器的时间开销。在不产生额外内存开销的情况下将全局过滤器支持了范围查询,通过形状编码来保证查询结果在并发场景下的正确性。


6.png

图2. GRF概览

GRF的优点具体包括:

(1)可以同时加速点查询和范围查询。

(2)使用形状编码技术来存储每个键在LSM-Tree中的分布情况。与传统的过滤器相比,形状编码能够更有效地表示键的未来位置,从而减少每次压缩操作时所需的更新。

(3)通过支持MVCC增强了并发查询的能力,解决了并发读写场景下查询结果不正确的问题。

(4)该数据结构的维护代价很低,在LSM-Tree合并多个排序数组的时候不需要额外处理,由此提高了LSM-Tree的写性能。

7.png

图3. 在具有形状编码的快照中搜索键


       该工作提出的GRF在提高数据库系统性能,尤其是在需要处理大量写入和查询的现代应用场景中,具有显著的应用价值。本论文一作为上海期智研究院实习生、清华大学交叉信息学院博士生王恒睿。


更多信息请阅读论文:

1. GRF:A Global Range Filter for LSM-Trees with Shape Encoding, Hengrui Wang, Te Guo, Junzhao Yang, Huanchen Zhang*, SIGMOD 2024.

2. LeCo: Lightweight Compression Via Learning Serial Correlations, Yihao Liu, Xinyu Zeng, Huanchen Zhang*, SIGMOD 2024.

3. Making In-Memory Learned Indexes Efficient on Disk, Jiaoyi Zhang, Kai Su, Huanchen Zhang*, SIGMOD 2024.

4. SALI: A Scalable Adaptive Learned Index Framework based on Probability Models, Jiake Ge, Huanchen Zhang, Boyu Shi, Yuanhui Luo, Yunda Guo, Yunpeng Chai, Yuxing Chen, and Anqun Pan*, SIGMOD 2024.

5. PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware, Shuangyu Cai, Boyu Tian, Huanchen Zhang, and Mingyu Gao*, SIGMOD 2024.