过滤豆瓣租房小组中介贴之 python 实现 布隆过滤器(三)

其实这篇文章跟过滤中介贴没什么关系,只是在爬豆瓣小组的时候遇到的一点思考,我们知道,其实爬虫就是循环的爬取网站的 url,但是怎么判断爬取的 url 是否重复呢,最简单的,维护一个列表,每次循环查找,很明显效率很低。进阶的,采用哈希表,每次查询都是 O(1), 看上去不错。不过如果一旦 url 大到一定程度时,单台机器的内存肯定吃不消,这个时候分布式方案就呼之欲出,变得越来越复杂。那么能不能在牺牲一点点精确性的前提下,有简单的方案呢,答案是肯定的。这就是 布隆过滤器。

布隆过滤器的原理是,当一个元素被加入集合时,通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点,把它们置为1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:如果这些点有任何一个 0 ,则被检元素一定不在;如果都是 1 ,则被检元素很可能在。这就是布隆过滤器的基本思想。(引用自维基百科)。布隆过滤器可以看成是 bitmap 的扩展,它的优点是空间和时间复杂度都是常数,缺点是有一定的误算率。
具体还可以参考:https://segmentfault.com/a/1190000002729689
维基百科

我们写爬虫很多时候会使用 redis 作为各种队列来提高性能。同样,这次我们将用 redis 和 python 结合起来写个布隆过滤器。

首先需要实现一个求 hash 的函数,这里采用 murmurhash 算法。然后算出 k 个点的位置(这里是 7 个点)。

1
2
3
4
5
6
BIT_SIZE = 5000000
SEEDS = [50, 51, 52, 53, 54, 55, 56]
def cal_offsets(self, content):
return [mmh3.hash(content, seed) % BIT_SIZE for seed in SEEDS]

接下来就是 insert 和 is_contains 方法

1
2
3
4
5
6
7
8
9
10
11
12
def insert(self, content):
locs = self.cal_offsets(content)
for loc in locs:
self.db.setbit(self.key, loc, 1)
def is_contains(self, content):
if not content:
return False
locs = self.cal_offsets(content)
return all(True if self.db.getbit(self.key, loc) else False for loc in locs)

在 is_contains 方法中,我们用了 any 这个函数,是因为只要 k 个点有一个不为 1 元素就不存在。当然,就算是都为 1,也会由于小概率的哈希冲突存在一定的误差,这个在前面说明过。

代码见 github : https://github.com/facert/BloomFilterForRedis

这里面其实还有很多细节,比如 redis setbit 的时候可以采用 pipeline 来批量操作,另外对于 redis string 来说,最大是 512M,如果超过这个大小会阻塞 redis 服务器做一个再次分配内存的操作,需要尽量避免,可以采用分配多个 string 的方式。

最后,redis bitmaps 操作可以用于统计数据的实时计算,非常节省空间。感兴趣的可以看下这篇文章: http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/