前言

博客：http://blog.healerjean.com

一、布隆过滤器

1、引入

上一节我们学会了使用 HyperLogLog 数据结构来进行估数，它非常有价值，可以解决很多精确度不高的统计需求。

但是如果我们想知道某一个值是不是已经在 HyperLogLog 结构里面了，它就无能为力了，它只提供了 pfadd 和 pfcount 方法，没有提供 pfcontains 这种方法。

问题1：我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的?

答案：你会想到服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。

问题2：问题是当用户量很大，每个用户看过的新闻又很多的情况下，这种方式，推荐系统的去重工作在性能上跟的上么?

答案：实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行 exists 查询，当系统并发量很高时，数据库是很难扛住压力的。

问题3：不使用数据库，那使用什么呢？

答案：你可能又想到了缓存，但是如此多的历史记录全部缓存起来，那得浪费多大存储空间啊?而且这个存储空间是随着时间线性增长，你撑得住一个月，你能撑得住几年么? 但是不缓存的话，性能又跟不上，这该怎么办 ?

问题4：缓存都扛不住，那还能用啥呢？

这时，布隆过滤器 (Bloom Filter) 闪亮登场了，它就是专门用来解决这种去重问题的。

问题5：为什么用布隆过滤器呢？

答案：它在起到去重的同时，在空间上还能节省 90% 以上，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。

问题6：布隆过滤器有什么缺点呢？

答案：只是稍有那么点不精确，也就是有一定的误判概率

2、布隆过滤器是什么？

布隆过滤器可以理解为一个不怎么精确的 set 结构，当你使用它的 contains 方法判断某个对象是否存在时，它可能会误判。

1、但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率

2、当布隆过滤器说某个值存在时，这个值可能不存在，当它说不存在时，那就肯定不存在。

套在上面的使用场景中，布隆过滤器能准确过滤掉那些已经看过的内容，那些没有看过的新内容，它也会过滤掉极小一部分 (误判)，但是绝大多数新内容它都能准确识别。这样就可以完全保证推荐给用户的内容都是无重复的。

3、`Redis` 中的布隆过滤器

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。(我这里没有进行安装，所以就看着文档过一下吧，以后有需要再回来看)

命令	说明
`bf.add`	添加元素
`bf.madd`	批量添加元素
`bf.exists`	查询元素是否存在
`bf.mexists`	批量查询元素是否存在

1）默认的布隆过滤器

在我们第一次 add 的时候自动创建默认参数的布隆过滤器

默认的 error_rate 是 0.01，默认的 initial_size 是 100。

127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1

127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2 
(integer) 1
127.0.0.1:6379> bf.exists codehole user3 
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0


127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1

127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7 
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

2）自定义的布隆过滤器

Redis 其实还提供了自定义参数的布隆过滤器，需要我们在 add 之前使用 bf.reserve 指令显式创建。如果对应的 key 已经存在，bf.reserve 会报错。bf.reserve 有三个参数，分别

⬤ key

⬤ error_rate ：错误率越低，需要的空间越大。

⬤ initial_size 参数表示预计放入的元素数量，当实际数量超出这个数值时，误判率会上升，所以需要提前设置一个较大的数值避免超出导致误判率升高。

3）注意事项

⬤ 布隆过滤器的 initial_size 估计的过大，会浪费存储空间，估计的过小，就会影响准确率，用户在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出估计值很多。

⬤ 布隆过滤器的 error_rate 越小，需要的存储空间就越大，对于不需要过于精确的场合， error_rate 设置稍大一点也无伤大雅。（比如在新闻去重上而言，误判率高一点只会让小部分文章不能让合适的人看到，文章的整体阅读量不会因为这点误判率就带来巨大的改变）

4、布隆过滤器的原理

每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。

1）`add`：添加元素

向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。

2）`exists`：校验元素是否存在

向布隆过滤器询问 key 是否存在时，跟 add 一样，也会把 hash 的几个位置都算出来，看看位数组中这几个位置是否都位 1

1、只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在。

2、如果都是 1，这并不能说明这个 key 就一定存在，只是极有可能存在，因为这些位被置为 1 可能是因为其它的 key 存在所致。如果这个位数组比较稀疏，这个概率就会很大，如果这个位数组比较拥挤，这个概率就会降低。具体的概率计算公式比较复杂，感兴趣可以阅读扩展阅读，非常烧脑，不建议读者细看。

3）实际元素超出初始化大小怎么办？

使用时不要让实际元素远大于初始化大小，由于 error_rate 不会因为数量超出就急剧增加（看下面的图表），这就给我们重建过滤器提供了较为宽松的时间，所以当实际元素开始超出初始化大小时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进去

注意：这就要求我们在其它的存储器中记录所有的历史元素，所以尽量一开始就尽量想好多大合适

4）空间占用估计

