这篇论文实现了一个PM友好的过滤器，主要是基于布谷过滤器进行改进。这篇博客记录一下文章中作者提出的优化点，公式推导以及实验对比。
1.背景介绍
近似成员查询数据结构(Approximate Membership Query)表示了一组用于近似成员查询的结构。AMQ对于将数据存储在DRAM，SSDS，硬盘上的数据库，网络管理等领域有很大的应用。对于这些存储媒介上的AMQS有很多的优化。新型非易失性内存兼顾了SSDs的持久性以及DRAM的低延迟。现在对于PM上的哈希，树等索引结构有了很大的优化，但是对于AMQS类似的数据结构优化几乎没有。这篇问文章的对比实验有BF(布隆过滤器)，CF(布谷过滤器)，MF( Morton Filter,一个基于DRAM进行优化的过滤器)，RSQF(Rank-and-Select Quotient Filter ,一个基于SSD进行优化的过滤器）。
2.设计方案
作者首先介绍了布谷过滤器，这一点详情见布谷过滤器。作者描述的主要的问题是布谷哈希在高负载因子下布谷哈希的频繁剔除操作会导致性能的下降。
2.1 Spillable bucket
这个方案类似于线性探测。布谷哈希的频繁剔除操作对于PM来说是不友好的。作者给出线性探测的策略提高哈希的负载因子，这里比较独特的是每个桶的第一个槽才会用来被当做用来存储其它桶用来存储的数据。由于每个bucket相对于来说比较小，每次线性探测遍历下一个桶类似于cache hit。具体的插入流程如图所示
对于插入，插入方式是从右边往左边插入，假设现在有四个槽，索引分别为0，1，2，3；那么插入数据的方式就是从3开始往2，1，0插入。
- 当插入数据满的时候，如果b[1][0]存储的是别的桶冲突的数据，那么b[1][1]中存储的值要大于b[1][2]，否则b[1][1]存储的数据要小于b[1][2]。
- 当桶不满的时候，b[1][0]有数据的话代表是别的桶溢出来的数据。
这样来看的话 一共有8个位置+探测的距离的桶存储相同的key。
2.2Lookahead Eviction
//为了减少CF的频繁剔除，这里随机选一个fp进行剔除，尝试剔除MAX_TRY次
之前的布谷过滤器的剔除是桶里的每个数据都去寻找路径。比如对于索引为0，1，2，3的一个桶。对于槽为0的数据，对应的桶数据满了，但是会遍历一遍它关联的桶的所有的数据，为了减少这个开销，作者将标记位保持在DRAM中，记录桶是否满了，从而减少遍历开销，判断需要剔除哪一个数据。与此同时去减少剔除次数的开销.
考虑这样一种情况，当H需要插入的时候，剔除A找空位的路径为 F->2 ,A->1, H->0.剔除E的话那么找到的空位为 E->2 H->0。用一个DRAM存储每个桶是否满的信息。只需要一位就行。1和0。如果空间用的还是多的话，就几个bucket共用一个标志位。只有两个桶都满的情况下，标志位才置为1，否则置为0.
2.3 Bucket Primacy
查询的时候需要对桶进行探测，比如桶b和b+1，每次查询需要遍历两个吗？假设b没有发生过替换，那么查询的次数就相当于多了一次，那可以避免吗，答案是可以的。还是按0，1，2，3来做说明，用2，3的数据的大小顺序来判断是否发生过替换。(这点我感觉不发生替换的次数应该很少吧。。。我猜的)
这里总结一下过滤器的插入操作，主要包括两个·提高负载因子的方法，一个是类似于线性探测，但是它比较独特的是，只有每个桶的第0个索引才能进行这一项操作。第二个就是驱逐操作，驱逐操作其实很类似于布谷哈希。主要就是剔除操作只在第二个桶中的指纹进行驱逐，作者为了加快驱逐操作，为每个桶设置了一个标记为来判断其满还是不满。为了加快查询操作，作者使用位置2，3的槽的key大小来标志其是否发生过迁移操作，从而减少对第二个桶的查询。为了判别哪些数据是线性探测来的，作者使用位置1和位置2的大小排序的数据进行判断。个
一个桶没存储溢出来的数据，也没驱逐数据到h2的时候，那么这个桶存储的key的顺序是 slot0<=slot1<=slot2<=slot3;当slot1>slot2时，意味着b[0]存储的是溢出的数据。当 slot2>slot3时，说明发生过驱逐。但是这有个问题？？这样子有个问题 比如 0，1，2，3存储的数据为1，2，3，4。假设1存储了一个溢出来的数据，那么现在变成了1 3 2 4 再发生 驱逐时，变成 1 3 4 2;4>3了 更改了之前的顺序关系！！！但是猜测一下，可能是变为了1，4，3，2。其中3小于4说明1是溢出来的数据，4小于3说明这个桶是驱逐过的。
3. 失败原子性
对于正常的设计来说，一般一个桶4个slot，存储四个指纹，每个指纹的大小是12bit，那么就导致一个桶大概是48bit，也就是6B。而Optane DIMM的原子写大小是8B。这样子来说的话，一个桶可能需要两次原子写才能刷下去。我们用日志解决了这个数据不一致的问题。简单地将指纹大小设置为8位或16位是不够的。8位指纹和4槽每桶，假阳性率为3%，这是太高的应用程序。例如，在LSM树中，与12位设置相比，这个设置可能导致更多不必要的IO。对于16位指纹，我们需要比12位多33%的内存空间，这也在很大程度上限制了它的适用性
3.1 日志介绍
（type C需要两个log的原因是重排序的时候可能将FP3 覆盖掉）
这里只使用了两个日志用来进行恢复。考虑bucket的标号和恢复有关。其中index%4为0或者3的桶称之为type A，其中index%4为1的桶称之为type B，其中idnex%4为2的桶称之为typeC。这个画个图就很容易理解，其中typeA的桶刷新 一个8B原子写就能搞定，type B和type C需要刷新两个桶。
bucket index 表明了插入的桶的编号，FP(insert)表示插入的指纹 ，FP(evict)表示插入时导致驱逐的指纹，unaligned FP表示 log-splitted bit表示是否需要两个日志来进行恢复，timestamp表示时间戳，用来标志日志写入的先后顺序。
3.2 恢复过程
当发生崩溃的时候，可以从日志获取崩溃的桶的信息，需要插入的数据，发生踢除的时候还存储着踢除的指纹的信息。假设擦除的指纹称作$FP_i$,剔除的指纹称作$FP_e$.发生崩溃可能存在下面n四种情况。当$FP_e$不存在，$FP_i$存在桶里的时候，可能是插入成功，也可能是部分写，这个就需要我们进行判断。其它三种情况要么没更新，要么是部分写，这个时候直接根据信息进行恢复就好了。下面重点考虑情形d。
A:下面考虑TYPE B的桶 d情形下崩溃时的情况。插入的时候先更新左边的16位（黑色位置），再更新后面48位。从日志可以看出，插入的值为$FP_i$, 需要将EA1剔除出去，对齐的位为E。这里插入的$FP_i$是FA1。
- 先考虑不剔除的场景（从左到右slot0，1，2，3），假设不需要剔除的话，说明有空余位置，那也不可能属于到情形四。
- 现在考虑剔除情形，如这个日志记录所看到的，在步骤3崩溃的话，检查spill status bit是不是对的，发现是错的，说明有不一致的地方，因此需要进行恢复。恢复的时候，只需要将E替换F，然后再重新进行插入操作即可。
PS:这里也可能是对的，假设这里的spill status是对的话，那说明插入成功。注意这里只是重排序是崩溃了。
B： 接下里考虑TYPE C的桶的情形下崩溃的情况，插入时先更新右边的16位，在更新后面的48位。这里为啥需要两个日志，再强调一遍，因为重排序可能把slot3中的指纹给覆盖掉了，这里举个简单的例子，EB1 EB2 EB3 FB4 插EB0的时候剔除掉EB3 那么就在步骤2 崩溃是 变成了 EB1 EB2 EB4 EB0，而日志为EB0 EB3 3 只能恢复成 EB1 EB2 EB3 EB0，FB4无法恢复，因此需要日志记录一下FB4，第二个日志记录$FP_e$变成了剔除的指纹，$FP_i$记录了slot3的指纹，恢复阶段先看时间戳靠前的即可
