用skip list实现实时排名?
问题是,怎么实现实时排名呢,对于有超过一亿用户,每天登录也有好几百万的博客来说,这不是个容易的问题。以前在博客魅力秀里,人数才不过几十万,都很困难。通过数据库基本没希望,你总不能每次要显示排名的时间,都执行下
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适合在内存中实现,一般来说内存的大小不是问题,即使对于博客这样有一亿用户的系统,就算每个用户占用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个节点),但后来没用上。相信经过小规模的改造,可能就能用来实现实时排名。
建议继续学习:
- 数学之美:StackOverflow问答排名算法 (阅读:9825)
- Hacker News 排名算法工作原理 (阅读:5374)
- 数学之美:Reddit评论排名算法 (阅读:4555)
- 跳表(skiplist)学习笔记 (阅读:4185)
- IMDB评分排名算法 (阅读:4129)
- 数学之美:Hacker News的热门排名算法 (阅读:4038)
- 实时排名,其实很简单 (阅读:3378)
- Reddit排名算法工作原理 (阅读:2227)
- 深入剖析 redis 数据结构 skiplist (阅读:2223)
- 浅谈 WHR 全历史排名 (阅读:1566)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:风轻扬 来源: 风轻扬
- 标签: skiplist 排名
- 发布时间:2009-11-08 23:16:24
- [67] Oracle MTS模式下 进程地址与会话信
- [65] 如何拿下简短的域名
- [65] Go Reflect 性能
- [59] 图书馆的世界纪录
- [59] 【社会化设计】自我(self)部分――欢迎区
- [59] android 开发入门
- [58] IOS安全–浅谈关于IOS加固的几种方法
- [53] 视觉调整-设计师 vs. 逻辑
- [47] 读书笔记-壹百度:百度十年千倍的29条法则
- [47] 界面设计速成