10亿+的超链接，如何防止重复爬取？

阅读本文大概需要 3 分钟。

前段时间领导给了一个任务：编程实现对一个指定论坛的舆情监控，在所有帖子中找出含有公司相关名称的帖子，查看是否不良言论，防止舆情风险。

接到这样一个任务，内心是激动的，一方面这个任务是有点挑战性，另一方面学的 Python 爬虫技术终于有用武之地了。

关注我的朋友大多是 Python 初学者，这里我啰嗦下什么是爬虫。知道的可以绕过。爬虫这个词非常形象的描述了程序的行为，把网页看做一个网，一个个超链接就是网中的连接点，而程序就像蜘蛛一样在网上爬来爬去，不断的获取网页的信息，寻找自己的目标。一般情况下，我们使用浏览器来查看网站上的内容，看到感兴趣的，我们会收藏网页或者复制内容保存到笔记，但特殊情况下，为了提高效率，就借助编程来实现快速获取网页内容，这里获取网页内容的程序就是爬虫，爬虫没什么神秘的，就是代替人下载网页而已。

前段时间有公司因为爬虫被抓了，一时间谈虫色变，其实虫师完全不用担心，很多网站都是希望爬虫爬的，这样他们才有流量，搜索引擎本质也是爬虫，公开的信息，其实都可以爬，只要不是恶意攻击，爬虫完全是光明正大的，如果因为发现网站漏洞，爬取未经许可的信息，比如用户隐私信息，那就另说了。

扯多了，回归正题。一个有点规模的论坛，少说也得有 10 万+以上的帖子，无论你使用哪一个爬虫框架，无论是深度优先还是广度优先，无论是多线程还是协程，都会面临一个基本的问题，如果避免爬取已经爬过的网站？不解决这个问题，你的爬虫就没有停止的时候。

也就是说，你要把已经爬过的 URL(网址) 保存在一个地方，遇到新的 URL，再判断它是不是已经在已经保存的 URL 中，如果不是，再去爬取其内容，否则直接忽略。

很容易想到的方法就是，将爬过的 URL 保存到哈希表中，因为哈希表的查询时间复杂度是 O(1)，非常高效，在 Python 中，哈希表对应的数据结构有集合和字典，这里仅需要判断新的 URL 是否在哈希表中，因此使用集合就够了。集合还有一个非常好的功能，自动去重，也就是存入集合的 URL 不会有重复的，有了查询高效的哈希表，才可以继续进行下一步。

这里先预估下内存占用：

>>> import sys
>>> url = {"https://bbs.wjdaily.com/bbs/thread-727508-1-1.html"}
>>> sys.getsizeof(url)
224
>>> 10*10000*224/1024/1024
21.3623046875
>>>

从上面执行结果来看，10 万个类似的 URL 的内存占用也就在 20MB 多点，100 万个就是 200~300MB，内存消耗并不大，还可以接受。

内存占用不大，哈希表的查询效率又很快，此时就可以开始编码了，后半部分就是如何使用并发来提高网页的爬取速度了，这里不再展开讨论。

上述方法简单，有效，不易出错，在实际的开发工作中，这样已经足够了。但从提升自己技术量级的角度看，还远远不够，假如监控范围扩展到 n 个论坛，甚至一些非论坛，URL 量级到达 10 亿，那占用的内存就是 208 GB 以上，单纯采用哈希表来存储 URL 的做法已经不适用，有简单点的解决办法么？

此种情况下仍然有简单的解决办法，就是使用分治思想，准备 25 台每台 10 GB 内存的机器，对 10 亿个 URL 先数字化，再对 25 求余，映射到这 25 台机器上，相当于将 10 亿个 URL 分布在了 25 台机器上，查询一个 URL 是否存在时，仍先对 25 求余看看可能存在哪台机器，比如第 11 台，然后再去第 11 台的机器的哈希表中查询即可。

除了分治法，还有别的解决方法吗？当然有，问题是 URL 占用的字节太多导致的，假如 10 亿个 URL 能一一对应到 10 亿个整数，申请一个长度为 10 亿的数组 A，数组内存放 0 或者 1，0 代表该 URL 未被爬取过，1 代表已被爬取过。比如 URL 对应的整数为 1024，A[1024] = 0 就代表该 URL 未被爬取过，可以爬取。此种情况下，假如我们使用一个字节的整数，占用的内存为 10 亿个字节，也就是约 1 GB 左右的空间，而且通过数组下标的方式访问，查询速度极快。你可能会问 URL 怎么能对应到整数的？其实有很多哈希函数可以实现这样的功能，这里就不展开介绍了。

有没有更节省内存的方案？其实还是有的，上述方法存放一个字节的整数，仍然有点浪费，其实只需要一个二进制位就够了，二进制的 0 和 1 即可代表该 URL 是否被爬取过，因此，我们可以申请 10 亿个二进制位来替换上述的方法，只需要 120 MB 左右的空间，占用空间仅为原来的八分之一。这种方法就是位图操作。

位图是很常用的数据结构，通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。如果要对某个二进制位上操作，则要先获取到操作数组的第几个元素，再获取相应的位索引，然后执行操作。你可搜索关键词[Python 位图]来查询位图是如何编码实现的，不再赘述。

虽然内存占用的问题解决了，但是随着 URL 数量的增多，内存占用还是会线性增加，就算使用位图操作，100 亿个 URL 仍然要使用 1200 MB 的内存，有没有办法使内存的占用成为一个固定值？

当然方法仍然是有的，但资源是有限的，要么拿时间换空间，要么拿空间换时间，这里就需要牺牲一点时间来换取空间。假如我们只申请 10 亿个二进制位，现在有 100 亿的 URL ，那么通过哈希函数计算一次后会有冲突，比如 10 亿零 1 和 1 对 10 亿求余的结果都是 1 ，这就无法判断二进制位中的第一位是对应 10 亿零 1 还是 1，这里的解决办法就是多次哈希，比如有个 URL 经过一次哈希得到的二进制索引是第 x 位，第二次哈希得到 y 位，第二次哈希得到 z 位，那么 x,y,z 联合起来代表该 URL，如果 x,y,z 的二进制位均为 1，说明该 URL 被访问过。这就是布隆过滤器，当然这种方法也有缺点，那就是会出现小概率的误判，比如当查询该 URL 访问过时，可能实际上未访问过，但查询该 URL 未访问过时，就是真的未访问过，这种误判对于搜索引擎的场景来说是可以接受的，毕竟网页太多了，搜索引擎不可能百分之百爬取到。

对于布隆过滤器，你也不需要重复造轮子，pip install pybloom 就可以用了，该模块包含两个类实现布隆过滤器功能。BloomFilter 是定容。ScalableBloomFilter 可以自动扩容。

总结：

关于搜索引擎爬虫网页去重问题的解决，从哈希表到位图，再到布隆过滤器，每一步都有很大的空间占用优化。布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。除了爬虫网页去重这个例子，还有比如统计一个大型网站的每天的 UV 数，也就是每天有多少用户访问了网站，我们就可以使用布隆过滤器，对重复访问的用户，进行去重。

处理数据的量级，代表着技术的应用能力，做为一个有追求的工程师，我们要不断追问自己，能否处理更大量级的数据，能否在时间、空间上进一步优化，只有这样，才能不断精进。

（完）