本期我们来聊聊URL去重那些事儿。以前我们曾使用Python的字典来保存抓取过的URL，目的是将重复抓取的URL去除，避免多次抓取同一网页。爬虫会将待抓取的URL放在todo队列中，从抓取到的网页中提取到新的URL，在它们被放入队列之前，首先要确定这些新的URL是否被抓取过，如果之前已经抓取过了，就不再放入队列。
有别于单机系统，在分布式系统中，这些URL应该存放在公共缓存中，才能让多个爬虫实例共享，我们继续使用Redis缓存这些数据。URL既可以存储在Redis的Set数据结构中，也可以将URL作为Key存储为Redis的String类型。至于这两种方案各有什么优缺点，就留给读者自己去思考了
直接存储URL
将URL以字符串的形式直接存储到内存中。保守估计一下URL的平均长度是100字节，那么1亿个URL所占的内存是: 100000000 * 0.0001MB = 10000MB，约等于10G。这也不是不能用，占用的空间再大都能通过扩容来解决。
问题是，如果一个服务器存不下这么多URL该怎么办呢？其实也简单，明确每台服务器的分工，也就是说得到一个URL就知道要交给哪台服务器存储，每台服务器只存储一类URL，比较简单的实现方式就是对URL先哈希再取模。虽然能用，但还是有很大优化空间的。
存储消息摘要
MD5是一个消息摘要算法，它的用途很广泛，我们这里用它来压缩URL。
消息摘要算法的特点：
无论输入的消息有多长，计算出来的消息摘要的长度总是固定的。 只要输入的消息不同，对其进行摘要以后产生的摘要消息也必不相同；但相同的输入必会产生相同的输出。 消息摘要是单向、不可逆的。只能进行正向的信息摘要，而无法从摘要中恢复出任何的原始消息。 以上特点说明我们可以通过存储URL的MD5来实现去重功能，因为不同的URL，MD5不同，相同的URL，MD5相同嘛。
以前我们要存的URL是这样的：http://news.baidu.com/ns?ct=1&rn=20&ie=utf-8&bs=%E4%BA%AC%E4%B8%9C%E9%87%91%E8%9E%8D&rsv_bp=1&sr=0&cl=2&f=8&prevct=no&tn=news&word=%E4%BA%AC%E4%B8%9C%E9%87%91%E8%9E%8D&rsv_sug3=1&rsv_sug4=6&rsv_sug1=1&rsv_sug=1
对应的MD5值是这样的：d552b0b40e21d06d73a1a0938635eb1a
怎么样？省了不少空间吧？
有人说，拓海你不要骗我，这个算法的输入是个无穷集合，而输出是一个有限集合，必然会存在碰撞的，也就是存在不同的URL算出相同的MD5。这会导致去重时误判，少抓数据！
好吧，从理论上来说，必然会出现这种情况。可是出现这种情况的概率是多少呢？下面就算算两个不同URL产生相同消息摘要的概率。
以下是三种常见的消息摘要算法，分别是32、64、128字节，每个字节是十六进制数字的字符，它们的可能值数量分别是：
md5: 16^32 = 2^128 = 3.4 * 10^38
sha256: 16^64 = 2^256 = 1.2 × 10^77
sha512: 16^128 = 2^512 = 1.3 × 10^154
可见，不同URL产生相同消息摘要的可能性非常小，简直像大海捞针。。。不是，简直像宇宙中捞原子一样难，所以就放心使用吧。
消息摘要实现了对URL的压缩，但压缩后的大小还是和原来在一个数量级，空间效率并没有质的提升。有没有办法只用几个bit来唯一标识一个URL呢？有！布隆过滤器就是专门解决这类问题的
布隆过滤器
Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。
它的原理很简单，首先需要准bit数组（所有位初始化为0）和k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，否则不存在。很明显这个过程并不保证查找的结果是100%正确的。
如何根据输入元素个数n，确定bit数组m的大小及hash函数个数呢？当hash函数个数k=(ln2)(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于nlg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge ，大概就是nlg(1/E)的1.44倍。假设错误率为0.01，则此时m应是n的13倍。这样k大概是8个。
下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。
为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。
在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive。
关于bloom算法，更多详情请参考 传送门