微博(Micro-Blog)顾名思义是微型博客,是一种基于用户关系的信息分享和传播平台,用户可通过浏览器、手机、及时通讯软件(MSN、QQ、Skype等)及外部API接口等多种渠道发布140字以内信息[1]。支持跨平台交流、与移动设备无缝连接的技术优势,饱含Web2.0特质。
有这么一道题 - 微博数据库设计:有A,B,C3个用户,A关注C,C关注A和B;A,B更新后C会收到信息提示,比如:
2010-11-16 22:40 用户A 发表a1;
2010-11-16 22:41 用户土木工程就业方向A 发表a2;
2010-11-16 22:42 用户A 发表a3
2010-11-16 23:40 用户B 发表b1;
2010-11-16 22:40 用户B 发表b2;
问题1:如何设计数据表和查询?
问题2:如果C关注了10000个用户,A被10万个人关注,系统又该如何设计?
2010-11-16 22:41 用户土木工程就业方向A 发表a2;
2010-11-16 22:42 用户A 发表a3
2010-11-16 23:40 用户B 发表b1;
2010-11-16 22:40 用户B 发表b2;
问题1:如何设计数据表和查询?
问题2:如果C关注了10000个用户,A被10万个人关注,系统又该如何设计?
问题1,我的解答是:设计两张表,一张用于表示用户user,有ID,用户名(username),发布内容(message),发布时间(time)等字段;另一张表用于表示用户之间关注,有ID,用户
名(username),关注的用户名,开始关注时间等字段。回去想了想,发现如果数据表照我这样设计的话,问题2的情况就会产生大量的数据,但如果把关注的用户都写在一个记录里那样字符串可能会更大。所以想听听诸位达人的意见,如果是你们会怎样设计数据表呢?
问题1简单而且随意,直接跳过,估计面试的人都不会看。问题2的困难在于:
第一点. C关注的用户太多,设计上必须在显示C的页面的过程中,避免去数据库查询所有被关注的用户是否有更新。
第二点. 第二点.A被关注的人太多,设计上必须在A更新的时候,避免去通知所有关注……
为避免不必要的复杂连接关系,最好还是设计符合第三范式的关系数据。
我想至少应该设计三张表,分别是:
用户表 user:ID,;
关注关系表 attention: ID->ID;
发布信息表 info:ID->message;
用户表 user:ID,;
关注关系表 attention: ID->ID;
发布信息表 info:ID->message;
三张表的设计是比较规范的,至于用户和关注之间的关联要看需求,做join也可以,做DataMap也可以。
个人觉得,需要的逻辑关系在哪儿,而且要进数据库,想不数据量大都不行。当然关注可以不做在一张表中也是一个选择,按关系类型分开走,可以减少特定需求的查询量。
个人觉得,需要的逻辑关系在哪儿,而且要进数据库,想不数据量大都不行。当然关注可以不做在一张表中也是一个选择,按关系类型分开走,可以减少特定需求的查询量。
这玩意得丢内存里头吧 memcached 发新的话题的话丢队列里头写数据库去
user
{
];
];
一句简短浪漫的情话];
}
然后,user[befollow[k]].topics=pics[j];
用户只要检查topics就好了 要不每次上来来个join什么的,估计数据库就挂了
user
{
];
];
一句简短浪漫的情话];
}
然后,user[befollow[k]].topics=pics[j];
用户只要检查topics就好了 要不每次上来来个join什么的,估计数据库就挂了
是直接写到数据库的,不能用join,发贴后就丢队列里,向每一个follow我的人的tweet写数据
不能用纯粹的关系数据库来解决问题,因为数据量和访问量都很大。所以设计必须首要考虑性能问题。
我假定前提,
1、一个用户不经常更改他的关注对象,
2、用户添加关注对象的操作远多于移除关注对象的操作。
3、用户发微博的频率是比较高的,要比更改关注用户操作的频率高。
4、消息的通知到达时间用户是不敏感的
有了这些前提,我们做平衡处理。
我们可以忍受
1、较慢的删除关注用户操作
2、比删除操作快但比发微博操作慢的添加关注用户操作。
3、快的微博提交操作
4、慢的消息通知
我假定前提,
1、一个用户不经常更改他的关注对象,
2、用户添加关注对象的操作远多于移除关注对象的操作。
3、用户发微博的频率是比较高的,要比更改关注用户操作的频率高。
4、消息的通知到达时间用户是不敏感的
有了这些前提,我们做平衡处理。
我们可以忍受
1、较慢的删除关注用户操作
2、比删除操作快但比发微博操作慢的添加关注用户操作。
3、快的微博提交操作
4、慢的消息通知
我们每一个用户建立一个InBox和OutBox,InBox包含关注我的用户ID,OutBox是我关注的用户ID下一站别离评价。
Box分为三个部分,一个是基准Box,一个是添加Box,一个是删除Box,实际的Box数据是基准Box和添加Box的并集和删除Box做差集后得到的集合。
1、用户插入关注用户,在用户的OutBox的添加Box加入一条,同时在被关注用户的庆三八妇女节演讲稿InBox的添加Box也加入一条添加
2、用户删除关主用户,在用户的OutBox的删除Box加入一条,同时在被关注用户的InBox的删除Box十大恐怖电影也加入一条添加
3、微博产生后发送消息,将发送微博的用户的InBox(其中含基准Box,插入Box和删除Box)连同微博操作连接一起发送给消息处理器。
4、消息处理器合并Box,并把Box的内容回写到发送微博用户的InBox的基准Box中。
5、在后台添加一个Box合并进程,缓慢的合并用户的Box数据。
6、前台在展示的时候,因为没有合并,展示列表展示OutBox的基准Box和我新添加用户
Box分为三个部分,一个是基准Box,一个是添加Box,一个是删除Box,实际的Box数据是基准Box和添加Box的并集和删除Box做差集后得到的集合。
1、用户插入关注用户,在用户的OutBox的添加Box加入一条,同时在被关注用户的庆三八妇女节演讲稿InBox的添加Box也加入一条添加
2、用户删除关主用户,在用户的OutBox的删除Box加入一条,同时在被关注用户的InBox的删除Box十大恐怖电影也加入一条添加
3、微博产生后发送消息,将发送微博的用户的InBox(其中含基准Box,插入Box和删除Box)连同微博操作连接一起发送给消息处理器。
4、消息处理器合并Box,并把Box的内容回写到发送微博用户的InBox的基准Box中。
5、在后台添加一个Box合并进程,缓慢的合并用户的Box数据。
6、前台在展示的时候,因为没有合并,展示列表展示OutBox的基准Box和我新添加用户
的Box以及删除用户的Box内容。
前台展示是需要商榷的,看PUM是否接受这种方式,如果不接受,我们只能在刷新时预测查询基准表,并且在页面合并。因为前台展示通常是分页的,这样会比较难获得准确的分页量,每页的显示量会不同。如果需要更高的要求,我们只能再添加其他数据结构。
如果需要更快的算法,我们必须抛弃关系数据库,将用户用B+树做索引,对于Box进行另外处理,需要论述的话,能写一个论文了。
前台展示是需要商榷的,看PUM是否接受这种方式,如果不接受,我们只能在刷新时预测查询基准表,并且在页面合并。因为前台展示通常是分页的,这样会比较难获得准确的分页量,每页的显示量会不同。如果需要更高的要求,我们只能再添加其他数据结构。
如果需要更快的算法,我们必须抛弃关系数据库,将用户用B+树做索引,对于Box进行另外处理,需要论述的话,能写一个论文了。
更正一下,抛弃关系数据库可能更好的方式是,用用户ID做Hash索引,因为用户不删除,只增加。
同时,我们可以采用的物理架构和产品,我们需要到一个轻量级的数据库存储引擎,例如我们可以用BDB,操作系统可以用vxWorks,然后专门针对消息发送和Box做一套系统。
同时,我们可以采用的物理架构和产品,我们需要到一个轻量级的数据库存储引擎,例如我们可以用BDB,操作系统可以用vxWorks,然后专门针对消息发送和Box做一套系统。
更正设计,InBox可以不需要,采用客户端拉的机制,可以去掉InBox,带来的问题就是你
必须在线才能得到通知。
InBox会很大,需要平衡,像姚晨这样的,会把消息处理器累死,所以,需要筛选,消息处理器的需要另外设计。
消息处理器可以去掉,当用户上线时,查阅关注博主的博文变更记录,根据阅读标志,阅读标志为每个用户建立一组。进行伪消息通知。
消息处理器存在于需要主动推送的场合。例如,短信和邮件。不是所有的用户都会进行短信订阅的,所以消息处理器的负载可以减轻。
InBox会很大,需要平衡,像姚晨这样的,会把消息处理器累死,所以,需要筛选,消息处理器的需要另外设计。
消息处理器可以去掉,当用户上线时,查阅关注博主的博文变更记录,根据阅读标志,阅读标志为每个用户建立一组。进行伪消息通知。
消息处理器存在于需要主动推送的场合。例如,短信和邮件。不是所有的用户都会进行短信订阅的,所以消息处理器的负载可以减轻。
陆兄的意思是不是:用DBMS底层的数据库引擎或相关数据结构(比如哈希,B+树等)重新设计一个适合微博应用环境的数据库,而不是利用现有的DBMS进行设计?
数据库是需要的,但不应该是关系型的。自己做数据库是可行的,在这个应用中,或者说需要高速处理的“热”数据中,是不需要关系的,也不应该用关系数据库的设计范式来约束
设计。
对于Box这样的数据结构,是不需要保存在一个关系数据库的数据表中的。做成Hash表会很好,当然可以采用现有的数据库产品,把Box的索引类型定义为Hash的。很多数据库产品是可以这样处理的。
但是,这样会有麻烦,因为Box和用户紧密关联的,不可能为一个用户去建立一个Hash索引的表,这样你又不得不回到关系数据库的老路上去了。你可能会说,我可以定义在Hash主键中包含用户的账号,这样Box的数据自然会按照用户分开了。但是,需要获取用户整个Box数据的时候又碰到麻烦,没有和用户关联的索引去快速检索。
能做的就是把Box保存在内存或者独立的文件中,在这种应用中对数据完整性的要求是很低的,Box应该在内存中保存,在适当的时机脱水持久化。而且活跃的Box可能很少很少。
所以我的建议是分别处理,持久化一块,“热”的实时播发一块,持久化为了简便采用传统
对于Box这样的数据结构,是不需要保存在一个关系数据库的数据表中的。做成Hash表会很好,当然可以采用现有的数据库产品,把Box的索引类型定义为Hash的。很多数据库产品是可以这样处理的。
但是,这样会有麻烦,因为Box和用户紧密关联的,不可能为一个用户去建立一个Hash索引的表,这样你又不得不回到关系数据库的老路上去了。你可能会说,我可以定义在Hash主键中包含用户的账号,这样Box的数据自然会按照用户分开了。但是,需要获取用户整个Box数据的时候又碰到麻烦,没有和用户关联的索引去快速检索。
能做的就是把Box保存在内存或者独立的文件中,在这种应用中对数据完整性的要求是很低的,Box应该在内存中保存,在适当的时机脱水持久化。而且活跃的Box可能很少很少。
所以我的建议是分别处理,持久化一块,“热”的实时播发一块,持久化为了简便采用传统
的关系数据库是可以的。
为了性能,需要特别处理。全部的设计,会很复杂,作为面试题,太难了!
为了性能,需要特别处理。全部的设计,会很复杂,作为面试题,太难了!
为了提高处理能力,并行是不可避免的,需要把Box这样的结构分解分发在不同的机器上处理。但是在这样的应用中,事务又是不需要的,数据完整性也是不需要的,甚至不需要日志来恢复数据,并行处理的时候用传统的RDBMS又会有瓶颈。
所以这不是一个数据库设计问题。靠做关系数据库的设计是完成不了这样的任务的。
所以这不是一个数据库设计问题。靠做关系数据库的设计是完成不了这样的任务的。
就是一个查询时间换空间的问题
本人认为在10万条以内,直接的标准关系型数据库设计就好
更大的话可以考虑做空间换时间的设计
具体可以做内存空间缓存,文件缓存,数据库缓存都可以
就数据库缓存来说,除了标准的关系型数据库外,另外需要加个表做个用户-》关注信息的表端午节四字祝福语
本人认为在10万条以内,直接的标准关系型数据库设计就好
更大的话可以考虑做空间换时间的设计
具体可以做内存空间缓存,文件缓存,数据库缓存都可以
就数据库缓存来说,除了标准的关系型数据库外,另外需要加个表做个用户-》关注信息的表端午节四字祝福语
每次有被关注的用户发布信息,就把其信息的ID写入被关注用户的用户关注信息表,对这个表可以优化,把比较老的数据及时删除。
还有一种折中的做法就是分别对关注关系的关注用户字段和用户信息的用户字段和时间字段做索引,问题就基本能解决,百万级没有问题
如果数量再大,需要对用户信息做时间的分表,保证每个表的信息数量在千万数量级
当然,每次访问都读取数据表就是一种愚蠢的做法,短期内数据不更新的情况下应当从内存读取数据或者文件缓存来读取数据
缓存的更新又是另外一个话题啦
还有一种折中的做法就是分别对关注关系的关注用户字段和用户信息的用户字段和时间字段做索引,问题就基本能解决,百万级没有问题
如果数量再大,需要对用户信息做时间的分表,保证每个表的信息数量在千万数量级
当然,每次访问都读取数据表就是一种愚蠢的做法,短期内数据不更新的情况下应当从内存读取数据或者文件缓存来读取数据
缓存的更新又是另外一个话题啦
问题2的困难在于:
第一点.C关注的用户太多,设计上必须在显示C的页面的过程中,避免去数据库查询所有被关注的用户是否有更新。
第二点.A被关注的人太多,设计上必须在A更新的时候,避免去通知所有关注他的人自己更新了(也就是数据库中为每个人设置标志或者增加记录)。
这两点其实是矛盾的,因为你总需要在某个时候交流“A更新了”这条信息。就需要在系统设计的时候进行折衷和权衡。甚至对不同的用户分类采用不同的方案。
第一点.C关注的用户太多,设计上必须在显示C的页面的过程中,避免去数据库查询所有被关注的用户是否有更新。
第二点.A被关注的人太多,设计上必须在A更新的时候,避免去通知所有关注他的人自己更新了(也就是数据库中为每个人设置标志或者增加记录)。
这两点其实是矛盾的,因为你总需要在某个时候交流“A更新了”这条信息。就需要在系统设计的时候进行折衷和权衡。甚至对不同的用户分类采用不同的方案。
可以采用以下的方案:
普通用户放到一张表中,视为B类。假设绝大多数用户都是B类,即关注的人不太多,被关注也不太多。进一步假设绝大多数的微博记录来自于普通的B类用户。
对那些关注别人太多的,分为C类。专门为C类用户增加一个表,他关注的人如果不是A类,则每次更新都在这张表里面推送一条记录。这样显示C的主页时,只用先查询这张表,再在A类人的专属表中查A类人的更新即可。因为C类的人数比较少,所以这张表应该会比较小,查起来会比较快。
对A类的人,则独立出来成为单独的一张表,供别人查询,因为A类的人数较少,所以这张表应该会比较小,查起来比较快。
这就是一个简单的设计,足以表示你针对问题进行考虑,并给出了有一定效果的解决方案。
当然,这是按照楼上要求的只通过表的设计来实现。
而实际构建系统的时候,该用视图的用视图,该建立索引的建立索引,花样会更多,效果会更好。
以下设计以sqlserver2005为例
记录用户信息的 用户表
Users(uid bigint identity(1000,1) primary key,uname varchar(50) not null unique);
记录A对B的关注信息的 关注表
Attention(byuser bigint foreign key references Users(uid),touser bigint foreign key
references Users(uid) primary key(byuser,touser));
记录用户信息的 用户表
Users(uid bigint identity(1000,1) primary key,uname varchar(50) not null unique);
记录A对B的关注信息的 关注表
Attention(byuser bigint foreign key references Users(uid),touser bigint foreign key
references Users(uid) primary key(byuser,touser));
注:byuser 发起关注者, touser 被关注者
记录某人发表文章信息的 文章表
Article(aid bigint identity(1000,1) primary key,uid bigint foreign key references Users
(uid),title varchar(100) not null,context ntext not null,publishDate datetime not null);
由于需要获取更新信息,所以要能记录哪些文章是查看过,那些不是的文章状态,并且此状态不是文章
的状态,而是每一个文章对于每一个关注者的状态。所以,新表的设计目的是某用户对某文章的查看状
态。
记录某人发表文章信息的 文章表
Article(aid bigint identity(1000,1) primary key,uid bigint foreign key references Users
(uid),title varchar(100) not null,context ntext not null,publishDate datetime not null);
由于需要获取更新信息,所以要能记录哪些文章是查看过,那些不是的文章状态,并且此状态不是文章
的状态,而是每一个文章对于每一个关注者的状态。所以,新表的设计目的是某用户对某文章的查看状
态。
AttentionUpdate(auid bigint identity(1,1) primary key,attentionUser bigint foreign key
references Users(uid),ariticle bigint foreign key references Article(aid) unique
(attentionUser,ariticle),attentionState char(1) not null);
注:unique约束的目的是保证某一个用户对某一个文章的关注唯一;attentionState状态的目的是记录
该用户对该文章的操作状态,比如查看、评论、分享等。
并且由题目得知(题目有不明之处,先查询出的用户A的更新信息是正序,而后查询出的用户B的更新信
references Users(uid),ariticle bigint foreign key references Article(aid) unique
(attentionUser,ariticle),attentionState char(1) not null);
注:unique约束的目的是保证某一个用户对某一个文章的关注唯一;attentionState状态的目的是记录
该用户对该文章的操作状态,比如查看、评论、分享等。
并且由题目得知(题目有不明之处,先查询出的用户A的更新信息是正序,而后查询出的用户B的更新信
息是倒叙,此处就按正序来做),在查询更新信息的时候,需要按照关注用户Id、文章更新时间的正序
排序。
所以
在要求:查询出用户C关注的A和B的关注信息的查询语句
(拟定用户C的ID为1003、A:1001、B:1002)
(拟定文章状态为'1'为未读)
有语句:
select art.publishDate,u.uname,art.title
from Users u,Article art
where u.uid=art.attentionUser and arti.aid in
(select aid from AttentionUpdate where attentionUser=1003 and attentionState='1')
order by u.uid asc,art.publishDate asc
排序。
所以
在要求:查询出用户C关注的A和B的关注信息的查询语句
(拟定用户C的ID为1003、A:1001、B:1002)
(拟定文章状态为'1'为未读)
有语句:
select art.publishDate,u.uname,art.title
from Users u,Article art
where u.uid=art.attentionUser and arti.aid in
(select aid from AttentionUpdate where attentionUser=1003 and attentionState='1')
order by u.uid asc,art.publishDate asc
限制:必须保证AttentionUpdate中的记录表示的关注状态和关注表中的记录相符,即是说 当某用户发表一篇文章的时候,就要根据该用户被关注的情况在AttentionUpdate表中插入attentionState为1 attentionUser为关注其用户的数据;在某用户删除一篇文章的时候,做相应删除;在某用户修改的时候 要做相应修改。
而且还可以做相应扩展,比如对用户分组,对组别设置访问权限。根据权限对AttentionUpdate表中的记录插入做选择性插入即可,修改、删除如是。
以上是我个人的设计,小子是5月份刚从学校毕业的学生,虽然现在在做一家b2c网站的开发,但对性能问题也不是很通透,只能给出一个我能想到的最优的解决方案...但对高并发访问 没有经验,也没有把握,猜测是在视图、存储过程、以及查询上做优化..
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论