美西北区域代友征友 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Piebridge - 鹊桥

美西北区域代友征友

美西北区域代友征友# Piebridge - 鹊桥

r*n2012-02-25 08:02

1 楼

被问了这个crawler的问题，大概就是给你10K个机器，每个机器有seed url，然
后要爬1B的url，机器之间不能通信，问你怎么样每个机器才能平均的分任务。同时保
证每个网站只能被crawler一次。
奇怪的设计题，完全没有master，就是很多事情都不好做了
纠缠了十几分钟后突然意识到这完全是个brain teaser式的system design，然后想到
了类似UUID hashing，对拿到的url做hash，事先规定好每台机器都只做那些hash
value的job，如果hash的值跟当前机器的预定值不一样就skip，一样才继续crawl
算是蒙混过关，又问了两个follow up问题，第二个没想好时间就到了
1. 如何判断crawling结束
2. 如果一半机器比另一半快怎样分配
请问大家什么思路?

s*22012-02-25 08:02

2 楼

想问一下住evergreen到三番城里或者半岛上班，怎么解决交通问题？
错开高峰期也要开很久啊。还是开到最近的caltrain站或者bart站然后坐bart?
谢谢

s*t2012-02-25 08:02

3 楼

好友女孩一枚，机灵可爱，活泼好动，心地善良，古灵精怪，求一有阅历的沉稳男士带
走。
站内联系。

d*o2012-02-25 08:02

4 楼

类似UUID的hashing是不行的，hash出来太分散不能连续crawl
类似geohash的应该可以，hashkey前面一截相同的归一台机器crawl
比如hash出来，如果都是www.facebook.com/user/123起头的都会被hash成9zefzd*
这样判断crawl结束条件就是一直找到没有这个key打头的

s*22012-02-25 08:02

5 楼

自己顶以下

c*o2012-02-25 08:02

6 楼

女孩一枚，机灵可爱，活泼好动，心地善良，古灵精怪，求一有阅历的沉稳男士捆走。
哥自个给自个征~~╮(╯▽╰)╭
心情不爽四处捣蛋哦也

d*o2012-02-25 08:02

7 楼

第二个follow up不是很懂
是已知一半机器的性能比另一半快吗？
如果是这样，那么性能高的机器分配的hashkey range大点就行

s*r2012-02-25 08:02

8 楼

way too far...

s*t2012-02-25 08:02

9 楼

^_^

【在 c********o 的大作中提到】

: 女孩一枚，机灵可爱，活泼好动，心地善良，古灵精怪，求一有阅历的沉稳男士捆走。
: 哥自个给自个征~~╮(╯▽╰)╭
: 心情不爽四处捣蛋哦也

h*d2012-02-25 08:02

10 楼

机器之间不能通信, 机器能跟别的机器（例如一个coordinator)通信吗？

h*d2012-02-25 08:02

11 楼

什么叫好友女孩？
好朋友的女儿？

w*m2012-02-25 08:02

12 楼

最简单的就是，把IP地址从0.0.0.0到255.255.255.255切成10k。
seed url如果IP靠的比较近，就扔给哪些弱机器。

t*12012-02-25 08:02

13 楼

难道不是你？
//看不懂鸟～

【在 h******d 的大作中提到】

: 什么叫好友女孩？
: 好朋友的女儿？

d*o2012-02-25 08:02

14 楼

ip地址怎么能做切分准则呢
像新浪这种大型网站的一个服务器集群里面，10个ip地址里的url总数比其他一些一千
个ip地址里面的url总数都要多

【在 w********m 的大作中提到】

: 最简单的就是，把IP地址从0.0.0.0到255.255.255.255切成10k。
: seed url如果IP靠的比较近，就扔给哪些弱机器。

h*d2012-02-25 08:02

15 楼

开始也以为是说我。
不过一看到心地善良，就知道不是我了。。。

【在 t**********1 的大作中提到】

: 难道不是你？
: //看不懂鸟～

l*y2012-02-25 08:02

16 楼

