c***0
发帖数: 449 | 1 系统设计题：
如果实现像facebook一样的activity broadcast.
一个朋友f1更新一条信息后，他的所有朋友都要看到这条信息。
条件：
1. 朋友数量极大。
2. 有的朋友在线，有的不在线，不在线的登陆后要能看到。
3. 如果储存空间有限，如何处理。
请大牛指教 |
z*********8
发帖数: 2070 | 2 此人所有的activity feed以时间排列 比如 A1, A2 ，A3， A4...
所有朋友的记录里面只需要保留上次得到的最新activity比如 A2 作为bookmark
下次login的时候， 只需要去找所有在A2之后的activity feed即可， 并同时更新
bookmark |
c***0
发帖数: 449 | 3 你是说每次Login都要看几个Millon好友的activity feed? 这些feed 存哪里？怎么存
？新登录的人怎么找到这些activity feed?
【在 z*********8 的大作中提到】
: 此人所有的activity feed以时间排列 比如 A1, A2 ，A3， A4...
: 所有朋友的记录里面只需要保留上次得到的最新activity比如 A2 作为bookmark
: 下次login的时候， 只需要去找所有在A2之后的activity feed即可， 并同时更新
: bookmark
|
p*****2
发帖数: 21240 | |
z*********8
发帖数: 2070 | 5 twitter怎么做？
我在G也遇到了类似的题目， 这个答案是面试官最后告诉我的， 我还和他争了很久，
回来想想貌似还是有道理
【在 p*****2 的大作中提到】
: 这个可以参考twitter吧？
|
b**********5
发帖数: 7881 | 6 no. Friend A who's doing the update is not sending out the feed. It's a
pull style, not a push style. Friend A has million friends, friend 1 to 1
million. Anyone from those range, whoever logs in, and check if there's any
update from their friends.
the updates for each user is ultimately stored in a database. I imagine.
But people can build cache on top of the database. I am just guessing here.
【在 c***0 的大作中提到】
: 你是说每次Login都要看几个Millon好友的activity feed? 这些feed 存哪里？怎么存
: ？新登录的人怎么找到这些activity feed?
|
c***0
发帖数: 449 | 7 问题在于， 你怎么知道哪个friend有update? 每个friend占一个bit 存在一个数列里
供别人查看是否有update吗？
还有个难点是，存储空间有限，如何合理的把所有friend的activity存在里面，然后别
人还能方便的找出来某一个friend的所有activity，等一个activity都发送完后，还要
清空
这个activity。
any
here.
【在 b**********5 的大作中提到】
: no. Friend A who's doing the update is not sending out the feed. It's a
: pull style, not a push style. Friend A has million friends, friend 1 to 1
: million. Anyone from those range, whoever logs in, and check if there's any
: update from their friends.
: the updates for each user is ultimately stored in a database. I imagine.
: But people can build cache on top of the database. I am just guessing here.
|
p*****2
发帖数: 21240 | 8
，
看一下twitter那个video
【在 z*********8 的大作中提到】
: twitter怎么做？
: 我在G也遇到了类似的题目， 这个答案是面试官最后告诉我的， 我还和他争了很久，
: 回来想想貌似还是有道理
|
z*********8
发帖数: 2070 | 9 不好意思做个伸手党了。。。二爷好歹给个关键字嘛
【在 p*****2 的大作中提到】
:
: ，
: 看一下twitter那个video
|
s********u
发帖数: 1109 | 10 那感觉还是有点像linkedlist+hashmap（只不过这里对应的是每个朋友一个node）。
【在 z*********8 的大作中提到】
: 此人所有的activity feed以时间排列 比如 A1, A2 ，A3， A4...
: 所有朋友的记录里面只需要保留上次得到的最新activity比如 A2 作为bookmark
: 下次login的时候， 只需要去找所有在A2之后的activity feed即可， 并同时更新
: bookmark
|
|
|
l*n
发帖数: 529 | 11 其实twitter就是个变种聊天室而已，所以不可能逃出聊天室的设计原理。
看得懂javascript的人可以看看这个，是nodejs开发聊天室的一个很简单的code
http://book.mixu.net/node/ch3.html
对应到当前问题，就是服务器要记得每个friend看过多少条博主的更新，下次登录就把
博主新更新过的内容都发到该friend，在线的人就直接给更新了。
存储空间有限不知道这里是为了限定什么。是博主的所有更新不能全部存储，还是指不
能把更新的内容直接copy到friend的feed文档里？如果需要方便friend搜索自己feed的
内容，大概还是把博主的更新copy过来比较合适，否则靠pointer或者msgID临时再
refer，效果会比较差。
【在 z*********8 的大作中提到】
: 此人所有的activity feed以时间排列 比如 A1, A2 ，A3， A4...
: 所有朋友的记录里面只需要保留上次得到的最新activity比如 A2 作为bookmark
: 下次login的时候， 只需要去找所有在A2之后的activity feed即可， 并同时更新
: bookmark
|
m**p
发帖数: 189 | 12 你怎么什么都用linkedlist+hashmap ?
【在 s********u 的大作中提到】
: 那感觉还是有点像linkedlist+hashmap（只不过这里对应的是每个朋友一个node）。
|
p*u
发帖数: 136 | |
s********u
发帖数: 1109 | 14 你看他给的思路，基本就是list，至于hashmap，这里相当于拿来当个数组。
主要是这个组合太强大了，一般关于维护一个动态的数据结构的设计题，首先肯定是要
求update和insert，delete的效率比较高，那array肯定枪毙掉了。然后stack和queue
用处很局限，何况都可以用list来实现。
list+hashmap，无论读写，效率都是O(1),感觉只有overpowered的可能。
只有在需要优先级或者最值之类问题的时候，才能想到用下heap。或者就是要求一个区
间那种的，那bst比较方便。
话说这道题如果activity需要按照时间顺序而不是朋友的顺序，比如
2月1日 朋友A更新了XXX；
2月2日 朋友B更新了yyy；
2月3日 朋友A更新了zzz；
就复杂了，好像用heap+list也不太方便。
【在 m**p 的大作中提到】
: 你怎么什么都用linkedlist+hashmap ?
|
z****e
发帖数: 54598 | 15 不能说你是错的
但是没有满足第三个条件，存储空间有限
你必需persistence
我觉得用db或者cassandra都好
只要不用hbase这种半天不响应的
不过db可能撑不住，数据继续大下去，p一定要被牺牲掉
用cassandra
参考内森那篇文章
其实这题最简单就告诉它
storm+cassandra
搞定
twitter在low latency上颇有建树，多参考它们的文章
queue
【在 s********u 的大作中提到】
: 你看他给的思路，基本就是list，至于hashmap，这里相当于拿来当个数组。
: 主要是这个组合太强大了，一般关于维护一个动态的数据结构的设计题，首先肯定是要
: 求update和insert，delete的效率比较高，那array肯定枪毙掉了。然后stack和queue
: 用处很局限，何况都可以用list来实现。
: list+hashmap，无论读写，效率都是O(1),感觉只有overpowered的可能。
: 只有在需要优先级或者最值之类问题的时候，才能想到用下heap。或者就是要求一个区
: 间那种的，那bst比较方便。
: 话说这道题如果activity需要按照时间顺序而不是朋友的顺序，比如
: 2月1日 朋友A更新了XXX；
: 2月2日 朋友B更新了yyy；
|
d***n
发帖数: 832 | 16 我觉得这个说得简洁明了
最后数据存储用no sql db
scalability有保证也快
amazon dynamo还全是SSD呢
【在 z*********8 的大作中提到】
: 此人所有的activity feed以时间排列 比如 A1, A2 ，A3， A4...
: 所有朋友的记录里面只需要保留上次得到的最新activity比如 A2 作为bookmark
: 下次login的时候， 只需要去找所有在A2之后的activity feed即可， 并同时更新
: bookmark
|
x******a
发帖数: 11 | |
j*****l
发帖数: 1624 | |
g***j
发帖数: 1275 | 19 他说的什么答案？
，
【在 z*********8 的大作中提到】
: twitter怎么做？
: 我在G也遇到了类似的题目， 这个答案是面试官最后告诉我的， 我还和他争了很久，
: 回来想想貌似还是有道理
|
g*****g
发帖数: 34805 | 20 类似Twitter, C*的time series是这种问题的经典解决方案。根据follower多少和blog
大小，可以对read path和write path做优化, read path优化无非就是caching。对
follower很多的，比如Beyonce那种千万级，caching可能也顶不住，比较可靠的办法就
是把tweet复制到每个人的feed里面。反过来follower少一点，blog大一点，caching就
比较好使，也节省存储。
这年头是个人都有smartphone，在线和离线的区别不明显。主要可以用来决定复制的优
先顺序而已。当然也可以先复制tweet的ID，再复制内容，中间的gap用cache撑着。要根
据follower多少和blog大小，在给定SLA前提下来看那种路线最优。 |
|
|
s******6
发帖数: 57 | |
s******6
发帖数: 57 | |
w*****5
发帖数: 75 | |
m******e
发帖数: 201 | 24 和gmail一样，每次更新就是群发所有好友，gmail怎么做就怎么做。
【在 c***0 的大作中提到】
: 系统设计题：
: 如果实现像facebook一样的activity broadcast.
: 一个朋友f1更新一条信息后，他的所有朋友都要看到这条信息。
: 条件：
: 1. 朋友数量极大。
: 2. 有的朋友在线，有的不在线，不在线的登陆后要能看到。
: 3. 如果储存空间有限，如何处理。
: 请大牛指教
|
s**x
发帖数: 7506 | 25 这个其实就是news feed design 的经典题。
1 limited storage, you have to store one copy for each activity.
So other friends can query. Otherwise, you can store multiple copies for
all his friends.
2. Storage layer. Have to use sharding or some distributed file systems like
google file system.Any persistent storage would work.
3. Friends list is large, again sharding is the key. 1m friends, we can
have 100 servers, each one handles 10k friends only.
4 login/loged out friends.
Loged in friends, use push, ie, message is initiated by the news owner.
Logged out users can query his friends when log in. |
y**********a
发帖数: 824 | |
j******w
发帖数: 91 | |
b*****d
发帖数: 39 | |
W*********y
发帖数: 481 | 29 mark
【在 c***0 的大作中提到】
: 系统设计题：
: 如果实现像facebook一样的activity broadcast.
: 一个朋友f1更新一条信息后，他的所有朋友都要看到这条信息。
: 条件：
: 1. 朋友数量极大。
: 2. 有的朋友在线，有的不在线，不在线的登陆后要能看到。
: 3. 如果储存空间有限，如何处理。
: 请大牛指教
|
l**********1
发帖数: 415 | |
