系统设计面试题 - 设计一个网页爬虫

引用：
系统设计入门

设计一个网页爬虫

解答

第一步：通过讨论，明确限制及用例，确定Scope

支持的用例：

• 系统抓取一系列的网址
  • 产生倒排索引
  • 产生网页的标题和摘要
• 用户可以输入关键词，系统显示出相关的网页标题及摘要
• 系统高可用 high availability

不支持的用例：

• 不支持搜索结果分析
• 不支持自定义搜索模式
• 不支持Page rank

Constraints and assumptions：

• 访问不均匀
• 搜索速度要快
• 有1 billion个网页需要抓取，每秒1,600次写操作
  • 每周重新抓取一次，因此每月需要抓取 4 billion 个网页
  • 每个网页平均 500 K
• 每月搜索 100 billion 次，每秒40,000次读操作

计算规模：

• 1 billion个网页占用：500K * 1 billion = 500TB
• 每月网页占用：4 * 500TB = 2PB
• 三年网页占用：72PB

第二步：高层次设计

设计一个网页爬虫

第三步：设计核心组件

假设我们有一个初始的网址列表 links_to_crawl，里面的网址是根据 popularity 排序的。可以使用Redis中的有序集合 sorted sets 来存储。

使用crawled_links存储已经处理过的网址及对应的网页签名 page signature。可以使用 key - value 的NoSQL数据库来存储。key 是网址，value 是网页签名。

Crawler Service 的主要工作：

• 从links_to_crawl取出一个优先级排序最高的网址，检查在crawled_links有没有相类似网页签名的记录：
  • 如果有，降低该网址的优先级
    • 这样可以防止系统进入死循环
  • 如果没有，抓取网页内容：
    • 发送任务到 Reverse Index Service 队列，用来产生倒排索引
    • 发送任务到 Document Service 队列，产生网页的标题和摘要
    • 产生网页签名
    • 将该网址从links_to_crawl中移除
    • 将该网址及网页签名添加到crawled_links中
    • 将该网页中包含的URL，添加到links_to_crawl中

处理重复：
防止抓取进入一个死循环。需要去除links_to_crawl中重复的网址。由于数据量很大，我们可以使用 MapReduce 来查询只出现了一次的网址。例如：

class RemoveDuplicateUrls(MRJob):
    def mapper(self, _, line):
        yield line, 1

    def reducer(self, key, values):
        total = sum(values)
        if total == 1:
            yield key, total

何时需要更新抓取结果：
使用timestamp记录每个网页上一次被抓取的时间。每隔一周需要重新抓取。
或者可以使用一些数据挖掘的方法，来估算每一个网页的更新时间。

搜索功能：提供一个Query REST API

• 解析输入字符串：
  • 去除标记 markup
  • 分词
  • Fix 输入错误 typo
  • 规范化大小写
• 调用 Reverse Index Service，获得输入关键字对应的网址列表
  • Reverse Index Service会对结果排序，并返回靠前的结果
• 随后调用 Document Service，获得每个网址的标题及摘要信息

返回的结果为JSON格式，例如：

{
    "title": "foo's title",
    "snippet": "foo's snippet",
    "link": "https://foo.com",
},
{
    "title": "bar's title",
    "snippet": "bar's snippet",
    "link": "https://bar.com",
}

第四步：扩展设计

设计一个网页爬虫

• 为了同时响应更多请求，对服务器水平扩展，并使用Load Balancer做负载均衡。
• 为了加快搜索效率，使用Memory Cache，存储热门的搜索结果。
• Reverse Index Service 和 Document Service 计算量和吞吐量比较大，可以创建多个实例，并行处理对应的Queue。
• Crawler Service可以维护一个自己的DNS lookup，来减少与外界DNS服务器的通信时间。