L家系统设计一题讨论 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

L家系统设计一题讨论

L家系统设计一题讨论# JobHunting - 待字闺中

k*r2015-11-29 08:11

1 楼

“已知一个函数，输入用户ID，可以返回该用户的所有友好（degree 1 friends），按
好友ID从小到大排序。要求实现函数来输出返回一个用户的所有好友的好友(degree 2
friends), 以及 degree 3 friends。－－这里感觉主要是聊天看思路，中间会临时加
一些限制条件，来进行时间或者空间的优化。”
这题是想考什么呢？单是3级朋友，是不是BFS就可以解决了？是还要考distributed
system怎样存取用户信息吗？大家有什么思路吗？谢谢，

k*r2015-11-29 08:11

2 楼

大牛们都度假去了吗？还是这个版现在不怎么讨论题了。。。。

b*52015-11-29 08:11

3 楼

一个machine没什么，像FB那样的， gazillion machine来存你的ID-》 friend list
信息，你怎没办？ machine 之间传来床去？
bandwidth怎没办？如果一个user，像justin bieber那样，有gazillion个friends
，你怎没办？

2

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

: “已知一个函数，输入用户ID，可以返回该用户的所有友好（degree 1 friends），按
: 好友ID从小到大排序。要求实现函数来输出返回一个用户的所有好友的好友(degree 2
: friends), 以及 degree 3 friends。－－这里感觉主要是聊天看思路，中间会临时加
: 一些限制条件，来进行时间或者空间的优化。”
: 这题是想考什么呢？单是3级朋友，是不是BFS就可以解决了？是还要考distributed
: system怎样存取用户信息吗？大家有什么思路吗？谢谢，

k*r2015-11-29 08:11

4 楼

对啊，怎么办呢。。。。。牛人能否给点提示啊？？？

list
friends

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

: 一个machine没什么，像FB那样的， gazillion machine来存你的ID-》 friend list
: 信息，你怎没办？ machine 之间传来床去？
: bandwidth怎没办？如果一个user，像justin bieber那样，有gazillion个friends
: ，你怎没办？
:
: 2

j*82015-11-29 08:11

5 楼

看看这个
https://engineering.linkedin.com/real-time-distributed-graph/using-set-cover
-algorithm-optimize-query-latency-large-scale-distributed
他们家engineering blog很多有用信息，多读读吧

2

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

k*r2015-11-29 08:11

6 楼

感谢大牛，我去拜读去啦！
下周就去他家丢人去啦，大牛还有什么可以赐教的吗？在下将感激不尽！！！

cover

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

: 看看这个
: https://engineering.linkedin.com/real-time-distributed-graph/using-set-cover
: -algorithm-optimize-query-latency-large-scale-distributed
: 他们家engineering blog很多有用信息，多读读吧
:
: 2

j*82015-11-29 08:11

7 楼

大牛不敢当
读blog吧，读得越多越好。。

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

: 感谢大牛，我去拜读去啦！
: 下周就去他家丢人去啦，大牛还有什么可以赐教的吗？在下将感激不尽！！！
:
: cover

k*r2015-11-29 08:11

8 楼

多谢！

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

: 大牛不敢当
: 读blog吧，读得越多越好。。

k*r2015-11-29 08:11

9 楼

学习了下这个链接还看了下相关的paper，似乎有了一些概念。
貌似是说建立一个network cache service，里面存有所有member的一层和二层的关系
，这样的话，求一个member的三层关系，只需要one remote call for each 2nd
connector。不知道这样理解对不对。
另外有个疑问，这个NCS，是个只用其memory的cluster吗？这个cluster可以装的下所
有用户以及每个用户所有的二层关系吗？

cover

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

g*e2015-11-29 08:11

10 楼

Its a cache

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

: 学习了下这个链接还看了下相关的paper，似乎有了一些概念。
: 貌似是说建立一个network cache service，里面存有所有member的一层和二层的关系
: ，这样的话，求一个member的三层关系，只需要one remote call for each 2nd
: connector。不知道这样理解对不对。
: 另外有个疑问，这个NCS，是个只用其memory的cluster吗？这个cluster可以装的下所
: 有用户以及每个用户所有的二层关系吗？
:
: cover

k*r2015-11-29 08:11

11 楼

应该不是一个server的cache吧，是个cluster？

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

: Its a cache

g*e2015-11-29 08:11

12 楼

a cluster

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

: 应该不是一个server的cache吧，是个cluster？

r*g2015-11-29 08:11

13 楼

论文的关键好像是说，当需要在db搜索(不是cache)的时候，如何很快找到所有的set，
这个就是apply set coverage algorithm，尽量争取在一台机器上找到，而不是多台机
器。但是它后面有些优化，好像很简单的办法就可以降低latency，这部分没看懂。

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