布隆过滤器之 Counting Bloom Filter

忘是亡心i 2024-03-24 14:44 29阅读 0赞

## 简介 ##

布隆过滤器（Bloom Filter）是一种空间效率高、误判率低的数据结构，通常用于判断一个元素是否在一个集合中。其原理是利用多个哈希函数将输入元素映射到一个位数组中，并将对应的位标记为1。判断一个元素是否在集合中时，只需要查询其对应的位是否都为1即可。

布隆过滤器的主要数据结构是一个由 m 个二进制位组成的位数组，初始时所有位都被置为0。同时，布隆过滤器还需要 k 个哈希函数，这些哈希函数将输入元素映射到位数组中的 k 个位置上，每个位置都标记为1。具体的哈希函数可以是任意一种哈希算法，例如 MD5、SHA1 等。

将一个元素插入到布隆过滤器时，需要将该元素通过 k 个哈希函数映射到位数组中的 k 个位置上，并将这些位置的值都置为1。查询一个元素是否在布隆过滤器中时，只需要将该元素通过 k 个哈希函数映射到位数组中的 k 个位置上，检查这些位置的值是否都为1，若都为1，则该元素可能存在于集合中，否则该元素肯定不存在于集合中。

由于布隆过滤器是基于哈希函数实现的，所以其查询时间和空间复杂度都非常低，但同时也存在误判率的问题。当布隆过滤器的位数组容量不够大时，会产生误判，即有些不存在于集合中的元素被错误地判断为存在于集合中。因此，布隆过滤器通常用于辅助其他数据结构进行快速查询，而不是单独使用。

## 如何计算具体的映射数组位置 ##

计算布隆过滤器中元素的映射位置需要使用哈希函数。布隆过滤器通常使用多个哈希函数，每个哈希函数将元素映射到位数组的不同位置。哈希函数的计算方法可以有多种，但是需要保证相同的输入元素得到的输出结果是固定的，且输出结果的分布尽可能均匀。

以最简单的一种哈希函数为例，假设需要将一个元素 e 映射到一个 m 个二进制位组成的位数组上。可以使用取模运算将元素 e 映射到位数组的某个位置上：

hash(e) = e % m

这种哈希函数的计算方法非常简单，只需要将元素 e 的哈希值（通常是一个整数）进行取模运算，然后将结果作为该元素在位数组中的映射位置。但是，这种哈希函数的分布不一定均匀，可能会导致某些位被频繁地标记为1，而其他位则很少被标记。

更好的哈希函数设计可以通过使用多个哈希函数，将元素映射到多个位置上，从而减小误判率。例如，可以使用 k 个不同的哈希函数，将元素映射到位数组的 k 个位置上，具体计算方法可以采用以下公式：

hash_i(e) = (hash_func_i(e) + i) % m

其中，hash\_func\_i(e) 表示第 i 个哈希函数对元素 e 进行哈希计算得到的值，i 是一个常量，表示第 i 个哈希函数得到的映射位置偏移量。通过这种方法，可以将元素映射到位数组的多个位置上，从而减小误判率。

布隆过滤器中哈希函数的计算方法可以根据实际情况进行优化，例如采用更加复杂的哈希算法，或者引入其他技术来减小误判率，例如 Counting Bloom Filter、Cuckoo Filter 等。

## Bloom Filter 开源工具包 ##

Google Guava：Guava 是一个 Google 开源的 Java 核心库，其中包括了布隆过滤器的实现。Guava 提供了 BloomFilter 类，可以使用 BloomFilter.create() 方法创建一个 BloomFilter 实例，然后调用 add() 方法添加元素，contains() 方法判断元素是否存在。

Apache Commons Collections：Commons Collections 是一个 Apache 开源的 Java 工具包，其中包括了布隆过滤器的实现。Commons Collections 提供了 BloomFilter 类，可以使用 BloomFilter.create() 方法创建一个 BloomFilter 实例，然后调用 add() 方法添加元素，contains() 方法判断元素是否存在。