刚刚得到onsite feedback，就跪在这个题上。

t*12012-02-25 08:02

17 楼

你哪儿不善良了？
//林夏也不是因为善良才不讨喜的呀

【在 h******d 的大作中提到】

: 开始也以为是说我。
: 不过一看到心地善良，就知道不是我了。。。

d*o2012-02-25 08:02

18 楼

PAT PAT
我上上周onsite也跪了个design，上周争取到一个design加试，还是跪了
另外我朋友onsite，也是跪在design

【在 l*********y 的大作中提到】

: 刚刚得到onsite feedback，就跪在这个题上。

q*y2012-02-25 08:02

19 楼

这种贴怎么会发在鹊版~~~~以正常思维来说~~~
骑士应该会发在戏班阿~~~~

w*m2012-02-25 08:02

20 楼

注意，题目说的，1Billion的任务，10k机器。每个机器就10w的任务。不管DFS还是BFS
，爬完收工。
每个机器带着seed url的ip的左边界和右边界，不要越界就可以了。

【在 d***o 的大作中提到】

: ip地址怎么能做切分准则呢
: 像新浪这种大型网站的一个服务器集群里面，10个ip地址里的url总数比其他一些一千
: 个ip地址里面的url总数都要多

s*t2012-02-25 08:02

21 楼

广播种才能多收粮

【在 q**y 的大作中提到】

: 这种贴怎么会发在鹊版~~~~以正常思维来说~~~
: 骑士应该会发在戏班阿~~~~

l*62012-02-25 08:02

22 楼

请问楼主和楼上的朋友你们是什么是面试遇到这题的？
小弟上周onsite也遇到一模一样的题目，还在等feedback

s*t2012-02-25 08:02

23 楼

那我改成心地丑恶吧

【在 h******d 的大作中提到】

: 开始也以为是说我。
: 不过一看到心地善良，就知道不是我了。。。

r*n2012-02-25 08:02

24 楼

不行，
可以的话啥问题都解决啦，相当于一个master嘛

【在 h*******d 的大作中提到】

: 机器之间不能通信, 机器能跟别的机器（例如一个coordinator)通信吗？

h*d2012-02-25 08:02

25 楼

他最近西版鸟版有点分不清。
经常发错。

【在 q**y 的大作中提到】

: 这种贴怎么会发在鹊版~~~~以正常思维来说~~~
: 骑士应该会发在戏班阿~~~~

h*e2012-02-25 08:02

26 楼

现在题都这么难了
还以为interviewbit看懂了就可以handle了呢

【在 r*********n 的大作中提到】

: 被问了这个crawler的问题，大概就是给你10K个机器，每个机器有seed url，然
: 后要爬1B的url，机器之间不能通信，问你怎么样每个机器才能平均的分任务。同时保
: 证每个网站只能被crawler一次。
: 奇怪的设计题，完全没有master，就是很多事情都不好做了
: 纠缠了十几分钟后突然意识到这完全是个brain teaser式的system design，然后想到
: 了类似UUID hashing，对拿到的url做hash，事先规定好每台机器都只做那些hash
: value的job，如果hash的值跟当前机器的预定值不一样就skip，一样才继续crawl
: 算是蒙混过关，又问了两个follow up问题，第二个没想好时间就到了
: 1. 如何判断crawling结束
: 2. 如果一半机器比另一半快怎样分配

h*d2012-02-25 08:02

27 楼

别介呀。。。
人真以为是说我了。。。
您老不转回西版去？
撒大网是不靠谱滴。

【在 s*********t 的大作中提到】

: 那我改成心地丑恶吧

n*l2012-02-25 08:02

28 楼

硅谷的non engineering team又在装逼。这种system design的题做好不容易吧。
大牛Linus也只敢说自己设计了git，连Linux kernel都说不是他设计的。

s*t2012-02-25 08:02

29 楼

那你到底心地丑恶还是善良？

【在 h******d 的大作中提到】

: 别介呀。。。
: 人真以为是说我了。。。
: 您老不转回西版去？
: 撒大网是不靠谱滴。

