第三节 Distributed System Design

什么是分布式系统： 用多台机器去解决一台机器不能解决的问题

Google 三剑客：

• Distributed file system GFS
• map reduce
• Bigtable

Distributed file system:

Scenario:

需求1：用户写入文件， 用户读取一个文件。 1000T

需求2： 多台机器存储这些文件。 10万台普通的机器 100k

Service:

p2p: decentralize，robust, 不好同步。

master/slave: 简单，怕master挂

Storage:

内存/DB/file System

meta data/ 视频 分开存，因为访问频率不一样。

GFS跟计算机里存小电影的原理是一样的：

电脑里的小电影：meta data存在disk的一块当做索引，video存在另外一块

GFS

存：master机器存meta data简历索引， chunk存在各个分布式的机器上。

写的时候：client直接跟chunk server写入。只在第一次找chunk server的时候需要跟master通信。后面的写入都是直接跟chunk server通信。

读出： master+ client + chunkServer

设计爬虫：

• 如何scale：DFS还是BFS。 选BFS，因为更容易把task分给不同的机器
• 如何避免重复访问：用一个hash set来存已经访问过的url.

如何prototype:

• 用单线程写一个crawler。缺点：慢。为什么：因为在等待网页的response。相当于把cpu时间浪费在了等待上。
• 所以用多线程：更快，缺点：线程共享资源，如果资源不够的情况怎么办。解决办法：sleep, condition varable, semaphore(1个资源可以被up to n 线程访问)
• 多线程怎么工作的：从url queue里面pop()一个url出来是一个写操作，需要hold住资源。处理完后，往queue里面append new urls也是一个写操作。同样需要hold住资源。

多台机器来web crawling:

用数据库来解决

设计type ahead:

存到db里面。最简单的办法用like搜索。缺点是一个range query非常慢，比如'abc'就是搜索'abc' 到 'abd'。怎么优化：单独存一个prefix的coloumn。空间换时间。