数学之美--关于图论引申出来的爬虫构想

 转载请注明出处：http://www.cnblogs.com/codefish/p/4971664.html

在了解爬虫之前，我一直认为是简单的对单一网站的采集，无非就是对于一个域名内定点的数据抓取而已，2012年买了《数学之美》后，就一直没有正儿八经的看，或者当时看了之后，由于自己的水平有限，压根就没有留下深刻的印象，以至于现在开始系统的研究一个框架的时候，总是粗浅的了解它的技术实现和API的调用一些方法，从来没有深入的去了解它背后的设计思想。这就造成了用了千百种工具，还是自己写不出一个好工具的尴尬，人最怕的就是洋洋得意与自我欺骗，前者让自己停止了前进的脚步，满足于当前的现状，后者是让自己固执，固步自封。

现在重新拿起原先的书开始看，感觉里面的东西通俗易懂，而且包含的思想深刻。

这里记录了关于爬虫的构建的一些要点：

1，是BFS(Breadth-First Search) 还是 DFS(Depth-First Search)

虽然在理论，这两个算法（在不考虑时间因素的前提下）都能免在大致相同的里爬下整个的“静态”互联网的内容，但是工程上的假设-都是在现实的世界里面做不到的

搜索引擎的网络爬虫问题更应该定义为“如何在有限的时间内最多的爬下最重要的网页”。显然各个网站最重要的内容应该是它的首页，在极端的情况下，如果爬虫非常的小，只能下载非常有限的网页。那么应该下载的是所有网站的首页，如果在爬虫在大一点，就应该下载和首页相关的直属链接，因为这些网页是网站设计者自己认为相当重要的内容。在这个前提下，显然BFS要明显优于DFS。事实在搜索引擎的爬虫里，虽然并不是简单的采用BFS，但是先爬哪一个网页，后爬哪一个网页，原理上基本都是BFS.

那DFS就不要使用了呢？也不是这样，这是和爬虫的分布式结构以及网络通信的握手成本相关的。所谓的“握手”是指下载服务器和网站的服务器建立通信的过程。这个过程是需要额外的时间，如果握手的次数太多，下载的效率就降低了。实际的网络爬虫都是一个由成百上千甚至上千成的服务器组成的分布式系统。对于某个网站，一般是由特定的一台或者几台服务器专门下载的。这些服务器下载完一个网站 ，然后再进入下一个网站，而不是每个网站先轮流下载5%,然后再回头下载第二批。这样就可以避免握手次数太多。如果是下载完成第一个网站再下载第二个，那么这有点像DPS了，虽然下载同一个网站还是需要BFS。

总结来说，网络爬虫对网页的遍历次序不是简单的BFS或者DFS，而是有一个相对复杂的下载优先级排序方法。管理这个优先级排序的子系统称为调度系统(Scheduler)。

这里，我们可以参考scrpay的核心组件，scheduler :

https://github.com/scrapy/scrapy/blob/master/scrapy/core/scheduler.py

由它来决定当一个网页下载完成后然后在下载哪一个。当然在调度系统里需要存储哪些已经发现的尚未下载的网页URL，它们一般存在一个优先级队列(Priority Queue)里，而用这种方式遍历的整个互联网，在工程上和BFS更相似。因此，在爬虫中，BFS的成分多一些。

这里引申另外一个内容，如果去重和共享队列。

我们知道，去重一般使用hash算法，由于hash集合的方便操作性，在数据量不大时，我们用hash集合来判断一个元素是否在一个集合中相当的方便，但是如果数据量相当大，我们都知道一个搜索引擎的爬虫决不可能只用一台机器的内容来存储这些已知的列表。这个时候就要介绍引入布隆过滤器了，关于bloom filter ，我在上一个文章里面已经提到了一些。请参考：

http://www.cnblogs.com/codefish/p/4962164.html

另外一个，一般使用scrapy的分布式的核心，就是关于url的队列操作引入到redis

参考：

https://github.com/rolando/scrapy-redis

我将在下一篇文章里面详细的介绍如何结合以及代码的分析。

第二，页面的分析以及URL的提取

早期的爬虫都很容易的运行，因为网页都是直接使用HTML语言写的，这些URL的内容都是以文本或者DOM node存放在节点之中，我们可以很容易的使用正则表达式或者xpath语法来规则的解析这些数据。不过，现在很多的网页偏向于Javascript 或者ajax来生成数据，你打开网页查看源代码之后，发现是需要运行一段脚本才来解决问题。所以，网页的分析就相对以前来说复杂的多了，这个里面需要js的引擎来渲染页面，才能得到那些隐藏的内容。

第三，记录哪些网页已经下载过的小本本–URL表

为了防止重复抓取，需要在一个hash表中记录哪些网页被下载过，再遇到它，我们就可以直接跳过它。采用哈希表的好处是，判断一个网页的URL是否存在表中，平均只需要一次（或者略多的）查找，效率上有巨大的优势。当然，如果遇到没有下载的网页，还需要在下载完成后，将这个网页的URL存到哈希表中，这个操作对哈希表来讲也是非常简单的。在一台下载服务器上建立下和维护一张哈希表并不是难事。但是如果同时有上千台服务器一起下载网页，维护一张统一的哈希表就不是一件容易的事情。首先，这张哈希表大到一台服务器存不下。其次，由于每个下载服务器在开始下载前和完成下载后都要访问和维护这张表，以免不同的服务器做重复的工作，这个存储哈希表的服务器的通信就成个整个爬虫系统的瓶颈。那如何解决呢？

首先，明天每台下载服务器的分工，也就是说在调度时看到某个URL就要知道交给哪台服务器去下载，这样就可以避免很多服务器对同一个URL做出是否需要下载的判断了

另外，在明确分工的基础上，判断URL是否下载就可以批处理了，比如每次向哈希表(一组独立的服务器)发送一大批话外音，或者每次更新一大批哈希表的内容(下载器的缓存更新机制与同步机制)这样通信的次数就大大减少了。

https://brucedone.com/2015/11/17/数学之美-关于图论引申出来的爬虫构想/

文章来源: brucedone.com，作者：大鱼的鱼塘，版权归原作者所有，如需转载，请联系作者。

原文链接：brucedone.com/archives/64