专栏首页技术探究-前端、Python、爬虫、数据分析、工具爬虫面试题 | 系统设计 —— 如何设计一个网页爬虫

爬虫面试题 | 系统设计 —— 如何设计一个网页爬虫

来源:https://juejin.im/post/598d1d3e51882548924134c2

译者:吃土小2叉

整编:离不开的网

设计一个网页爬虫

第一步:简述用例与约束条件

把所有需要的东西聚集在一起,审视问题。不停的提问,以至于我们可以明确使用场景和约束。讨论假设。

我们将在没有面试官明确说明问题的情况下,自己定义一些用例以及限制条件。

1.1 用例

我们把问题限定在仅处理以下用例的范围中

  • 服务 抓取一系列链接:
    • 生成包含搜索词的网页倒排索引
    • 生成页面的标题和摘要信息
      • 页面标题和摘要都是静态的,它们不会根据搜索词改变
  • 用户 输入搜索词后,可以看到相关的搜索结果列表,列表每一项都包含由网页爬虫生成的页面标题及摘要
    • 只给该用例绘制出概要组件和交互说明,无需讨论细节
  • 服务 具有高可用性

无需考虑

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

1.2 限制条件与假设

提出假设

  • 搜索流量分布不均
    • 有些搜索词非常热门,有些则非常冷门
  • 只支持匿名用户
  • 用户很快就能看到搜索结果
  • 网页爬虫不应该陷入死循环
    • 当爬虫路径包含环的时候,将会陷入死循环
  • 抓取 10 亿个链接
    • 要定期重新抓取页面以确保新鲜度
    • 平均每周重新抓取一次,网站越热门,那么重新抓取的频率越高
    • 每月抓取 40 亿个链接
  • 每个页面的平均存储大小:500 KB
    • 简单起见,重新抓取的页面算作新页面
  • 每月搜索量 1000 亿次

用更传统的系统来练习 —— 不要使用 [solr]、[nutch]以上两类的现成系统。

计算用量

如果你需要进行粗略的用量计算,请向你的面试官说明。

  • 每月存储 2 PB 页面
    • 每月抓取 40 亿个页面,每个页面 500 KB
    • 三年存储 72 PB 页面
  • 每秒 1600 次写请求
  • 每秒 40000 次搜索请求

简便换算指南:

  • 一个月有 250 万秒
  • 每秒 1 个请求,即每月 250 万个请求
  • 每秒 40 个请求,即每月 1 亿个请求
  • 每秒 400 个请求,即每月 10 亿个请求

第二步:概要设计

列出所有重要组件以规划概要设计。

第三步:设计核心组件

对每一个核心组件进行详细深入的分析。

3.1 用例:爬虫服务抓取一系列网页

假设我们有一个初始列表 links_to_crawl(待抓取链接),它最初基于网站整体的知名度来排序。当然如果这个假设不合理,我们可以使用 Yahoo、DMOZ 等知名门户网站作为种子链接来进行扩散 。

我们将用表 crawled_links (已抓取链接 )来记录已经处理过的链接以及相应的页面签名。

我们可以将 links_to_crawlcrawled_links 记录在键-值型 NoSQL 数据库中。对于 crawled_links 中已排序的链接,我们可以使用 Redis 的有序集合来维护网页链接的排名。

爬虫服务按照以下流程循环处理每一个页面链接:

  • 选取排名最靠前的待抓取链接
    • 在 NoSQL 数据库的 crawled_links 中,检查待抓取页面的签名是否与某个已抓取页面的签名相似
    • 若存在,则降低该页面链接的优先级
      • 这样做可以避免陷入死循环
      • 继续(进入下一次循环)
    • 若不存在,则抓取该链接
      • 在倒排索引服务任务队列中,新增一个生成倒排索引任务。
      • 在文档服务任务队列中,新增一个生成静态标题和摘要的任务。
      • 生成页面签名
      • 在 NoSQL 数据库的 links_to_crawl 中删除该链接
      • 在 NoSQL 数据库的 crawled_links 中插入该链接以及页面签名

向面试官了解你需要写多少代码。

PagesDataStore 是爬虫服务中的一个抽象类,它使用 NoSQL 数据库进行存储。

