布隆过滤器在海量数据去重验证中应用

本文最后更新于:2024年7月6日 早上

引子

今天一个技术群里的小伙伴提了这样一个问题:

你爬虫的时候假如有海量的url,怎么保证不重复?

他说是之前在面试中遇到了这样的问题,大家第一时间想到的都差不多,用集合这种数据结构不久可以轻松的解决这个问题吗?

然而事情似乎没有这么简单,因为及时是存在Redis中,在海量数据的前提下,直接使用set作为数据存储来判断是否出现过,成本似乎比较高(内存条还是比较贵的。。。)

面试结束级方案——从数据库中取

爬虫每采集过一个 URL,就把这个 URL 存入数据库中,每次一个新的 URL 过来就到数据库查询下是否访问过。

1
select id from table where url = 'https://jaychen.cc'

但是随着爬虫爬过的 URL 越来越多,每次请求前都要访问数据库一次,并且对于这种字符串的 SQL 查询效率并不高。

新手级方案——利用redis的set数据结构

Redis 的 set 结构也可以满足这个需求,并且性能优于数据库,时间复杂度是O(1)。似乎一切都很美好,甚至还表现出了你对redis还是有一些了解的。但是 Redis 也存在一个问题:耗费过多的内存。

当这些问题中的海量,其实已经提示了,你必须想好如何应对这样的大数据。如果面试官提出了这样的问题,他显然不希望你只考虑到了,时间复杂度。

专业级方案——利用布隆过滤器

Ehgo59.jpg

OK,不闹了,不是上面这个布隆。

我们先看维基百科给出的解释

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

基本概念

如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为 O(n),O(log n),O(1)。

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

优点

相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数O(k)。另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集,其它任何数据结构都不能;

k和m相同,使用同一组散列函数的两个布隆过滤器的交并[来源请求]运算可以使用位操作进行。

缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

上面的专业解释看不懂?OK,下面有通俗的解释。

布隆过滤器的数据结构

布隆过滤器本质是一个位数组,位数组就是数组的每个元素都只占用 1 bit 。每个元素只能是 0 或者 1。这样申请一个 10000 个元素的位数组只占用 10000 / 8 = 1250 B 的空间。布隆过滤器除了一个位数组,还有 K 个哈希函数。当一个元素加入布隆过滤器中的时候,会进行如下操作:

  • 使用 K 个哈希函数对元素值进行 K 次计算,得到 K 个哈希值。
  • 根据得到的哈希值,在位数组中把对应下标的值置为 1。

假设布隆过滤器有 3 个哈希函数:f1, f2, f3 和一个位数组 arr。现在要把 https://jaychen.cc 插入布隆过滤器中:

  • 对值进行三次哈希计算,得到三个值 n1, n2, n3。
  • 把位数组中三个元素 arr[n1], arr[n2], arr[3] 置为 1。

当要判断一个值是否在布隆过滤器中,对元素再次进行哈希计算,得到值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么说明这个值在布隆过滤器中,如果存在一个值不为 1,说明该元素不在布隆过滤器中。

布隆过滤器的工作流程

布隆过滤器是一个 bit 向量或者说 bit 数组,长这样:

Ehqr9K.jpg

如果我们要映射一个值到布隆过滤器中,我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为:

Ehqs1O.jpg

Ok,我们现在再存一个值 “tencent”,如果哈希函数返回 3、4、8 的话,图继续变为:

EhqBh6.jpg

值得注意的是,4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位,因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在,哈希函数返回了 1、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话,那么哈希函数必然会返回 1、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “baidu” 存在了么?答案是不可以,只能是 “baidu” 这个值可能存在。

这是为什么呢?答案跟简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。

布隆过滤器的优缺点

看了上面的说明,必然会提出一个问题:当插入的元素原来越多,位数组中被置为 1 的位置就越多,当一个不在布隆过滤器中的元素,经过哈希计算之后,得到的值在位数组中查询,有可能这些位置也都被置为 1。这样一个不存在布隆过滤器中的也有可能被误判成在布隆过滤器中。但是如果布隆过滤器判断说一个元素不在布隆过滤器中,那么这个值就一定不在布隆过滤器中。简单来说:

  • 布隆过滤器说某个元素在,可能会被误判。
  • 布隆过滤器说某个元素不在,那么一定不在。

这个布隆过滤器的缺陷放到上面爬虫的需求中,可能存在某些没有访问过的 URL 可能会被误判为访问过,但是如果是访问过的 URL 一定不会被误判为没访问过。

Redis 中的布隆过滤器

redis 在 4.0 的版本中加入了 module 功能,布隆过滤器可以通过 module 的形式添加到 redis 中,所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器。但是这不是最简单的方式,使用 docker 可以直接在 redis 中体验布隆过滤器。

1
2
3
> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli
复制代码

redis 布隆过滤器主要就两个命令:

  • bf.add 添加元素到布隆过滤器中:bf.add urls https://jaychen.cc
  • bf.exists 判断某个元素是否在过滤器中:bf.exists urls https://jaychen.cc

上面说过布隆过滤器存在误判的情况,在 redis 中有两个值决定布隆过滤器的准确率:

  • error_rate:允许布隆过滤器的错误率,这个值越低过滤器的位数组的大小越大,占用空间也就越大。
  • initial_size:布隆过滤器可以储存的元素个数,当实际存储的元素个数超过这个值之后,过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值:

1
2
bf.reserve urls 0.01 100
复制代码

三个参数的含义:

  • 第一个值是过滤器的名字。
  • 第二个值为 error_rate 的值。
  • 第三个值为 initial_size 的值。

使用这个命令要注意一点:执行这个命令之前过滤器的名字应该不存在,如果执行之前就存在会报错:(error) ERR item exists

参考资料

jaychen:https://juejin.im/post/5bc7446e5188255c791b3360

Young Chenhttps://zhuanlan.zhihu.com/p/43263751

维基百科:https://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8


布隆过滤器在海量数据去重验证中应用
https://yance.wiki/布隆过滤器/
作者
Yance Huang
发布于
2019年6月23日
许可协议