亿级数据存储利器：探秘布隆过滤器应用

0 398

亿级数据存储利器：探秘布隆过滤器Applications

布隆过滤器是一种采用长二进制数组的技术，通过多个哈希算法计算数据的哈希值，并将其作为数组索引，以判断数据是否存在。当索引位置全部为1时，表示数据存在；若包含0，则数据不存在。

布隆过滤器应用场景

防止缓存穿透

通过使用布隆过滤器来防范缓存穿透问题，我们能够有效地避免由于数据误删或恶意攻击而引起的缓存穿透。在访问特定数据之前，我们首先检查布隆过滤器是否包含该数据，如果不存在，就直接返回预定义的信息，从而避免所有请求直接访问数据库。这种方法的前提是在系统启动时根据实际业务场景执行缓存预热，确保将所有热点数据加载到布隆过滤器中。

Blacklist

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

网页爬虫对 URL 的去重

布隆过滤器的优点

以极小的空间开销存储的二进制数组，非常适用于处理大规模数据。其查询速度迅猛，通过计算数据哈希值，并将其作为数组索引，实现快速查询，时间复杂度为 O(k)，其中 k 为哈希计算次数。此外，布隆过滤器具备卓越的保密性，外部无法直观识别存储的具体数据。

布隆过滤器的缺点

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

为什么会出现误判?

主要问题源于哈希碰撞，即不同数据计算得到相同的哈希值。例如，数据 A的哈希值是5，导致二进制数组中索引为5的位置被标记为1。现在，需求是检查数据B是否存在，但数据B的哈希计算结果也是5，导致误判，因为二进制数组中索引5的位置已被标记为1。实际上，数据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。

布隆过滤器的实现

<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 实现的布隆过滤器

<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);
}