电子学报 ›› 2021, Vol. 49 ›› Issue (11): 2090-2095.DOI: 10.12263/DZXB.20200945

• 学术论文 • 上一篇    下一篇

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

俞加平, 陈华辉, 钱江波, 董一鸿   

  1. 宁波大学信息科学与工程学院, 浙江 宁波 315211
  • 收稿日期:2020-08-27 修回日期:2021-04-14 出版日期:2021-11-25 发布日期:2021-11-25
  • 作者简介:俞加平 男,1995年生于浙江湖州.现为宁波大学信息科学与工程学院硕士研究生.主要研究方向为非关系型数据库、数据挖掘等. E-mail:1811082061@nbu.edu.cn
    陈华辉(通信作者) 男,1964年生于浙江宁波.现为宁波大学教授、博士生导师.主要研究方向为数据流处理及大数据处理、数据挖掘等. E-mail:chenhuahui@nbu.edu.cn
    钱江波 男,1974年生于浙江宁波. 现为宁波大学教授、博士生导师.主要研究方向为数据库管理、多维度索引及查询优化等. E-mail:qianjb@163.com
    董一鸿 男,1969年生于浙江宁波. 现为宁波大学教授、硕士生导师.主要研究方向为大数据处理、数据挖掘及人工智能. E-mail:dongyihong@nbu.edu.cn
  • 基金资助:
    国家自然科学基金(61572266);浙江省自然科学基金(LZ20F020001)

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

Jia-ping YU, Hua-hui CHEN, Jiang-bo QIAN, Yi-hong DONG   

  1. College of Information Science and Engineering,Ningbo University,Ningbo,Zhejiang 315211,China
  • Received:2020-08-27 Revised:2021-04-14 Online:2021-11-25 Published:2021-11-25

摘要:

日志结构合并(Log-Structured-Merge,LSM)树中常使用布隆过滤器减少无效磁盘I/O.但是用户无法无限制地细化布隆过滤器的粒度,原因是在一些数据量庞大而数据项较小的工作流中,这些元数据需要占用大量存储空间.其次在一些内存受限的环境下,内存缓冲区无法容纳更多的过滤器数据,造成缓冲区与磁盘的频繁数据交换.针对上述问题本文提出LSM树中的异构布隆过滤器方案,在LSM树的每一层维护热度预测模型,新生成的SSTable通过预测的热度来分配不同粒度的布隆过滤器,然后使用特定缓存管理方案来维护缓存中的过滤器数据并处理工作流热度发生改变的情况.实验证明,本文的方案在保持相同外存占用与内存消耗的情况下,读取吞吐量比采用原始LSM树结构的LevelDB提升22%~53%.

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

Abstract:

Bloom filters are often used in the LSM(Log-Structured-Merge) tree to reduce unnecessary disk I/O. However, 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.

Key words: log-structured-merge-tree, key-value store, read performance, Bloom filter, storage management, hotness prediction

中图分类号: