n*********y
发帖数: 41 | 1 刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
list, user可以发Post, 问如何设计friends可见。
后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user朋
友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法？
不知道怎么答了。。
大家有什么好方法吗？ |
t******c
发帖数: 348 | 2 Make the user's friend list as a hash map? |
j**********r
发帖数: 3798 | 3 这东西其实要看N有多大。N不大，读可以，N大，靠写。这是典型的Twitter设计题。
多一层就多给你一个选择，全读，全写，写朋友。选啥要靠实测。
【在 n*********y 的大作中提到】
: 刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
: list, user可以发Post, 问如何设计friends可见。
: 后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user朋
: 友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法？
: 不知道怎么答了。。
: 大家有什么好方法吗？
|
n*********y
发帖数: 41 | 4
假设FB的情况，N=200，每个User200个friend. 请问如果是写的话是用HashMap的意思
吗？写到cache里面？
这东西其实要看N有多大。N不大，读可以，N大，靠写。这是典型的Twitter设计题。
【在 j**********r 的大作中提到】
: 这东西其实要看N有多大。N不大，读可以，N大，靠写。这是典型的Twitter设计题。
: 多一层就多给你一个选择，全读，全写，写朋友。选啥要靠实测。
|
n*********y
发帖数: 41 | 5 请问HashMap的话是不是要放在cache里面，否则跟N^2次DB read得到friend的friend
list也没多大差别了吧？cache能放下这么大hashMap吗？需要sharding？会不会有
overhead啥的？
【在 t******c 的大作中提到】
: Make the user's friend list as a hash map?
|
d****n
发帖数: 12461 | 6 经典题。
每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
），全部去重按时间线逆序合并起来再把帖子读出来。
帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
朋友都在一个地区的话，其实都是内存操作。
【在 n*********y 的大作中提到】
: 刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
: list, user可以发Post, 问如何设计friends可见。
: 后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user朋
: 友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法？
: 不知道怎么答了。。
: 大家有什么好方法吗？
|
n*********y
发帖数: 41 | 7 你说的是friends可见吧，怎么实现friends的friends可见，而且O（N）？
【在 d****n 的大作中提到】
: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。
|
d****n
发帖数: 12461 | 8 你写和读的都是朋友圈啊。
你和小A是朋友，小A和小B是朋友。你的发帖就发到小A那里去了，然后小B读到小A的帖
子里面就有你的。
O(N)是近似，就是假设每个人平均每小时发5个贴，然后每个人平均有20个朋友，然后
每次给你看3小时历史，那就是~N*5*20*3，其中N是你的朋友数。
【在 n*********y 的大作中提到】
: 你说的是friends可见吧，怎么实现friends的friends可见，而且O（N）？
|
j**********r
发帖数: 3798 | 9 写就是直接把帖子写到朋友的timeline里。这样对读优化。这么做的原因就是写可以异
步，对延迟要求不高，而读不行。
牺牲存储可以提高Scalability，避免hot row. 反过来N小读不是问题，就可以对存储优
化。
【在 n*********y 的大作中提到】
: 你说的是friends可见吧，怎么实现friends的friends可见，而且O（N）？
|
p******a
发帖数: 130 | 10 能不能维护一个 friend of friend list？post 的时候根据 privacy 给这个list上的
人发。
[在 neverlandly (neverlandly) 的大作中提到：]
:刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
:list, user可以发Post, 问如何设计friends可见。
:后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user
朋友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法
？ 不知道怎么答了。。
:大家有什么好方法吗？ |
|
|
d****n
发帖数: 12461 | 11 结论是不可行。
例如你和小D是小C的朋友，所以你们俩是FoF。但是如果你删了C，C删了你，C删了D，D
删了C，都会造成你刚刚po给D的帖子必须删掉。
如果考虑到你和D也可以是直接朋友，所以上面当中其中有几个是做不到的。
friend
user
【在 p******a 的大作中提到】
: 能不能维护一个 friend of friend list？post 的时候根据 privacy 给这个list上的
: 人发。
: [在 neverlandly (neverlandly) 的大作中提到：]
: :刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
: :list, user可以发Post, 问如何设计friends可见。
: :后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user
: 朋友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法
: ？ 不知道怎么答了。。
: :大家有什么好方法吗？
|
p******a
发帖数: 130 | 12 每个人按远近程度有不同的 frends list, 假如D也是我的直接朋友，那我的f有 C和D
，然后f of f也有C 和 D。如果我和C删除好友，C从我的f list上消失，D从我的f of
f list上消失；接着C 和 D删除好友，C 从我的 f of f list上消失。最后我的 f
list 上有D，f of f list 空着。这样貌似也可行？
[在 dynkin (化神奇为腐朽) 的大作中提到：]
:结论是不可行。
:例如你和小D是小C的朋友，所以你们俩是FoF。但是如果你删了C，C删了你，C删了D，
D删了C，都会造成你刚刚po给D的帖子必须删掉。
:如果考虑到你和D也可以是直接朋友，所以上面当中其中有几个是做不到的。
:friend
:user |
j**********r
发帖数: 3798 | 13 当然是可以的，timeline这种东西是不recall的。我封了你我不见得想让你知道，我之
前的帖子你可能已经看过了，拿掉反而让你知道我封了你。
，D
【在 d****n 的大作中提到】
: 结论是不可行。
: 例如你和小D是小C的朋友，所以你们俩是FoF。但是如果你删了C，C删了你，C删了D，D
: 删了C，都会造成你刚刚po给D的帖子必须删掉。
: 如果考虑到你和D也可以是直接朋友，所以上面当中其中有几个是做不到的。
:
: friend
: user
|
d****n
发帖数: 12461 | 14 然后面试官就可以问你以下的问题：
我和c已经是好友，然后e加我为好友，你就要把c之前发的帖子全部拷贝一份给e？
我和f原先是好友，然后我删掉了f，你就要在f那里把所有c的帖子删掉，然后在c那里
把所有f的帖子也删掉？
如果我是大v，我有2000个朋友，是不是每次我加减一个好友你都要对我目前所有的好
友之间做一样的操作？
假如我没有加减好友，只是c修改了帖子，是不是对我所有的好友要把之前的旧帖子删
掉或者修改？你觉得数据库怎么设计才可以实现这样随机修改的功能？
D
of
【在 p******a 的大作中提到】
: 每个人按远近程度有不同的 frends list, 假如D也是我的直接朋友，那我的f有 C和D
: ，然后f of f也有C 和 D。如果我和C删除好友，C从我的f list上消失，D从我的f of
: f list上消失；接着C 和 D删除好友，C 从我的 f of f list上消失。最后我的 f
: list 上有D，f of f list 空着。这样貌似也可行？
: [在 dynkin (化神奇为腐朽) 的大作中提到：]
: :结论是不可行。
: :例如你和小D是小C的朋友，所以你们俩是FoF。但是如果你删了C，C删了你，C删了D，
: D删了C，都会造成你刚刚po给D的帖子必须删掉。
: :如果考虑到你和D也可以是直接朋友，所以上面当中其中有几个是做不到的。
: :friend
|
d****n
发帖数: 12461 | 15 这个属于没搞清楚需求。
面试官肯定会问你这个问题：你在fb上加了一个朋友，你觉得是不是想马上可以看到他
朋友圈的帖子？你删了一个朋友，你是不是马上不想看到他所有的朋友圈帖子？
无论你回答是或者否，一般接下来面试官都会按照这个需求来让你设计。
【在 j**********r 的大作中提到】
: 当然是可以的，timeline这种东西是不recall的。我封了你我不见得想让你知道，我之
: 前的帖子你可能已经看过了，拿掉反而让你知道我封了你。
:
: ，D
|
s****3
发帖数: 270 | 16 这个time line 是都存在内存里吗? 因为就算内存crash 似乎也不用重建 history 看
不到就看不到了呗
【在 d****n 的大作中提到】
: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。
|
s****3
发帖数: 270 | 17 大牛能说说这怎么设计吗.....thanks
【在 d****n 的大作中提到】
: 然后面试官就可以问你以下的问题：
: 我和c已经是好友，然后e加我为好友，你就要把c之前发的帖子全部拷贝一份给e？
: 我和f原先是好友，然后我删掉了f，你就要在f那里把所有c的帖子删掉，然后在c那里
: 把所有f的帖子也删掉？
: 如果我是大v，我有2000个朋友，是不是每次我加减一个好友你都要对我目前所有的好
: 友之间做一样的操作？
: 假如我没有加减好友，只是c修改了帖子，是不是对我所有的好友要把之前的旧帖子删
: 掉或者修改？你觉得数据库怎么设计才可以实现这样随机修改的功能？
:
: D
|
j**********r
发帖数: 3798 | 18 timeline都是做成immutable, 这才是scalability的关键。朋友圈帖子在前，删朋友在
后，完全没有收回的必要。收回反而显得不自然。微信你要recall,也就给你很短时间。
【在 d****n 的大作中提到】
: 这个属于没搞清楚需求。
: 面试官肯定会问你这个问题：你在fb上加了一个朋友，你觉得是不是想马上可以看到他
: 朋友圈的帖子？你删了一个朋友，你是不是马上不想看到他所有的朋友圈帖子？
: 无论你回答是或者否，一般接下来面试官都会按照这个需求来让你设计。
|
d****n
发帖数: 12461 | 19 前面有。
【在 s****3 的大作中提到】
: 大牛能说说这怎么设计吗.....thanks
|
p******a
发帖数: 130 | 20 谢谢指点！有一点不太明白的是为什么要在朋友（或者朋友的朋友）的timeline中主动
删之前的post，是不是跟pull/push方式的选择有关？假定我们使用pull模式，用户登
录或者刷新后，根据自己的friend list 和 f of f list 去pull有权限的posts；此后
若任何朋友关系变动，只更新这两个lists；直到下次再登陆或者刷新的时候，根据改
动后的lists去pull。大v的问题是不是可以特殊处理：对大v不考虑 f of f 关系？
【在 d****n 的大作中提到】
: 然后面试官就可以问你以下的问题：
: 我和c已经是好友，然后e加我为好友，你就要把c之前发的帖子全部拷贝一份给e？
: 我和f原先是好友，然后我删掉了f，你就要在f那里把所有c的帖子删掉，然后在c那里
: 把所有f的帖子也删掉？
: 如果我是大v，我有2000个朋友，是不是每次我加减一个好友你都要对我目前所有的好
: 友之间做一样的操作？
: 假如我没有加减好友，只是c修改了帖子，是不是对我所有的好友要把之前的旧帖子删
: 掉或者修改？你觉得数据库怎么设计才可以实现这样随机修改的功能？
:
: D
|
|
|
w**z
发帖数: 8232 | 21 fanout 一般都是在写的时候做的。 immutable 确实是关键。如果能把 post 做到能改
的就太牛了。
timeline都是做成immutable, 这才是scalability的关键。朋友圈帖子在前，删朋
友在
间。
【在 j**********r 的大作中提到】
: timeline都是做成immutable, 这才是scalability的关键。朋友圈帖子在前，删朋友在
: 后，完全没有收回的必要。收回反而显得不自然。微信你要recall,也就给你很短时间。
|
F*********0
发帖数: 602 | 22 上路了已经
【在 p******a 的大作中提到】
: 谢谢指点！有一点不太明白的是为什么要在朋友（或者朋友的朋友）的timeline中主动
: 删之前的post，是不是跟pull/push方式的选择有关？假定我们使用pull模式，用户登
: 录或者刷新后，根据自己的friend list 和 f of f list 去pull有权限的posts；此后
: 若任何朋友关系变动，只更新这两个lists；直到下次再登陆或者刷新的时候，根据改
: 动后的lists去pull。大v的问题是不是可以特殊处理：对大v不考虑 f of f 关系？
|
a****o
发帖数: 6612 | 23 大牛，我想了一天，终于明白你的解释了。
这个应该算O(N)的算法。
【在 d****n 的大作中提到】
: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。
|
n*********y
发帖数: 41 | 24 大牛你好，我今天跟FB一专门搞privacy的美国大牛又谈到了这个问题，把post时候写
到朋友timeline这个思路跟他说了一遍，想不到他是这样回复的：
This can be done simpler, without any extra writes.
A hint: You are thinking about the problem as "How to check if C is a friend
of friends of A". But it is possible to rephrase the question in an other
way which will make the problem much simpler to solve.
竟然还有更好的办法，any idea？
【在 d****n 的大作中提到】
: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。
|
m******3
发帖数: 346 | |
a****i
发帖数: 1182 | 26 这个意思是A写的时候写到朋友B那儿
然后B的朋友C从B那儿读？
然后复杂度，写是A的朋友个数；读是C的朋友个数？
【在 a****o 的大作中提到】
: 大牛，我想了一天，终于明白你的解释了。
: 这个应该算O(N)的算法。
|
s*****p
发帖数: 30 | 27
我知道我来的很晚了， 但是 我还是有个疑惑想问问，不知道你看不看得到。
就是读帖子的时候从朋友那里度， 写的时候也全部写到朋友那里，
那么这样就有个问题就是你自己的朋友的post你怎么读到呢？
比如你和A是好友， A发一个帖子到你的 timeline去了， 但是你看帖的时候只会从你
的朋友的timeline里面去找， 这样是找不到A的帖子的啊？ 除了这一个疑惑， 我觉得
您的思路很好的解决了friends of friends的问题，很棒！
【在 d****n 的大作中提到】
: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。
|
s********k
发帖数: 6180 | 28 所有人的post都进一个大immutable hash table，key 是user id， value是内容，你
每次读只需要本地搞定friend，FoF或者其他隐私，算出来一个读user的list，然后去
table把内容都读出来
scalability再扩展慢慢来，
friend
【在 n*********y 的大作中提到】
: 大牛你好，我今天跟FB一专门搞privacy的美国大牛又谈到了这个问题，把post时候写
: 到朋友timeline这个思路跟他说了一遍，想不到他是这样回复的：
: This can be done simpler, without any extra writes.
: A hint: You are thinking about the problem as "How to check if C is a friend
: of friends of A". But it is possible to rephrase the question in an other
: way which will make the problem much simpler to solve.
: 竟然还有更好的办法，any idea？
|
f*****n
发帖数: 2126 | |
f*****n
发帖数: 2126 | |
|
|
d******v
发帖数: 801 | |
