本文主要介绍“如何在Redis中实现布隆过滤器”。在日常操作中,相信很多人对于如何在Redis中实现Bloom过滤器有疑问。边肖查阅了各种资料,整理出简单易用的操作方法,希望能帮助大家解答“如何在Redis中实现Bloom滤镜”的疑惑!接下来,请和边肖一起学习!
概述
Bloom Filter是一种数据结构,由Burton Howard Bloom在1970年提出。它实际上是一个很长的二进制向量和一系列随机映射函数。【相关推荐:Redis视频教程】
布隆过滤器可以用于高效的检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远优于一般的算法,缺点是有一定的误识别率,而且难以删除(一般不支持,需要额外的实现)。
差错率是指可以判断该元素肯定不在集合中,该元素可能在集合中,不能判断该元素一定在集合中。
布隆过滤器之所以高效,因为它是一个概率数据结构,它能确认元素肯定不在集合中,或者元素可能在集合中。之所以说是可能,是因为它有一定的误识别率,使得无法 100% 确定元素一定在集合中。
00-1010在日常工作中,通常需要确定一个元素是否在集合中。例如,以下场景
给定一个IP黑名单库,检查指定的IP是否在黑名单中。
当收到邮件时,你能确定一个电子邮件地址是否是垃圾邮件吗?
在文字处理软件中,检查一个英语单词是否拼写正确。
遇到这种问题时,直觉通常会告诉我们,要用集合的数据结构来实现。例如,首先将IP黑名单库中的所有IP存储在一个集合中,然后将指定的IP带到集合中检查是否存在,如果存在,则表示该IP命中黑名单。
通过一段代码来模拟IP黑名单库的存储和检查。
publicclassIPBlackList黑名单{
publicationstativitmain(String[]args){ 0
SetStringset=new hashset();
set . add(' 192 . 168 . 1 . 1 ');
set . add(' 192 . 168 . 1 . 2 ');
set . add(' 192 . 168 . 1 . 4 ');
system . out . println(set . contains(' 192 . 168 . 1 . 1 '));
system . out . println(set . contains(' 192 . 168 . 1 . 2 '));
system . out . println(set . contains(' 192 . 168 . 1 . 3 '));
system . out . println(set . contains(' 192 . 168 . 1 . 4 '));
}
}集合的内部,通常是使用散列表来实现。其优点是查询非常高效,缺点是比较耗费存储空间。
通常,当数据量相对较少时,我们会使用集合进行存储。以空间换时间,占用空间少的同时,可以提高查询效率。
然而,当存储的数据量相对较大时,消耗大量空间将是一个问题。因为这些数据通常存储在进程内存中,以加快查询效率。机器的内存通常是有限的,应该尽可能高效地使用。
另一方面,哈希表需要在空间和效率上达到平衡。如果存储相同数量的元素,哈希表容量越小,冲突的概率越高,解决冲突的时间越长,从而影响性能。
布隆过滤器的出现可以很好地解决这个问题。一方面,它可以用更少的内存存储数据,另一方面,它可以实现非常高效的查询性能。
00-1010首先,构建一个二进制向量,并将所有位设置为0。
然后,选择k个散列函数对元素进行k次散列,并计算向量的位索引。
00-1010当一个元素被添加到集合中时,k个散列函数分别被应用到该元素,
生成 K 个值作为下标,并对向量的相应位设置为 1。
检查元素
如果要检查一个元素是否存在集合中,用同样的散列方法,生成 K 个下标,并检查向量的相应位是否全部是 1。
如果全为 1,则该元素很可能在集合中;否则(只要有1个或以上的位为0),该元素肯定不在集合中。
Demo
-
假设有一个布隆过滤器,容量是15位,使用2个哈希函数,如下所示。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|0|||||||||||||||||||
-
添加一个字符串
a
,2次哈希得到下标为 4 和 10,将 4 和 10 对应的位由 0 标记为 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|||||||||
-
再添加一个字符串
b
,2 次哈希得到下标为 11,将 11 对应的位由 0 标记为 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|1||||||||
-
再添加一个字符串
c
,2 次哈希得到下标为 11 和 12,将对应的位由 0 标记为 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|||||1||||||1|1|1|||||||
-
最后添加一个字符串
sam
,2 次哈希得到下标为 0 和 7,将对应的位由 0 标记为 1。
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|1||||1|||1|||1|1|1|||||||
上面,我们添加了 4 个字符串,每个字符串分别进行 2 次哈希,对应的2个位标记为1,最终被标记为1的共有6位而不是8位。
这说明,不同的元素,哈希后得到的位置是可能出现重叠的。如果元素越多,出现重叠的概率会更高。如果有2个元素出现重叠的位置,我们是无法判断任一元素一定在集合中的。
如果要检查一下元素是否存在集合中,只需要以相同的方法,进行 2 次哈希,将得到的 2 个下标在布隆过滤器中的相应位进行查找。如果对应的 2 位不是全部为1,则该元素肯定不在集合中。如果对应的 2 位全部为1,则说明该元素可能在集合中,也可能不存在。
例如,检查字符串 b
是否存在集合中,哈希得到的 2 个下标都为11。检查发现,11对应的位为1。但是,这并不能说明 b
一定在集合中。这是因为,字符串 c
哈希后的下标也包含11,有可能只是字符串c在集合中,而 b
却不存在,这就是造成了误识别,也称为假阳性。
再检查字符串 foo
,哈希得到的下标分别为 8 和 13,对应的位都为0。因此,字符串 foo
肯定不在集合中。
数学原理
布隆过滤器背后的数学原理是
两个完全随机的数字相冲突的概率很小,因此可以在很小的误识别率条件下,用很少的空间存储大量信息。
误识别率
误识别率(FPP
,false positive probabilistic
)的计算如下。
假设布隆过滤器大小为 m
比特,存储了 n
个元素,使用 k
次散列函数来计算元素的存储位置。
-
添加 1 个元素,则任一比特为 1 的概率为
1/m
,任一比特为 0 的概率为1-1/m
; -
添加 1 个元素,执行 k 次散列之后,则任一比特为 0 的概率为
(1-1/m)^k
,任一比特为 1 的概率为1-(1-1/m)^k
; -
如果添加 n 个元素,那么任一比特为 0 的概率为
(1-1/m)^kn
,任一比特为 1 的概率为1-(1-1/m)^kn
; -
如果将 1 个新的元素,添加到已存在
n
个元素的布隆过滤器中,则任一比特已经为 1 的概率与上面相同,概率为1-(1-1/m)^kn
。因此,k 个比特都为1的概率为:(1-(1-1/m)^kn)^k
,此即为新插入元素的误识别率。
当 n 值比较大时,$(1-(1-1/m)^{kn})^k$
约等于 $(1-e^{-kn/m})^k$
假定布隆过滤器大小 m
为 16 比特,k为 8,存储元素 n
为1,那么误识别(假阳性)的概率是万分之五(5/10000)。
此时,m/n=16
,事实上这表示 1个元素使用 16 个比特的空间来存储。
因此,当 k
相同时,m/n
为 16/1、32/2、64/4 等值时具有相同的误识别率。
网站 Bloom Filters - the math 给出了布隆过滤器的误识别率表,可以很方便的查处不同 m
,n
,k
给定值下的误识别率。
解决误识别率
解决误识别率的常用方法包括
-
白名单
-
回溯确认
白名单
解决误识别率的常见方法,是建立一个较小的白名单,用来存储那些可能被误识别的数据。
以垃圾邮件过滤为例。假设我们有一个垃圾邮件库,用于在接收邮件的时候过滤掉垃圾邮件。
这时可以先将这个垃圾邮件库存储到布隆过滤器中,当接收到邮件的时候,可以先通过布隆过滤器高效的过滤出大部分正常邮件。
而对于少部分命中(可能为)垃圾邮件的,其中有一部分可能为正常邮件。
再创建一个白名单库,当在布隆过滤器中判断可能为垃圾邮件时,通过查询白名单来确认是否为正常邮件。
对于没在白名单中的邮件,默认会被移动到垃圾箱。通过人工识别的方式,当发现垃圾箱中存在正常邮件的时候,将其移入白名单。
回源确认
很多时候,使用布隆过滤器是为了低成本,高效率的拦截掉大量数据不在集合中的场景。例如
-
Google Bigtable,Apache HBase以及Apache Cassandra和PostgreSQL 使用 Bloom 过滤器来减少对不存在的行或列的磁盘查找。避免进行昂贵的磁盘查找,可大大提高数据库查询操作的性能。
-
在谷歌浏览器用于使用布隆过滤器来识别恶意URL的网页浏览器。首先会针对本地 Bloom 过滤器检查所有 URL,只有在 Bloom 过滤器返回肯定结果的情况下,才对执行的 URL 进行全面检查(如果该结果也返回肯定结果,则用户会发出警告)。
-
拦截掉大量非IP黑名单请求,对于少量可能在黑名单中的IP,再查询一次黑名单库。
这是布隆过滤器非常典型的应用场景,先过滤掉大部分请求,然后只处理少量不明确的请求。
这个方法,和白名单库的区别是,不需要再另外建立一套库来处理,而是使用本来就已经存在的数据和逻辑。
例如 Google Bigtable 查询数据行本来就是需要查的,只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的,同样是先使用布隆过滤器来拦截掉大部分IP。
而上面垃圾邮件的处理,对于可能为垃圾邮件的情况,不是通过完整的垃圾邮件库再查询一次进行确认,而是用增加白名单来进行判断的方式。因为通常来说,白名单库会更小,便于缓存。
这里所说的回源,实际上是对可能被误识别的请求,最后要回到数据源头或逻辑确认一次。
Guava中的布隆容器的实现
Guava 中就提供了一种 Bloom Filter 的实现。
guava包引入
要使用 Bloom Filter,需要引入 guava 包
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>23.0</version> </dependency>
误判率测试
下面对布隆容器的误判率进行测试,分2步
-
往过滤器中放一百万个数,然后去验证这一百万个数是否能通过过滤器
-
另外找一万个数,去检验漏网之鱼的数量
/** * 测试布隆过滤器(可用于redis缓存穿透) * * @author 敖丙 */ public class TestBloomFilter { private static int total = 1000000; private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total); // private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001); public static void main(String[] args) { // 初始化1000000条数据到过滤器中 for (int i = 0; i < total; i++) { bf.put(i); } // 匹配已在过滤器中的值,是否有匹配不上的 for (int i = 0; i < total; i++) { if (!bf.mightContain(i)) { System.out.println("有坏人逃脱了~~~"); } } // 匹配不在过滤器中的10000个值,有多少匹配出来 int count = 0; for (int i = total; i < total + 10000; i++) { if (bf.mightContain(i)) { count++; } } System.out.println("误伤的数量:" + count); } }
运行结果
误伤的数量:320
运行结果表示,遍历这一百万个在过滤器中的数时,都被识别出来了。一万个不在过滤器中的数,误伤了320个,错误率是0.03左右。
Bloom Filter 源码分析
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) { return create(funnel, (long) expectedInsertions); } public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) { return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions } public static <T> BloomFilter<T> create( Funnel<? super T> funnel, long expectedInsertions, double fpp) { return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64); } static <T> BloomFilter<T> create( Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) { ...... }
Bloom Filter 一共四个 create
方法,不过最终都是走向第4个。看一下每个参数的含义
-
funnel
:数据类型(一般是调用Funnels工具类中的) -
expectedInsertions
:期望插入的值的个数 -
fpp
: 错误率(默认值为0.03) -
strategy
: 哈希算法 Bloom Filter的应用
到此,关于“Redis中的布隆过滤器怎么实现”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注网站,小编会继续努力为大家带来更多实用的文章!
内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/155990.html