一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 2915|回复: 31
收起左侧

脸书详细设计题挂经

[复制链接] |试试Instant~ |码农类general, 美国面经, 面试经验, facebook
地里的匿名用户
地里的匿名用户  发表于 2020-6-2 12:38:18 |阅读模式
本楼: 👍   100% (1)
 
 
0% (0)   👎

2020(4-6月) 码农类General 硕士 全职@Facebook - 内推 - Onsite  | Fail/Rej | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
今天得到消息脸书面挂了,我觉得coding考的完全没问题, 全是lc 里面的,即使不是原题也只是稍有变动。 挂就挂在了老大爷design轮。 我发现题目还在,所以放出来给大家讨论一下,大家可以好好准备一下:

我直接翻译成中文,翻译水平见笑了:

假如你是一个黑客,你有10,000台电脑。带宽和cpu 都很高。但是node 之间的访问非常受限。
你从 某个根节点url 开始访问, 大概用过递归能得到10^9个url。你需要吧每个url的内容都下载下来,而且不能重复下载。
现在请你设计一个系统:
下载所有的网站, 不能重复下载, 尽量减少
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
ffic。所以设计的时候要多考虑怎么做到减少node 之间的traffic。

现在面试都面完了, 求大米看包裹。谢谢大家!



评分

参与人数 14大米 +30 收起 理由
dr.rc + 2 谢谢分享!
kylelua + 2 给你点个赞!
lyqk1998 + 1 很有用的信息!
chishui + 1 很有用的信息!
caizhi + 2 很有用的信息!
kiawe + 2 很有用的信息!
qjx026 + 2 很有用的信息!
mchzh + 3 给你点个赞!
Wu_kong + 1 赞一个
thinkmate + 3 很有用的信息!

查看全部评分


上一篇:新鲜巨硬虚拟上门(内含BQ)
下一篇:Facebook Phone Infra 面经
我的人缘0
magicsets 2020-6-3 07:48:53 | 显示全部楼层
本楼: 👍   100% (4)
 
 
0% (0)   👎
全局: 👍   99% (1128)
 
 
0% (8)    👎
树状结构 + 并行化处理在单机多核下的经典框架是 task parallel + work stealing,在分布式场景下应该仍然适用。

很多人可能读过这篇seminal paper(然后作业是用Cilk写黑白棋游戏的并行minimax search):
http://supertech.csail.mit.edu/papers/steal.pdf

回到这个面试题,我们可以把每一个url的下载操作抽象为一个task,那么这个题目的挑战有两点:

(1) task的全集并不是一开始就给定的,而是动态生成的。

也就是说,只有完成了上一层的task(下载了url的页面内容),才能从下载的页面内中知道下一层的 task 是什么 —— 这是典型的task-parallel paradigm,我们可以将读取一个url页面抽象为一个task,task支持run()接口,可以序列化从而调度到其他机器上,run()完成后可以spawn出sub-tasks并添加到任务队列里。

(2) task重调度是需要代价的。

单机下执行节点(worker)是线程,代价相对较小,如果用shared memory的话,主要是细粒度情况下的锁操作/CPU cache miss会成为瓶颈。而分布式场景执行节点是不同的机器/进程,涉及到网络带宽/进程间通信,代价会大很多。

而上面的seminal paper提出了一个解决方案叫做work stealing,从而最小化task的重调度。也就是说每个worker自己的task所生成的subtask先放在本地队列里,尽量自己做。如果有一些worker提前把自己的整个task tree都做完了,那么这些worker可以去“偷”别人的task,而且优先转移task tree中顶层的节点,因为其对应相对较大的subtree,从而减少再次重调度的可能性。

至于如何实现distributed work stealing机制,简单一点就是有一台metadata server,其他机器都每隔一段时间向metadata server报告自己的状态(这个状态可以仅仅是一个整数表示estimated number of unprocessed tasks,所以维护代价非常低)。然后完成了当前所有任务的机器通过metadata server再与需要被steal work的机器建立连接再转移task。

至于分布式消息队列,可以类比为单机情况下使用一个全局阻塞式任务队列来分配tasks到各个线程的方案,比起work stealing来说可能会有大量的重调度开销。

评分

参与人数 1大米 +1 收起 理由
srigter + 1 赞一个

查看全部评分

回复

使用道具 举报

我的人缘0
lch04 2020-6-3 06:04:51 | 显示全部楼层
本楼: 👍   100% (4)
 
 
0% (0)   👎
全局: 👍   94% (356)
 
 
5% (19)    👎
darksoul_xray 发表于 2020-6-3 06:00
你kafka和DB的机子都从这10000台里面出
从node出来N个page 如果你distribute到1000个partition上,就相 ...

你是对的,这题我感觉就是考察P2P
这个帖子我感觉写的还可以 https://medium.com/@morefree7/de ... rawler-f67a8ebb8336
回复

使用道具 举报

我的人缘0
珊珊爱破车 2020-6-22 13:22:26 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (41)
 
 
0% (0)    👎
magicsets 发表于 2020-6-3 07:48
树状结构 + 并行化处理在单机多核下的经典框架是 task parallel + work stealing,在分布式场景下应该仍然 ...

