布隆过滤器是一种由位数组和多个哈希函数组成概率数据结构,返回两种结果 可能存在 和 一定不存在。
布隆过滤器里的一个元素由多个状态值共同确定。位数组存储状态值,哈希函数计算状态值的位置。
根据它的算法结构,有如下特征:
使用有限位数组表示大于它长度的元素数量,因为一个位的状态值可以同时标识多个元素。
不能删除元素。因为一个位的状态值可能同时标识着多个元素。
添加元素永远不会失败。只是随着添加元素增多,误判率会上升。
如果判断元素不存在,那么它一定不存在。
比如下面,X,Y,Z 分别由 3个状态值共同确定元素是否存在,状态值的位置通过3个哈希函数分别计算。
关于误判概率,因为每个位的状态值可能同时标识多个元素,所以它存在一定的误判概率。如果位数组满,当判断元素是否存在时,它会始终返回<code>true</code>,对于不存在的元素来说,它的误判率就是100%。
那么,误判概率和哪些因素有关,已添加元素的数量,布隆过滤器长度(位数组大小),哈希函数数量。
根据维基百科推理误判概率 \(P_{fp}\) 有如下关系:
\[{ 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$ 的关系如下图:
根据误判概率公式可以做一些事
估算最佳布隆过滤器长度。
估算最佳哈希函数数量。
当 \(n\) 添加元素和 \(P_{fp}\)误报概率确定时,\(m\) 等于:
\[{\displaystyle m=-{\frac {n\ln P_{fp}}{(\ln 2)^{2}}} \approx -1.44\cdot n\log _{2}P_{fp}}\]
当 \(n\) 和 \(P_{fp}\) 确定时,\(k\) 等于:
\[{\displaystyle k=-{\frac {\ln P_{fp} }{\ln 2}}=-\log _{2}P_{fp} }\]
当 \(n\) 和 \(m\) 确定时,\(k\) 等于:
\[{\displaystyle k={\frac {m}{n}}\ln 2}\]
使用布隆过滤器前,我们一般会评估两个因素。
预期添加元素的最大数量。
业务对错误的容忍程度。比如1000个允许错一个,那么误判概率应该在千分之一内。
很多布隆过滤工具都提供了预期添加数量和误判概率配置参数,它们会根据配置的参数计算出最佳的长度和哈希函数数量。
Java中有一些不错的布隆过滤工具包。
<code>Guava</code> 中 <code>BloomFilter</code>。
<code>redisson</code> 中 <code>RedissonBloomFilter</code> 可以redis 中使用。
看下 <code>Guava</code> 中 <code>BloomFilter</code> 的简单实现,创建前先计算出位数组长度和哈希函数数量。
根据最佳布隆过滤器长度公式,计算最佳位数组长度。
根据最佳哈希函数数量公式,计算最佳哈希函数数量。
在<code>redisson</code> 中 <code>RedissonBloomFilter</code> 计算方法也是一致。
设想一个手机号去重场景,每个手机号占用<code>22 Byte</code>,估算逻辑内存如下。
<col>
expected
HashSet
fpp=0.0001
fpp=0.0000001
100万
18.28MB
2.29MB
4MB
1000万
182.82MB
22.85MB
40MB
1亿
1.78G
228.53MB
400MB
注:实际物理内存占用大于逻辑内存。
误判概率 \(p\) 和已添加的元素 \(n\),位数组长度 \(m\),哈希函数数量 \(k\) 关系如下:
弱密码检测;
垃圾邮件地址过滤。
浏览器检测钓鱼网站;
缓存穿透。
维护一个哈希过弱密码列表。当用户注册或更新密码时,使用布隆过滤器检查新密码,检测到提示用户。
维护一个哈希过垃圾邮件地址列表。当用户接收邮件,使用布隆过滤器检测,检测到标识为垃圾邮件。
使用布隆过滤器来查找钓鱼网站数据库中是否存在某个网站的 URL。
缓存穿透是指查询一个根本不存在的数据,缓存层和数据库都不会命中。当缓存未命中时,查询数据库
数据库不命中,空结果不会写回缓存并返回空结果。
数据库命中,查询结果写回缓存并返回结果。
一个典型的攻击,模拟大量请求查询不存在的数据,所有请求落到数据库,造成数据库宕机。
其中一种解决方案,将存在的缓存放入布隆过滤器,在请求前进行校验过滤。
对于千万亿级别的数据来说,使用布隆过滤器具有一定优势,另外根据业务场景合理评估预期添加数量和误判概率是关键。
参考
https://en.wikipedia.org/wiki/Bloom_filter https://hur.st/bloomfilter