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

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

Bloom 简介

关于布隆过滤器有众多文章做过介绍，这里不作详解，仅贴出简介：Bloom 是由 Bloom 在 1970 年提出的二进制向量数据结构，它具有很好的空间和时间效率，被用来检测一个元素是不是集合中的一个成员。如果检测结果为是，该元素不一定在集合中；但如果检测结果为否，该元素一定不在集合中。因此Bloom 具有100%的召回率。这样每个检测请求返回有“在集合内（可能错误）”和“不在集合内（绝对不在集合内）”两种情况，可见 Bloom 是牺牲了正确率和时间以节省空间。

Bloom 优点就是它的插入和查询时间都是常数，另外它查询元素却不保存元素本身，具有良好的安全性。它的缺点也是显而易见的，当插入的元素越多，错判“在集合内”的概率就越大了，另外 Bloom 也不能删除一个元素，因为多个元素哈希的结果可能在 Bloom 结构中占用的是同一个位，如果删除了一个比特位，可能会影响多个元素的检测。

Bloom

标准Bloom 对于需要精确检测结果的场景将不再适用，而带计数器的Bloom 的出现解决了这个问题。 Bloom 实际只是在标准Bloom 的每一个位上都额外对应得增加了一个计数器，在插入元素时给对应的 k （k 为哈希函数个数）个 的值分别加 1，删除元素时给对应的 k 个 的值分别减 1。

Bloom 通过多占用几倍的存储空间的代价，给Bloom 增加了删除操作。这其中最关键的问题是 Bloom 需要增加多少存储量？在论文中给出了相关计算，假设数组的长度为m（对应bloom 的位数组），Ci表示数组中第i个的大小，即哈希函数映射到第i位的次数，则每个最少位数N为：

SBF（ Bloom ）作为 Bloom 的一种实现，将所有排成一个位串，之间完全不留空隙计数式布隆过滤器(counting bloom filter)Redis实现分析，然后通过建立索引结构来访问，并达到了只使用O(N) + O(m)位的存储目标，O(m)的构建时间。虽然SBF解决了动态的存储问题，但其引入了复杂的索引结构，这让每个的访问变得复杂而耗时。

Count

为改进SBF的缺点，人们又发明了DCF（ Count ），其使用两个数组来存储所有的，它们的长度都为m（即bloom 的位数组长度）。第一个数组是一个基本的CBF（即下图中的CBFV， bloom ），的长度固定，为x = log(M/n)，其中M是集合中所有元素的个数计数式布隆过滤器(counting bloom filter)Redis实现分析，n为集合中不同元素的个数。第二个数组用来处理的溢出（即下图中的OFV， ），数组每一项的长度并不固定，根据的溢出情况动态调整。

在查询一个时bloom filter java，DCF要求两次内存访问。假设想查询位置为j的的值bloom filter java，我们先读出CBFV和OFV的值，分别为Cj和OFj，那么的值就可以表示为Vj = (2x×OFj ＋ Cj)。

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

基于Redis的实现

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

对于DCF的Redis实现，最简单的就是采用模式，主要是因为其能方便支持Lua 并使用事务，另外还需要在客户端实现分片算法。但其有个缺点就是需要在开始时规定Redis实例数量，如要横向扩展Redis实例则需要将数据进行重分片，代价很大。

客户端函数包含 query，add， 三种操作，且都先通过mod运算进行分片，对应到具体Redis实例后，执行对应Lua脚本。基本流程图如下：

参考资料 bloom Cache: A Wide-Area

Web Cache Bloom 概念和原理 Count Bloom for Large-Scale Data