r*********n
发帖数: 32 | 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. 如果一半机器比另一半快怎样分配
请问大家什么思路? |
d***o
发帖数: 113 | 2 类似UUID的hashing是不行的，hash出来太分散不能连续crawl
类似geohash的应该可以，hashkey前面一截相同的归一台机器crawl
比如hash出来，如果都是www.facebook.com/user/123起头的都会被hash成9zefzd*
这样判断crawl结束条件就是一直找到没有这个key打头的 |
d***o
发帖数: 113 | 3 第二个follow up不是很懂
是已知一半机器的性能比另一半快吗？
如果是这样，那么性能高的机器分配的hashkey range大点就行 |
h*******d
发帖数: 69 | 4 机器之间不能通信, 机器能跟别的机器（例如一个coordinator)通信吗？ |
w********m
发帖数: 1137 | 5 最简单的就是，把IP地址从0.0.0.0到255.255.255.255切成10k。
seed url如果IP靠的比较近，就扔给哪些弱机器。 |
d***o
发帖数: 113 | 6 ip地址怎么能做切分准则呢
像新浪这种大型网站的一个服务器集群里面，10个ip地址里的url总数比其他一些一千
个ip地址里面的url总数都要多
【在 w********m 的大作中提到】
: 最简单的就是，把IP地址从0.0.0.0到255.255.255.255切成10k。
: seed url如果IP靠的比较近，就扔给哪些弱机器。
|
l*********y
发帖数: 24 | 7 刚刚得到onsite feedback，就跪在这个题上。 |
d***o
发帖数: 113 | 8 PAT PAT
我上上周onsite也跪了个design，上周争取到一个design加试，还是跪了
另外我朋友onsite，也是跪在design
【在 l*********y 的大作中提到】
: 刚刚得到onsite feedback，就跪在这个题上。
|
w********m
发帖数: 1137 | 9 注意，题目说的，1Billion的任务，10k机器。每个机器就10w的任务。不管DFS还是BFS
，爬完收工。
每个机器带着seed url的ip的左边界和右边界，不要越界就可以了。
【在 d***o 的大作中提到】
: ip地址怎么能做切分准则呢
: 像新浪这种大型网站的一个服务器集群里面，10个ip地址里的url总数比其他一些一千
: 个ip地址里面的url总数都要多
|
l**********6
发帖数: 10 | 10 请问楼主和楼上的朋友你们是什么是面试遇到这题的？
小弟上周onsite也遇到一模一样的题目，还在等feedback |
|
|
r*********n
发帖数: 32 | 11 不行，
可以的话啥问题都解决啦，相当于一个master嘛
【在 h*******d 的大作中提到】
: 机器之间不能通信, 机器能跟别的机器（例如一个coordinator)通信吗？
|
h**********e
发帖数: 4328 | 12 现在题都这么难了
还以为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. 如果一半机器比另一半快怎样分配
|
n****l
发帖数: 1739 | 13 硅谷的non engineering team又在装逼。 这种system design的题做好不容易吧。
大牛Linus也只敢说自己设计了git，连Linux kernel都说不是他设计的。 |
h*******d
发帖数: 69 | 14 有没有可能URL的数量小于10w在ip的左边界和右边界。URL的数量和IP RANGE没有关系
吧。
BFS
【在 w********m 的大作中提到】
: 注意，题目说的，1Billion的任务，10k机器。每个机器就10w的任务。不管DFS还是BFS
: ，爬完收工。
: 每个机器带着seed url的ip的左边界和右边界，不要越界就可以了。
|
p*****2
发帖数: 21240 | 15 System design 一般也没有什么正确答案，考察点一般不是设计的正确与否，而是其他
方面。 |
l********n
发帖数: 49 | 16 被问过一模一样的题目，觉得是设计的非常好的题目。解法其实就是自己在设计具有
sharding(设计hash函数，UUID肯定是不对的，其实很简单的hash函数就可以了），
load balance，replicas，error recovery（比如安排一台机器去爬hash=
xxxxx的url机器down了怎么办？）的分布式系统。我记得在答题的时候能够感觉到每回
答出一个followup都是hit到一个分布式系统的重要知识点。这轮是我觉得FB面试中唯
一一轮有技术含量的面试。anyway，最后还是没去FB。 |
p*****2
发帖数: 21240 | 17
distributed system 机器间不能通讯？
【在 l********n 的大作中提到】
: 被问过一模一样的题目，觉得是设计的非常好的题目。解法其实就是自己在设计具有
: sharding(设计hash函数，UUID肯定是不对的，其实很简单的hash函数就可以了），
: load balance，replicas，error recovery（比如安排一台机器去爬hash=
: xxxxx的url机器down了怎么办？）的分布式系统。我记得在答题的时候能够感觉到每回
: 答出一个followup都是hit到一个分布式系统的重要知识点。这轮是我觉得FB面试中唯
: 一一轮有技术含量的面试。anyway，最后还是没去FB。
|
l********n
发帖数: 49 | 18 他理解错题目了，机器间可以通信，但是需要尽量少的通信，两三台之间是可以的。这
样就不能假设有master存在。如果机器完全不能通信爬网页下来也没啥用了不是。
【在 p*****2 的大作中提到】
:
: distributed system 机器间不能通讯？
|
s****r
发帖数: 68 | 19 我来抛砖引玉吧：
题目要求平均任务，其实就是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******c
发帖数: 348 | 20 我感觉用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*******d
发帖数: 69 | 21 大牛能不能多说点，比如load balance,replica是两三个机器组成一个cluster？怎么
知道一个cluster比其他cluster load多？
【在 l********n 的大作中提到】
: 被问过一模一样的题目，觉得是设计的非常好的题目。解法其实就是自己在设计具有
: sharding(设计hash函数，UUID肯定是不对的，其实很简单的hash函数就可以了），
: load balance，replicas，error recovery（比如安排一台机器去爬hash=
: xxxxx的url机器down了怎么办？）的分布式系统。我记得在答题的时候能够感觉到每回
: 答出一个followup都是hit到一个分布式系统的重要知识点。这轮是我觉得FB面试中唯
: 一一轮有技术含量的面试。anyway，最后还是没去FB。
|
p******a
发帖数: 130 | 22 这个题目我也遇到了，当时给的条件是机器之间的通信带宽很小，但并不是完全不能通
信。最开始我设计了个二叉树结构的系统，貌似面试官不满意，然后又用了环状的拓扑
结构，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******f
发帖数: 2144 | |
s****r
发帖数: 68 | 24 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*********0
发帖数: 2727 | 25 没人考虑从seed url怎么得到之后的url吗？
如果没有通信，每台机器不是还得爬所有的网页，才能得到网页里的url，然后判断是
不是自己负责的）
就算有通信，怎么通信最少也是问题 |
w*********m
发帖数: 4740 | 26 是这个问题。所以普通hash不work。上面有人说的按prefix分，像geohash一样，是条
思路
【在 a*********0 的大作中提到】
: 没人考虑从seed url怎么得到之后的url吗？
: 如果没有通信，每台机器不是还得爬所有的网页，才能得到网页里的url，然后判断是
: 不是自己负责的）
: 就算有通信，怎么通信最少也是问题
|
a*********0
发帖数: 2727 | 27 我觉得你没看明白我的意思，怎么分有意义吗？每台机器不是还得去扒下来所有网页才
能知道自己负责的有哪些
【在 w*********m 的大作中提到】
: 是这个问题。所以普通hash不work。上面有人说的按prefix分，像geohash一样，是条
: 思路
|
m******e
发帖数: 82 | 28 能不能每台机器爬取后先去重，再扔到一个datastore里。之后每台机器都去这个
datastore取。 |
s****r
发帖数: 68 | |
G**O
发帖数: 147 | 30 你说不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******c
发帖数: 2407 | 31 这么多人就随意把要求改成允许通讯吗？改成少通讯，改成邻居通讯，面试时不能这么
改题吧，当然问过人家允许了另说，人家不允许怎么办？
也许这个题有人问的是可以通讯，但是楼主的描述仔细读下来是可能的。
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******g
发帖数: 138 | 32 我觉得就是 hash+queue。 机器间不需要通信，把爬到的url都送给message queue 比
如kafka. 可以给kafka 分配10k 个partitions, 每个机器从固定的一个partition来取
url。根据url hash来决定哪个url 去哪个partition. 机器把爬到的url发送给特定的
partition即可。如果一半的机器比另一半的机器快，那就分出15k的partitions. 5k慢
的每个机器读一个partition. 5k快的每个机器读两个partitions. |
j**********r
发帖数: 3798 | 33 不如都扔进Cassandra，已经抓过的就不再抓了，处理1B很轻松。 |
a******f
发帖数: 9 | |
a*****s
发帖数: 1121 | 35 不能通信是说机器之间，没说机器和外部系统。一点愚见
要解决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******v
发帖数: 801 | |
P******r
发帖数: 1342 | 37 把爬到url放到priority queue里继续爬。priority根据域名计算，但是每个node算
priority的公式不一样，比如按照node id url算hash作为priority。
这样各个node都能有足够的网页爬，并且会优先爬不同的网页 |
p**r
发帖数: 5853 | 38 那就是中心控制了，这题目很明显要求去中心的分布式设计。
【在 m******e 的大作中提到】
: 能不能每台机器爬取后先去重，再扔到一个datastore里。之后每台机器都去这个
: datastore取。
|
p**r
发帖数: 5853 | 39 看来job大牛们都比较保守，没一个出来指点一下的，
算了，我刚刷完一个medium题，现在脑子还比较好使，来说说。
这题在系统设计里算难的，如果自己没做过这样的系统，100%跪，没有例外。
大方向就是先预算每个node的范围，然后对每个url hash后落到相应的node
无论单纯的爬完，还是大致均衡每个node的负载，
只要不涉及到容灾，每台机器之间100%完全不需要通讯，
因为都可以用预处理做到，
也不需要用lb，用lb其实又往中心控制上去了。
请各路top2小硕博后大神拍砖，我是三流野鸡大学非科班最高学历本科生。 |
p**r
发帖数: 5853 | 40 这说明你们刷题都已经到家了，
可怜我现在一道md题刷了一整天，苦逼啊。
【在 d***o 的大作中提到】
: PAT PAT
: 我上上周onsite也跪了个design，上周争取到一个design加试，还是跪了
: 另外我朋友onsite，也是跪在design
|
|
|
s*******e
发帖数: 1630 | 41 我记得原题是要crawl wikipedia的全部页面，并假设从wiki的主页开始，一定能通过
hyperlink覆盖全部1B pages，不存在孤岛。机器之间不能通信，忘了是不是严格要求
每页只能crawl一次了 |
g****y
发帖数: 2810 | 42 其实我老当年就挂在过这道题上，几年过去了我现在觉得可以用区块链解决。
1. 需要crawl的url存储在一个去中心的社区上，每台机器从任何另一台下载，然后校
验。不同于区块链的是多个末节点，是树桩。
2. 不保证不重复，可以重复，谁先发现了就发布。
3. 与区块链不同，后发现的计算结果和第一个发现者相同，所以计算结果就是校验。
刚发现[email protected]就是一个类似架构上的项目。不过目的不是crawler是科学计算。
我简单看了一下这个项目，还不算是去中心化的。
：
： |
x*******1
发帖数: 28835 | 43 用表或者hashSet 去重复，太消耗space了。 |
x*******1
发帖数: 28835 | 44 大牛，按照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小硕博后大神拍砖，我是三流野鸡大学非科班最高学历本科生。
|
