设计一个网络爬虫(Python)

第 1 步：概述用例和约束

收集需求并确定问题的范围。提出问题以澄清用例和约束。讨论假设。

如果没有面试官来解决澄清问题，我们将定义一些用例和约束。

用例

我们将问题范围限定为仅处理以下用例

• 服务抓取 url 列表：
  • 生成包含搜索词的页面的反向索引
  • 为页面生成标题和片段
    • 标题和片段是静态的，它们不会根据搜索查询而改变
• 用户输入搜索词并查看相关页面列表，其中包含爬虫生成的标题和片段
  • 仅为此用例绘制高级组件和交互，无需深入
• 服务具有高可用性

超出范围

• 搜索分析
• 个性化搜索结果
• 网页排名

约束和假设

状态假设

• 流量分布不均
  • 有些搜索很受欢迎，而有些搜索只执行一次
• 仅支持匿名用户
• 生成搜索结果应该很快
• 网络爬虫不应陷入无限循环
  • 如果图包含一个循环，我们就会陷入无限循环
• 10 亿个要抓取的链接
  • 页面需要定期爬取，保证新鲜度
  • 平均刷新率约为每周一次，对于热门网站更频繁
    • 每月抓取 40 亿个链接
  • 每个网页的平均存储大小：500 KB
    • 为简单起见，计数更改与新页面相同
• 每月 1000 亿次搜索

练习使用更传统的系统——不要使用现有的系统，例如solr或nutch。

计算用量

如果您应该进行粗略的使用计算，请与您的面试官澄清。

• 每月存储 2 PB 的页面内容
  • 每页 500 KB * 每月抓取 40 亿个链接
  • 3 年内存储 72 PB 的页面内容
• 每秒 1,600 个写入请求
• 每秒 40,000 个搜索请求

方便的转换指南：

• 每月 250 万秒
• 每秒 1 个请求 = 每月 250 万个请求
• 每秒 40 个请求 = 每月 1 亿个请求
• 每秒 400 个请求 = 每月 10 亿个请求

第 2 步：创建高级设计

概述包含所有重要组件的高级设计。

第三步：设计核心组件

深入了解每个核心组件的细节。

用例：服务抓取 url 列表

我们假设我们有一个links_to_crawl最初基于整体网站受欢迎程度的排名的初始列表。如果这不是一个合理的假设，我们可以使用链接到外部内容（如Yahoo、DMOZ等）的流行网站为爬虫播种。

我们将使用一个表crawled_links来存储处理后的链接及其页面签名。

我们可以将links_to_crawl和存储crawled_links在键值NoSQL 数据库中。对于 中的排名链接links_to_crawl，我们可以使用带有排序集的Redis来维护页面链接的排名。我们应该讨论选择 SQL 或 NoSQL 之间的用例和权衡。

• 爬虫服务通过循环执行以下操作来处理每个页面链接：
  • 抓取排名靠前的页面链接
    • crawled_links在NoSQL 数据库中检查具有相似页面签名的条目
      • 如果我们有相似的页面，降低页面链接的优先级
        • 这可以防止我们进入一个循环
        • 继续
      • 否则，抓取链接
        • 将作业添加到反向索引服务队列以生成反向索引
        • 将作业添加到文档服务队列以生成静态标题和片段
        • 生成页面签名
        • 从NoSQL 数据库links_to_crawl中删除链接
        • crawled_links在NoSQL 数据库中插入页面链接和签名

与你的面试官澄清你需要写多少代码。

PagesDataStore是使用NoSQL 数据库的爬虫服务中的抽象：

class PagesDataStore(object):
 
    def __init__(self, db);
        self.db = db
        ...
 
    def add_link_to_crawl(self, url):
        """Add the given link to `links_to_crawl`."""
        ...
 
    def remove_link_to_crawl(self, url):
        """Remove the given link from `links_to_crawl`."""
        ...
 
    def reduce_priority_link_to_crawl(self, url)
        """Reduce the priority of a link in `links_to_crawl` to avoid cycles."""
        ...
 
    def extract_max_priority_page(self):
        """Return the highest priority link in `links_to_crawl`."""
        ...
 
    def insert_crawled_link(self, url, signature):
        """Add the given link to `crawled_links`."""
        ...
 
    def crawled_similar(self, signature):
        """Determine if we've already crawled a page matching the given signature"""
        ...

Page是Crawler Service中的一个抽象，它封装了页面、其内容、子 url 和签名：

class Page(object):
 
    def __init__(self, url, contents, child_urls, signature):
        self.url = url
        self.contents = contents
        self.child_urls = child_urls
        self.signature = signature

class Crawler(object):
 
    def __init__(self, data_store, reverse_index_queue, doc_index_queue):
        self.data_store = data_store
        self.reverse_index_queue = reverse_index_queue
        self.doc_index_queue = doc_index_queue
 
    def create_signature(self, page):
        """Create signature based on url and contents."""
        ...
 
    def crawl_page(self, page):
        for url in page.child_urls:
            self.data_store.add_link_to_crawl(url)
        page.signature = self.create_signature(page)
        self.data_store.remove_link_to_crawl(page.url)
        self.data_store.insert_crawled_link(page.url, page.signature)
 
    def crawl(self):
        while True:
            page = self.data_store.extract_max_priority_page()
            if page is None:
                break
            if self.data_store.crawled_similar(page.signature):
                self.data_store.reduce_priority_link_to_crawl(page.url)
            else:
                self.crawl_page(page)

class RemoveDuplicateUrls(MRJob):
 
    def mapper(self, _, line):
        yield line, 1
 
    def reducer(self, key, values):
        total = sum(values)
        if total == 1:
            yield key, total