c******n
发帖数: 16666 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: ravichouhan (ravi!), 信区: JobHunting
标 题: 脸家系统设计，web crawler, 机器之间不能通信。
发信站: BBS 未名空间站 (Thu Jun 29 02:17:19 2017, 美东)
被问了这个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. 如果一半机器比另一半快怎样分配
请问大家什么思路? |
c******n
发帖数: 16666 | 2 这题的follow up怎么做啊
怎么都想不出来 尤其是第二个，
机器快没鸟用 如果分配给快的都是土豆服务器上的链接，你本身再快也没用啊
没一个挥鞭子的 互相又不能交流 这效率肯定很低啊 |
y****i
发帖数: 12114 | |
V********n
发帖数: 3061 | 4 把url编码然后加总得一数字，把这个数字除以crawler数量得到余数，一号crawler爬
余数为1的url，二号crawer爬余数为2的.... |
c******n
发帖数: 16666 | 5 你这个只解决了 最开始分配的问题
之后的才是麻烦的
【在 V********n 的大作中提到】
: 把url编码然后加总得一数字，把这个数字除以crawler数量得到余数，一号crawler爬
: 余数为1的url，二号crawer爬余数为2的....
|
c******n
发帖数: 16666 | 6 我也奇怪这点 不是知道是不是原lz转述时候的问题
【在 y****i 的大作中提到】
: 为啥要设定“机器之间不能通信”这个条件？
|
s**********d
发帖数: 36899 | 7 按快慢加权不就好了。
编号后除以总速度，每个机器余数区间按速度比例。
【在 c******n 的大作中提到】
: 你这个只解决了 最开始分配的问题
: 之后的才是麻烦的
|
o****p
发帖数: 9785 | 8 雪特，这第一题小脑也知道hash一下了，居然想十多分钟…
第二题不懂
【在 c******n 的大作中提到】
: 我也奇怪这点 不是知道是不是原lz转述时候的问题
|
c******n
发帖数: 16666 | 9 嗯 第一题没啥好说的 hash了均分了拉到 各种优化都容易有坑
而且本身crawler，分开点弄还不怕被封IP
但是第二个这个完全不知道怎么搞
【在 o****p 的大作中提到】
: 雪特，这第一题小脑也知道hash一下了，居然想十多分钟…
: 第二题不懂
|
V********n
发帖数: 3061 | 10 如果按照余数分配，基本上是非常均匀的，怎么可能出现follow up的问题二呢？如果
知道总url数，follow up的问题一也就不存在了吧 |
V********n
发帖数: 3061 | 11 如果是crawler本身机器快慢或者crawler的算法不同引起的，那应该管用，如果是url
的内容引起的，这样不好使吧
: 按快慢加权不就好了。
: 编号后除以总速度，每个机器余数区间按速度比例。
【在 s**********d 的大作中提到】
: 按快慢加权不就好了。
: 编号后除以总速度，每个机器余数区间按速度比例。
|
w*********m
发帖数: 4740 | 12 hash也有问题，因为1b url不是事先知道的,要用dfs去网上crawl下来去发现新的url
但是如果发现一个URL不在自己的hash范围内，就不去crawl，那就没法去接着发现新的
属于自己的url。很多机器很快就得stop
他还要求每个url只能被crawl一遍，更麻烦。
【在 c******n 的大作中提到】
: 嗯 第一题没啥好说的 hash了均分了拉到 各种优化都容易有坑
: 而且本身crawler，分开点弄还不怕被封IP
: 但是第二个这个完全不知道怎么搞
|
a***e
发帖数: 27968 | 13 尼玛1B，iPV4都遍历了
大家按ip分就是了，快慢机加个权，就是设个单位速度v
每台机器是nv,mv,求和总速度m+n，ip直接求余,然后按m,n分割
麻烦的是网页的密度的处理速度这种有动态的，还有循环的会不会爬死？
不过可以再加个层数？
【在 c******n 的大作中提到】
: 这题的follow up怎么做啊
: 怎么都想不出来 尤其是第二个，
: 机器快没鸟用 如果分配给快的都是土豆服务器上的链接，你本身再快也没用啊
: 没一个挥鞭子的 互相又不能交流 这效率肯定很低啊
|
