共计 6449 个字符,预计需要花费 17 分钟才能阅读完成。
布隆过滤器
- 作者: 博学谷狂野架构师
- GitHub:GitHub 地址(有我精心筹备的 130 本电子书 PDF)
只分享干货、不吹水,让咱们一起加油!😄
什么是布隆过滤器
布隆过滤器(Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器能够用于检索一个元素是否在一个汇合中。它的长处是空间效率和查问工夫都比个别的算法要好的多,毛病是有肯定的误识别率和删除艰难。
布隆过滤器能够了解为一个不怎么准确的 set 构造,当你应用它的 contains 办法判断某个对象是否存在时,它可能会误判。然而布隆过滤器也不是特地不准确,只有参数设置的正当,它的精确度能够管制的绝对足够准确,只会有小小的误判概率。
当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就必定不存在。打个比方,当它说不意识你时,必定就不意识;当它说见过你时,可能基本就没见过面,不过因为你的脸跟它意识的人中某脸比拟类似 (某些熟脸的系数组合),所以误判以前见过你。
套在下面的应用场景中,布隆过滤器能精确过滤掉那些曾经看过的内容,那些没有看过的新内容,它也会过滤掉极小一部分 (误判),然而绝大多数新内容它都能精确辨认。这样就能够齐全保障举荐给用户的内容都是无反复的。
布隆过滤器的原理
其本质就是一个只蕴含 0 和 1 的数组。具体操作当一个元素被退出到汇合外面后,该元素通过 K 个 Hash 函数运算失去 K 个 hash 后的值,而后将 K 个值映射到这个位数组对应的地位,把对应地位的值设置为 1。查问是否存在时,咱们就看对应的映射点地位如果全是 1,他就很可能存在(跟 hash 函数的个数和 hash 函数的设计无关),如果有一个地位是 0,那这个元素就肯定不存在。
- 首先须要初始化一个 二进制的数组,长度设为 L,同时初始值全为 0。
- 当 写入一个 A1=1000 的数据时,须要 进行 H 次 hash 函数的运算 (这里为 2 次);与 HashMap 有点相似,通过 算出的 HashCode 与 L 取模后定位到 0、2 处,将该处的值设为 1。
- A2=2000 也是同理计算后将 4、7 地位设为 1。
- 当有一个 B1=1000 须要判断是否存在时,也是做两次 Hash 运算,定位到 0、2 处,此时他们的值都为 1,所以认为 B1=1000 存在于汇合中。
- 当有一个 B2=3000 时,也是同理。第一次 Hash 定位到 index=4 时,数组中的值为 1,所以再进行第二次 Hash 运算,后果定位到 index=5 的值为 0,所以认为 B2=3000 不存在于汇合中。
整个的写入、查问的流程就是这样,汇总起来就是:
对写入的数据做 H 次 hash 运算定位到数组中的地位,同时将数据改为 1。当有数据查问时也是同样的形式定位到数组中。一旦其中的有一位为 0 则认为数据必定不存在于汇合,否则数据可能存在于汇合中。
布隆过滤器的特点
只有返回数据不存在,则必定不存在。
返回数据存在,但只能是大概率存在。
同时 不能革除 其中的数据。
在无限的数组长度中寄存大量的数据,即使是 再完满的 Hash 算法也会有抵触,所以有可能两个齐全不同的 A、B 两个数据最初定位到的地位是截然不同的。
删除数据也是同理,当我把 B 的数据删除时,其实也相当于是把 A 的数据删掉了,这样也会造成后续的误报。
基于以上的 Hash 抵触的前提,所以 Bloom Filter 有肯定的误报率,这个误报率和 Hash 算法的次数 H,以及数组长度 L 都是无关的。
利用场景
缓存穿透
咱们常常会把一部分数据放在 Redis 等缓存,比方产品详情。这样有查问申请进来,咱们能够依据产品 Id 间接去缓存中取数据,而不必读取数据库,这是晋升性能最简略,最广泛,也是最无效的做法。个别的查问申请流程是这样的:先查缓存,有缓存的话间接返回,如果缓存中没有,再去数据库查问,而后再把数据库取出来的数据放入缓存,所有看起来很美妙。然而如果当初有大量申请进来,而且都在申请一个不存在的产品 Id,会产生什么?既然产品 Id 都不存在,那么必定没有缓存,没有缓存,那么大量的申请都怼到数据库,数据库的压力一下子就上来了,还有可能把数据库打死。
应用布隆过滤器的特点,只有返回数据不存在,则必定不存在,返回数据存在,但只能是大概率存在,这种特点能够大批量的有效申请过滤掉,可能穿透缓存的常识漏网之鱼,无关紧要。
查看单词拼写
查看一个单词拼写是否正确,因为有海量的单词数量,每天可能有新的单词,应用布隆过滤器,能够将单词映射到很小的内存中,能够通过简略的几次 hash 运行就能够进行校验,只有返回数据不存在,则必定不存在,返回数据存在,但只能是大概率存在,尽管可能有误报,然而对系统的晋升是革命性的。
Guava 的布隆过滤器
这就又要提起咱们的 Guava 了,它是 Google 开源的 Java 包,提供了很多罕用的性能。
Guava 中,布隆过滤器的实现次要波及到 2 个类,BloomFilter 和 BloomFilterStrategies,首先来看一下 BloomFilter 的成员变量。须要留神的是不同 Guava 版本的 BloomFilter 实现不同。
布隆过滤器解析
成员变量剖析
COPY/** guava 实现的以 CAS 形式设置每个 bit 位的 bit 数组 */
private final LockFreeBitArray bits;
/** hash 函数的个数 */
private final int numHashFunctions;
/** guava 中将对象转换为 byte 的通道 */
private final Funnel<? super T> funnel;
/**
* 将 byte 转换为 n 个 bit 的策略,也是 bloomfilter hash 映射的具体实现
*/
private final Strategy strategy;
这是它的 4 个成员变量:
- LockFreeBitArray 是定义在
BloomFilterStrategies
中的外部类,封装了布隆过滤器底层 bit 数组的操作。 - numHashFunctions 示意哈希函数的个数。
- Funnel,它和 PrimitiveSink 配套应用,能将任意类型的对象转化成 Java 根本数据类型,默认用 java.nio.ByteBuffer 实现,最终均转化为 byte 数组。
-
Strategy 是定义在 BloomFilter 类外部的接口,代码如下,次要有 2 个办法,put 和 mightContain。
COPYinterface Strategy extends java.io.Serializable { /** 设置元素 */ <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits); /** 判断元素是否存在 */ <T> boolean mightContain(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits); ..... }
创立布隆过滤器,BloomFilter并没有私有的构造函数,只有一个公有构造函数,而对外它提供了 5 个重载的 create 办法,在缺省状况下误判率设定为 3%,采纳 BloomFilterStrategies.MURMUR128_MITZ_64 的实现。
BloomFilterStrategies.MURMUR128_MITZ_64是 Strategy 的两个实现之一,Guava 以枚举的形式提供这两个实现,这也是《Effective Java》书中举荐的提供对象的办法之一。
COPYenum BloomFilterStrategies implements BloomFilter.Strategy {MURMUR128_MITZ_32() {//....}
MURMUR128_MITZ_64() {//....}
}
二者对应了 32 位哈希映射函数,和 64 位哈希映射函数,后者应用了 murmur3 hash 生成的所有 128 位,具备更大的空间,不过原理是相通的,咱们抉择绝对简略的 MURMUR128_MITZ_32 来剖析。
先来看一下它的 put 办法,它用两个 hash 函数来模仿多个 hash 函数的状况,这是布隆过滤器的一种优化。
put 办法
COPYpublic <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {long bitSize = bits.bitSize();
// 先利用 murmur3 hash 对输出的 funnel 计算失去 128 位的哈希值,funnel 现将 object 转换为 byte 数组,// 而后在应用哈希函数转换为 long
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
// 依据 hash 值的高下位算出 hash1 和 hash2
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
boolean bitsChanged = false;
// 循环体内采纳了 2 个函数模仿其余函数的思维, 相当于每次累加 hash2
for (int i = 1; i <= numHashFunctions; i++) {int combinedHash = hash1 + (i * hash2);
// 如果是正数就变为负数
if (combinedHash < 0) {combinedHash = ~combinedHash;}
// 通过基于 bitSize 取模的形式获取 bit 数组中的索引,而后调用 set 函数设置。bitsChanged |= bits.set(combinedHash % bitSize);
}
return bitsChanged;
}
在 put 办法中,先是将索引地位上的二进制置为 1,而后用 bitsChanged 记录插入后果,如果返回 true 表明没有反复插入胜利,而 mightContain 办法则是将索引地位上的数值取出,并判断是否为 0,只有其中呈现一个 0,那么立刻判断为不存在。
mightContain 办法
COPYpublic <T> boolean mightContain(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {long bitSize = bits.bitSize();
long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {int combinedHash = hash1 + (i * hash2);
// Flip all the bits if it's negative (guaranteed positive number)
if (combinedHash < 0) {combinedHash = ~combinedHash;}
// 和 put 的区别就在这里,从 set 转换为 get,来判断是否存在
if (!bits.get(combinedHash % bitSize)) {return false;}
}
return true;
}
Guava 为了提供效率,本人实现了 LockFreeBitArray 来提供 bit 数组的无锁设置和读取。咱们只来看一下它的 put 函数。
COPYboolean set(long bitIndex) {if (get(bitIndex)) {return false;}
int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex
long oldValue;
long newValue;
// 经典的 CAS 自旋重试机制
do {oldValue = data.get(longIndex);
newValue = oldValue | mask;
if (oldValue == newValue) {return false;}
} while (!data.compareAndSet(longIndex, oldValue, newValue));
bitCount.increment();
return true;
}
Guava 布隆过滤器应用
引入坐标
COPY<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
代码实现
COPY
public class GuavaBloomFilter {
/**
* 设置布隆过滤器大小
*/
private static final int size = 100000;
/**
* 构建一个 BloomFilter
* 第一个参数 Funnel 类型的参数
* 第二个参数 冀望解决的数据量
* 第三个参数 误判率 可不加,默认 0.03D
*/
private static final BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), size);
public static void main(String[] args) {
// 胜利计数
float success = 0;
// 失败计数
float fial = 0;
Set<String> stringSet = new HashSet<String>();
for (int i = 0; i < size; i++) {
// 生成随机字符串
String randomStr = RandomStringUtils.randomNumeric(10);
// 退出到 set 中
stringSet.add(randomStr);
// 退出到布隆过滤器
bloomFilter.put(randomStr);
}
for (int i = 0; i < size; i++) {
// 生成随机字符串
String randomStr = RandomStringUtils.randomNumeric(10);
// 布隆过滤器校验存在
if (bloomFilter.mightContain(randomStr)) {
//set 中存在
if (stringSet.contains(randomStr)) {
// 胜利计数
success++;
} else {
// 失败计数
fial++;
}
// 布隆过滤器校验不存在
} else {
// set 中存在
if (stringSet.contains(randomStr)) {
// 失败计数
fial++;
} else {
// 胜利计数
success++;
}
}
}
System.out.println("判断胜利数:"+success + ",判断失败数:" + fial + ",误判率:" + fial / 100000);
}
输入
COPY 判断胜利数:97084.0,判断失败数:2916.0,误判率:0.02916
能够通过减少误判率的参数来调整误判率
COPY/**
* 构建一个 BloomFilter
* 第一个参数 Funnel 类型的参数
* 第二个参数 冀望解决的数据量
* 第三个参数 误判率 可不加,默认 0.03D
*/
private static final BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), size,0.00001);
输入
COPY 判断胜利数:100000.0,判断失败数:0.0,误判率:0.0
本文由
传智教育博学谷狂野架构师
教研团队公布。如果本文对您有帮忙,欢送
关注
和点赞
;如果您有任何倡议也可留言评论
或私信
,您的反对是我保持创作的能源。转载请注明出处!