使用bloomfilter实现亿级别爬虫url链接去重对比

这边的爬虫系统又出现了一些个瓶颈。由于网络间的链接错综复杂,蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道蜘蛛已经访问过那些URL。一开始我们首先排除掉了set集合,虽然set集合比数组类型的list。但是内存占用的大小,和几十亿条数据对比的时候,还是很出现性能的瓶颈 。 


这个时候大家可以用bitmap和bloomfilter来做高效的处理。 bitmap 其实和bloomfilter很像,但是他的冲突率要比bloomfilter要高 。 


Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。


bloomfilter和bitmap都不能做删除的, 你要是有删除的需求,可以用bloomfilter的加强版,cbf    ~

我们现在已经把bloomfilter用上了,性能上和内存消耗上有长足的进步。 



对Golang感兴趣的朋友可以加群: 278517979 !!!
另外如果大家觉得文章对你有些作用! 如果想赏钱,可以用微信扫描下面的二维码, 感谢!
另外再次标注博客原地址  xiaorui.cc

4 Responses

  1. go 2014年11月15日 / 上午8:23

    写的不错

  2. SA 2014年9月15日 / 下午6:21

    take me , big god!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">