Skip to main content
 首页 » 编程设计

data-structures之设计网络爬虫

2024年02月27日17cmt

我遇到过一个面试问题“如果你正在设计一个网络爬虫,你会如何避免陷入无限循环?”,我正在尝试回答它。

这一切是如何从头开始的。 假设谷歌从一些中心页面开始,说有数百个(这些中心页面最初是如何找到的是一个不同的子问题)。 当 Google 跟踪某个页面的链接等时,它是否会不断创建哈希表以确保它不会跟踪之前访问过的页面。

如果同一个页面有 2 个名称(URL),那么现在我们有 URL 缩短器等。

我以谷歌为例。虽然谷歌没有透露其网络爬虫算法和页面排名等如何工作,但你有什么猜测吗?

请您参考如下方法:

如果您想获得详细答案,请查看section 3.8 this paper ,它描述了现代抓取工具的 URL-seen 测试:

In the course of extracting links, any Web crawler will encounter multiple links to the same document. To avoid downloading and processing a document multiple times, a URL-seen test must be performed on each extracted link before adding it to the URL frontier. (An alternative design would be to instead perform the URL-seen test when the URL is removed from the frontier, but this approach would result in a much larger frontier.)

To perform the URL-seen test, we store all of the URLs seen by Mercator in canonical form in a large table called the URL set. Again, there are too many entries for them all to fit in memory, so like the document fingerprint set, the URL set is stored mostly on disk.

To save space, we do not store the textual representation of each URL in the URL set, but rather a fixed-sized checksum. Unlike the fingerprints presented to the content-seen test’s document fingerprint set, the stream of URLs tested against the URL set has a non-trivial amount of locality. To reduce the number of operations on the backing disk file, we therefore keep an in-memory cache of popular URLs. The intuition for this cache is that links to some URLs are quite common, so caching the popular ones in memory will lead to a high in-memory hit rate.

In fact, using an in-memory cache of 2^18 entries and the LRU-like clock replacement policy, we achieve an overall hit rate on the in-memory cache of 66.2%, and a hit rate of 9.5% on the table of recently-added URLs, for a net hit rate of 75.7%. Moreover, of the 24.3% of requests that miss in both the cache of popular URLs and the table of recently-added URLs, about 1=3 produce hits on the buffer in our random access file implementation, which also resides in user-space. The net result of all this buffering is that each membership test we perform on the URL set results in an average of 0.16 seek and 0.17 read kernel calls (some fraction of which are served out of the kernel’s file system buffers). So, each URL set membership test induces one-sixth as many kernel calls as a membership test on the document fingerprint set. These savings are purely due to the amount of URL locality (i.e., repetition of popular URLs) inherent in the stream of URLs encountered during a crawl.

基本上,他们使用散列函数对所有 URL 进行散列,以保证每个 URL 的唯一散列,并且由于 URL 的局部性,因此很容易找到 URL。谷歌甚至开源了他们的哈希函数:CityHash

警告!
他们也可能在谈论机器人陷阱!机器人陷阱是页面的一部分,它不断生成具有唯一 URL 的新链接,通过跟踪该页面提供的链接,您实际上会陷入“无限循环”。这并不完全是一个循环,因为循环可能是访问同一 URL 的结果,但它是一个无限的 URL 链,您应该避免对其进行爬网。

更新 12/13/2012 - 世界末日的第二天:)

根据 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 页面会将信用值均匀地分配给数据库中的所有页面,并且在每个周期中,机器人陷阱页面都会失去越来越多的信用值,直到它的信用值非常少,以至于几乎再也不会被爬行。对于好的页面来说,这种情况不会发生,因为它们经常从其他页面上找到的反向链接中获得积分。这也会导致动态页面排名,您会注意到,每当您拍摄数据库快照时,根据页面拥有的积分数量对页面进行排序,那么它们很可能会根据其 进行大致排序真实页面排名

这只能避免无限循环类型的机器人陷阱,但有 many other bot traps您应该注意这些,并且也有一些方法可以绕过它们。