学到了,层主。也大概看了一遍那篇paper,根据楼主对题目的描述,确实work stealing是最好的解决方案。当然如果提出消息队列分发处理,面试官顺便问下how to design message queue也是有可能的。

几个关键点我们考虑用distributed work stealing
1. 资源/性能/计算量 不平均
如果用消息队列, 构建消息队列也需要distributed system(sharding)。如果已有机器的性能不平均 那很容易不平衡。处理消息的worker也会有这种问题。hot partition也会有这种问题。
work stealing不存在不平衡的问题,因为他就是dynamically解决不平衡。

2. 最小化 nodes 通信
消息队列的分发会牵扯大量的nodes之间的通信。针对这个问题尤其明显,因为新生成的url会被放到消息队列,然后消息队列的nodes会分发到各个workernodes。这样下来最小化nodes通信的问题就被放大化了。
work stealing的方法可以是随机抢也可以是层主这样有个metadata server有参考性的去抢。而且每一个node当然优先处理自己本身产生的url,大大减少了nodes之间的不必要communication。

dedup的过程说实话我没有想的特别明白, 根据url partition 在本地去重是可以实现的。但是work stealing之后在新的机器上并没有其他机器的记录,所以100% dedup可能是完成不了的。如果引入shared service记录重复 是不是会增加nodes的communication。这些tradeoff可能要 和面试官讨论。

评分

参与人数 1大米 +1 收起 理由
srigter + 1 赞一个

查看全部评分

回复

使用道具 举报

我的人缘0
darksoul_xray 2020-6-2 14:11:49 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   71% (5)
 
 
28% (2)    👎
如果要求是要尽量减少机器间的互动,那么hash + msg queue的方法应该就不work吧? 因为对于每一个url,你发到的page是随机的
换个角度,如果我们就尽可能地在每台机器上去process某一个hostname下面的所有page,只有遇到外链,我们才distribute到别的机器上。
回复

使用道具 举报

我的人缘0
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   95% (170)
 
 
4% (8)    👎
Consistent hash url,每个节点需要下载的Url就很有限了吧?mur nur hash在10^9这个级别的碰撞是狠少的。

补充内容 (2020-6-1 21:55):
不足够,手机打字不方便 明天来讨论吧。
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
有没有feedback 说你系统设计挂在什么地方?
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (16)
 
 
5% (1)    👎
我理解是要你把10^9的URL下载任务平均分配到10000个host上。因为不能重复下载,所以要host之间做consistent checks。所以最小化host通信实际是要求你最少consistent checks。

我理解这个问题需要预处理。就是先把所有URLcache到一个机器上,在map reduce。cache的时候去重之类的。
回复

使用道具 举报

我的人缘0
YYSW 2020-6-2 23:11:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (20)
 
 
0% (0)    👎
同样问到这题,感觉很炸,除了这题几乎所有都准备了。。。

搜了一下答案,只有一个地方有答案 就是consist hashing url 然后再p2p 的propagate。 但是这样子没法做rate limiting呀。

要想有politeness control的话感觉必须要有一个地方做message queue之类的呀。 否则那个domain不是分分钟炸了吗嘛。

我设计的是

所有通讯都是p2p的,每个node只知道一些别的node,一些node做deduplicator 用consist hash shard, 然后deduplicator会发给一些message queue node 然后这些 message queue node可以limit rate。

然而感觉consist hashing更简单。。。。

面完一搜 感觉就跪了。。。。

回复

使用道具 举报

我的人缘0
happyljx 2020-6-3 02:29:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (66)
 
 
0% (0)    👎
url的domain做hash,作为sharding key。
然后参考canssadra的架构,机器上hash环。每个节点有一段hash的url要处理。如果发现一个不属于自己处理的,可以内部实现一个coordinator类型的,去和对应的node链接,然后send过去,考虑到里面上万机器,应该用短连接。
找对应的node链接,可能还是需要几个个中心metadata的node,但是每次有新域名的时候还是会一个链接(或者按照c*的gossip协议,不太会)。也可以把这个hash给分发到每个机器上。
回复

使用道具 举报

我的人缘0
lulufamilyEYVM 2020-6-3 03:12:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (54)
 
 
0% (0)    👎
billycheung 发表于 2020-6-2 13:16
有没有feedback 说你系统设计挂在什么地方?

没有 就发邮件告诉我挂了。
回复

使用道具 举报

我的人缘0
lulufamilyEYVM 2020-6-3 03:13:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (54)
 
 
0% (0)    👎
simplify 发表于 2020-6-2 14:21
我理解是要你把10^9的URL下载任务平均分配到10000个host上。因为不能重复下载,所以要host之间做consistent ...

10^9个url 你是不知道的。需要通过root url 爬出来。
回复

使用道具 举报

我的人缘0
lulufamilyEYVM 2020-6-3 03:14:15 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (54)
 
 
0% (0)    👎
YYSW 发表于 2020-6-2 23:11
同样问到这题,感觉很炸,除了这题几乎所有都准备了。。。

搜了一下答案,只有一个地方有答案 就是consi ...

我面的时候 当我提到用message queue的时候,面试官就叫我设计message queue。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-7-6 13:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表