FB设计题求教。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

FB设计题求教。

FB设计题求教。# JobHunting - 待字闺中

t*a2015-01-30 08:01

1 楼

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

p*22015-01-30 08:01

2 楼

redis就可以了

up
aggregator

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

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

t*a2015-01-30 08:01

3 楼

大牛能详细说一下吗，谢了

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

: redis就可以了
:
: up
: aggregator

c*i2015-01-30 08:01

4 楼

关注

g*g2015-01-30 08:01

5 楼

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

up
aggregator

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

t*a2015-01-30 08:01

6 楼

看了一下Cassandra distributed counter的实现算法，这现场弄一个出来略难啊，设
计完整的read/write protocol, vector clock, ack机制。最多说说想法。

【在 g*****g 的大作中提到】

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

w*k2015-01-30 08:01

7 楼

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

g*g2015-01-30 08:01

8 楼

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

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

: 看了一下Cassandra distributed counter的实现算法，这现场弄一个出来略难啊，设
: 计完整的read/write protocol, vector clock, ack机制。最多说说想法。

h*t2015-01-30 08:01

9 楼

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

g*g2015-01-30 08:01

10 楼

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

consistency

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

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

t*a2015-01-30 08:01

11 楼

看了一下，和我说的是一个意思，就是多建几个counter并行处理，然后再sum.
cassandra distributed counter也是一个方法。只不过cassandra加了vector clock,
ack机制。availability 和 fault tolerance更好了。我开始没想明白的是如果自己设
计加counter， counter放在哪一层好。最早想的是放在APP server, 现在看来应该放
在DB server，离data近一点。

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

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

t*a2015-01-30 08:01

12 楼

嗯，明白了，多谢。不过我觉得要是真面这题的话，最后肯定还是要求实现
distributed counter

【在 g*****g 的大作中提到】

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

p*32015-01-30 08:01

13 楼

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原理，拿来会用不就得了。

t*a2015-01-30 08:01

14 楼

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

key

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

: 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原理，拿来会用不就得了。

m*k2015-01-30 08:01

15 楼

redis 3.0 cluster 才出来吧，好用么？

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

: redis就可以了
:
: up
: aggregator

m*k2015-01-30 08:01

16 楼

actually this seems a typical storm/trident use case.

up
aggregator

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

m*k2015-01-30 08:01

17 楼

类似前一段时间好莱坞女星私密照被黑客放出来，转发量并发量可能不会小吧。

【在 g*****g 的大作中提到】

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

g*g2015-01-30 08:01

18 楼

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

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

: 类似前一段时间好莱坞女星私密照被黑客放出来，转发量并发量可能不会小吧。

m*k2015-01-30 08:01

19 楼

对呀，转发通常不就是复制原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?
请大牛指教。

【在 g*****g 的大作中提到】

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

p*22015-01-30 08:01

20 楼

应该不好用自己做cluster

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

: redis 3.0 cluster 才出来吧，好用么？

p*22015-01-30 08:01

21 楼

你说的这些redis都能做

consistency

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