设计网络爬虫

Question

我遇到了一个采访问题"如果你正在设计一个网络爬虫,你将如何避免进入无限循环？"我试图回答它.

这一切从一开始就是如何开始的.比如谷歌开始时,一些中心页面上说有数百个(首先如何找到这些中心页面是一个不同的子问题).当Google跟踪来自页面的链接等时,它是否继续制作哈希表以确保它不遵循先前访问过的页面.

如果同一页面有2个名称(URL),如果我们有URL缩短器等,那么该怎么办呢？

我以谷歌为例.虽然谷歌没有泄漏其网络爬虫算法和页面排名等的工作方式,但任何猜测？

Answer 1

如果你想得到一个详细的答案,请看看本文的第3.8节,它描述了现代刮刀的URL看见测试:

在提取链接的过程中,任何Web爬网程序都会遇到指向同一文档的多个链接.为避免多次下载和处理文档,必须先对每个提取的链接执行URL查看测试,然后再将其添加到URL边界.(另一种设计是在从边界移除URL时执行URL看到的测试,但这种方法会产生更大的边界.)

为了执行URL看到的测试,我们将Mercator以规范形式看到的所有URL存储在一个称为URL集的大表中.同样,它们都有太多条目可以放入内存中,因此与文档指纹集一样,URL集主要存储在磁盘上.

为了节省空间,我们不会将每个URL的文本表示存储在URL集中,而是存储固定大小的校验和.与呈现给内容看见的测试的文档指纹集的指纹不同,针对URL集测试的URL流具有非平凡的局部性.因此,为了减少后备磁盘文件上的操作数,我们保留了常用URL的内存缓存.这个缓存的直觉是指向某些URL的链接非常常见,因此在内存中缓存流行的URL将导致高内存命中率.

实际上,使用2 ^ 18个条目的内存缓存和类似LRU的时钟替换策略,我们在内存缓存中实现了66.2%的总体命中率,并且在表中的命中率为9.5%.最近添加的网址,净点击率为75.7%.此外,在流行URL缓存和最近添加的URL表中丢失的24.3%请求中,大约1 = 3在我们的随机访问文件实现中产生缓冲区命中,该实现也驻留在用户空间中.所有这些缓冲的最终结果是我们对URL集执行的每个成员资格测试导致平均0.16次搜索和0.17次读取内核调用(其中一部分是从内核的文件系统缓冲区中提供的).因此,每个URL集成员资格测试引起的内核调用数量是文档指纹集上的成员资格测试的六分之一.这些节省纯粹是由于在爬网期间遇到的URL流中固有的URL位置(即,流行URL的重复)的数量.

基本上,它们使用散列函数散列所有URL,以保证每个URL的唯一散列,并且由于URL的位置,查找URL变得非常容易.Google甚至开源了他们的散列函数:CityHash

警告!
他们也可能在谈论机器人陷阱!机器人陷阱是页面的一部分,它不断生成具有唯一URL的新链接,并且通过遵循该页面所服务的链接,您将基本上陷入"无限循环".这不是一个循环,因为循环是访问同一个URL的结果,但它是一个无限的URL链,你应该避免抓取.

2012 年 12月13 日更新- 世界应该结束的第二天:)

根据Fr0zenFyr的评论:如果使用AOPIC算法来选择页面,那么很容易避免无限循环类型的僵尸陷阱.以下是AOPIC如何工作的摘要:

1. 获取一组N个种子页面.
2. 为每个页面分配X信用额度,使得每个页面在开始爬行之前具有X/N信用(即等额信用额度).
3. 选择页面P,其中P具有最高信用额度(或者如果所有页面具有相同的信用量,则抓取随机页面).
4. 抓取页面P(让我们说P在抓取时有100个筹码).
5. 从页面P中提取所有链接(假设有10个链接).
6. 将P的积分设为0.
7. 获取10%的"税"并将其分配到Lambda页面.
8. 从P的原始信用分配在P页上找到的每个链接的等量信用 - 税:所以(100(P学分) - 10(10%税))/ 10(链接)=每个链接9个学分.
9. 从第3步开始重复.

由于Lambda页面不断收税,最终它将成为信用额度最大的页面,我们将不得不"抓取"它.我在引号中说"抓取",因为我们实际上并没有为Lambda页面发出HTTP请求,我们只是将其信用并将它们平均分配给我们数据库中的所有页面.

由于僵尸陷阱只提供内部链接信用,而且他们很少从外部获得信用,他们将不断泄漏信用(从税收)到Lambda页面.Lambda页面将均匀地分配给数据库中的所有页面,并且在每个循环中,机器人陷阱页面将丢失越来越多的信用,直到它具有如此少的信用,它几乎永远不会被再次爬行.良好的页面不会发生这种情况,因为它们通常会从其他页面上的反向链接中获得积分.这也会产生动态页面排名,您会注意到,每当您拍摄数据库快照时,按照他们拥有的信用额度排序页面,那么他们很可能会根据他们的真实页面排名大致排序.

这只能避免无限循环类型的机器人陷阱,但是还有许多其他机器人陷阱你应该注意,并且有办法绕过它们.

Answer 2

虽然这里的每个人都已经建议过如何创建您的网络抓取工具,但以下是Google如何对网页进行排名.

Google根据回调链接的数量为每个页面提供排名(其他网站上指向特定网站/页面的链接数量).这称为相关性得分.这是基于如果页面有许多其他页面链接到它的事实,它可能是一个重要的页面.

每个站点/页面都被视为图形中的节点.与其他页面的链接是有向边.顶点的度数被定义为入射边缘的数量.具有更多入射边缘的节点排名更高.

以下是PageRank的确定方式.假设页面Pj具有Lj链接.如果其中一个链接是页面Pi,则Pj将其重要性的1/Lj传递给Pi.然后,Pi的重要性排名是链接到它的页面所做的所有贡献的总和.因此,如果我们表示通过Bi链接到Pi的页面集合,那么我们有这个公式:

Importance(Pi)= sum( Importance(Pj)/Lj ) for all links from Pi to Bi

排名放在一个称为超链接矩阵的矩阵中:H [i,j]

如果存在从Pi到Bi的链接,则该矩阵中的行为0或1/Lj.该矩阵的另一个属性是,如果我们对列中的所有行求和,则得到1.

现在我们需要将这个矩阵乘以一个名为I(特征值为1)的特征向量,这样:

I = H*I

现在我们开始迭代:我H,I我H,我我我 ^ h .... I ^ K*小时,直到解收敛.也就是说,我们在步骤k和k + 1的矩阵中得到几乎相同的数字.

现在I矢量中剩下的是每页的重要性.

有关简单的课堂作业示例,请参阅http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

至于解决面试问题中的重复问题,在整个页面上做一个校验和,并使用校验和或校验和的bash作为地图中的关键字来跟踪访问过的页面.