海量数据处理以及缓存穿透这两个场景让我意识了 布隆过滤器,我查阅了一些材料来理解它,然而很多现成材料并不满足我的需要,所以就决定本人总结一篇对于布隆过滤器的文章。心愿通过这篇文章让更多人理解布隆过滤器,并且会理论去应用它!
上面咱们将分为几个方面来介绍布隆过滤器:
- 什么是布隆过滤器?
- 布隆过滤器的原理介绍。
- 布隆过滤器应用场景。
- 通过 Java 编程手动实现布隆过滤器。
- 利用 Google 开源的 Guava 中自带的布隆过滤器。
- Redis 中的布隆过滤器。
1. 什么是布隆过滤器?
首先,咱们须要理解布隆过滤器的概念。
布隆过滤器(Bloom Filter)是一个叫做 Bloom 的老哥于 1970 年提出的。咱们能够把它看作由二进制向量(或者说位数组)和一系列随机映射函数(哈希函数)两局部组成的数据结构。相比于咱们平时罕用的的 List、Map、Set 等数据结构,它占用空间更少并且效率更高,然而毛病是其返回的后果是概率性的,而不是十分精确的。实践状况下增加到汇合中的元素越多,误报的可能性就越大。并且,寄存在布隆过滤器的数据不容易删除。
位数组中的每个元素都只占用 1 bit,并且每个元素只能是 0 或者 1。这样申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间。
总结:一个名叫 Bloom 的人提出了一种来检索元素是否在给定大汇合中的数据结构,这种数据结构是高效且性能很好的,但毛病是具备肯定的谬误识别率和删除难度。并且,实践状况下,增加到汇合中的元素越多,误报的可能性就越大。
2. 布隆过滤器的原理介绍
当一个元素退出布隆过滤器中的时候,会进行如下操作:
- 应用布隆过滤器中的哈希函数对元素值进行计算,失去哈希值(有几个哈希函数失去几个哈希值)。
- 依据失去的哈希值,在位数组中把对应下标的值置为 1。
当咱们须要判断一个元素是否存在于布隆过滤器的时候,会进行如下操作:
- 对给定元素再次进行雷同的哈希计算;
- 失去值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么阐明这个值在布隆过滤器中,如果存在一个值不为 1,阐明该元素不在布隆过滤器中。
举个简略的例子:
如图所示,当字符串存储要退出到布隆过滤器中时,该字符串首先由多个哈希函数生成不同的哈希值,而后在对应的位数组的下表的元素设置为 1(当位数组初始化时,所有地位均为 0)。当第二次存储雷同字符串时,因为先前的对应地位已设置为 1,所以很容易晓得此值曾经存在(去重十分不便)。
如果咱们须要判断某个字符串是否在布隆过滤器中时,只须要对给定字符串再次进行雷同的哈希计算,失去值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么阐明这个值在布隆过滤器中,如果存在一个值不为 1,阐明该元素不在布隆过滤器中。
不同的字符串可能哈希进去的地位雷同,这种状况咱们能够适当减少位数组大小或者调整咱们的哈希函数。
综上,咱们能够得出:布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不在,那么这个元素肯定不在。
3. 布隆过滤器应用场景
- 判断给定数据是否存在:比方判断一个数字是否存在于蕴含大量数字的数字集中(数字集很大,5 亿以上!)、避免缓存穿透(判断申请的数据是否无效防止间接绕过缓存申请数据库)等等、邮箱的垃圾邮件过滤、黑名单性能等等。
- 去重:比方爬给定网址的时候对曾经爬取过的 URL 去重。
4. 通过 Java 编程手动实现布隆过滤器
咱们下面曾经说了布隆过滤器的原理,晓得了布隆过滤器的原理之后就能够本人手动实现一个了。
如果你想要手动实现一个的话,你须要:
- 一个适合大小的位数组保留数据
- 几个不同的哈希函数
- 增加元素到位数组(布隆过滤器)的办法实现
- 判断给定元素是否存在于位数组(布隆过滤器)的办法实现。
上面给出一个我感觉写的还算不错的代码(参考网上已有代码改良失去,对于所有类型对象皆实用):
import java.util.BitSet;
public class MyBloomFilter {
/**
* 位数组的大小
*/
private static final int DEFAULT_SIZE = 2 << 24;
/**
* 通过这个数组能够创立 6 个不同的哈希函数
*/
private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};
/**
* 位数组。数组中的元素只能是 0 或者 1
*/
private BitSet bits = new BitSet(DEFAULT_SIZE);
/**
* 寄存蕴含 hash 函数的类的数组
*/
private SimpleHash[] func = new SimpleHash[SEEDS.length];
/**
* 初始化多个蕴含 hash 函数的类的数组,每个类中的 hash 函数都不一样
*/
public MyBloomFilter() {
// 初始化多个不同的 Hash 函数
for (int i = 0; i < SEEDS.length; i++) {func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
}
}
/**
* 增加元素到位数组
*/
public void add(Object value) {for (SimpleHash f : func) {bits.set(f.hash(value), true);
}
}
/**
* 判断指定元素是否存在于位数组
*/
public boolean contains(Object value) {
boolean ret = true;
for (SimpleHash f : func) {ret = ret && bits.get(f.hash(value));
}
return ret;
}
/**
* 动态外部类。用于 hash 操作!*/
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
/**
* 计算 hash 值
*/
public int hash(Object value) {
int h;
return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
}
}
}
测试:
String value1 = "https://javaguide.cn/";
String value2 = "https://github.com/Snailclimb";
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
Output:
false
false
true
true
测试:
Integer value1 = 13423;
Integer value2 = 22131;
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
Output:
false
false
true
true
5. 利用 Google 开源的 Guava 中自带的布隆过滤器
本人实现的目标次要是为了让本人搞懂布隆过滤器的原理,Guava 中布隆过滤器的实现算是比拟权威的,所以理论我的项目中咱们不须要手动实现一个布隆过滤器。
首先咱们须要在我的项目中引入 Guava 的依赖:
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
理论应用如下:
咱们创立了一个最多寄存 最多 1500 个整数的布隆过滤器,并且咱们能够容忍误判的概率为百分之(0.01)
// 创立布隆过滤器对象
BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(),
1500,
0.01);
// 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素增加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
在咱们的示例中,当 mightContain()
办法返回true 时,咱们能够 99%确定该元素在过滤器中,当过滤器返回 false 时,咱们能够 100%确定该元素不存在于过滤器中。
Guava 提供的布隆过滤器的实现还是很不错的(想要具体理解的能够看一下它的源码实现),然而它有一个重大的缺点就是只能单机应用(另外,容量扩大也不容易),而当初互联网个别都是分布式的场景。为了解决这个问题,咱们就须要用到 Redis 中的布隆过滤器了。
6.Redis 中的布隆过滤器
[](https://github.com/Snailclimb…
Redis v4.0 之后有了 Module(模块 / 插件)性能,Redis Modules 让 Redis 能够应用内部模块扩大其性能。布隆过滤器就是其中的 Module。详情能够查看 Redis 官网对 Redis Modules 的介绍:https://redis.io/modules
另外,官网举荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module, 地址:https://github.com/RedisBloom/RedisBloom. 其余还有:
- redis-lua-scaling-bloom-filter(lua 脚本实现):https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
- pyreBloom(Python 中的疾速 Redis 布隆过滤器):https://github.com/seomoz/pyreBloom
- 《2020 最新 Java 根底精讲视频教程和学习路线!》
- ……
RedisBloom 提供了多种语言的客户端反对,包含:Python、Java、JavaScript 和 PHP。
6.2 应用 Docker 装置
如果咱们须要体验 Redis 中的布隆过滤器非常简单,通过 Docker 就能够了!咱们间接在 Google 搜寻docker redis bloomfilter 而后在排除广告的第一条搜素后果就找到了咱们想要的答案(这是我平时解决问题的一种形式,分享一下),具体地址:https://hub.docker.com/r/redislabs/rebloom/(介绍的很具体)。
具体操作如下:
➜ ~ docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
➜ ~ docker exec -it redis-redisbloom bash
root@21396d02c252:/data# redis-cli
127.0.0.1:6379>
6.3 常用命令一览
留神:key: 布隆过滤器的名称,item : 增加的元素。
BF.ADD
:将元素增加到布隆过滤器中,如果该过滤器尚不存在,则创立该过滤器。格局:BF.ADD {key} {item}
。BF.MADD
: 将一个或多个元素增加到“布隆过滤器”中,并创立一个尚不存在的过滤器。该命令的操作形式BF.ADD
与之雷同,只不过它容许多个输出并返回多个值。格局:BF.MADD {key} {item} [item ...]
。BF.EXISTS
: 确定元素是否在布隆过滤器中存在。格局:BF.EXISTS {key} {item}
。BF.MEXISTS
:确定一个或者多个元素是否在布隆过滤器中存在格局:BF.MEXISTS {key} {item} [item ...]
。
另外,BF.RESERVE
命令须要独自介绍一下:
这个命令的格局如下:
BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]
。
上面简略介绍一下每个参数的具体含意:
- key:布隆过滤器的名称
- error_rate : 误报的冀望概率。这应该是介于 0 到 1 之间的十进制值。例如,对于冀望的误报率 0.1%(1000 中为 1),error_rate 应该设置为 0.001。该数字越靠近零,则每个我的项目的内存耗费越大,并且每个操作的 CPU 使用率越高。
- capacity: 过滤器的容量。当理论存储的元素个数超过这个值之后,性能将开始降落。理论的降级将取决于超出限度的水平。随着过滤器元素数量呈指数增长,性能将线性降落。
可选参数:
- expansion:如果创立了一个新的子过滤器,则其大小将是以后过滤器的大小乘以
expansion
。默认扩大值为 2。这意味着每个后续子过滤器将是前一个子过滤器的两倍。
6.4 理论应用
127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0