class PagesDataStore(object):

    def __init__(self, db);
        self.db = db
        ...

    def add_link_to_crawl(self, url):
        """将指定链接加入 `links_to_crawl`。"""
        ...

    def remove_link_to_crawl(self, url):
        """从 `links_to_crawl` 中删除指定链接。"""
        ...

    def reduce_priority_link_to_crawl(self, url)
        """在 `links_to_crawl` 中降低一个链接的优先级以避免死循环。"""
        ...

    def extract_max_priority_page(self):
        """返回 `links_to_crawl` 中优先级最高的链接。"""
        ...

    def insert_crawled_link(self, url, signature):
        """将指定链接加入 `crawled_links`。"""
        ...

    def crawled_similar(self, signature):
        """判断待抓取页面的签名是否与某个已抓取页面的签名相似。"""
        ...

Page 是爬虫服务的一个抽象类,它封装了网页对象,由页面链接、页面内容、子链接和页面签名构成。

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

Crawler 是爬虫服务的主类,由PagePagesDataStore 组成。

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):
        """基于页面链接与内容生成签名。"""
        ...

    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)

处理重复内容

我们要谨防网页爬虫陷入死循环,这通常会发生在爬虫路径中存在环的情况。

向面试官了解你需要写多少代码.

删除重复链接:

  • 假设数据量较小,我们可以用类似于 sort | unique 的方法。(译注:先排序,后去重)
  • 假设有 10 亿条数据,我们应该使用 MapReduce 来输出只出现 1 次的记录。
class RemoveDuplicateUrls(MRJob):

    def mapper(self, _, line):
        yield line, 1

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

比起处理重复内容,检测重复内容更为复杂。我们可以基于网页内容生成签名,然后对比两者签名的相似度。可能会用到的算法有 Jaccard index 以及 cosine similarity。

抓取结果更新策略

要定期重新抓取页面以确保新鲜度。抓取结果应该有个 timestamp 字段记录上一次页面抓取时间。每隔一段时间,比如说 1 周,所有页面都需要更新一次。对于热门网站或是内容频繁更新的网站,爬虫抓取间隔可以缩短。

尽管我们不会深入网页数据分析的细节,我们仍然要做一些数据挖掘工作来确定一个页面的平均更新时间,并且根据相关的统计数据来决定爬虫的重新抓取频率。

当然我们也应该根据站长提供的 Robots.txt 来控制爬虫的抓取频率。

用例:用户输入搜索词后,可以看到相关的搜索结果列表,列表每一项都包含由网页爬虫生成的页面标题及摘要

  • 客户端向运行反向代理的 Web 服务器发送一个请求
  • Web 服务器 发送请求到 Query API 服务器
  • 查询 API 服务将会做这些事情:
    • 解析查询参数
      • 删除 HTML 标记
      • 将文本分割成词组 (译注:分词处理)
      • 修正错别字
      • 规范化大小写
      • 将搜索词转换为布尔运算
  • 使用倒排索引服务来查找匹配查询的文档
    • 倒排索引服务对匹配到的结果进行排名,然后返回最符合的结果
  • 使用文档服务返回文章标题与摘要

我们使用 REST API 与客户端通信:

$ curl https://search.com/api/v1/search?query=hello+world

响应内容:

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

对于服务器内部通信,我们可以使用 远程过程调用协议(RPC)

第四步:架构扩展

根据限制条件,找到并解决瓶颈。

重要提示:不要直接从最初设计跳到最终设计!

现在你要 1) 基准测试、负载测试。2) 分析、描述性能瓶颈。3) 在解决瓶颈问题的同时,评估替代方案、权衡利弊。4) 重复以上步骤。请阅读设计一个系统,并将其扩大到为数以百万计的 AWS 用户服务 来了解如何逐步扩大初始设计。

讨论初始设计可能遇到的瓶颈及相关解决方案是很重要的。例如加上一套配备多台 Web 服务器的负载均衡器是否能够解决问题?CDN呢?主从复制呢?它们各自的替代方案和需要权衡的利弊又有哪些呢?

我们将会介绍一些组件来完成设计,并解决架构规模扩张问题。内置的负载均衡器将不做讨论以节省篇幅。

为了避免重复讨论,请参考系统设计主题索引相关部分来了解其要点、方案的权衡取舍以及替代方案。

  • DNS
  • 负载均衡器
  • 水平扩展
  • Web 服务器(反向代理)
  • API 服务器(应用层)
  • 缓存
  • NoSQL
  • 一致性模式
  • 可用性模式

