布隆过滤器(Bloom Filter)和布谷鸟过滤器(Cuckoo Filter)

布隆过滤器Bloom Filter

原理

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。
其结构很简单，就是一个包含m位的位数组，初始值全部为0，示意如下：
notion image
为了表达这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到的范围中。对任意一个元素x，第i个哈希函数映射的位置就会被置为1（1≤i≤k）
💡
简单点说，对于任意一个元素x，对其使用k个hash函数，得到hash值h1,h2..hk，将布隆过滤器中h1~hk对应的位置置为1
notion image
上图，yyj的hash值为16和26，只需要将数组的16和26位设置为1。
判断一个元素是否存在，同样计算k次hash值，判断对应位置是否全部为1即可

假阳性率False Positive

如果判断一个元素不存在，则一定不存在；如果判断存在，实际上不一定存在。
💡
能提供“一定不存在”，但只能提供“可能存在”
因为，例如字符串s1的hash值是5、16，字符串s2的hash值是16和26，字符串s3的hash值是5和26；当s1和s2存在于布隆过滤器中时，s3即使不存在，也会被误认为存在。
具体的数学计算过程可以参考wiki百科的介绍中的过程，m代表bit数组的大小，k代表hash函数的个数，n代表bloom filter中元素的数量，最终假阳性率约为：
最佳hash函数的个数为
此时，可以得到最低的false positive为

反推内存

根据期望的假阳性率和数据量可以反推需要使用的内存：
在的情况下，粗略计算需要的内存
  • 1亿数据457M
  • 10亿数据5141M
  • 100亿数据57131M
内存大小受数据量影响比较大，受p的值影响较小
n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));

Counting Bloom Filter

bloom filter中数据是不能移除的，参考上方的例子。如果s1和s2都添加到bloom filter中，移除s2将会导致s1不存在。一种改进的方式，是每个位置不再是0-1bit位，而是存储一个数字(即多个bit位代替bloom的一个bit)，每次插入该位置时，counter+1，删除数据时，counter-1。
notion image
一般count设置4位就行，可以计数16次

布谷鸟过滤器Cuckoo Filter

布隆过滤器存在几个缺点：
  1. 空间效率低：初期无论使用多少内存，都要分配整个数组的，因为扩张数组大小，需要重新载入数据。
  1. CPU效率低：一个数据s的k次hash值在内存中分布的比较分散，不能很好的利用缓存
  1. 不支持删除和计数
最近有听说一个新的布谷鸟过滤器，为什么叫布谷鸟呢？来源于「鸠占鹊巢」，布谷鸟孵卵都是占用别人的窝，将别的鸟的蛋扔掉换成自己的，和布谷鸟过滤器很像。

布谷鸟哈希

基本思想是使用2个hash函数来处理碰撞，从而每个key都对应到2个位置。(这个2是可以扩增的）。其提出是期望通过解决hash碰撞，来提高hash table的空间利用率。
插入操作如下：
  1. 对key值hash，生成两个hash key值，hashk1和 hashk2, 如果对应的两个位置上有一个为空，那么直接把key插入即可。
  1. 否则，任选一个位置，把key值插入，把已经在那个位置的key值踢出来。
  1. 被踢出来的key值，需要重新插入，直到没有key被踢出为止。
以上存在一个问题，那就是可能会存在挤兑循环。比如两个不同的元素，hash 之后的两个位置正好相同，这时候它们一人一个位置没有问题。但是这时候来了第三个元素，它 hash 之后的位置也和它们一样，很明显，这时候会出现挤兑的循环。
即使不像上述那样产生循环，也可能产生一个比较大的挤兑链条，通常使用的时候，会设置一个阈值，当一次插入时剔除、插入执行的次数超过阈值，认为数组太拥挤了，需要扩容。
notion image
上图(a)中，假设插入元素x，其hash为2和6，两个位置都被占据了，于是踢出a，x占用6；a的hash是6和4，于是挪动a到4，踢出c；c的hash是1和4，挪动c到1，最终结果如(b)所示。
但是实际上，在不发生hash碰撞的时候，一维数组的空间利用率也只有50%，和其他hash函数差别不大，但是改成二维数组，如图(c)所示，可以提高空间利用率到90%。
在二维数组中，原先一个槽位扩展到4个，数据可以存储在其中任意一个位置，降低挤兑次数。
还有一种优化方案就是增加hash函数的数量。

过滤器

好了，以上介绍了cuckoo hash相关的，利用其理念，实现的filter。
首先，相对于上面的hash table，filter数组存储的不再是原始数据，而是指纹。与上述cuckoo hash的两个hash函数不同，布谷鸟过滤器巧妙的地方就在于设计了一个独特的 hash 函数，使得可以根据 p1 和 元素指纹 直接计算出 p2，而不需要完整的 x 元素。如下
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)  // 异或
这样，也可以根据p2和指纹计算出p1p1 = p2 ^ hash(fp)
因为filter存储的是指纹，我们计算的两个hash值p1和p2必须和指纹相关联。
cuckoo filter设计上，也是采用了二维数组的slot，每个位置存储的是原始数据的指纹，对于数据S，计算指纹f，和hash值p1，然后根据两者计算p2，然后在p1 or p2所在位置，存储指纹
校验数据是否存在的时候，也是计算数据的指纹，然后去p1 or p2处查找。
两个问题：
  1. 为什么存储的是指纹
      2. 因为cuckoo filter实际上和hash table没有太大区别，还是找个位置，存储元素，但是存储元素本身太大了，所以改存储指纹
  1. 为什么p2要和指纹还有p1关联，而不是直接使用hash函数计算？
      2. 因为当发生两个hash结果都存储了元素的时候，需要把旧的踢走，旧的移动到新的位置，需要根据指纹和当前hash值，获得移动到哪里。
 

实践介绍

结合redis海量信息去重存储

之前的一个业务，主要是会采集海量的位置信息，包含设备MAC地址和经纬度、时间信息。关心的是设备的轨迹，所以如果设备长期呆在一个地方不移动，可以把N分钟之内的数据视为一个数据。
整个数据量大概一天在10亿～百亿，使用redis进行去重。几个核心的点：
  1. 使用redis的SETBIT命令
  1. redis一个key最大512M，在N分钟内数据量去重，会超过最大内存
    1. 根据设备MAC，不同MAC映射到不同的redis实例
    2. 对数据分桶，创建多个bloom filter，不同MAC映射到不同的filter内
  1. 采用Pipeline批量操作优化IO

曝光去重

在首页信息流推荐，需要过滤掉用户已经看过的内容。
  1. 每个用户，最多存储5000条已读记录
  1. 不能一次性初始化5000条的内存，太浪费，根据用户实际数据量，按照1000条的层级分配

参考链接

  1. Bloom Filter概念和原理
  1. Counting Bloom Filter 的原理和实现
  1. Bloom Filter Redis Java实现示例
  1. 我的基于Spring-Data-Redis的Bloom Filter
  1. https://en.wikipedia.org/wiki/Bloom_filter
  1. cmu关于cuckoo的论文
  1. 曝光去重设计与实践
  1. 知乎已读服务的前生今世与未来-InfoQ
  1. 布隆过滤器过时了，未来属于布谷鸟过滤器？
  1. Bloom filter calculator
 
本文作者： Song 本文链接： https://www.jiangyuesong.me 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

© Song 2015 - 2023