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

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

日志结构合并(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.