LSM树中基于热度预测的异构布隆过滤器方案  

A Heterogeneous Bloom Filter Scheme in LSM Tree Based on Hotness Prediction

作　　者：俞加平 陈华辉[1] 钱江波[1] 董一鸿[1] YU Jia-ping;CHEN Hua-hui;QIAN Jiang-bo;DONG Yi-hong(College of Information Science and Engineering,Ningbo University,Ningbo,Zhejiang 315211,China)

机构地区：[1]宁波大学信息科学与工程学院,浙江宁波315211

出　　处：《电子学报》2021年第11期2090-2095,共6页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61572266,No.61472194);浙江省自然科学基金(No.LZ20F020001,No.LY20F020009)。

摘　　要：日志结构合并(Log-Structured-Merge,LSM)树中常使用布隆过滤器减少无效磁盘I/O.但是用户无法无限制地细化布隆过滤器的粒度,原因是在一些数据量庞大而数据项较小的工作流中,这些元数据需要占用大量存储空间.其次在一些内存受限的环境下,内存缓冲区无法容纳更多的过滤器数据,造成缓冲区与磁盘的频繁数据交换.针对上述问题本文提出LSM树中的异构布隆过滤器方案,在LSM树的每一层维护热度预测模型,新生成的SSTable通过预测的热度来分配不同粒度的布隆过滤器,然后使用特定缓存管理方案来维护缓存中的过滤器数据并处理工作流热度发生改变的情况.实验证明,本文的方案在保持相同外存占用与内存消耗的情况下,读取吞吐量比采用原始LSM树结构的LevelDB提升22%~53%.Bloom filters are often used in the LSM(Log-Structured-Merge)tree to reduce unnecessary disk I/O.How⁃ever,users cannot refine the granularity of Bloom filters infinitely,because in some workflows with huge data volume and small data items,these metadata require a lot of storage space.Secondly,in some memory-constrained environments,the cache cannot accommodate more filter data,resulting in frequent data exchange between memory and disk.In view of the above problems,we propose a heterogeneous Bloom filter scheme in LSM tree.The hotness prediction model is maintained at each layer of the LSM tree,and the newly generated disk components are distributed with different granularity according to the predicted hotness.And a specific cache management scheme is used to maintain the filter data in memory cache and deal with changes in workflow hotness.It is experimentally proven that the proposed scheme improves read throughput by 22%~53%over LevelDB with the original LSM tree structure while maintaining the same storage occupation and memory consumption.

关 键 词：日志结构合并树 键值存储 读取性能 布隆过滤器 存储管理 热度预测 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]