有些搜索词非常热门,有些则非常冷门。热门的搜索词可以通过诸如 Redis 或者 Memcached 之类的内存缓存来缩短响应时间,避免倒排索引服务以及文档服务过载。内存缓存同样适用于流量分布不均匀以及流量短时高峰问题。从内存中读取 1 MB 连续数据大约需要 250 微秒,而从 SSD 读取同样大小的数据要花费 4 倍的时间,从机械硬盘读取需要花费 80 倍以上的时间。

以下是优化爬虫服务的其他建议:

  • 为了处理数据大小问题以及网络请求负载,倒排索引服务和文档服务可能需要大量应用数据分片和数据复制。
  • DNS 查询可能会成为瓶颈,爬虫服务最好专门维护一套定期更新的 DNS 查询服务。
  • 借助于连接池,即同时维持多个开放网络连接,可以提升爬虫服务的性能并减少内存使用量。
    • 改用 UDP 协议同样可以提升性能
  • 网络爬虫受带宽影响较大,请确保带宽足够维持高吞吐量。

其他要点

是否深入这些额外的主题,取决于你的问题范围和剩下的时间。

SQL 扩展模式

  • 读取复制
  • 联合
  • 分片
  • 非规范化
  • SQL 调优

NoSQL

  • 键-值存储
  • 文档类型存储
  • 列型存储
  • 图数据库
  • SQL vs NoSQL

缓存

  • 在哪缓存
    • 客户端缓存
    • CDN 缓存
    • Web 服务器缓存
    • 数据库缓存
    • 应用缓存
  • 什么需要缓存
    • 数据库查询级别的缓存
    • 对象级别的缓存
  • 何时更新缓存
    • 缓存模式
    • 直写模式
    • 回写模式
    • 刷新

异步与微服务

  • 消息队列
  • 任务队列
  • 背压
  • 微服务

通信

  • 可权衡选择的方案:
    • 与客户端的外部通信 - 使用 REST 作为 HTTP API
    • 内部通信 - RPC
  • 服务发现

持续探讨

  • 持续进行基准测试并监控你的系统,以解决他们提出的瓶颈问题。
  • 架构扩展是一个迭代的过程。

文章任何内容,如有侵权,请联系作者删除!!!

本文分享自微信公众号 - 离不开的网(Gy_dxj),作者:离不开的网

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 爬虫系列(10)Scrapy 框架介绍、安装以及使用。

    运行命令:scrapy startproject myfrist(your_project_name)

    小Gy
  • 爬虫系列(1)第一步肯定是先介绍介绍爬虫。

    网络爬虫也叫网络蜘蛛,如果把互联网比喻成一个蜘蛛网,那么蜘蛛就是在网上爬来爬去的蜘蛛,爬虫程序通过请求url地址,根据响应的内容进行解析采集数据,比如:如果响应...

    小Gy
  • 【前端攻略--HTML/CSS】媒体查询

    1)媒体查询 @media 是个好东西,至少对像我一样刚入行的小前端做响应式是个不错的选择。

    小Gy
  • 完美假期第一步:用Python寻找最便宜的航班!

    这个简单的问题经常会得到一个积极的回复甚至还会额外收到一个或两个冒险的故事。通常来讲,旅行是一种体验新文化和拓宽自己视野的好方法。

    abs_zero
  • 完美假期第一步:用Python寻找最便宜的航班!

    这个简单的问题经常会得到一个积极的回复甚至还会额外收到一个或两个冒险的故事。通常来讲,旅行是一种体验新文化和拓宽自己视野的好方法。

    CDA数据分析师
  • 【学习】网站数据分析:电子商务网站RFM分析

    ? 根据美国数据库营销研究所Arthur Hughes的研究,客户数据库中有三个神奇的要素,这三个要素构成了数据分析最好的指标: 最近一次消费(Recency...

    小莹莹
  • 爬虫入门篇(上手即用)

    若有些网址设有反爬机制,请求若没有headers就会报错。 可以通过chrome浏览器的F12-network查看request的headers,将该网页的h...

    星辉
  • AngularJS 对SEO是硬伤

    在过去的2014年, 前端开发因为大量前端框架的出现开发模式有了巨大的改变,MVC这个web服务器端开发的模式,由于angularjs们的出现,变成了前端MVV...

    前朝楚水
  • 做产品的态度

    用户1756920
  • keras_bert文本多分类

    用户1750490

扫码关注云+社区

领取腾讯云代金券