亿级海量数据存储之布隆过滤器

站长

2024年08月02日 20:00 · 阅读数 22

本文主要讲解布隆过滤器的基本原理以及在生产中如何使用

🔥布隆过滤器的概念

布隆过滤器是采用一个很长的二进制数组，通过不同的哈希算法计算出数据的哈希值作为二进制数组元素的索引来判断这个数据是否存在的一种技术。如果通过索引查找到的值全都是 1，那就说明这个数据存在，如果查找到的值包含 0 ，那就说明这个数据不存在。亿级海量数据存储之布隆过滤器

🔥布隆过滤器应用场景

防止缓存穿透

使用布隆过滤器来防止缓存穿透，可以有效的避免因数据误删或者恶意攻击导致的缓存穿透问题，当访问某个数据时，先检查布隆过滤器里面是否存在这个数据，如果不存在则直接返回预定义的信息，避免请求全打到数据库层。这么做的前提是需要根据实际的业务场景做好缓存预热，比如在系统启动时就将所有热点数据加载到布隆过滤器当中。

黑名单

如果黑名单数据量非常大，存储在布隆过滤器是一个不错的选择

网页爬虫对 URL 的去重

🔥布隆过滤器的优点

二进制数据组成的数组，占用的空间非常小，适合大数据量的存储
查询速度非常快，计算出数据的哈希值，再将哈希值作为数组索引查找二进制数组的值，查询时间复杂度是 O(k)，k 表示哈希计算的次数。
保密性非常好，无法直观的看出存储的是什么数据。

🔥布隆过滤器的缺点

无法删除数据
存在误判的情况，这是无法避免的，但是可以设置误判率

🔥为什么会出现误判?

主要是由于哈希碰撞引起的，不同的数据计算出的哈希值相同，假设数据 A 之前计算出的哈希值是 5，那么二进制数组下标为 5 的位置就会被标记为 1，然后现在有个需求是查询数据 B 是否存在，结果数据 B 经过哈希计算后的结果也是 5，就发现二进制数组中 5 这个位置的值已经被标记为 1 了，所以检查结果就是数据 B 已经存在，实际上数据 B 根本不存在，出现了误判。

🔥如何减少误判率?

误判率可以在使用布隆过滤器时直接设置，但是不能设置的太小，误判率设置的越小，需要哈希计算的次数就会越多，因为只有这样才能减少误判的概率，性能就会越差。

🔥为什么要使用不同的哈希函数进行多次哈希计算？

主要目的是通过多次哈希计算，减少误判的概率，因为不同的哈希函数对于同一个数据计算出的哈希值是不一样的，根据布隆过滤器的规则，必须所有哈希值索引对应的二进制数据都是 1 才证明这个数据存在，但凡有一个 0 都不能证明这个数据存在，所以多次哈希计算就可以有效的降低误判的概率。

比如数据 A 经过 hash1 (A)计算得出的结果是 5，经过 hash2(A)计算出的结果是 6，假设此时有个需求是检查数据 B 是否存在，数据 B 经过 hash1(B)计算出的结果也是 5，但是 5 这个位置的值已经是 1 了，经过 hash2(B)计算出的结果是 7，7 这个位置的值是 0，那么就可以判定数据 B 不存在。假设没有第二个哈希函数进行第二次计算，那么就直接是误判了，因为 5 这个位置的 1 证明的是数据 A 存在，而不是数据 B。

⚠️多次哈希计算也是有弊端的，首先是性能会降低，因为哈希计算的次数多，所消耗的时间就比较长；其次是占用的空间大，因为每个计算出的哈希值对应的索引都需要存储 0 或者 1 进去，哈希计算越多，存的也就越多。

🔥布隆过滤器的实现

✅基于 Guava 实现的布隆过滤器

引入 Google Guava 依赖

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

测试代码如下所示

public class Main {

    /**
     * 预计存入的数据量
     **/
    private final static int SIZE = 100;
    /**
     * 误判率
     **/
    private final static double FPP = 0.01;
    /**
     * 布隆过滤器
     **/
    private final static BloomFilter<String> BLOOM_FILTER = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), SIZE, FPP);

    public static void main(String[] args) {
        // 存入10086
        BLOOM_FILTER.put("10086");
        // 检查10086是否存在
        boolean mightContain1 = BLOOM_FILTER.mightContain("10086");
        // 检查20086是否存在
        boolean mightContain2 = BLOOM_FILTER.mightContain("20086");
        // true
        System.out.println("10086是否存在：" + mightContain1);
        // false
        System.out.println("20086是否存在：" + mightContain2);
    }
}

布隆过滤器的误判率测试

public class Main {

    /**
     * 预计存入的数据量
     **/
    private final static int SIZE = 1000000;
    /**
     * 误判率
     **/
    private final static double FPP = 0.01;
    /**
     * 布隆过滤器
     **/
    private final static BloomFilter<Integer> BLOOM_FILTER = BloomFilter.create(Funnels.integerFunnel(), SIZE, FPP);

    public static void main(String[] args) {
        //加入100w测试数据
        for (int i = 0; i < 1000000; i++) {
            BLOOM_FILTER.put(i);
        }
        // 误判数
        int count = 0;
        // 使用另外10w测试数据测试误判率
        for (int i = 1000000; i < 1100000; i++) {
            if (BLOOM_FILTER.mightContain(i)) {
                count++;
            }
        }
        // 误判数输出是947个，相当于10w数据误判了947个，很符合我们初始化时设置的误判率0.01
        System.out.println("总共的误判数：" + count);
    }
}

✅基于 Redisson 实现的布隆过滤器

引入 Redisson 依赖

<dependency>
  <groupId>org.redisson</groupId>
  <artifactId>redisson</artifactId>
  <version>3.16.7</version>
</dependency>

测试代码如下所示

public static void main(String[] args) {
        // 创建RedissonClient连接Redis
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6380")
                .setPassword("wjw123456")
                .setDatabase(0);
        RedissonClient redissonClient = Redisson.create(config);
        // 创建布隆过滤器
        RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("phone");
        // 初始化布隆过滤器,预计存储100w个数据，误差率为0.01
        bloomFilter.tryInit(1000000, 0.01);
        // 添加一个数据进去
        bloomFilter.add("10086");
        bloomFilter.add("10087");
        // 检查这个数据是否存在
        boolean firstContains = bloomFilter.contains("10086");
        // true
        System.out.println("10086是否存在:" + firstContains);
        // 测试10088是否存在
        boolean secondContains = bloomFilter.contains("10088");
        // false
        System.out.println("10088是否存在:" + secondContains);
}

🔥往期文章

转载自:https://juejin.cn/post/7307857947802533926