百度笔试题详细讨论

向下

百度笔试题详细讨论

帖子  mutouren1544 于 周五 七月 30, 2010 6:31 pm

特别感谢 PBDigg网友 的友情投稿
在一个有1000万用户的系统中,设计一个推送(feed)系统。以下是一些预定义概念
1、用户:在这个系统中,每个用户用一个递增的unsigned int来表示user id(简写为uid);则uid的范围是从1到1000万的正整数。
2、好友:用户之间可以形成好友关系,好友是双向的;比如说uid为3和uid为4的两个用户可以互为好友。每个用户好友的上限是500个;用户之间的好友关系可以被解除
3、活动:每个用户只能发文章;文章可以被作者删除,其他人不能删除非自己发表的文章;每篇文章通过一个blogid表示。
4、feed:我们希望,每个用户可以看到他所有好友的活动列表,在这个简化的系统中就是所有好友的文章更新列表。
5、访问量要求:所有feed访问量每天在1亿量级;所有的blogid增加量每天在百万量级。
题目:请在以上限制条件下,设计一个高效的feed访问系统。
要求:
1、能够尽快的返回每个用户的好友feed列表,每个用户可以最多保留1000条feed;feed的展现按照时间倒排序,最新的在最前面
2、用户删除某篇文章后,被推出去的feed需要及时消失。即每个用户看到的好友feed都是未被删除的
3、尽可能高效。


我的解答:
用堆来维护好友更新列表,而每个好友的文章列表用链表来表示。由于用户访问太多,需要负载平衡设计,我想法是将每个用户好友放到各个服务器上,有一个中心

服务器,它进行转发请求,在进行查找用户(ID)时可以设计一个Hash.如果效果还不是很好则可以考虑镜像问题,为每个用户信息进行在多台服务器上进行存储,按每个用户信息复制两个副本,分别存储在一个网络中的两台机子上面,这样如果有一个服务器死掉了,用户始终能进行访问.(二流本科生愚见,请高手指教),这个思路借鉴GFS(Google File System)

mutouren1544

帖子数 : 44
注册日期 : 10-07-27

查阅用户资料

返回页首 向下

返回页首


 
您在这个论坛的权限:
不能在这个论坛回复主题