爬虫url去重策略
爬虫url去重策略
1、将访问过的url保存到数据库中
最简单的方式,但是用的很少
2、将访问过的url保存到内存(set)中,只需要O(1)的代价就可以查询url
这样内存的占用会越来越大。
当有1亿条url时,假设每个url占用50个字符(这是保守估计了),
100000000*2byte*50个字符/1024/1024/1024=9G
即当url有1亿条的时候,就会占用9G内存
然而,对于小型爬虫来说,1亿条数据并不算多
3、url经过md5等方法哈希后保存到set中
md5编码可以将字符缩减到固定的长度
比如md5一般的编码长度时128bit=16byte,即一个url占用16byte,而前面2的方式占用的时50*2=100byte
相当于进行了成倍的压缩,所以占用的内存也会成倍下降
scrapy采用的就是这个方式
4、用bitmap方法,将访问过的url通过hash函数映射到某一位
但是bitmap的哈希冲突会比较大,所以这种方法用的也是比较少的
5、bloomfilter方法对bitmap进行改进,多重hash函数降低冲突
采用哈希的话,1亿个url对应1 000000000bit=1000000000/8byte=12500000byte=12500000/1024 KB=12207 KB
=12207/1024 MB = 12M
所以理想情况下1亿个url用哈希的话占用内存12M,当时实际肯定要比这个大,因为会有很多冲突,但是不论怎么大也会比前几种好几个G的要好太多