总在低点割肉， - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Stock

总在低点割肉，

总在低点割肉，# Stock

c*02010-01-21 08:01

1 楼

系统设计题：
如果实现像facebook一样的activity broadcast.
一个朋友f1更新一条信息后，他的所有朋友都要看到这条信息。
条件：
1. 朋友数量极大。
2. 有的朋友在线，有的不在线，不在线的登陆后要能看到。
3. 如果储存空间有限，如何处理。
请大牛指教

x*f2010-01-21 08:01

2 楼

早上八点多刚起来就和老爸打架,打的都报了110.这日子没法过了,我不知道我有没有能力离开我的家.可是我真的好想离开家.离开爸爸,不,现在我都不想叫他爸爸.他不配当我爸爸.并不是我在说气话.10多年了.没有和爸爸一起生活.可我们见面唯一说的话就是骂.我被他骂还没什么,连我妈也跟着我一起挨他骂.爸妈已经离婚整10年了.现如今他俩就跟仇人一样.把我夹在中间,最受气的就是我.他俩不对了,就拿我出气.今天早上我又迎来了一场战争.结果由于我体力不支,身体瘦弱.结果被打的还是我,我在接受深心和身体上的双重摧残．现在被打的浑身是伤，也不知道找谁说．没有人可以帮到我．我家的事谁都管不了．110都管不了，警察说他是我爸爸．打我他们也管不了．现在有气也不知道冲谁撒．
我现在的心理很乱，离家出走都没有条件，我没有地方可以去．朋友家我都不想去，给人家添麻烦,我可以脱离这个家吗?我可以离开我的爸爸妈妈吗?虽然我现在独立了,成年了,可我依然没有条件离开家.离开家我去哪住?这是个很现实的问题.我没有独立生活的勇气.我觉得我自己特没用,爸妈吵架我在中间起不了作用.而且还被打.爸爸这么多年了,脾气一直没有改观,虽然50多岁了,但打起架来还像个年轻人.而且他不念一点感情,甚至打我可以往死了打.他早就不认我这个女儿了.虽然我还叫他爸爸.但他早就不把我当女儿了.觉得做人很失败.自己的爸爸都不认我.我长这么大,从来没有犯过严重错误.他不认我就是因为我妈,他和我妈不合,因为我总站在妈妈这边,所以他也恨我.
让我哭吧，哭出来我会好受一点！现在的我好无助，觉得自己很孤单！

b*n2010-01-21 08:01

3 楼

我的13年5月PD，15年6月RD。降级EB3 140 PP 4月6号被批准。议员主卡崔绿在4月26日
，被
告知“to be assigned to an officer".
自己副卡5月10日 online SR, 11号又得到“ in line to be reviewed by an officer
"的邮件答复。
看来只好等下年度了。

g*42010-01-21 08:01

4 楼

哎！讨个包子寻找安慰。

z*82010-01-21 08:01

5 楼

此人所有的activity feed以时间排列比如 A1, A2 ，A3， A4...
所有朋友的记录里面只需要保留上次得到的最新activity比如 A2 作为bookmark
下次login的时候，只需要去找所有在A2之后的activity feed即可，并同时更新
bookmark

p*e2010-01-21 08:01

6 楼

是的，模版回复，只知道background check 已经通过了，赶紧找议员催，只要有人
work你的case分分钟可以绿。
[在 bigsalmon (salmon) 的大作中提到：]
:我的13年5月PD，15年6月RD。降级EB3 140 PP 4月6号被批准。议员主卡崔绿在4月26
日，被
:告知“to be assigned to an officer".
:自己副卡5月10日 online SR, 11号又得到“ in line to be reviewed by an
officer"的邮件答复。
:看来只好等下年度了。

w*o2010-01-21 08:01

7 楼

你割了啥？今天大盘这样，反正都在跌，我是打算都死捂了。

c*02010-01-21 08:01

8 楼

你是说每次Login都要看几个Millon好友的activity feed? 这些feed 存哪里？怎么存
？新登录的人怎么找到这些activity feed?

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

: 此人所有的activity feed以时间排列比如 A1, A2 ，A3， A4...
: 所有朋友的记录里面只需要保留上次得到的最新activity比如 A2 作为bookmark
: 下次login的时候，只需要去找所有在A2之后的activity feed即可，并同时更新
: bookmark

b*n2010-01-21 08:01

9 楼

谢谢！我再找Senator试试！体检很快要过期了！

g*42010-01-21 08:01

10 楼

哎，割的比止损还低，自从老被MM戏弄，我不再设physical的止损order了，但设在心
里，一到就割，但因为无法盯盘，割时总比止损位低而且往往是最低点。不爽。怎么，
给个baozi吧。