布隆过滤器的空间占用有一个简单的计算公式，但是推导比较繁琐，这里就省去推导过程了，直接引出计算公式

布隆过滤器有两个参数，第一个是预计元素的数量 n，第二个是错误率 f。公式根据这两个输入得到两个输出，第一个输出是位数组的长度 L，也就是需要的存储空间大小 (bit)，第二个输出是 hash 函数的最佳数量 k。hash 函数的数量也会直接影响到错误率，最佳的数量会有最低的错误率。

输入	说明
`n`	预计元素的数量 `n`
`f`	错误率 `f`

输出	说明
`L`	位数组的长度 `L`，也就是需要的存储空间大小 `(bit)`
`k`	`hash` 函数的最佳数量 `k`

k = 0.7*(1/n) # 约等于

f = 0.6185^(L/n)   #表示次方计算，也就是 math.pow

1、位数组相对越长 (l/n)，错误率 f 越低，这个和直观上理解是一致的

2、位数组相对越长 (l/n)，hash 函数需要的最佳数量也越多，影响计算效率

3、当一个元素平均需要 1 个字节 (8bit) 的指纹空间时 (L/n=8)，错误率大约为 2%

4、错误率为 10%，一个元素需要的平均指纹空间为 4.792 个 bit，大约为 5bit

5、错误率为1%，一个元素需要的平均指纹空间为 9.585 个 bit，大约为 10bit

6、错误率为 0.1%，一个元素需要的平均指纹空间为 14.377 个 bit，大约为 15bit

5）总结

问题：你也许会想，如果一个元素需要占据 15 个 bit，那相对 set 集合的空间优势是不是就没有那么明显了?

答案：这里需要明确的是，set 中会存储每个元素的内容，而布隆过滤器仅仅存储元素的指纹。

1、元素的内容大小就是字符串的长度，它一般会有多个字节，甚至是几十个上百个字节

2、每个元素本身还需要一个指针被 set 集合来引用，这个指针又会占去 4 个字节或 8 个字节，取决于系统是 32bit 还是 64bit。而指纹空间只有接近 2 个字节，所以布隆过滤器的空间优势还是非常明显的。

问题：计算太麻烦了，有没有一个计算的工具呢？

https://krisives.github.io/bloom-calculator/

6）实际元素超出时，误判率会怎样变化

当实际元素超出预计元素时，错误率会有多大变化，它会急剧上升么，还是平缓地上升，这就需要另外一个公式，引入参数 t 表示实际元素和预计元素的倍数

f = (1-0.5^t) ^ k # 极限近似，k 是 hash 函数的最佳数量

当 t 增大时，错误率，f 也会跟着增大，分别选择错误率为 10% ,1%, 0.1% 的 k 值，画出它的曲线进行直观观察。

从这个图中可以看出曲线还是比较陡峭的

1、错误率为 10% 时，倍数比为 2 时，错误率就会升至接近 40%，这个就比较危险了

2、错误率为 1% 时，倍数比为 2 时，错误率升至 15%，也挺可怕的

3、错误率为 0.1%，倍数比为 2 时，错误率升至 5%，也比较悬了

5、布隆过滤器的场景

1、邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，因为用了这个过滤器，所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中，这个就是误判所致，概率很低

2、布隆过滤器可以显著降低数据库的 IO 请求数量。当用户来查询某个 row 时，可以先通过内存中的布隆过滤器过滤掉大量不存在的 row 请求，然后再去磁盘进行查询。

6、其他布隆过滤器

1）`java`

1）`com.google.guava`

<dependencies>  
  <dependency>  
    <groupId>com.google.guava</groupId>  
    <artifactId>guava</artifactId>  
    <version>23.0</version>  
  </dependency>  
</dependencies> 

public class BloomFilterTest {

  private static final int capacity = 1000000;
  private static final int key = 999998;

  private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), capacity);

  static {
    for (int i = 0; i < capacity; i++) {
      bloomFilter.put(i);
    }
  }

  public static void main(String[] args) {
    /*返回计算机最精确的时间，单位微妙*/
    long start = System.nanoTime();

    if (bloomFilter.mightContain(key)) {
      System.out.println("成功过滤到" + key);
    }
    long end = System.nanoTime();
    System.out.println("布隆过滤器消耗时间:" + (end - start));
    int sum = 0;
    for (int i = capacity + 20000; i < capacity + 30000; i++) {
      if (bloomFilter.mightContain(i)) {
        sum = sum + 1;
      }
    }
    System.out.println("错判率为:" + sum);
  }
}



// 成功过滤到999998
// 布隆过滤器消耗时间:215518
// 错判率为:318
//可以看到，100w个数据中只消耗了约0.2毫秒就匹配到了key，速度足够快。然后模拟了1w个不存在于布隆过滤器中的key，匹配错误率为318/10000，也就是说，出错率大概为3%，跟踪下BloomFilter的源码发现默认的容错率就是0.03：


