< 返回主菜单

完整:张焕晨团队提出高效的数据压缩和索引技术LeCo

2024-07-02

Innovation Highlights


1. 提出了Learned Compression (LeCo)数据压缩框架。该框架创新地利用机器学习算法消除数据中的序列相关性冗余,不仅使数据列的压缩率显著提高,而且支持超低延迟的随机访问。在实践中打通了数据压缩和数据挖掘之间的技术隔阂,使得数据挖掘中的各类模式识别算法可以直接用于数据序列的压缩。

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

3. 提出了一套通用的转换和优化准则 (SGACRU),并将其应用于现有的内存型学习型索引。这一通用转换方法能够有效将内存中的学习型索引转化为适用于磁盘场景的索引,同时获得比之前更快的查询速度和更少的内存占用。


Achievements Summary

LeCo—基于机器学习的轻量级数据压缩

当今海量数据的产生与对查询极高的响应时间要求,让大数据压缩技术面临着全新的挑战。轻量级数据压缩是一项使列存储在分析查询中表现出优越的性能的关键技术。大量的已有工作都基于字典编码展开,而少有系统地利用列中的序列相关性进行压缩的工作。

相对于传统的消除数据重复的思路,张焕晨团队从一个全新的角度建模数据压缩问题,首次提出了Learned Compression(LeCo)数据压缩框架,一个利用机器学习自动消除相似性冗余以实现出色压缩比和解压性能的框架。LeCo将现有算法融入框架中,使得压缩率突破信息熵下界,同时加速解码过程以提升后续计算的效率。

1.png


图1.   LeCo框架 - 各模块及其交互概述


LeCo框架的核心创新在于:

(1)使用机器学习来识别和利用数据中的序列相关性,这是之前研究中未被系统性利用的领域。

(2)提出了一种通用方法,将现有的算法如Frame-of-Reference (FOR)、Delta编码和Run-Length编码(RLE)作为特殊情况纳入其框架。

(3)通过形状编码技术,将序列划分和回归模型结合,以实现高效的压缩。

(4)包含一个超参数顾问,用于选择最佳的回归模型类型和压缩比。



2.png


图2.  LeCo字符串压缩 - 包括算法和存储格式修改的示例


在实验测试的十二个数据集上,LeCo在压缩比和随机访问速度上比现有解决方案实现了Pareto改进。将LeCo集成到广泛使用的系统中时,在列式执行引擎Arrow+Parquet上有5.2倍的查询加速,而在RocksDB中的吞吐量增加了16%。



3.png

图3. 压缩微基准测试


针对现实系统中的混合事物分析场景,提出了系统性压缩的工具链。在列存的基础上,提出解决方案LeCo,用数据挖掘和模式识别技术将单列数据的分布信息凝缩在模型中,并存储错误修正码以实现无损压缩。在多个真实系统测试中,该压缩方案凭借突出的压缩率与轻量级解压操作提升查询速度、缓解内存瓶颈,在Parquet读取和Hash join算子中有着高至12倍和96倍的速度提升。



4.png


图4. 性能-空间的权衡


LeCo框架的应用价值体现在能够为现代数据分析系统提供更高的性能和存储效率,同时保持了良好的兼容性和易用性。LeCo在不同的工作负载和数据集上都展现出了卓越的性能,证明了其在实际应用中的潜力。本论文一作为上海期智研究院实习生、清华大学交叉信息学院博士生刘奕好。



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

5.png

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


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



6.png

图6. GRF概览


GRF的优点具体包括:

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

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

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

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



7.png

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


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





3. 使内存中的学习型索引在磁盘上高效

近年来,学习型索引已成为数据库管理系统的研究热点。然而,目前最先进的学习型索引主要针对内存场景设计,与基于磁盘的数据库管理系统并不完全匹配。为解决这一问题,张焕晨团队提出了一套通用的转换和优化准则(SGACRU),并将其应用于现有的内存型学习型索引。这一通用转换方法能够有效将内存中的学习型索引转化为适用于磁盘场景的索引,同时获得比之前更快的查询速度和更少的内存占用。

8.png

8.png

图8. SGACRU架构


SGACRU准则包括:

G1: (Search) 根据磁盘和工作负载特征,在“最后一英里”搜索期间确定叶页获取策略。

G2: (Granularity) 确定学习模型的预测粒度(例如,项与页)。

G3: (Alignment) 利用页面对齐扩展索引训练的错误界限,以减少模型数量,同时保持相同的预期I/O页面。

G4: (Compression) 通过压缩模型参数减少内存使用,接受与主导I/O时间相比微不足道的CPU开销增加。

G5: (Robustness) 对于CDF难以学习的数据集,回退到高效压缩的区域映射索引。

G6: (Update) 使用混合索引进行高效更新。



9.png

图9. CPU时间与I/O时间对比


这一套通用的转换和优化准则在提升索引结构的速度、空间利用、鲁棒性、智能化水平等方面具有显著优势,同时减轻了研究人员设计磁盘场景下学习型索引的负担。具体包括:

(1)结合磁盘特性和学习型索引的特点,提出了内存和磁盘交互、模型预测的粒度两方面的优化策略,以加速基于磁盘的学习型索引的响应速度。

(2)总结了多种学习型索引的构建算法,并提出通用的优化,可以显著减少索引的内存占用,同时保持高效的查询性能。

(3)从功能性和鲁棒性的角度分别提供相应的优化策略,有助于研究人员更好地理解和高效使用学习型索引。

(4)这一通用转换方法可应用于现有的内存中的学习型索引,使研究人员无需为磁盘场景重新设计索引结构,从而有效提高了开发效率。



10.png

图10. 在Facebook数据集上与FILM的吞吐量和空间成本比较


该工作提升了学习索引在磁盘上的性能和效率,推动了人工智能与数据库融合的学习型索引的发展,具有重要的理论和应用价值。本论文一作为上海期智研究院实习生、清华大学交叉信息学院博士生张缴怡。



更多信息请阅读论文:



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.











分享到