美文网首页架构设计
系统设计面试题 - 设计一个网页爬虫

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

作者: 专职跑龙套 | 来源:发表于2018-04-26 16:51 被阅读56次

    引用:
    系统设计入门

    设计一个网页爬虫

    解答

    第一步:通过讨论,明确限制及用例,确定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服务器的通信时间。

    相关文章

      网友评论

        本文标题:系统设计面试题 - 设计一个网页爬虫

        本文链接:https://www.haomeiwen.com/subject/lciplftx.html