注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

风轻扬

活着就是为了追求幸福

 
 
 

日志

 
 
关于我

关注互联网应用架构、分布式与海量数据处理技术、云计算、数据库技术

网易考拉推荐

用skip list实现实时排名?  

2009-10-31 13:16:05|  分类: WEB应用 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
博客有积分了,根据积分要排名了,有人希望这个排名是实时的吗?可能会有的吧,这样就可以发一篇文章,马上看下我的排名上升了多少位,由于用博客的人多,可能会发现写一篇文章,就有几万个人被抛在身后,或者原来排名是Top 3.27%,写篇文章后就变成Top 3.16%了,这等感觉多爽啊,我想至少对晓文哥这种试图通过狂发test日志赶上名博的人是有吸引力的吧。

问题是,怎么实现实时排名呢,对于有超过一亿用户,每天登录也有好几百万的博客来说,这不是个容易的问题。以前在博客魅力秀里,人数才不过几十万,都很困难。通过数据库基本没希望,你总不能每次要显示排名的时间,都执行下
SELECT COUNT(*) FROM Users WHERE 积分 < 我的积分;
吧,这种方法一般只有在用户不过万的时间才具有可行性。

以前也用过这样的方法。使用一个表记录积分和排名,初始的排名是脱机计算的,上线后,每当一个用户的积分发生变化,就统计一下新老积分之间的用户数,然后将自己的排名上升这么多位,把被我赶超的用户的排名都下降一位,用SQL语句示意就是这样
cnt = SELECT COUNT(*) FROM Users WHERE 积分 > 我的老积分 AND 积分 < 我的新积分;
UPDATE Users SET 排名 = 排名 - cnt WHERE UserID = 我的ID;
UPDATE Users SET 排名 = 排名 + 1 WHERE 积分 > 我的老积分 AND 积分 < 我的新积分;

使用这种方法,显示排名时是很快,因为排名已经计算好存在在数据库里了。但还是不行,只要人数过十万,积分更新比较频繁(如超过1秒10次),更新时的性能就不行了,并发冲突和死锁问题会非常严重。

可能要做实行排名,比较好的是用skip list,skip list是一个多级索引,如下图所示。由于高级的索引可以跳过大段大段的区间,使用skip list统计比指定的数值小的项的个数的时间复杂度是log(n)级的,节点中的数值发生变化时,更新的代价也是log(n)级。这样,使用skip list作为基本的数据结构实现实时排名是可行的。
用skip list实现实时排名? - 风轻扬 - 风轻扬

skip list适合在内存中实现,一般来说内存的大小不是问题,即使对于博客这样有一亿用户的系统,就算每个用户占用100个字节(良好的实现应该可以做到50个字节左右),总共也不过10G内存,单机就可放得下。不过以下两个问题是需要处理的。

一是单机的处理能力可能跟不上,虽然skip list为纯内存数据结构,但如果一秒有上千次显示排名请求,系统就很可能撑不住。解决这一问题有两个方法,用多个skip list备份,或者按积分区间对skip list进行划分。第二个问题是skip list与数据库的同步。原始的积分信息当然是存储在数据库里的,skip list只不过是一种索引机制。两者同步可以由应用负责,即应用更新积分时同时更新数据库和skip list,也可以通过回放数据库更新日志(如MySQL的binlog或使用触发器来记录日志)来更新skip list。考虑到skip list程序可能崩溃,不能假设skip list中的积分与数据库中的积分总是一致的,这样更新skip list时,需要指定要更新的用户ID而不是用户的新老积分,这样,就需要在skip list的基础上增加一个哈希表,记录用户ID到skip list节点的映射关系。

一个好消息是这样的数据结构我们去年已经做了,当时的skip list是准备用在论坛里用于实现快速跳页的(因为skip list也可以高效定位第n个节点),但后来没用上。相信经过小规模的改造,可能就能用来实现实时排名。
  评论这张
 
阅读(3112)| 评论(9)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017