5分钟掌握Bloom滤镜（古驰bloom香水）

布隆过滤器

布鲁姆滤镜是一种位数组而且多个哈希函数形成一个返回两个结果的概率数据结构可能存在而且一定不存在。

Bloom过滤器中的一个元素由多个元素组成状态值共同决定。位数组存储状态值，计算哈希函数状态值年代的位置。

根据其算法结构，它具有以下特点:

• 使用有限位数组来表示大于其长度的元素数量，因为一个位状态值可以同时识别多个元素。
• 不能删除元素。因为有一点状态值多个元素可以同时被识别。
• 添加元素从来不会失败。随着添加元素数量的增加，误判率也会增加。
• 如果判断元素不存在，那么它一定不存在。

例如，X, Y, Z分别由3组成状态值共同确定一个元素是否存在，状态值的位置由三个哈希函数分别计算。

数学关系

误判概率

关于误判的概率，因为每一个比特’s状态值它可以同时识别多个元素，因此有一定的误判概率。如果位数组已满，则在检查元素是否存在时总是返回真正的，对于不存在的元素，其误判率为100%。

然后，哪些因素与误判概率、添加元素的数量、Bloom过滤器的长度(位数组大小)和哈希函数的数量相关。

来自维基百科的推理误判概率( P_{fp} ) has the following relationship:

$ $
{ P_{fp} =left(1-left[1-{frac {1}{m}}right]^{kn}right)^{k}approx left(1-e^{{-frac {kn}{m}}}right)^{k}}
$ $

• $m$是位数组的大小;
• $n$是添加的元素数量;
• $k$是哈希函数的个数;
• $e$数学常数，近似等于2.718281828。

由此可得，当添加的元素个数为0时，虚警率为0;当所有位数组都为1时，虚警率为100%。

在不同数量的哈希函数下，$P_{fp}$和$n$之间的关系如下:

根据假阳性概率公式可以做些什么

• 估计最佳的花滤镜长度。
• 估计哈希函数的最优数目。

最佳绽放滤镜长度

When (n ) elements are added 而且 ( P_{fp} ) the false positive probability is determined, ( m ) is equal to:

$ $
{displaystyle m=-{frac {nln P_{fp}}{(ln 2)^{2}}} approx -1.44cdot nlog _{2}P_{fp}}
$ $

哈希函数的最优数目

When ( n ) 而且 (P_{fp} ) are determined, ( k ) is equal to:

$ $
{displaystyle k=-{frac {ln P_{fp} }{ln 2}}=-log _{2}P_{fp} }
$ $

When ( n ) 而且 ( m ) are determined, ( k ) is equal to:

$ $
{displaystyle k={frac {m}{n}}ln 2}
$ $

实现Bloom过滤器

使用布隆过滤器以前，我们一般评估两个因素。

• 期望添加的元素的最大数量。
• 企业对错误的容忍度。例如，允许1000例错误，那么误判的概率应该在千分之一以内。

许多bloom过滤器工具提供期望增加数量而且误判概率配置参数，将根据配置参数计算最优长度而且哈希函数个数。

Java中有一些很好的bloom过滤器工具包。

• 番石榴中间BloomFilter。
• redisson中间RedissonBloomFilter可以在redis中使用。

看看番石榴中间BloomFilter它的一个简单实现在创建之前进行计算位数组长度而且哈希函数个数。

static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long 预期Insertions, double fpp, Strategy strategy) {
/**
* 预期Insertions: Expected number of additions
* fpp: false positive probability
*/
long numBits = optimalNumOfBits(预期Insertions, fpp);
int numHashFunctions = optimalNumOfHashFunctions(预期Insertions, numBits);
try {
return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException e) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
}
}

根据最佳绽放滤镜长度计算最佳位数组长度的公式。

static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

根据哈希函数的最优数目计算哈希函数最优个数的公式。

static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}

存在redisson中间RedissonBloomFilter计算方法也相同。

    private int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
private long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

内存使用情况

设想一个手机号码重复数据删除场景，每个手机号码占用22字节，估计的逻辑内存如下。

注意:实际物理内存占用率大于逻辑内存占用率。

误判概率( p ) 而且添加元素 ( n )，位数组长度 ( m )，哈希函数个数( k ) The relationship is as follows:

应用场景

1. 弱密码检测;
2. 垃圾邮件地址过滤。
3. 网络钓鱼网站浏览器检测;
4. 缓存渗透。

弱密码检测

维护带有弱散列的密码列表。当用户注册或更新密码时，使用Bloom过滤器检查新密码，检测到提示用户。

垃圾邮件地址过滤

维护散列垃圾邮件地址列表。当用户收到一封电子邮件时，它会被Bloom过滤器检测到，并被识别为垃圾邮件。

浏览器检测钓鱼网站

使用Bloom过滤器来查找网站的URL是否存在于钓鱼网站的数据库中。

缓存渗透

缓存穿透指的是查询不存在的数据，缓存层和数据库都不会命中。查询缓存缺失的数据库

1. 数据库未命中，空结果不会写回缓存并返回空结果。
2. 数据库命中，查询结果被写回缓存并返回结果。

典型的攻击模拟大量请求查询不存在的数据，所有请求都落在数据库上，导致数据库瘫痪。

其中一个解决方案就是现有的缓存放入Bloom过滤器并在请求之前执行验证过滤。

总结

对于千万亿级的数据，使用Bloom过滤器具有一定的优势，并且可以根据业务场景进行合理的评估期望增加数量而且误判概率是关键。

参考

https://en.wikipedia.org/wiki& # 8230;

https://hur.st/bloomfilter