Long Story

Appearance

Redis BloomFilter ​

本文介绍Bloom Filter（布隆过滤器）的原理、实现以及使用。

1. 介绍与原理 ​

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。

布隆过滤器存在误判，有可能将不存在集合中的元素判断为存在集合中。

布隆过滤器实质上是一个很长的二进制位数组（bit array）和一系列随机映射函数（哈希函数）。

布隆过滤器原理如下：

  • 初始化： 创建一个长度为 m 的位数组，所有位都初始化为0。同时，选择 k 个不同的哈希函数。
  • 添加元素： 当需要将一个元素添加到集合中时，会用这 k 个哈希函数分别对该元素进行计算，得到 k 个哈希值。这些哈希值会映射到位数组中的 k 个位置，然后，将这 k 个位置上的位都设置为1。
  • 查询元素： 当需要判断一个元素是否在集合中时，同样用这 k 个哈希函数对该元素进行计算，得到 k 个哈希值，并检查位数组中对应的 k 个位置。
    • 如果这 k 个位置中有任何一个位是0，那么该元素一定不在集合中。 （因为如果它在集合中，在添加的时候这些位都应该被设置为1了）
    • 如果这 k 个位置上的位都是1，那么该元素“可能”在集合中。 这就是布隆过滤器的“概率性”所在，因为有可能这些位是在添加其他元素时被设置为1的，这被称为“误判”（False Positive）或“假阳性”。

2. 自定义布隆过滤器 ​

要实现布隆过滤器，即实现初始化、添加元素和查询元素这三个功能：

  • 初始化：最主要的任务是确定位数组长度m和哈希函数个数k，当然，我们可以直接在构造方法中指定这两个值，但是也可以通过计算得出。一般定义布隆过滤器时，会考虑以下两个参数：

    • 预计存储的元素数量 (n)： 大概会往布隆过滤器中添加多少个元素。
    • 可接受的误判率 (P)： 能容忍的假阳性概率是多少。这个值越小，所需的空间和哈希函数数量就越大。

    基于n和P，可通过以下公式计算位数组长度和哈希函数个数：

    • 位数组长度 (m) 的计算公式：$ m=− \frac{n \times lnP}{(ln2)^{2}}$
    • 哈希函数数量 (k) 的计算公式： k=mn×ln2，即k=−lnPln2

  • 添加元素：对该元素进行k次哈希计算，得到k个哈希值，将这k个哈希值映射到位数组的k个位置，将这k个位置上的位设置为1；

  • 查询元素：按照添加元素的方法得到k个哈希值，判断这k个哈希值映射到位数组的k个位置，是否存在其中一个位置为0，如果是，则返回false，如果全部位置都是1，则返回true（无法判断该元素是真的存在集合中还是误判）；

首先引入Guava依赖库（用于引入哈希函数）：

是一个由 Google 开发的开源 Java 核心库集合。它提供了一系列实用的工具类和新的数据结构，旨在简化 Java 开发，提高代码质量和开发效率。

可以把 Guava 理解为一个 Java 开发的“瑞士军刀”，它包含了许多在日常编程中非常有用但 JDK 标准库中缺失或不方便使用的功能。

xml
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>33.4.8-jre</version>
</dependency>

自定义过滤器如下：

java
public class MyBloomFilter {
    private BitSet bitSet;
    private int length;
    private int numberOfHash;

    /**
     * 创建布隆过滤器
     * @param number 预计插入的元素数量
     * @param fpp 误判率，0-1之间
     */
    public MyBloomFilter(int number, double fpp){
        int m = (int) (-Math.log(fpp) * number / (Math.log(2) * Math.log(2)));
        length = m;
        numberOfHash = (int)(-Math.log(fpp) / Math.log(2));
        bitSet= new BitSet(m);
    }


    /**
     * 向布隆过滤器中添加元素
     * @param element 元素
     */
    public void add(int element){
        for (int hashPosition : getHashPositions(element)) {
            bitSet.set(hashPosition % length);
        }
    }

    private int[] getHashPositions(int element){
        int[] positions = new int[numberOfHash];
        for (int i = 0; i < numberOfHash; i++) {
            positions[i] = hash(element, i);
        }
        return positions;
    }

    private int hash(int element, int position){
        HashCode hashCode = Hashing.murmur3_128(0).hashInt(element);
        HashCode hashCode1 = Hashing.murmur3_128(1).hashInt(element);
        return Math.abs(hashCode.asInt() + position * hashCode1.asInt());
    }

    /**
     * 判断布隆过滤器中是否包含element元素
     * @param element
     * @return
     */
    public boolean contain(int element){
        for (int hashPosition : getHashPositions(element)) {
            int p = hashPosition % length;
            if (!bitSet.get(p)) {
                return false;
            }
        }
        return true;
    }
}

测试代码：