p*22010-01-21 08:01

11 楼

这个可以参考twitter吧？

a*92010-01-21 08:01

12 楼

not good action

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

: 你割了啥？今天大盘这样，反正都在跌，我是打算都死捂了。

z*82010-01-21 08:01

13 楼

twitter怎么做？
我在G也遇到了类似的题目，这个答案是面试官最后告诉我的，我还和他争了很久，
回来想想貌似还是有道理

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

: 这个可以参考twitter吧？

p*y2010-01-21 08:01

14 楼

前几天我的AIG割在最低点,卖了不到两分钟就tmd彪起来两块.好在后来又回调了一下,
心理平衡一点点.今天说什么也不割了,决定加入捂帮了.

b*52010-01-21 08:01

15 楼

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?

w*o2010-01-21 08:01

16 楼

关键是我还不会设止损，以前也经常都割到地板上，所以总是接飞刀-止损-接飞刀-止
损的循环，帐上的钱也就越来越少。相反的我捂得基本都能出水还有盈利。所以我现在
都是只在相对低的位子买，决不追高，这样就算是套也套不了多深，只要不破产。

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

: not good action

c*02010-01-21 08:01

17 楼

问题在于，你怎么知道哪个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*22010-01-21 08:01

18 楼

，
看一下twitter那个video

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

: twitter怎么做？
: 我在G也遇到了类似的题目，这个答案是面试官最后告诉我的，我还和他争了很久，
: 回来想想貌似还是有道理

z*82010-01-21 08:01

19 楼

不好意思做个伸手党了。。。二爷好歹给个关键字嘛

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

:
: ，
: 看一下twitter那个video

s*u2010-01-21 08:01

20 楼

那感觉还是有点像linkedlist+hashmap（只不过这里对应的是每个朋友一个node）。

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

l*n2010-01-21 08:01

21 楼

其实twitter就是个变种聊天室而已，所以不可能逃出聊天室的设计原理。
看得懂javascript的人可以看看这个，是nodejs开发聊天室的一个很简单的code
http://book.mixu.net/node/ch3.html
对应到当前问题，就是服务器要记得每个friend看过多少条博主的更新，下次登录就把
博主新更新过的内容都发到该friend，在线的人就直接给更新了。
存储空间有限不知道这里是为了限定什么。是博主的所有更新不能全部存储，还是指不
能把更新的内容直接copy到friend的feed文档里？如果需要方便friend搜索自己feed的
内容，大概还是把博主的更新copy过来比较合适，否则靠pointer或者msgID临时再
refer，效果会比较差。

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

m*p2010-01-21 08:01

22 楼

你怎么什么都用linkedlist+hashmap ?

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

: 那感觉还是有点像linkedlist+hashmap（只不过这里对应的是每个朋友一个node）。

p*u2010-01-21 08:01

23 楼

mark

s*u2010-01-21 08:01

24 楼

你看他给的思路，基本就是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*e2010-01-21 08:01

25 楼

不能说你是错的
但是没有满足第三个条件，存储空间有限
你必需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*n2010-01-21 08:01

26 楼

我觉得这个说得简洁明了
最后数据存储用no sql db
scalability有保证也快
amazon dynamo还全是SSD呢

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

x*a2010-01-21 08:01

27 楼

Scaling Twitter:
http://www.youtube.com/watch?v=gxUWfQmN8-4
邓侃解剖Twitter:
http://blog.sina.com.cn/s/blog_46d0a3930100fai8.html

j*l2010-01-21 08:01

28 楼

mark

g*j2010-01-21 08:01

29 楼

他说的什么答案？

，

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

: twitter怎么做？
: 我在G也遇到了类似的题目，这个答案是面试官最后告诉我的，我还和他争了很久，
: 回来想想貌似还是有道理

g*g2010-01-21 08:01

30 楼

类似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*62010-01-21 08:01

31 楼

mark

s*62010-01-21 08:01

32 楼

mark

w*52010-01-21 08:01

33 楼

mark

m*e2010-01-21 08:01

34 楼

和gmail一样，每次更新就是群发所有好友，gmail怎么做就怎么做。

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

: 系统设计题：
: 如果实现像facebook一样的activity broadcast.
: 一个朋友f1更新一条信息后，他的所有朋友都要看到这条信息。
: 条件：
: 1. 朋友数量极大。
: 2. 有的朋友在线，有的不在线，不在线的登陆后要能看到。
: 3. 如果储存空间有限，如何处理。
: 请大牛指教

s*x2010-01-21 08:01

35 楼

这个其实就是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.