1. outline

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

2. 爬虫

2.1 Scenario

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

URL-网页内容

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

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

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

总结分析爬虫的工作量：

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

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

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

2.1.1单线程爬取

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

2.1.2 生产者消费者模型

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

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

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

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 需求

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

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