技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 用skip list实现实时排名?

用skip list实现实时排名?

浏览:5358次  出处信息
    博客有积分了,根据积分要排名了,有人希望这个排名是实时的吗?可能会有的吧,这样就可以发一篇文章,马上看下我的排名上升了多少位,由于用博客的人多,可能会发现写一篇文章,就有几万个人被抛在身后,或者原来排名是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个节点),但后来没用上。相信经过小规模的改造,可能就能用来实现实时排名。    

建议继续学习:

  1. 数学之美:StackOverflow问答排名算法    (阅读:9825)
  2. Hacker News 排名算法工作原理    (阅读:5374)
  3. 数学之美:Reddit评论排名算法    (阅读:4555)
  4. 跳表(skiplist)学习笔记    (阅读:4185)
  5. IMDB评分排名算法    (阅读:4129)
  6. 数学之美:Hacker News的热门排名算法    (阅读:4038)
  7. 实时排名,其实很简单    (阅读:3378)
  8. Reddit排名算法工作原理    (阅读:2227)
  9. 深入剖析 redis 数据结构 skiplist    (阅读:2223)
  10. 浅谈 WHR 全历史排名    (阅读:1566)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1