如何下载互联网上的所有网页

叁歲伎倆 2022-04-24 13:04 262阅读 0赞

本文是学习吴军的课程《谷歌方法论》的总结。

如何构建一个网络爬虫，下载互联网上的全部网页？

简单的回答是：“整个互联网是彼此相连的，从任何一个网页出发，获取网页上的超链接，采用深度优先搜索（DFS）或者广度优先搜索（BFS），就可以下载全部网页。”

这种回答没有错，但仅仅理解到这一步，是无法构建起一个实用的网络爬虫。在工程中有许多实际问题需要讨论。

首先，互联网非常庞大，Google的索引中有超过1万亿个网页，更新最频繁的基础索引也有超过1百亿个网页。假设下载一个网页需要1秒，下载1百亿个网页需要317年，下载1万亿个网页需要32000年左右。这样的爬虫显然不实用。

稍微有点计算机工作经验的人会马上想到并行计算。让1000台服务器同时工作，可以大大缩减下载时间。但是，并行计算也是有成本的，为了保障这1000台服务器不会把某个网页访问多次，而把另外一些网页漏掉，需要记录下载过的网页。如果每条记录需要8个字节，那么存1百亿个网页的记录需要80G左右的内存。至今还没有哪台通用服务器有这么大的内存。即使有，把这些记录存储在一台服务器上，其它所有的服务器在下载前都要访问它，这台服务器也一定会成为瓶颈。如果把这些记录分散到不同的服务器中，那么每次下载前，都要访问所有的服务器，显然也不现实。

事实上，一个商用的网络爬虫需要成千上万台服务器，并且通过高速网络连接起来。如何建立起这样复杂的网络系统，如何协调这些服务器的任务，就是网络和程序设计的艺术了。

其次，下载网页时，到底采用深度优先搜索（DFS）或者广度优先算法（BFS）？

网络爬虫要考虑：“如何在有限的时间里，下载更多的重要的网页”。显然各个网站最重要的网页是它的首页，次重要是首页上链接的网页。如果爬虫非常小，只能下载非常有限的网页，那么它应该下载所有网站的首页。如果爬虫大一些，就应该再下载首页上链接的网页。从这个角度看，广度优先搜索（BFS）优于深度优先搜索（DFS）。

那么，网络爬虫是否只用到广度优先搜索呢（BFS）？也不是。由于通信中的握手（下载服务器和网站服务器之间建立通信的过程）需要花费时间，如果握手次数太多，下载效率就降低了。所以对于某个网站，一般由特定的下载服务器专门下载，下载完成后再进入下一个网站，这就用到了深度优先搜索（DFS）。

总之，网络爬虫不是简单的使用深度优先搜索（DFS）或者广度优先搜索(BFS)，而是有一个相对复杂的调度系统，由它决定网页的下载顺序。调度系统里会在优先级队列里，存储那些已经发现但尚未下载的网页链接。用这种方式遍历整个互联网，在工程上和广度优先搜索(BFS)更相似。因此，在网络爬虫里，广度优先搜索(BFS)的成分会更多一些。