0x00 前言
在论文ElasticBF: Fine-grained and Elastic Bloom Filter Towards Efficient Read for LSM-tree-based KV Stores中，作者认为在基于LSM的KV-Store中，即使是同一Level中的不同SSTable之间也存在访问倾斜。也即有的SSTable访问频率高，而有的SSTable访问频率较低。
而在论文ElasticBF: Elastic Bloom Filter with Hotness Awareness for Boosting Read Performance in Large Key-Value Stores中，作者进一步认为，在同一SSTable内的不同区域之间也存在访问倾斜。基于数据访问倾斜的特性，在设计Bloom Filter时，可以对hot data分配更大的bits-per-key，来减少FPR，以进一步减少由于FP导致的额外I/O提高KV Store的读性能。
下面将对该论文的内容进行摘要总结。
0x10 Motivation
为了证明不仅SSTable之间存在访问倾斜，而且SSTable内部不同区域之间也存在访问倾斜，作者做了一系列实验进行验证。这些实验关闭了SSTable的Bloom Filter，这样在查找某个key时，只能一层一层的，一个SSTable一个SSTable的进行查找。
图2展示了不同SSTable的访问频率。可得出如下结论：
- lower level的SSTable访问频率更高，这是因为在执行查找时总是自上而下查找的；
- 从曲线的波动情况来看，同一层中不同的SSTable之间的访问频率也有很大的差异，而且这种情况不只发尚在某一层中，而是在每层都普遍存在的，且高层的波动范围更剧烈，这说明越高的level，其数据冷热差异越明显；
第二点结论也说明Moneky论文提出的单纯基于level来确定Bloom Filter的bits-per-key，以利用数据倾斜，是不够合理的。
为了进一步利用顺序写的带宽优势，SSTable的大小有可能会进一步增加，例如RocksDB的SSTable达到了64MB。因此，SSTable内部的访问倾斜可能也很严重。
记录每个KV对的访问频率对内存和CPU来讲都是很大的开销，因此本文在进行实验验证时将64MB的SSTable划分为64个区域，每个区域1MB，仅记录每个区域的访问频率。
图3展示了同一SSTable中所有区域的最大和最小访问频率之差与其平均访问频率之比。可以看到，在很多的SSTable中，此比值是非常大的。这也意味着，即使是在同一SSTable中，不同区域之间也存在很严重的访问倾斜。
因此，可以通过调整Bloom Filter，根据SSTable或者SSTable的区域的热度来调整bits-per-key，在不增加额外内存空间的基础上减少FPR。
0x20 Design
ElasticBF的架构图如图4所示，包括三个部分：
- fine-grained Bloom filter allocation；
- hotness identification and inheritance；
- Bloom filter management in memory；
0x21 Fine-grained Bloom Filter Allocation
可以通过减少Bloom Filter 的FP所造成的额外I/O来提高KV Store的读性能。下面将分析如何为SSTable构建多个Bloom Filter，并根据热度动态调整Bloom Filter以减少FP。
Construction of multiple Bloom filters
ElasticBF为每个SSTable生成多个具有较少bits-per-key的Bloom Filter，每个Bloom Filter采用不同且独立的哈希函数。Elastic将每个Bloom Filter称为filter unit，单个SSTable的所有filter unit构成一个filter group，如图5所示。
一个Filter Group的FPR等于具有相同bits-per-key的单个Bloom Filter（$(0.618^{b/n})^n = 0.618^b$）。
Finer-grained design with chunking
前面提到，即使是在同一SSTable中也存在很严重的访问倾斜，因此可以通过进一步区分同一SSTable中不同key的访问热度来减少FP。但是记录每个key的热度会带来很大的CPU和内存开销。权衡之下，将每个SSTable划分为多个区域，每个区域称为segment，以segment的粒度来计算访问热度。如图7所示，每个segment分配一组filter unit。
需要注意的是，segment的大小设置很重要，过于大了体现不出热度区分，过于小了开销太大。
0x22 Hotness Identification and Inheritance
Hotness identification
segment的热度主要由其访问频率和自上次访问以来的持续时间所决定。
文章提出了一个expiring policy策略来区分segment的cold或hot。该策略表述如下。
维持一个名为currentTime的全局变量，代表整个KV Store的Get请求次数。每个Segment关联一个expiredTime，表示其被「expired」的时间。$expiredTime = lastAccessedTime + lifeTime$，lastAccessedTime表示其上次被访问的时间，lifeTime是个固定值。每当一个segment被访问时，currentTime加1，并更新该segment的lastAccessedTime，进而更新其expiredTime。
当currentTime超过一个segment的expiredTime时，该segment被标记为「expired」。也就是，当一个segment在最近的lifeTime次请求中没有被访问时，其被标记为「expired」，也即认为该segment的cold的。
Hotness inheritance after compaction
Compaction操作会对SSTable执行归并排序生成新的SSTable。因此，如何对新的SSTable中的Segment热度进行初始化是个很重要的问题。
Elastic使用旧的segment的热度来估计新的segmented热度，其计算方法如图8所示。
0x23 Bloom Filter Management in Memory
本小节描述如何管理segment的filter unit。
Bloom filter adjusting rule
- E[Extra IO]表示由于FP所导致的预计额外IO次数，来指导Bloom Filter的调整；
- M表示KV Store的总segment数量；
- $f_i$表示segment $i$的访问频率；
- $r_i$表示segment $i$的FPR；
当一个segment被访问时，更新其访问频率和E[Extra IO]。检查是否可以通过enable某个segment的filter unit并disable其他某个segment的filter unit，在不增加内存占用的情况下减少E[Extra IO]，若可行，则应用该调整。
Realizing dynamic adjustment with Multi-Queue
如图9所示，ElasticBF在内存中维持一个LRU队列来管理每个segment的元数据。将这些队列依次命名为$Q_0,…Q_n$，其中n表示每个segment可以分配的filter unit数量上限，$Q_i$表示该队列中的segment有$i$个enabled filter unit。
查找哪个filter unit应该被disable的步骤如下：
- 首先，从$Q_m$到$Q_1$查找「expired」segment；
- 然后再从每个队列的LRU侧向MRU侧查找；
- 找到「expired」segment后检查是否可以通过disable它的filter unit来减少E[Extra IO]，若可行则释放它的一个filter unit，并将其降到下一层队列中；