分类：LSM-Tree optimization，Bloom filter

ElasticBF: Hotstorage 18

Backgroup

LSM-base 的KVstore 中都使用level compaction的policy，导致了严重的write amplification问题。并且在查询的时候，数据是分很多层级的，会带来read amplification的问题。

虽然有bloom filter存在，但是bloom filter也有如下的问题：

• 需要在内存中，会消耗大量内存
• false positive问题，导致io操作

Motivation

提高 bloom filter的设计：

• 减少内存消耗
• 减少read的io消耗
• 提高查询performance

Main idea

主要的方法是来源于对某种现象的统计：

• access frequecies of sstable in lower level are higher
• unevenness of accesses even within the same level

方法：

• elastic schema according to access freque

• sstalbe with high access frequency

  • more powerful bloom filter
  • lower false positive -> fewer extra io
  • larger memory consumption

Main design and implementation

ElasticBF的设计

问题：

• how to reduce the false positive？

• bits per key

  >hot sstable，使用更多的bloom filter，cold sstable使用更少的bloom filter（实际上减少bits per key）
  

• how to adjust the bloom filter dynamically ？

  However, the bits-per- key allocated to a filter is fixed and unable to change as long as the filter has been generated, so it is unable to dynamically adjust the allocation for different filters at running time.

如何实现呢：

1. build multiple filters，每一个filter都分配比较小的bits-per-key，如下图所示。

Since multiple filter units within a filter group are independent, when querying for a key exists in the SSTable, the key must be nonexistent certainly as long as one filter unit gives a negative return.

image.png

实现的基础：

1. separability 分离性

false positive rate of a filter group is exactly the same as that of a single Bloom filter which uses the same number of bits-per-key allocated to all filter units within the filter group

如何减少io访问的数学证明

在内存固定的情况下，如何减少io

设定一个目标优化函数：

image.png

函数的含义就是表示，因为false positive造成的io的影响。

所以可以在固定内存的情况下去，调整每一个sstable的false positive，调整每个sstable的false positive的方法就是调整load到内存中的filter unit。

implementation

最终的目标就是计算优化函数的值，通过选择加入一个或者多个当前sstable的filter unit，然后去除某些sstable的filter unit来达到目标函数值变小的结果。但是如何快速找到需要被移除出内存的filter unit以及个数是一个非常重要的问题。

通过上小结了解到了目标函数和约束（内存有限，也就是载入到内存的filter unit是有限的）。当一个sstable被访问的时候，增加这个sstable的访问频率（frequency），然后去检查是否可以把其他的filter unit移除，把这个sstable的filter unit加入，从而使得我们的目标优化函数的值减小。这就涉及到了：

1. 需要去除哪一个sstable的filter unit，以及个数

2. 需要load对应的sstable的filter unit的个数

方法：

实现multi-queue：队列i存储的是load到内存i个filter unit的sstable的item。每一个item保存了一个expireTime（表示过期时间，代表了对应的sstable是否为cold），expireTime的计算等于访问这个sstable的currentTime+lifeTime。每一个队列的存储都是按照LRU的方式。

去除方式：从MQ的最大队列m（filter unit最多的）的LRU部分开始查找 expired的sstable，然后把对应的sstable降级到下一层m-1，去除对应一个filter unit。如果没有找到expired的sstable，就接着向下层寻找，如果都没有找到，就不进行调整。

image.png

experiment

首先评估自己方案带来的overhead（写，内存，compaction），解释自己的方案这些overhead都不是太重，可以忽略。

worload description

• 机器配置

• 实验室平台

• 数据量：分析内存，等占用

• workload distribution：uniform，zipf（多种zipf分布），latest分布

performance analysis

• read performance

  • throughput

  • io count

• memory analysis

  • 大量memory的情况下，elasticBF性能下降，但是打的bloom filter在现实中是不允许的。

方法收获

• 如何去计算写的throughput（通过iostat采集，然后进行积分即可）。

  • iostat 统计写入速率，然后计算平均写入速率。

  • 统计总的flush磁盘的大小，总的系统运行时间，平均计算写入磁盘的速度。

  • leveldb，rocksdb计算吞吐的方式：total_kv/total_time，total_time/total_operation,total_size/total_time

• 如何统计io count（目前还是未知，询问论文作者）。

• kv 数据分布的含义。

• 如何解释实验的某种workload或者实际情况是不存在的。

疑问

目标函数：文件的frequency和对应文件的false positive（false positive可以通过载入内存的filter unit进行调整）。

约束条件：内存一定，也就是在内存中存放的filter unit的个数是一定的，在稳定的情况下，载入一个filter unit，就需要移除某个sstable的filter unit。