h*d2012-02-25 08:02

30 楼

有没有可能URL的数量小于10w在ip的左边界和右边界。URL的数量和IP RANGE没有关系
吧。

BFS

【在 w********m 的大作中提到】

: 注意，题目说的，1Billion的任务，10k机器。每个机器就10w的任务。不管DFS还是BFS
: ，爬完收工。
: 每个机器带着seed url的ip的左边界和右边界，不要越界就可以了。

L*n2012-02-25 08:02

31 楼

My type !!!
How about me a ???????????????

【在 s*********t 的大作中提到】

: 好友女孩一枚，机灵可爱，活泼好动，心地善良，古灵精怪，求一有阅历的沉稳男士带
: 走。
: 站内联系。

p*22012-02-25 08:02

32 楼

System design 一般也没有什么正确答案，考察点一般不是设计的正确与否，而是其他
方面。

j*52012-02-25 08:02

33 楼

Bless

l*n2012-02-25 08:02

34 楼

被问过一模一样的题目，觉得是设计的非常好的题目。解法其实就是自己在设计具有
sharding(设计hash函数，UUID肯定是不对的，其实很简单的hash函数就可以了），
load balance，replicas，error recovery（比如安排一台机器去爬hash=
xxxxx的url机器down了怎么办？）的分布式系统。我记得在答题的时候能够感觉到每回
答出一个followup都是hit到一个分布式系统的重要知识点。这轮是我觉得FB面试中唯
一一轮有技术含量的面试。anyway，最后还是没去FB。

p*22012-02-25 08:02

35 楼

distributed system 机器间不能通讯？

【在 l********n 的大作中提到】

: 被问过一模一样的题目，觉得是设计的非常好的题目。解法其实就是自己在设计具有
: sharding(设计hash函数，UUID肯定是不对的，其实很简单的hash函数就可以了），
: load balance，replicas，error recovery（比如安排一台机器去爬hash=
: xxxxx的url机器down了怎么办？）的分布式系统。我记得在答题的时候能够感觉到每回
: 答出一个followup都是hit到一个分布式系统的重要知识点。这轮是我觉得FB面试中唯
: 一一轮有技术含量的面试。anyway，最后还是没去FB。

l*n2012-02-25 08:02

36 楼

他理解错题目了，机器间可以通信，但是需要尽量少的通信，两三台之间是可以的。这
样就不能假设有master存在。如果机器完全不能通信爬网页下来也没啥用了不是。

【在 p*****2 的大作中提到】

:
: distributed system 机器间不能通讯？

s*r2012-02-25 08:02

37 楼

我来抛砖引玉吧：
题目要求平均任务，其实就是sharding的设计。我的想法：
1. IP知道不？不知道的话每台机器查一下每个URL的IP。
2. 基本思路：url prefix越相似，它crawling的cost也越接近。那么可以build trie
之类的数据结构 for urls，然后round robin assign leaf urls to each machine。
注意seed file一样，每个机器算法一样，那么数据结构也一样。只要每个机器有一个
从1到N的ID， round robin就可以保证不重复，不遗漏。
3. 对不同host的urls，可能用IP来做类似的结构来分配会更balence一些。
replica / error recovery 应该是不用想了。没有机器间通讯没法做。只能假定没有
error。

t*c2012-02-25 08:02

38 楼

我感觉用consistent hashing的思路来hash url，每个机器负责hash值在某个range的
URL，需要让同一个domain下的hash值接近。hash完，和周围机器确认一下就好了，不
需要master

: 我来抛砖引玉吧：

: 题目要求平均任务，其实就是sharding的设计。我的想法：

: 1. IP知道不？不知道的话每台机器查一下每个URL的IP。

: 2. 基本思路：url prefix越相似，它crawling的cost也越接近。那么可以build
trie

: 之类的数据结构 for urls，然后round robin assign leaf urls to each
machine。

: 注意seed file一样，每个机器算法一样，那么数据结构也一样。只要每个机器
有一个

: 从1到N的ID， round robin就可以保证不重复，不遗漏。

: 3. 对不同host的urls，可能用IP来做类似的结构来分配会更balence一些。

: replica / error recovery 应该是不用想了。没有机器间通讯没法做。只能假
定没有

: error。

【在 s****r 的大作中提到】

: 我来抛砖引玉吧：
: 题目要求平均任务，其实就是sharding的设计。我的想法：
: 1. IP知道不？不知道的话每台机器查一下每个URL的IP。
: 2. 基本思路：url prefix越相似，它crawling的cost也越接近。那么可以build trie
: 之类的数据结构 for urls，然后round robin assign leaf urls to each machine。
: 注意seed file一样，每个机器算法一样，那么数据结构也一样。只要每个机器有一个
: 从1到N的ID， round robin就可以保证不重复，不遗漏。
: 3. 对不同host的urls，可能用IP来做类似的结构来分配会更balence一些。
: replica / error recovery 应该是不用想了。没有机器间通讯没法做。只能假定没有
: error。

h*d2012-02-25 08:02

39 楼

大牛能不能多说点，比如load balance,replica是两三个机器组成一个cluster？怎么
知道一个cluster比其他cluster load多？

【在 l********n 的大作中提到】

p*a2012-02-25 08:02

40 楼

这个题目我也遇到了，当时给的条件是机器之间的通信带宽很小，但并不是完全不能通
信。最开始我设计了个二叉树结构的系统，貌似面试官不满意，然后又用了环状的拓扑
结构，consistant hashing 分配url，用选mac地址最大的做master，heartbeat 检测
failure。
[在 ravichouhan (ravi!) 的大作中提到：]
:被问了这个crawler的问题，大概就是给你10K个机器，每个机器有seed url，然
:后要爬1B的url，机器之间不能通信，问你怎么样每个机器才能平均的分任务。同时保
:证每个网站只能被crawler一次。
:奇怪的设计题，完全没有master，就是很多事情都不好做了
:纠缠了十几分钟后突然意识到这完全是个brain teaser式的system design，然后想到
:了类似UUID hashing，对拿到的url做hash，事先规定好每台机器都只做那些hash
:value的job，如果hash的值跟当前机器的预定值不一样就skip，一样才继续crawl
:算是蒙混过关，又问了两个follow up问题，第二个没想好时间就到了
: 1. 如何判断crawling结束
:请问大家什么思路?

c*f2012-02-25 08:02

41 楼

看来都是考这题呀

s*r2012-02-25 08:02

42 楼

Why does consistent hashing help here? Consistent hashing solves the problem
to have minimum hash change when adding a node or removing a node. It seems
having nothing to do with URL locality.
In this question, nodes are fixed. Then consistent hashing can not play a
role here.

build

【在 t******c 的大作中提到】

: 我感觉用consistent hashing的思路来hash url，每个机器负责hash值在某个range的
: URL，需要让同一个domain下的hash值接近。hash完，和周围机器确认一下就好了，不
: 需要master
:
:
: 我来抛砖引玉吧：
:
: 题目要求平均任务，其实就是sharding的设计。我的想法：
:
: 1. IP知道不？不知道的话每台机器查一下每个URL的IP。
:
: 2. 基本思路：url prefix越相似，它crawling的cost也越接近。那么可以build
: trie
:
: 之类的数据结构 for urls，然后round robin assign leaf urls to each

a*02012-02-25 08:02

43 楼

没人考虑从seed url怎么得到之后的url吗？
如果没有通信，每台机器不是还得爬所有的网页，才能得到网页里的url，然后判断是
不是自己负责的）
就算有通信，怎么通信最少也是问题

w*m2012-02-25 08:02

44 楼

是这个问题。所以普通hash不work。上面有人说的按prefix分，像geohash一样，是条
思路

【在 a*********0 的大作中提到】

: 没人考虑从seed url怎么得到之后的url吗？
: 如果没有通信，每台机器不是还得爬所有的网页，才能得到网页里的url，然后判断是
: 不是自己负责的）
: 就算有通信，怎么通信最少也是问题

a*02012-02-25 08:02

45 楼

我觉得你没看明白我的意思，怎么分有意义吗？每台机器不是还得去扒下来所有网页才
能知道自己负责的有哪些

【在 w*********m 的大作中提到】

: 是这个问题。所以普通hash不work。上面有人说的按prefix分，像geohash一样，是条
: 思路

m*e2012-02-25 08:02

46 楼

能不能每台机器爬取后先去重，再扔到一个datastore里。之后每台机器都去这个
datastore取。

s*r2012-02-25 08:02

47 楼

楼主说的题目说seed urls，不通信，还平均workload，还不能重复，基本不make
sense。
还是学点crawler的基本设计吧，比猜题强。比如这篇http://www.michaelnielsen.org/ddi/how-to-crawl-a-quarter-billion-webpages-in-40-hours/

G*O2012-02-25 08:02

48 楼

你说不make sense没用啊，题目这么要求的。
不过lz说的不通信，根据其他面经来看，应该是机器之间bad
connection，尽量少通信。
所以你搞个master就会给master很大的通信。
基本上应该向上面几个人说的，大概弄个环状拓扑，P2P无master才行吧。

【在 s****r 的大作中提到】

: 楼主说的题目说seed urls，不通信，还平均workload，还不能重复，基本不make
: sense。
: 还是学点crawler的基本设计吧，比猜题强。比如这篇http://www.michaelnielsen.org/ddi/how-to-crawl-a-quarter-billion-webpages-in-40-hours/

d*c2012-02-25 08:02

49 楼

这么多人就随意把要求改成允许通讯吗？改成少通讯，改成邻居通讯，面试时不能这么
改题吧，当然问过人家允许了另说，人家不允许怎么办？
也许这个题有人问的是可以通讯，但是楼主的描述仔细读下来是可能的。
1.这不是crawler问题，目的不是爬下所有网页，注意是说1B url
2.不通讯显然是个奇怪要求，不是做不到，会有很多重复工作，但人家问的就是不通讯
，又不是不可能
问的要点就是各自做，不通讯，但仍然能协调。
ip不行，太不均衡，楼主说的url hash我觉得就对了。
geohashing不行，因为任何一个url所引用的url可以来自各种domain，用geohashing没
有任何分隔作用，没有任何优势--你把prefix a的url分给机器a，但是a 引用的url可
能有prefix b的，b还是要爬这个prefix a url
判断结束没啥特别的把，大家都达到预设目标就行了
机器快的话就给快的机器多分一倍hash value

r*g2012-02-25 08:02

50 楼

我觉得就是 hash+queue。机器间不需要通信，把爬到的url都送给message queue 比
如kafka. 可以给kafka 分配10k 个partitions, 每个机器从固定的一个partition来取
url。根据url hash来决定哪个url 去哪个partition. 机器把爬到的url发送给特定的
partition即可。如果一半的机器比另一半的机器快，那就分出15k的partitions. 5k慢
的每个机器读一个partition. 5k快的每个机器读两个partitions.

j*r2012-02-25 08:02

51 楼

不如都扔进Cassandra，已经抓过的就不再抓了，处理1B很轻松。

a*f2012-02-25 08:02

52 楼

总得加一个DB吧？

a*s2012-02-25 08:02

53 楼

不能通信是说机器之间，没说机器和外部系统。一点愚见
要解决load balancing的问题，我引入kafka cluster，就是个distributed queue，把
新找到的link放在tasks topic里面，每个机器注册自己的offset到另外一个topic里面
，用来处理failure的回滚
对于重复访问问题，我用redis做一个visited 的cache，里面放这所有visited过的链
接，如果需要persistence，加一个nosql database （如果数据小用rdbms也可以）
每个机器新找到的link，先与visited比较，如果还有新的，先commit自己的task，然
后把新找到的放回到kafka里面去，自己再从kafka consume一些link（基本task单位，
不可太小，太小会导致通信过度频繁，也不能太大，太大会导致最慢的节点处理不完，
上线是最慢的节点能处理完一个task的时候，所有任务结束，下限是link的处理时间必
须要是通信调度的开销的10倍以上），接着做，并update offset topic（这一步是
commit彻底transaction结束，如果之前有任何错误，不回丢失link，所以必须先
insertnewlink，然后在update offset）。当tasks topic 对应的offset全部昨晚的时
候，就是任务结束的时候。

d*v2012-02-25 08:02

54 楼

mark

P*r2012-02-25 08:02

55 楼

把爬到url放到priority queue里继续爬。priority根据域名计算，但是每个node算
priority的公式不一样，比如按照node id url算hash作为priority。
这样各个node都能有足够的网页爬，并且会优先爬不同的网页

p*r2012-02-25 08:02

56 楼

那就是中心控制了，这题目很明显要求去中心的分布式设计。

【在 m******e 的大作中提到】

: 能不能每台机器爬取后先去重，再扔到一个datastore里。之后每台机器都去这个
: datastore取。

p*r2012-02-25 08:02

57 楼

看来job大牛们都比较保守，没一个出来指点一下的，
算了，我刚刷完一个medium题，现在脑子还比较好使，来说说。
这题在系统设计里算难的，如果自己没做过这样的系统，100%跪，没有例外。
大方向就是先预算每个node的范围，然后对每个url hash后落到相应的node
无论单纯的爬完，还是大致均衡每个node的负载，
只要不涉及到容灾，每台机器之间100%完全不需要通讯，
因为都可以用预处理做到，
也不需要用lb，用lb其实又往中心控制上去了。
请各路top2小硕博后大神拍砖，我是三流野鸡大学非科班最高学历本科生。

p*r2012-02-25 08:02

58 楼

这说明你们刷题都已经到家了，
可怜我现在一道md题刷了一整天，苦逼啊。

【在 d***o 的大作中提到】

: PAT PAT
: 我上上周onsite也跪了个design，上周争取到一个design加试，还是跪了
: 另外我朋友onsite，也是跪在design

s*e2012-02-25 08:02

59 楼

我记得原题是要crawl wikipedia的全部页面，并假设从wiki的主页开始，一定能通过
hyperlink覆盖全部1B pages，不存在孤岛。机器之间不能通信，忘了是不是严格要求
每页只能crawl一次了

g*y2012-02-25 08:02

60 楼

其实我老当年就挂在过这道题上，几年过去了我现在觉得可以用区块链解决。
1. 需要crawl的url存储在一个去中心的社区上，每台机器从任何另一台下载，然后校
验。不同于区块链的是多个末节点，是树桩。
2. 不保证不重复，可以重复，谁先发现了就发布。
3. 与区块链不同，后发现的计算结果和第一个发现者相同，所以计算结果就是校验。
刚发现[email protected]就是一个类似架构上的项目。不过目的不是crawler是科学计算。
我简单看了一下这个项目，还不算是去中心化的。

：
：

x*12012-02-25 08:02

61 楼

用表或者hashSet 去重复，太消耗space了。

x*12012-02-25 08:02

62 楼

大牛，按照url 来hash，会不会极端不balanced。如果需要re-balance有需要一个
central place to coordinate了。不管是distributed queue or data-store。

【在 p**r 的大作中提到】

: 看来job大牛们都比较保守，没一个出来指点一下的，
: 算了，我刚刷完一个medium题，现在脑子还比较好使，来说说。
: 这题在系统设计里算难的，如果自己没做过这样的系统，100%跪，没有例外。
: 大方向就是先预算每个node的范围，然后对每个url hash后落到相应的node
: 无论单纯的爬完，还是大致均衡每个node的负载，
: 只要不涉及到容灾，每台机器之间100%完全不需要通讯，
: 因为都可以用预处理做到，
: 也不需要用lb，用lb其实又往中心控制上去了。
: 请各路top2小硕博后大神拍砖，我是三流野鸡大学非科班最高学历本科生。