当前在线人数17985
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
Re: FB设计题求教。
[版面:待字闺中][首篇作者:tdscdma] , 2015年01月30日04:07:27 ,2339次阅读,20次回复
来APP回复,赚取更多伪币 关注本站公众号:
[首页][上页] [下页] [末页][分页:1 2 ]
peking2
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: peking2 (Lambda), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 07:24:27 2015, 美东)

redis就可以了


【 在 tdscdma (tdscdma) 的大作中提到: 】
: 原题
: design photo reference counting system at fb scale
: 感觉这题主要是要解决high volume concurrent writing. 我想的是如果要scaling
up
: , 在每个Appserver 上对每个photo加一个counter,然后每隔T时间传到一个
aggregator
: 把所有与目标相关的counter相加,然后update DB和Memcached. 一些细节还没想清楚
: ,求讨论。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 166.]

 
tdscdma
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: tdscdma (tdscdma), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 13:25:52 2015, 美东)

大牛能详细说一下吗,谢了
【 在 peking2 (Lambda) 的大作中提到: 】
: redis就可以了
: up
: aggregator



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 216.]

 
ctci
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: ctci (ctci), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 15:57:27 2015, 美东)

关注
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 63.]

 
goodbug
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: goodbug (好虫), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 16:22:32 2015, 美东)

fb这样的系统,photo数量很大,但是每个photo的count不高。有很多方法都可以。
MySQL sharding, Cassandra distributed counter. 二爷说的Redis cluster
optimistic locking 也行。


【 在 tdscdma (tdscdma) 的大作中提到: 】
: 原题
: design photo reference counting system at fb scale
: 感觉这题主要是要解决high volume concurrent writing. 我想的是如果要scaling
up
: , 在每个Appserver 上对每个photo加一个counter,然后每隔T时间传到一个
aggregator
: 把所有与目标相关的counter相加,然后update DB和Memcached. 一些细节还没想清楚
: ,求讨论。






--
※ 修改:·goodbug 於 Jan 30 16:29:15 2015 修改本文·[FROM: 69.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
tdscdma
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: tdscdma (tdscdma), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 16:42:18 2015, 美东)

看了一下Cassandra distributed counter的实现算法,这现场弄一个出来略难啊,设
计完整的read/write protocol, vector clock, ack机制。最多说说想法。
【 在 goodbug (好虫) 的大作中提到: 】
: fb这样的系统,photo数量很大,但是每个photo的count不高。有很多方法都可以。
: MySQL sharding, Cassandra distributed counter. 二爷说的Redis cluster
: optimistic locking 也行。
: up
: aggregator



--
※ 修改:·tdscdma 於 Jan 30 16:43:38 2015 修改本文·[FROM: 66.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 66.]

 
waxwak
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: waxwak (AAA), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 16:45:47 2015, 美东)

google的技术讲座,讲到了并发counter的设计,应该是类似的。
http://highscalability.com/numbers-everyone-should-know
前面有人说redis,许多面试恐怕不会允许用这样,或者要求你说明redis怎么运作的。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
goodbug
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: goodbug (好虫), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 16:47:36 2015, 美东)

我的意思就是单counter上的并发量不大,哪怕RDBMS都够了。所谓scale在图片数量上
,这个除了sharding别无他法。

【 在 tdscdma (tdscdma) 的大作中提到: 】
: 看了一下Cassandra distributed counter的实现算法,这现场弄一个出来略难啊,设
: 计完整的read/write protocol, vector clock, ack机制。最多说说想法。




--
※ 修改:·goodbug 於 Jan 30 16:48:05 2015 修改本文·[FROM: 69.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
hlight
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: hlight (hlight), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 17:22:12 2015, 美东)

F家设计题如果只提到用什么tech/framework来实现是行不通的,面试官接着会更详细
的问具体是如何实现的。而重心通常都围绕着scalability, partitioning,
replication,fault tolerance, availability, concurrency, caching, consistency
之类的问题。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
goodbug
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: goodbug (好虫), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 17:26:58 2015, 美东)

这道题单counter并发量又不大,最简单的transaction即可。

【 在 hlight (hlight) 的大作中提到: 】
: F家设计题如果只提到用什么tech/framework来实现是行不通的,面试官接着会更详细
: 的问具体是如何实现的。而重心通常都围绕着scalability, partitioning,
: replication,fault tolerance, availability, concurrency, caching,
consistency
: 之类的问题。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 69.]

 
tdscdma
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: tdscdma (tdscdma), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 20:11:26 2015, 美东)

看了一下,和我说的是一个意思,就是多建几个counter并行处理,然后再sum.
cassandra distributed counter也是一个方法。只不过cassandra加了vector clock,
ack机制。availability 和 fault tolerance更好了。我开始没想明白的是如果自己设
计加counter, counter放在哪一层好。最早想的是放在APP server, 现在看来应该放
在DB server,离data近一点。
【 在 waxwak (AAA) 的大作中提到: 】
: google的技术讲座,讲到了并发counter的设计,应该是类似的。
: http://highscalability.com/numbers-everyone-should-know
: 前面有人说redis,许多面试恐怕不会允许用这样,或者要求你说明redis怎么运作的。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
tdscdma
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: tdscdma (tdscdma), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 20:20:24 2015, 美东)

