基于Redis的Bloomfilter去重（附代码） - 文章 - 开发者社区

专栏作者简介

九茶

Python工程师，目前居于广州。Github知名开源爬虫 QQSpider 和 SinaSpider 作者，经常会在CSDN上分享一些爬虫、数据等福利。爬过的网站有 QQ空间、新浪微博、Facebook、Twitter、WooYun、Github、SearchCode、CSDN、博客园、天猫、大众点评、图吧网、域名与IP数据、证券投资数据、中国土地数据、某些政府网站等。除了爬虫领域之外，还会分享一些Python小应用（例如Python+PhantomJS批量注册账号，登录等），接下来在Python中文社区还会分享一些Python在大数据运算（ES、Spark）和数据挖掘方面的文章。

CSDN：http://blog.csdn.net/bone\_ace

Github： https://github.com/

liuxingming

前言

“去重”是日常工作中会经常用到的一项技能，在爬虫领域更是常用，并且规模一般都比较大。去重需要考虑两个点：去重的数据量、去重速度。为了保持较快的去重速度，一般选择在内存中进行去重。

数据量不大时，可以直接放在内存里面进行去重，例如python可以使用set()进行去重。
当去重数据需要持久化时可以使用redis的set数据结构。
当数据量再大一点时，可以用不同的加密算法先将长字符串压缩成16/32/40个字符，再使用上面两种方法去重；
当数据量达到亿（甚至十亿、百亿）数量级时，内存有限，必须用“位”来去重，才能够满足需求。Bloomfilter就是将去重对象映射到几个内存“位”，通过几个位的0/1值来判断一个对象是否已经存在。
然而Bloomfilter运行在一台机器的内存上，不方便持久化（机器down掉就什么都没啦），也不方便分布式爬虫的统一去重。如果可以在Redis上申请内存进行Bloomfilter，以上两个问题就都能解决了。

本文即是用Python，基于Redis实现Bloomfilter去重。下面先放代码，最后附上说明。

代码


      1. `# encoding=utf-8`
2. 
3. `import redis`
4. `from hashlib import md5`
5. 
6. 
7. `class SimpleHash(object):`
8. `def __init__(self, cap, seed):`
9. `self.cap = cap`
10. `self.seed = seed`
11. 
12. `def hash(self, value):`
13. `ret = 0`
14. `for i in range(len(value)):`
15. `ret += self.seed * ret + ord(value[i])`
16. `return (self.cap - 1) & ret`
17. 
18. 
19. `class BloomFilter(object):`
20. `def __init__(self, host='localhost', port=6379, db=0, blockNum=1, key='bloomfilter'):`
21. `"""`
22. `:param host: the host of Redis`
23. `:param port: the port of Redis`
24. `:param db: witch db in Redis`
25. `:param blockNum: one blockNum for about 90,000,000; if you have more strings for filtering, increase it.`
26. `:param key: the key's name in Redis`
27. `"""`
28. `self.server = redis.Redis(host=host, port=port, db=db)`
29. `self.bit_size = 1 << 31  # Redis的String类型最大容量为512M，现使用256M`
30. `self.seeds = [5, 7, 11, 13, 31, 37, 61]`
31. `self.key = key`
32. `self.blockNum = blockNum`
33. `self.hashfunc = []`
34. `for seed in self.seeds:`
35. `self.hashfunc.append(SimpleHash(self.bit_size, seed))`
36. 
37. `def isContains(self, str_input):`
38. `if not str_input:`
39. `return False`
40. `m5 = md5()`
41. `m5.update(str_input)`
42. `str_input = m5.hexdigest()`
43. `ret = True`
44. `name = self.key + str(int(str_input[0:2], 16) % self.blockNum)`
45. `for f in self.hashfunc:`
46. `loc = f.hash(str_input)`
47. `ret = ret & self.server.getbit(name, loc)`
48. `return ret`
49. 
50. `def insert(self, str_input):`
51. `m5 = md5()`
52. `m5.update(str_input)`
53. `str_input = m5.hexdigest()`
54. `name = self.key + str(int(str_input[0:2], 16) % self.blockNum)`
55. `for f in self.hashfunc:`
56. `loc = f.hash(str_input)`
57. `self.server.setbit(name, loc, 1)`
58. 
59. 
60. `if __name__ == '__main__':`
61. `""" 第一次运行时会显示 not exists!，之后再运行会显示 exists! """`
62. `bf = BloomFilter()`
63. `if bf.isContains('http://www.baidu.com'):   # 判断字符串是否存在`
64. `print 'exists!'`
65. `else:`
66. `print 'not exists!'`
67. `bf.insert('http://www.baidu.com')`

说明：

1、Bloomfilter算法如何使用位去重，这个百度上有很多解释。简单点说就是有几个seeds，现在申请一段内存空间，一个seed可以和字符串哈希映射到这段内存上的一个位，几个位都为1即表示该字符串已经存在。插入的时候也是，将映射出的几个位都置为1。

2、需要提醒一下的是Bloomfilter算法会有漏失概率，即不存在的字符串有一定概率被误判为已经存在。这个概率的大小与seeds的数量、申请的内存大小、去重对象的数量有关。下面有一张表，m表示内存大小（多少个位），n表示去重对象的数量，k表示seed的个数。例如我代码中申请了256M，即1<<31（m=2^31，约21.5亿），seed设置了7个。看k=7那一列，当漏失率为8.56e-05时，m/n值为23。所以n = 21.5/23=0.93(亿），表示漏失概率为8.56e-05时，256M内存可满足0.93亿条字符串的去重。同理当漏失率为0.000112时，256M内存可满足0.98亿条字符串的去重。

picture.image
3、基于Redis的Bloomfilter去重，其实就是利用了Redis的String数据结构，但Redis一个String最大只能512M，所以如果去重的数据量大，需要申请多个去重块（代码中blockNum即表示去重块的数量）。

4、代码中使用了MD5加密压缩，将字符串压缩到了32个字符（也可用hashlib.sha1()压缩成40个字符）。它有两个作用，一是Bloomfilter对一个很长的字符串哈希映射的时候会出错，经常误判为已存在，压缩后就不再有这个问题；二是压缩后的字符为 0~f 共16中可能，我截取了前两个字符，再根据blockNum将字符串指定到不同的去重块进行去重。

总结

基于Redis的Bloomfilter去重，既用上了Bloomfilter的海量去重能力，又用上了Redis的可持久化能力，基于Redis也方便分布式机器的去重。在使用的过程中，要预算好待去重的数据量，则根据上面的表，适当地调整seed的数量和blockNum数量（seed越少肯定去重速度越快，但漏失率越大）。

另外针对基于Scrapy+Redis框架的爬虫，我使用Bloomfilter作了一些优化，只需替换scrapy_redis模块即可使用Bloomfilter去重，并且去重队列和种子队列可以拆分到不同的机器上。

详情见 《scrapy_redis去重优化（已有7亿条数据），附Demo福利》 ：http://blog.csdn.net/bone\_ace/article/details/53099042

代码地址 ：https://github.com/LiuXingMing/Scrapy\_Redis\_Bloomfilter

点击阅读全文进入作者博客主页

picture.image