public static <T> BloomFilter<T> create(Funnel<T> funnel, int expectedInsertions /* n */) {
  return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}

2）

7、优缺点

如果对查询速度有较高要求且可以容忍一定的误判率，那么布隆过滤器可能是一个更好的选择。

1）优点

1、空间效率高：布隆过滤器通过多个哈希函数将元素映射到位数组中的多个位置，从而实现了高效的空间利用。如果允许存在一定的误判率，布隆过滤器是非常节省空间的。

2、时间复杂度低：布隆过滤器的增加和查询元素的时间复杂度都是O(k)，其中k是哈希函数的个数，通常比较小。因此，布隆过滤器在查询速度上具有很大的优势。

3、保密性强：布隆过滤器不存储元素本身，只存储元素的哈希值。这在一定程度上增强了数据的保密性。

2）缺点

1、存在一定的误判率：由于布隆过滤器使用多个哈希函数将元素映射到位数组中的多个位置，因此可能会出现多个元素映射到相同位置的情况，导致误判。虽然可以通过调整参数来降低误判率，但无法完全消除。

2、不支持删除元素：传统的布隆过滤器不支持元素的删除操作。一旦元素被插入到布隆过滤器中，就无法再将其删除（除非使用变形的特定布隆过滤器，但这类过滤器通常具有额外的复杂性和限制）。

3、访问空间地址不连续：布隆过滤器的位数组是稀疏的，即大部分位都是0，只有少数位是1。这导致在访问位数组时，内存寻址消耗较大，可能影响性能。

二、布谷鸟过滤器

布隆过滤器不记录元素本身，并且存在一个位被多个元素共用的情况，所以它不支持删除元素。布谷鸟过滤器，它支持删除操作，此外它还带来了其他优势：

1、查找性能更高：布隆过滤器要采用多种哈希函数进行多次哈希，而布谷鸟过滤器只需一次哈希

2、节省更多空间：布谷鸟过滤器记录元素更加紧凑，论文中提到，如果期望误报率在 3% 以下，半排序桶布谷鸟过滤器每个元素所占用的空间要比布隆过滤器中单个元素占用空间要小

1、为什么叫布谷鸟过滤器？

答案：布谷鸟过滤器之所以被称为“布谷鸟”，是因为它的工作原理类似于布谷鸟在自然界中的行为。布谷鸟以将自己的蛋产在其他鸟类的巢中而闻名，这样一来，寄主鸟就会抚养布谷鸟的幼鸟

在布谷鸟过滤器中，如果一个位置已经被占用，新元素会“驱逐”现有元素，将其移到其他位置。这种“驱逐”行为类似于布谷鸟将其他鸟蛋推出巢外，以便安置自己的蛋。因此，这种过滤器得名为“布谷鸟”过滤器。

2、基本原理

1、指纹（Fingerprint）：布谷鸟过滤器不是直接存储元素本身，而是存储元素的指纹。指纹是通过哈希函数计算得到的一个简短的摘要，通常比元素本身的长度要短。

2、桶（Bucket）：布谷鸟过滤器使用桶来存储指纹。每个桶可以存储一个或多个指纹，具体取决于设计。桶数组是一个固定大小的数组，每个桶可以存储一定数量的指纹。

3、操作方式

1）添加元素

1、当需要插入一个新元素时，首先计算该元素的指纹。

2、然后，使用一个或多个哈希函数来确定该指纹应该存储在哪个桶里。

3、如果目标桶已经有其他的指纹，可能会发生碰撞。这时会采用类似布谷鸟哈希的方法来处理碰撞，即新来的指纹会“踢出”桶中的某个旧指纹，然后尝试将旧指纹重新插入到另一个位置。

4、如果连续几次都无法成功插入（即连续踢出其他指纹导致无法停止），则可能会触发重新组织（reorganization），重新分配所有元素到桶中。

布谷鸟过滤器本质上是一个 桶数组，每个桶中保存若干数量的指纹（指纹由元素的部分 Hash 值计算出来）。定义一个布谷鸟过滤器，每个桶记录 2 个指纹，5 号桶和 11 号桶分别记录保存 a, b 和 c, d 元素的指纹，如下所示：

此时，向其中插入新的元素 e，发现它被哈希到的两个候选桶分别为 5 号和 11 号，但是这两个桶中的元素已经添加满了：

按照布谷鸟过滤器的特性，它会将其中的一个元素重哈希到其他的桶中（具体选择哪个元素，由具体的算法指定），新元素占据该元素的位置，如下：