嗯,明白了,多谢。不过我觉得要是真面这题的话,最后肯定还是要求实现
distributed counter
【 在 goodbug (好虫) 的大作中提到: 】
: 这道题单counter并发量又不大,最简单的transaction即可。
: consistency



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
peking3
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: peking3 (doofus programmer), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 21:12:31 2015, 美东)

request 会打在web server上,每个web server再实时的batch processing log,再内
存keep一个简单的aggregation map。batch size 到了就把old aggregation map写到
sharded的key value store上,一般支持batch write一个shard就发一个request,key
value
store最好支持merge operation,不支持race condition的几率也很小。

解释个毛线的key value store原理,拿来会用不就得了。


--
※ 修改:·peking3 於 Jan 30 21:16:33 2015 修改本文·[FROM: 199.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 199.]

 
tdscdma
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: tdscdma (tdscdma), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Fri Jan 30 21:51:51 2015, 美东)

多谢。不过面试真没准,有的人就瞎问。我CV上没写任何data base,file system还被
人问过I-NODE, D-NODE,以及如何实现。写Dijkstra算法,让自己实现heap(这个还好)
,然后再解释A*。


【 在 peking3 (doofus programmer) 的大作中提到: 】
: request 会打在web server上,每个web server再实时的batch processing log,再内
: 存keep一个简单的aggregation map。batch size 到了就把old aggregation map写到
: sharded的key value store上,一般支持batch write一个shard就发一个request,
key
:  value
: store最好支持merge operation,不支持race condition的几率也很小。
: 解释个毛线的key value store原理,拿来会用不就得了。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
madmonk
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: madmonk (madmonk), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Sat Jan 31 01:47:10 2015, 美东)

redis 3.0 cluster 才出来吧,好用么?


【 在 peking2 (Lambda) 的大作中提到: 】
: redis就可以了
: up
: aggregator




--
※ 修改:·madmonk 於 Jan 31 02:18:36 2015 修改本文·[FROM: 76.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
madmonk
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: madmonk (madmonk), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Sat Jan 31 01:47:39 2015, 美东)

actually this seems a typical storm/trident use case.

【 在 tdscdma (tdscdma) 的大作中提到: 】
: 原题
: design photo reference counting system at fb scale
: 感觉这题主要是要解决high volume concurrent writing. 我想的是如果要scaling
up
: , 在每个Appserver 上对每个photo加一个counter,然后每隔T时间传到一个
aggregator
: 把所有与目标相关的counter相加,然后update DB和Memcached. 一些细节还没想清楚
: ,求讨论。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
madmonk
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: madmonk (madmonk), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Sat Jan 31 01:52:10 2015, 美东)

类似前一段时间好莱坞女星私密照被黑客放出来,转发量并发量可能不会小吧。
【 在 goodbug (好虫) 的大作中提到: 】
: 这道题单counter并发量又不大,最简单的transaction即可。
: consistency



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
goodbug
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 18 ]

发信人: goodbug (好虫), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Sat Jan 31 02:06:44 2015, 美东)

转发的做法是复制,T的东西尤其典型。这种面试题主要是看你思路,如果前提跟面试
官不一致会很快提醒你,知道定量分析恐怕比分布式计数器的算法更有意义。


【 在 madmonk (madmonk) 的大作中提到: 】
: 类似前一段时间好莱坞女星私密照被黑客放出来,转发量并发量可能不会小吧。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

 
madmonk
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 19 ]

发信人: madmonk (madmonk), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Sat Jan 31 02:53:26 2015, 美东)

对呀,转发通常不就是复制原link么?

For photo reference counting, take mitbbs logo as example,
My understanding is how many times "http://www.mitbbs.com/img/logo_us.gif"  is requested.

unless photo reference counting means different?
请大牛指教。


【 在 goodbug (好虫) 的大作中提到: 】
: 转发的做法是复制,T的东西尤其典型。这种面试题主要是看你思路,如果前提跟面试
: 官不一致会很快提醒你,知道定量分析恐怕比分布式计数器的算法更有意义。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
peking2
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 20 ]

发信人: peking2 (Lambda), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Sat Jan 31 03:51:46 2015, 美东)

应该不好用 自己做cluster


【 在 madmonk (madmonk) 的大作中提到: 】
: redis 3.0 cluster 才出来吧,好用么?

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 166.]

 
peking2
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 21 ]

发信人: peking2 (Lambda), 信区: JobHunting
标  题: Re: FB设计题求教。
发信站: BBS 未名空间站 (Sat Jan 31 03:53:06 2015, 美东)

你说的这些redis都能做


【 在 hlight (hlight) 的大作中提到: 】
: F家设计题如果只提到用什么tech/framework来实现是行不通的,面试官接着会更详细
: 的问具体是如何实现的。而重心通常都围绕着scalability, partitioning,
: replication,fault tolerance, availability, concurrency, caching,
consistency
: 之类的问题。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 166.]

[首页][上页] [下页] [末页][分页:1 2 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996