【九章系统设计】爬虫系统与搜索建议系统

1. outline

  • Design a web crawler 爬虫
  • Design thread-safe producer and consumer 线程安全的生产者-消费者
  • Design a Typeahead 搜索建议

2. 爬虫

2.1 Scenario

思考:搜索引擎是如爬取网页的?我们需要获取什么样的表格?

URL-网页内容

爬到了这些数据怎么用呢?

用户搜索关键词,google去数据表中的网页内容字段寻找包含用户query的数据,返回对应的url给用户,之后进行排序等优化操作。

那么想要用程序完成爬取互联网上所有网页及其内容这个目标,我们首先要知道一个事实,也就是互联网上的内容其实是互相索引的,也就是就像如下的大网一样:

总结分析爬虫的工作量:

假设我们需要在一周内爬取互联网中所有的网页,之后至少一周更新一次。

  1. 互联网上共有1trillion个网页,则每秒需要爬取1.6m个网页
  2. 每个网页大概10K,那么将这些网页存下来需要10P的存储空间

把互联网上的网页看成是一张图,爬虫相当于遍历这个图,有DFS和BFS两种实现方式,一般采用BFS进行爬取,因为DFS不好并行爬取。

2.1.1单线程爬取

对于单线程的爬虫来说,就是搞一个队列,用BFS爬取集合:

2.1.2 生产者消费者模型

producer-consumer pattern生产者消费者模型

由于存取速度不一样,所以二者中间有一个buffer

img

但是单线程有一个问题,就是慢的很。解决——多线程爬虫

2.1.3 多线程爬取

不同线程之间共享同一个队列

为什么多线程会比单线程快呢?

多线程存在的问题:

多个线程都会从队列里向外拿URL,相当于对队列的一次写操作,这时候就会发生冲突,也就是互斥

需要注意的是,争取共享资源,就要考虑以下三个机制

  • sleep —— 就是睡一会,设置一定的时间,然后回来看看资源能用了不。但问题是:在道资源可以使用的第一时间知道,效率很低
  • condition variable 信号量(实现互斥)—— 相当于所有的线程都在等着,然后信号量通知他们能用的时候,就都立马去抢占用资源,谁抢到算谁的
  • semaphore —— 就像门上挂上五把钥匙一样,每次可以进去5个人,出来的时候还钥匙,也就是允许同一时间有多个线程访问用一个资源。

单线程 –> 多线程:

思考一个问题,既然多线程这么快,是否可以尽量多的开线程,比如开一万个?

不行,原因如下:

  • 线程之间来回切换(context switch)还是有花费(需要保存线程执行状态,还需要切换二级缓存等)的,因此线程不能太多,线程过多效率会很低
  • 一个CPU在同一时间只能处理一个线程,如果机器只有一个CPU线程依然在排队
  • 线程端口数目是有限的(TCP/IP协议中,端口只有2个字节,也就是65536个端口,操作系统还会预留一些端口给其他服务)
  • 网络带宽有限制,线程很多,单台的带宽是不能够满足的

因此我们可以改进一下:

2.1.4 分布式爬取

分多台机器爬取,就可以突破单台机器的限制了!此时分布式爬虫依然共享一个内存中的URL queue.

分布式爬虫虽然解决了线程不能太多的问题,但是又带来了一个问题:URL队列在内存中放不下了(假设1trillion,差不多要40T的内存)!这是不行的。那么我们考虑一下把URL queue存在硬盘里,也就是数据库里。

但是放到数据库里之后,又有一个很要命的限制是:没有办法控制网页抓取的顺序和优先级啊!

解决:给数据库加入一个优先级的列,再加一个频率的列

每一行是一个任务:

  • ID,URL
  • state:是否正在运行的状态(即能去重,也能防止重复运算)
  • priority:优先级
  • available_time:控制抓取频率,也就是这个时刻之后再进行抓取。如果本次有更新,那么就把时间设置地更近一些;如果本次没有更新,那么就把时间设置地更远一些

  • webPage Storage : 分布式存储系统,存储爬取的东西
  • 分布式爬虫
  • Task table : 就是上面的任务表

2.4 Scale 优化

2.4.1 Task Table 拆分

task table 最终会非常大!1 trillion 个task,而且会越来越大

解决——拆表sharding,加速访问

那么拆表就有一个细节需要注意,需要一个scheduler,用来安排去哪里要数据。

2.4.2 抓取频率问题

如何控制抓取频率呢?有一个暴力的方法:

  • 如果本次抓了有更新(更新频繁),那就把下次抓取的时间提前一半
  • 如果本次抓了没更新(更新不频繁),就把下次抓取的时间往后移2倍

调整合适的抓频率可以优化计算资源

2.4.3 死循环问题

比如爬取新浪新闻,基本上连接也都是新浪新闻,

有些网站是互相指向的,比如sina.com。而且所有的URL都是与sina.com差不多的。这样就会使用大量的资源去抓取这种巨型网站,太耗费资源了。对于那些小博客就不公平。

解决办法:单位时间对同一个网站,不要分配过多的计算资源给巨型网站就好啦。

2.4.4 分区域问题

中国的爬虫爬美国的网站,或者网站在美国爬中国的网站就会很慢

解决:分区域爬取,分区域简历task table,然后定期和全世界的数据库进行同步

3. Typeahead 搜索建议

3.1 scenario 场景分析

我们以google Suggesion为例分析

  • DAU日活跃用户:500m
  • 搜索量:4 x 6 x 500m = 12b (每人搜索6次,输入4个单词 = 使用了typeahead四次)
  • QPS : 12b / 86400 = 138k
  • Peak QPS = QPS X 2 = 276k

typeahead的最关键问题是快!一定要在用户敲字母的同时给出建议

3.2 service 需求

  1. query survice 处理检索,在极短的时间内返回以输入为前缀的建议热门词
  2. data collection service 收集某段时间内用户搜索的热门词

3.3 Storage