论文部分内容阅读
键值系统主要用于为数据密集型应用提供存储服务,系统采用的主流架构为LSM-tree。LSM-tree将键值对存储在固定大小的文件内,称这些文件为SSTable,SSTable被进一步组织在LSM-tree的分层结构中。系统在执行读操作时,需要发出多个I/O请求对不同层的SSTable进行检查,直到获取目标键值对,过多I/O请求导致读性能较差。为提高读性能,键值系统为每个SSTable配置一个布隆过滤器,但是布隆过滤器的误报同样会引发额外的I/O请求。且现有设计对系统内所有布隆过滤器采用统一设定,也不能对布隆过滤器误报率进行动态调整,其统一降低误报率的办法将会给系统环境带来巨大内存开销。为提高读性能,减少布隆过滤器技术的内存空间使用量,本文提出弹性布隆过滤器机制(Elastic Bloom Filter,ElasticBF)。ElasticBF 为每个 SSTable 构建多个占用空间小的布隆过滤器,对这些小过滤器进行组合可以得到不同误报率。ElasticBF根据各SSTable访问频率差异,动态的为每个SSTable加载小过滤器,实现了运行时误报率弹性可调节的弹性布隆过滤器机制。为给每个SSTable加载合适数量的小过滤器,我们以最大程度降低布隆过滤器误报引发的I/O请求为目标,基于各SSTable的访问频率,设计了一套完整的过滤器调整规则。并且为了使过滤器的动态调整开销较小,我们扩展了多级队列这一数据结构,使用多级队列对布隆过滤器进行管理。因此,ElasticBF能够动态调节每个SSTable布隆过滤器的误报率和内存使用量,使得其在内存使用总量保持不变情况下,大大减少(实验中最高可达67%)读操作中因布隆过滤器误报引发的I/O请求,从而提高读性能。我们在LevelDB的基础上实现了 ElasticBF,并在服务器上进行了性能测试。实验结果显示,ElasticBF读吞吐量最高是LevelDB的2.24倍,且基本没有对写性能造成损失。在ElasticBF集成到系统的过程中,我们进一步研究了小过滤器的配置方案,以提高系统启动阶段的读性能,并减少小过滤器动态调整开销对读性能的影响。首先,我们基于LSM-tree的特性,提出了层间异构布隆过滤器配置技术(Heterogeneous Bloom Filter,HBF)。随后,建立模型定量描述系统读性能与布隆过滤器配置方案的关系。最后,我们使用动态规划算法求解层间异构布隆过滤器的最优配置方案。该方案既能指导ElasticBF中小过滤器的配置,也能直接应用于键值系统中优化系统读性能。