计数式布隆过滤器(counting bloom filter)Redis实现分析

时间:2024-04-05 11:55:29

Bloom filter简介

关于布隆过滤器有众多文章做过介绍,这里不作详解,仅贴出简介:Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。如果检测结果为是,该元素不一定在集合中;但如果检测结果为否,该元素一定不在集合中。因此Bloom filter具有100%的召回率。这样每个检测请求返回有“在集合内(可能错误)”和“不在集合内(绝对不在集合内)”两种情况,可见 Bloom filter 是牺牲了正确率和时间以节省空间。
计数式布隆过滤器(counting bloom filter)Redis实现分析
Bloom filter 优点就是它的插入和查询时间都是常数,另外它查询元素却不保存元素本身,具有良好的安全性。它的缺点也是显而易见的,当插入的元素越多,错判“在集合内”的概率就越大了,另外 Bloom filter 也不能删除一个元素,因为多个元素哈希的结果可能在 Bloom filter 结构中占用的是同一个位,如果删除了一个比特位,可能会影响多个元素的检测。

Counting Bloom filter

标准Bloom filter对于需要精确检测结果的场景将不再适用,而带计数器的Bloom filter的出现解决了这个问题。Counting Bloom filter实际只是在标准Bloom filter的每一个位上都额外对应得增加了一个计数器,在插入元素时给对应的 k (k 为哈希函数个数)个 Counter 的值分别加 1,删除元素时给对应的 k 个 Counter 的值分别减 1。
计数式布隆过滤器(counting bloom filter)Redis实现分析
Counting Bloom Filter通过多占用几倍的存储空间的代价,给Bloom Filter增加了删除操作。这其中最关键的问题是Counting Bloom filter需要增加多少存储量?在论文中给出了相关计算,假设counter数组的长度为m(对应bloom filter的位数组),Ci表示counter数组中第i个counter的大小,即哈希函数映射到第i位的次数,则每个counter最少位数N为:
计数式布隆过滤器(counting bloom filter)Redis实现分析
SBF(Spectral Bloom Filter)作为Counting Bloom Filter的一种实现,将所有counter排成一个位串,counter之间完全不留空隙,然后通过建立索引结构来访问counter,并达到了只使用O(N) + O(m)位的存储目标,O(m)的构建时间。虽然SBF解决了动态counter的存储问题,但其引入了复杂的索引结构,这让每个counter的访问变得复杂而耗时。

Dynamic Count Filter

为改进SBF的缺点,人们又发明了DCF(Dynamic Count Filter),其使用两个数组来存储所有的counter,它们的长度都为m(即bloom filter的位数组长度)。第一个数组是一个基本的CBF(即下图中的CBFV,counting bloom filter vector),counter的长度固定,为x = log(M/n),其中M是集合中所有元素的个数,n为集合中不同元素的个数。第二个数组用来处理counter的溢出(即下图中的OFV,overflow vector),数组每一项的长度并不固定,根据counter的溢出情况动态调整。
计数式布隆过滤器(counting bloom filter)Redis实现分析
在查询一个counter时,DCF要求两次内存访问。假设想查询位置为j的counter的值,我们先读出CBFV和OFV的值,分别为Cj和OFj,那么counter的值就可以表示为Vj = (2x×OFj + Cj)。

在集合增加元素时,如果OFV的最大值从2x – 1增加到2x,OFV就需要给每一项增加1位,否则就会溢出。对应的,当OFV的最大值从2x减少到2x – 1时,OFV就需要减少1位。每次OFV大小改变的时候都需要重新创建一个OFV数组,然后把旧OFV数组的值拷贝到新建的OFV数组中,最后把旧OFV数组的空间释放掉。对于减少的情况,可以采用一些策略延迟OFV的重建,以避免一些临时性的减少导致OFV反复重建。

基于Redis的实现

鉴于单机有内存限制,我们不禁就会想到使用外部存储来实现,其中Redis是较好的选择。Redis有如下优点:1. 性能优异,2.接口功能丰富,3.可靠稳定。

对于DCF的Redis实现,最简单的就是采用standalone模式,主要是因为其能方便支持Lua script并使用事务,另外还需要在客户端实现Sharding分片算法。但其有个缺点就是需要在开始时规定Redis实例数量,如要横向扩展Redis实例则需要将数据进行重分片,代价很大。
客户端函数包含 query,add,delete 三种操作,且都先通过mod运算进行分片,对应到具体Redis实例后,执行对应Lua脚本。基本流程图如下:
计数式布隆过滤器(counting bloom filter)Redis实现分析

参考资料

  1. bloom filter
  2. Summary Cache: A Scalable Wide-Area
    Web Cache Sharing Protocol
  3. Counting Bloom Filter
  4. Bloom Filter概念和原理
  5. Dynamic Count Filter
  6. Accurate Counting Bloom Filters for Large-Scale Data Processing