以上便是向布谷鸟过滤器中添加元素并发生冲突时的操作流程，在我们的例子中，重新放置元素 e 触发了另一个重置，将现有的项 a 从桶 5 踢到桶 15。这个过程可能会重复，直到找到一个能容纳元素的桶，这就使得布谷鸟哈希表更加紧凑，因此可以更加节省空间。如果没有找到空桶则认为此哈希表太满，无法插入。虽然布谷鸟哈希可能执行一系列重置，但其均摊插入时间为 O(1)。

2）查询操作

1、当查询一个元素是否存在时，同样使用相同的哈希函数来计算该元素的指纹，并查找对应的桶。

2、如果桶中有匹配的指纹，则认为该元素可能存在于集合中。

3、如果没有找到匹配的指纹，则可以确定该元素不在集合中。

3）删除操作

1、布谷鸟过滤器支持删除操作。

2、删除一个元素时，先计算其指纹，然后查找该指纹所在的桶。

3、如果找到了对应的指纹，就将其删除。

4、删除操作可能会导致桶变得空闲，但这不影响过滤器的正常工作。

4、优缺点

如果需要支持删除操作且对存储空间有一定要求，可以考虑使用布谷鸟过滤器

1）优点：

1、支持删除元素：布谷鸟过滤器与布隆过滤器的主要区别之一是它支持元素的删除操作。虽然删除操作并不完美（可能误删除其他具有相同哈希值的元素），但在某些应用场景下，删除功能是非常重要的。

2、查询效率高：布谷鸟过滤器只需一次哈希，布隆过滤器要采用多种哈希函数进行多次哈希

3、存储空间开销更低：对于相同的误判率，布谷鸟哈希表更加紧凑，布谷鸟过滤器在错误率小于3%的时候空间性能是优于布隆过滤器，布谷鸟过滤器比布隆过滤器空间节省40%多

2）缺点：

1、插入性能较低：由于布谷鸟过滤器采用备用候选桶的方案，当首选桶已满时，需要将已存储的值踢出到候选桶。这种操作增加了插入的复杂性和耗时，特别是在表元素增多的情况下，碰撞概率和插入耗时都会增加。

2、重复元素插入存在上限：布谷鸟过滤器对已存在的值会执行踢出操作，因此重复元素的插入存在上限。当达到这个上限时，再插入重复元素可能会导致插入失败。

3、删除操作的不完美性：如前所述，布谷鸟过滤器的删除操作并不完美。如果元素没有插入就进行删除，可能会出现误删除；如果元素插入了多次，但每次删除操作只删除一个值，那么就需要知道元素插入了多少次才能彻底删除，或者循环删除直到失败为止。

5、应用场景

布谷鸟过滤器适用于需要高效查询、支持动态更新（插入和删除）并且可以容忍一定误报率的场景，例如：

1、数据库索引：在数据库中，可以用来加速查询过程。

2、网络安全：用于快速识别已知的恶意IP地址或URL。

3、内存管理：用于跟踪页面的存在性，提高内存管理效率。

ContactAuthor

HealeJean的梦想博客

一个高级软件开发工程师的成长之路

Redis之_层峦叠嶂_布隆过滤器

一、布隆过滤器

1、引入

2、布隆过滤器是什么？

3、`Redis` 中的布隆过滤器

1）默认的布隆过滤器

2）自定义的布隆过滤器

3）注意事项

4、布隆过滤器的原理

1）`add`：添加元素

2）`exists`：校验元素是否存在

3）实际元素超出初始化大小怎么办？

4）空间占用估计

5）总结

6）实际元素超出时，误判率会怎样变化

5、布隆过滤器的场景

6、其他布隆过滤器

1）`java`

1）`com.google.guava`

2）

7、优缺点

1）优点

2）缺点

二、布谷鸟过滤器

1、为什么叫布谷鸟过滤器？

2、基本原理

3、操作方式

1）添加元素

2）查询操作

3）删除操作

4、优缺点

1）优点：

2）缺点：

5、应用场景

一、布隆过滤器

1、引入

2、布隆过滤器是什么？

3、Redis 中的布隆过滤器

1）默认的布隆过滤器

2）自定义的布隆过滤器

3）注意事项

4、布隆过滤器的原理

1）add：添加元素

2）exists：校验元素是否存在

3）实际元素超出初始化大小怎么办？

4）空间占用估计

5）总结

6）实际元素超出时，误判率会怎样变化

5、布隆过滤器的场景

6、其他布隆过滤器

1）java

1）com.google.guava

2）

7、优缺点

1）优点

2）缺点

二、布谷鸟过滤器

1、为什么叫布谷鸟过滤器？

2、基本原理

3、操作方式

1）添加元素

2）查询操作

3）删除操作

4、优缺点

1）优点：

2）缺点：

5、应用场景

3、`Redis` 中的布隆过滤器

1）`add`：添加元素

2）`exists`：校验元素是否存在

1）`java`

1）`com.google.guava`