Facebook system design - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Facebook system design

Facebook system design# JobHunting - 待字闺中

s*x2015-08-07 07:08

1 楼

设计一个系统，能够满足以下条件
boolean CanView(Viewer, Object, Owner);
返回true表示viewer可以看到owner发布的object；返回false则看不到。
Object目前有一个property，可以设置成public或者friends，即如果是public，那么
viewer可以看到object，如果是friends，则viewer必须是owner的friend才可以看到。
请大家过目。
谢谢。

z*82015-08-07 07:08

2 楼

This sounds more like a OO design than system design.

s*x2015-08-07 07:08

3 楼

很不幸，我就是挂在了这个design上。。。
哎，印度女生出题，的确有水平。

【在 z*********8 的大作中提到】

: This sounds more like a OO design than system design.

b*w2015-08-07 07:08

4 楼

具体说说呗　水平体现在哪

【在 s******x 的大作中提到】

: 很不幸，我就是挂在了这个design上。。。
: 哎，印度女生出题，的确有水平。

n*s2015-08-07 07:08

5 楼

这题怎么fail?

s*x2015-08-07 07:08

6 楼

我哪儿不会就问哪儿，可不是水平么 =。=

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

:
: 具体说说呗　水平体现在哪

h*l2015-08-07 07:08

7 楼

is it possible to try it below?
if(Object.property ==public)
return true;
else if(viewer == owner.friend)
return true;
else return false;

【在 s******x 的大作中提到】

: 设计一个系统，能够满足以下条件
: boolean CanView(Viewer, Object, Owner);
: 返回true表示viewer可以看到owner发布的object；返回false则看不到。
: Object目前有一个property，可以设置成public或者friends，即如果是public，那么
: viewer可以看到object，如果是friends，则viewer必须是owner的friend才可以看到。
: 请大家过目。
: 谢谢。

d*g2015-08-07 07:08

8 楼

是不是得考虑scale的问题，如何在FB的规模内存储和读取friends信息和property的信息

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

: is it possible to try it below?
: if(Object.property ==public)
: return true;
: else if(viewer == owner.friend)
: return true;
: else return false;

h*l2015-08-07 07:08

9 楼

i agree with you

信息

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

: 是不是得考虑scale的问题，如何在FB的规模内存储和读取friends信息和property的信息

h*02015-08-07 07:08

10 楼

能否详细说说你怎么挂了？看不出来这题难点在哪儿？
就算是facebook级别的，查一个人的friend要很费劲吗？一个人的friend顶破天有几
千把？

g*g2015-08-07 07:08

11 楼

The problem can be reduced to an isFriend design.
You have 2 users, check if they are friends. There's a classic RDBMS design
and there's a NoSQL design. it's not hard either way.

a*u2015-08-07 07:08

12 楼

普通人是几千，但fb有public page，那就很多很多了

能否详细说说你怎么挂了？看不出来这题难点在哪儿？就算是facebook级别的，查一
个人的friend要很费劲吗？一个人的friend顶破天有几千把？

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

: 能否详细说说你怎么挂了？看不出来这题难点在哪儿？
: 就算是facebook级别的，查一个人的friend要很费劲吗？一个人的friend顶破天有几
: 千把？

s*x2015-08-07 07:08

13 楼

哪儿能看到你说的两个design？

design

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

: The problem can be reduced to an isFriend design.
: You have 2 users, check if they are friends. There's a classic RDBMS design
: and there's a NoSQL design. it's not hard either way.

z*m2015-08-07 07:08

14 楼

if(Object.property ==public)
return true;
else if(Object.property==friends)
if(viewer is owner's friend)
return true;
else return false;
else return false;

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

: is it possible to try it below?
: if(Object.property ==public)
: return true;
: else if(viewer == owner.friend)
: return true;
: else return false;

T*U2015-08-07 07:08

15 楼

friend是双向的，查friend少的那一方就行了

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

: 普通人是几千，但fb有public page，那就很多很多了
:
: 能否详细说说你怎么挂了？看不出来这题难点在哪儿？就算是facebook级别的，查一
: 个人的friend要很费劲吗？一个人的friend顶破天有几千把？

j*32015-08-07 07:08

16 楼

mark

l*e2015-08-07 07:08

17 楼

虽然给了个api
感觉还是主要内容在系统设计
FB的设计估计肯定要考虑scalability

k*a2015-08-07 07:08

18 楼

我觉得这个设计包含两个部分，
1. Object Meta data的storage
2. Friend relationship的管理.
对于1，可以用distributed hash map + memcached解决
对于2，可以参考facebook的TAO设计。就是说维护A-FRIEND-B的GRAPH。对于两个朋友
，使用两个有向边维护。为什么用graph，而不是一般的map设计（比如，A的朋友表示
为A->[B, C, D, ....]）？我觉得主要是scale问题。对于facebook这样这么大的用户
量，用户之间联系这么复杂的，使用map引起的写操作和写锁会非常难处理。对于这个
friend的有向图，主要是处理A-FRIEND-B这样的三元组的读写。那么可以使用
distributed hash map+index。并且用cache加速读操作。可以通过直接写cache，
batch写disk得方法解决写速度问题。
剩下的问题就是函数本身。先取Object,看property,如果是friends，查看owner的朋友
是否包含viewer，然后true/false。
为什么不查看viewer的friends。这就是facebook的特点。1个人发文章，100个人看。
那么owner的信息更有可能在cache中。
我现在就这点水了。大虾们请补充。

z*e2015-08-07 07:08

19 楼

这题很有水平啊
入门门槛不高，随便一个人都可以随便扯蛋出不少东西来
但是要说好比较难，也不是那么难了
看看graph db，比如neo4j之类的设计思想
大概就有谱了