Redis-布谷鸟过滤器-使用/原理/实例

简介

说明

本文介绍Redis的布谷鸟过滤器的原理，优缺点，使用场景，实例。

布谷鸟过滤器起源

布谷鸟算法的启发来自于布谷鸟，因为布谷鸟这种鸟很有意思，生出来的孩子自己不养，直接把孩子扔到其他鸟的鸟巢中去了。但有时候，这些布谷鸟蛋会被被寄宿的鸟妈妈发现，然后就被抛弃；有时候，这些宿主会直接放弃整个鸟巢寻找新住处。然而道高一尺魔高一丈，有些品种的布谷鸟生下来的布谷鸟蛋的颜色和被寄宿的鸟的鸟蛋颜色很像，并且布谷鸟的破壳时间往往比宿主的鸟蛋早，小布谷鸟破壳后会将一些鸟蛋扔出鸟巢以获得更多的食物，小布谷鸟还能模拟宿主鸟孩子的叫声来骗取更多的食物！简单来说，就是如何更高效地去骗吃骗喝。

布谷鸟哈希

原理

最简单的布谷鸟哈希结构是一维数组结构，会有两个 hash 算法将新来的元素映射到数组的两个位置。如果两个位置中有一个位置为空，那么就可以将元素直接放进去。但是如果这两个位置都满了，它就不得不「鸠占鹊巢」，随机踢走一个，然后自己霸占了这个位置。

1. 保存元素 （位置都没有被占）

新来的元素a经过hash会落在（A2，B1）的位置，由于A2还没有元素，a直接落入A2

2. 保存元素 （其中一个位置被占）

新插入元素b的hash会落在(A2,B3),由于A2已经被a占了，所以b会落在b3

3. 保存元素 （两个位置都被占）

新来元素c的hash为(A2,B3), 由于两个位置都已经被占，它会随机将一个元素挤走，这里挤走了a 

4. 被挤掉的元素重新找位置

a会重新进行hash，找到还未被占的B1位置

从上面可以看出，布谷鸟哈希算法会帮这些受害者（被挤走的蛋）寻找其它的窝。因为每一个元素都可以放在两个位置，只要任意一个有空位置，就可以塞进去。所以这个伤心的被挤走的蛋会看看自己的另一个位置有没有空，如果空了，自己挪过去也就皆大欢喜了。但是如果这个位置也被别人占了呢？好，那么它也会再来一次「鸠占鹊巢」，把别人赶走。然后这个新的受害者还会重复这个过程直到所有的蛋都找到了自己的巢为止。

问题

如果数组太拥挤了，连续踢来踢去几百次还没有停下来，这时候会严重影响插入效率。这时候布谷鸟哈希会设置一个阈值，当连续占巢行为超出了某个阈值，就认为这个数组已经几乎满了。这时候就需要对它进行扩容，重新放置所有元素。

还会有另一个问题，那就是可能会存在挤兑循环。比如两个不同的元素，hash 之后的两个位置正好相同，这时候它们一人一个位置没有问题。但是这时候来了第三个元素，它 hash 之后的位置也和它们一样，很明显，这时候会出现挤兑的循环。不过让三个不同的元素经过两次 hash 后位置还一样，这样的概率并不是很高，除非你的 hash 算法太挫了。

出现挤兑循环时，布谷鸟过滤器认为数组太拥挤了，会进行扩容，重新计算每个指纹的位置。

布谷鸟过滤器

原理简介

布谷鸟过滤器由一个数组组成，数组中每个元素大小为4个字节，可以存储4个指纹，每个指纹占一个字节(2^8 = 256种)。这样有以下两个好处：

1. 避免出现hash后的位置一致而导致的循环挤兑的情况。
   1. 这样即使两个元素被 hash 在了同一个位置，也不必立即「鸠占鹊巢」，因为这里有4个座位，你可以随意坐一个。除非这多个座位都被占了，才需要进行挤兑。这会显著降低挤兑次数。
2. 同一个位置上的多个座位在内存空间上是连续的，可以有效利用 CPU 高速缓存。

插入

初始化一个给定容量的过滤器Filter，这个容量数为2的n次方，如果不为2的n次方，内部会通将其转化为2的n次方。

先进行一次hash，得出应当插入位置和应当插入的值。如果这个这个位置（bucket内的4个位置均被占用）插入失败，会进行第二次hash，查看第二个位置能否插入。若第二个位置插入失败，则会随机在两个位置挑选一个将其中的一个值标记为旧值，用新值覆盖旧值，旧值会在重复上面的步骤进行插入。