java
public static void main(String[] args) {
    MyBloomFilter bloomFilter = new MyBloomFilter(10000, 0.03);

    for (int i = 0; i < 10000; i++) {
        bloomFilter.add(i);
    }

    int falsePositiveNumber = 0;
    for (int i = 10000; i < 11000; i++) {
        if(bloomFilter.contain(i)) {
            System.out.println("误判了：" + i);
            falsePositiveNumber++;
        }
    }
    System.out.println("总共误判了：" + falsePositiveNumber);
}

结果如下：

txt
误判了：10109
误判了：10133
误判了：10135
误判了：10271
误判了：10276
误判了：10306
误判了：10351
误判了：10433
误判了：10454
误判了：10462
误判了：10464
误判了：10563
误判了：10586
误判了：10665
误判了：10730
误判了：10821
误判了：10859
误判了：10880
误判了：10884
误判了：10944
误判了：10945
误判了：10990
总共误判了：22

3. Guava版布隆过滤器 ​

在Guava中也提供了布隆过滤器实现，我们可以直接使用。

使用如下静态方法创建Guava的布隆过滤器：

java
public static <T extends @Nullable Object> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp){
  // ... 
}

  • Funnel<? super T> funnel：布隆过滤器的核心是哈希函数，这些哈希函数操作的是原始的字节序列。然而，在 Java 中，我们通常处理的是各种复杂的对象（例如字符串、整数、自定义的 User 对象、Product 对象等），布隆过滤器不知道 User 等对象应该如何转换为字节序列。

    Funnel 就是为了解决这个问题而设计的。它是一个泛型接口 Funnel<T>，其中 T 是想要放入布隆过滤器中的对象的类型。

    java
    public interface Funnel<T extends @Nullable Object> extends Serializable {
  void funnel(@ParametricNullness T from, PrimitiveSink into);
}

    当实现 Funnel 时，需要提供一个 funnel 方法，该方法负责：

    1. 接收自定义对象 T。
    2. 接收一个 PrimitiveSink 对象（原始类型的数据槽）。
    3. 将 T 对象的关键属性（那些希望参与哈希计算的属性）“写入”到 PrimitiveSink 中。

    对于常见的 Java 类型，Guava 提供了 Funnels 工具类，其中包含了许多预定义的 Funnel 实现，非常方便：

    • Funnels.stringFunnel(Charset charset)：用于字符串。
    • Funnels.byteArrayFunnel()：用于字节数组。
    • Funnels.integerFunnel()：用于整型。
    • Funnels.longFunnel()：用于长整型。

  • long expectedInsertions：布隆过滤器中期望放入元素的数量；

  • double fpp：期望的误判率；

使用案例如下：

java
void test1(){
    BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 10000, 0.01);

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

    int falsePositiveNumber = 0;
    for (int i = 10000; i < 11000; i++) {
        if(bloomFilter.mightContain(i)){
            System.out.println("误判了：" + i);
            falsePositiveNumber++;
        }
    }
    System.out.println("总共误判了：" + falsePositiveNumber);
}

结果如下：

txt
误判了：10067
误判了：10071
误判了：10143
误判了：10233
误判了：10303
误判了：10370
误判了：10666
误判了：10843
误判了：10889
误判了：10893
误判了：10906
误判了：10937
总共误判了：12

4. Redis版布隆过滤器 ​

Redis也提供了布隆过滤器的实现，使用如下。

创建布隆过滤器：

txt
BF.RESERVE key error_rate capacity
  • key：布隆过滤器名称；
  • error_rate：误判率，0-1之间，
  • capacity：布隆过滤器容量，即期望插入的元素数量；

向布隆过滤器中添加元素：

txt
BF.ADD key item

判断布隆过滤器中是否存在某个元素：

txt
BF.EXISTS key item

返回值为1表示可能存在，返回值为0表示不存在。

使用案例如下：

image-20250617141406060

注意，Redis 8之后自带Redis Bloom模块，如果是之前的版本，需要自行加载模块。

请参考：https://redis.io/blog/bloom-filter/

5. 布隆过滤器的应用 ​

缓存穿透： 解决缓存穿透问题，避免大量对不存在数据的请求直接打到数据库，造成数据库压力。例如，在查询缓存前，先用布隆过滤器判断key是否存在，如果不存在则直接返回，避免查询缓存和数据库。

垃圾邮件过滤： 将已知的垃圾邮件地址或垃圾邮件特征添加到布隆过滤器中，快速识别并过滤掉垃圾邮件。

黑名单/白名单过滤： 用于网站或应用的用户黑名单、敏感词过滤等。

大数据去重： 在海量数据中进行去重操作，例如爬虫抓取URL去重，推荐系统过滤已推荐内容等。

推荐系统： 过滤掉用户已经看过或不感兴趣的内容，避免重复推荐。

Copyright © 2024-present by 水木子