%0 Journal Article %A 俞加平 %A 陈华辉 %A 钱江波 %A 董一鸿 %T LSM树中基于热度预测的异构布隆过滤器方案 %D 2021 %R 10.12263/DZXB.20200945 %J 电子学报 %P 2090-2095 %V 49 %N 11 %X

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

%U https://www.ejournal.org.cn/CN/10.12263/DZXB.20200945