会对插入的值进行校验，只有当未插入过该值时才会插入成功，若过滤器中已经存在该值，会插入失败返回false。

扩容

如果数组过小，会发生循环挤兑的情况，如果超过最大挤兑次数，进行扩容，重新计算每个指纹的位置。

查找

用两个hash函数计算，将计算结果与两个元素中的8个位置的指纹进行对比，如果对比成功则表示数据存在。先进行一次hash查询数据，若没有该值会进行第二次hash进行查询，若还是没有会返回false。

删除

通过两次hash找到索引位置，若有该数据，将该位置数据删除。因为每个对象的指纹会存储到一个位置中，所以可以通过删除这个指纹来删除数据。

删除功能无法使用的情况：如果相同对象存储超过8个，就无法使用删除功能；如果俩数据的哈希值和指纹相同时，会出现误删除情况。

删除全部

布谷鸟过滤器可以删除全部元素（重置数组为0）。

更新

删除后再添加新指纹。

原理详述

布谷鸟过滤器和布谷鸟哈希结构一样，它也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个bit，类似于布隆过滤器），过滤器牺牲了数据的精确性换取了空间效率。

布谷鸟过滤器还是只会选用两个 hash 函数，但是每个位置可以放置多个座位。这两个 hash 函数选择的比较特殊，因为过滤器中只能存储指纹信息。当这个位置上的指纹被挤兑之后，它需要计算出另一个对偶位置，计算这个对偶位置是需要元素本身的。

哈希位置计算公式：

fp = fingerprint(x)
p1 = hash1(x) % l
p2 = hash2(x) % l

 知道了 p1 和 x 的指纹，是没办法直接计算出 p2 的。

布谷鸟过滤器

一个独特的 hash 函数，可以根据 p1 和 元素指纹 直接计算出 p2，而不需要完整的 x 元素。

fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)  // 异或

从上面的公式中可以看出，知道 fp 和 p1，可以算出 p2。同样如果我们知道 p2 和 fp，也可以直接算出 p1 —— 对偶性。 

p1 = p2 ^ hash(fp)

所以不需要知道当前的位置是 p1 还是 p2，只需要将当前的位置和 hash(fp) 进行异或计算就可以得到对偶位置。只需要确保 hash(fp) != 0 就可以确保 p1 != p2，就不会出现自己踢自己导致死循环的问题。

为什么这里的 hash 函数不需要对数组的长度取模呢？实际上是需要的，但是布谷鸟过滤器强制数组的长度必须是 2 的指数，所以对数组的长度取模等价于取 hash 值的最后 n 位。在进行异或运算时，忽略掉低 n 位 之外的其它位就行。将计算出来的位置 p 保留低 n 位就是最终的对偶位置。

优缺点

优点

1. 支持新增和删除元素。
   1. 布隆过滤器不支持删除元素
2. 更节省空间。
   1. 布谷鸟哈希表更加紧凑
   2. 布谷鸟过滤器在错误率小于3%的时候空间性能是优于布隆过滤器
   3. 布谷鸟过滤器比布隆过滤器空间节省40%多
3. 查询效率很高
   1. 布谷鸟过滤器只需一次哈希
   2. 布隆过滤器要采用多种哈希函数进行多次哈希

缺点

1. 插入性能较差
   1. 布谷鸟过滤器在计算哈希后可能当前位置上已经存储了指纹，这时就要将已存储的项踢到候选桶，随着桶越来越满，产生冲突的可能性越来越大，插入耗时越来越高
   2. 布隆过滤器插入时计算好哈希直接写入位即可
2. 插入重复元素存在上限
   1. 布谷鸟过滤器对已存在的值会做踢出操作，因此重复元素的插入存在上限。
   2. 布隆过滤器在插入重复元素时并没有影响，只是对已存在的位再置一遍。
3. 空间大小
   1. 布谷鸟过滤器必须是2的指数。
   2. 布隆过滤器不需要2的指数。
4. 删除问题
   1. 有上述重复插入的限制，删除时也会出现相关的问题：
      1. 删除仅在相同哈希值被插入一次时是完美的
      2. 如果元素没有插入便进行删除，可能会出现误删除，这和假阳性率的原因相同
      3. 如果元素插入了多次，那么每次删除仅会删除一个值，你需要知道元素插入了多少次才能删除干净，或者循环运行删除直到删除失败为止

代码实现

目前没有很完善的java实现，可以参考如下项目：

Redis布谷鸟过滤器：https://github.com/kristoff-it/redis-cuckoofilter

Redis通过插件支持sql及布谷鸟过滤器：https://github.com/RedBeardLab/rediSQL ​