Redisson：Redisson 是一个基于 Redis 的分布式 Java 工具包，其中包括了布隆过滤器的实现。Redisson 提供了 RBloomFilter 类，可以使用 RedissonClient.getBloomFilter() 方法获取一个 RBloomFilter 实例，然后调用 add() 方法添加元素，contains() 方法判断元素是否存在。

## CountingBloomFilter 原理 ##

Bloom Filter不支持删除功能。  
Counting Bloom Filter的出现解决了这个问题，它将标准Bloom Filter位数组的每一位扩展为一个小的计数器(Counter)，在插入元素时给对应的k(k为哈希函数个数)个Counter的值分别加1，删除元素时给对应的k个Counter的值分别减1，Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。  
**CountingBloomFilter添加删除**  
假设counter值设为4，Bloom Filter位数组对应的每个位都是counter位的数组，Counting Bloom Filter对应的添加删除过程如下图所示。  
![在这里插入图片描述][022bcfd1c81a43a1a9461030be958285.png]

**Counter**取值  
对于大多数情况来说，4位就足够了。具体推导请见 https://blog.csdn.net/zhaoyunxiang721/article/details/41123007

## Counting Bloom Filter 如何实现 ##

Counting Bloom Filter（CBF）是一种基于 Bloom Filter 的改进算法，它能够统计每个元素的重复次数，并且允许删除元素。CBF 在网络协议、数据压缩、分布式存储系统等领域得到了广泛的应用。

CBF 的主要特点是在位数组中不再只存储 0 或 1，而是使用计数器来存储每个元素出现的次数。具体来说，CBF 采用一个 m 个元素的位数组 C 和 k 个哈希函数，每个哈希函数可以将元素映射到位数组的一个位置上。对于一个元素 e，对应的 CBF 计算方法如下：

将 C 中所有经过哈希函数映射到的位置的计数器加 1。

如果计数器的值超过了一个阈值（通常为 3），则将这个元素标记为存在于 CBF 中。

查询一个元素是否在 CBF 中时，需要查询所有哈希函数映射到的位置上的计数器的值是否都大于 0，如果都大于 0，则认为这个元素可能存在于 CBF 中。

删除一个元素时，需要将 CBF 中所有哈希函数映射到的位置上的计数器减 1。如果某个位置上的计数器减为了 0，则认为这个元素已经不存在于 CBF 中。

CBF 的实现过程比较简单，只需要将 Bloom Filter 中的位数组改成计数器数组，增加一个计数器加减的操作即可。CBF 中的计数器需要支持加法和减法操作，因此通常采用计数器数组代替位数组，计数器数组中的每个元素都是一个计数器，可以进行加法和减法操作。此外，CBF 还需要定义一个阈值，用于判断某个元素是否存在于 CBF 中。阈值的选择需要根据具体的应用场景进行调整，通常选择 3 或 4。

由于使用了计数器数组，CBF 的空间复杂度要高于 Bloom Filter，因为需要存储每个元素的计数器。此外，CBF 的误判率也会随着计数器阈值的增大而增大。因此，CBF 的适用场景需要根据具体的需求进行选择。

## 基于本地内存的CountingBloomFilter实现 ##

网上已有代码实现基于本地内存的CountingBloomFilter方式基本一致，分两种形式：

*  当Counter为：8、16、32、64时，采用数组方式进行存储，利用储存结构特性，如果是8，则取byte数组，正好每一位对应的8bit；如果是16，则取short数组；如果是32，则取int数组，如果是64，则取long数组。
 *  当Counter不为这几个时，建立一个大小为m（总大小）\*counter的BitSet。

### Add操作： ###

和BloomFilter基本一致，在每次计算出的hash位上加1。

### Check操作： ###

和BloomFilter基本一致，检查是不是所有hash位的值大于0。

### Delete操作 ###

在每个hash位上减1。

## 基于Redis的CountingBloomFilter实现过程 ##

基于Redis的CountingBloomFilter实现和基于内存的逻辑一致，只是存储地址由本地内存改为了Redis。  
在已有开源代码基础上需要自己实现的部分，主要就CountingBloomFilter储存的初始化，以及add、delete、check的逻辑代码。

### 初始化 ###

因为CountingBloomFilter比BloomFilter膨胀了Counter倍，所以对应可能使用的Redis的bitmap数量也会膨胀Counter倍。因此，初始化CountingBloomFilter时，需要根据总大小m来进行Redis的bitmap分片。总大小m为整型，所以最大值为2^32-1。  
假设：总大小m为2^32-1，Counter为4。  
这时候分片结果:  
共有4个bitMap,每个bitMap所负责的位

*  Bitmap1:\[0,2^30-1\]
 *  Bitmap2:\[230,231-1\]
 *  Bitmap3:\[231,231+2^30-1\]
 *  Bitmap4:\[231+230,2^32-1\]

### 逻辑运算 ###

添加删除为了保证原子性操作，通过Redis执行lua脚本方式保证其原子性（Redis在执行脚本时，不会执行其他脚本或Redis命令，所以lua脚本不宜过长，可能阻塞线程导致整个Redis服务不可用。）  
**使用Redis位运算的方法：BITFIELD**

> BITFIELD key \[GET type offset\] \[SET type offset value\] \[INCRBY type offset increment\] \[OVERFLOW WRAP|SAT|FAIL\] 自3.2.0起可用。  
> 该命令将 Redis字符串视为一个位数组进行操作。  
> 所支持的子命令如下：  
> GET- 返回指定的位域。  
> SET- 设置指定的位域并返回其旧值。  
> INCRBY-递增或递减（如果给定负递增）指定的位域并返回新值。
> 
> type：字段决定操作的类型，通过 i 为有符号整数和 u 无符号整数加上整数类型的位数来组成。  
> offset：字段为起始的位  
> value：字段为要设置的值(十进制) increment：字段为递增或递减的值  
> OVERFLOW：为溢出控制，控制溢出处理策略。 WRAP：默认值。环绕，例如，如果i8整数设置为127，则将其递增1 -128。  
> SAT：饱和算术，向上溢出置为最大整数，想下溢出置为最小。例如，i8从数值120开始递增一个以10 为增量的整数结果为数值127。  
> FAIL：溢出直接失败，返回值 NULL，以向调用者发送信号。

有了BITFIELD这个方法处理就很简单了。

*  添加删除的lua脚本：

--lua 下标从 1 开始
     --rediskey
    local key = KEYS[1] 
     --起始操作位
    local position = tonumber(ARGV[1]) 
    --创建bitfield的
    local countingBits = 'u' .. ARGV[2] 
    --自增的值，如果为add，则为1，del时， 则为-1
    local bit = tonumber(ARGV[3])
    -- 自增或自减，采取fail模式，如果失败则返回null
    local res = redis.call('bitfield', key , 'overflow', 'fail','incrby', countingBits, position ,bit)
    return res

*  查询方法伪代码：

//check方法
      public boolean check(String redisKey, int position, int counter){
                
        //判断当前Counter位的十进制值是否大于0
        return redisClient.bitfield(redisKey,"get", "u" + counter ,position )>0;
    }

至此，CountingBloomFilter主要逻辑完成。至于如何实现累加，只需要增加一个配置开关。  
如果需要累加，添加时，不判断是否存在，直接添加；如果不需要累加，添加时，先判断是否存在

## 使用场景总结 ##

**Bloom Filter**  
结论：适用于大数据量下的集合过滤。  
优点：空间效率和查询时间都远远超过一般的算法。  
缺点：有一定的误识别率和无法删除。  
使用场景举例：

1.  网页爬虫对URL的去重，避免爬取相同的URL地址；
2.  反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）；
3.  缓存击穿，将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

**Counting Bloom Filter**  
结论：Bloom Filter的变种，支持了计数及删除。  
优点：保证了空间和时间的同时，支持了计数及删除。  
缺点：有一定的误识别率和空间上使用比Bloom Filter多。  
使用场景举例：

1.  需要支持删除的名单缓存
2.  .caffine cache的LRU缓存实现了类似的功能

[022bcfd1c81a43a1a9461030be958285.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/c0efa90d2e93403d84e13a12146dac1a.png