博客有积分了，根据积分要排名了，有人希望这个排名是实时的吗？可能会有的吧，这样就可以发一篇文章，马上看下我的排名上升了多少位，由于用博客的人多，可能会发现写一篇文章，就有几万个人被抛在身后，或者原来排名是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适合在内存中实现，一般来说内存的大小不是问题，即使对于博客这样有一亿用户的系统，就算每个用户占用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个节点），但后来没用上。相信经过小规模的改造，可能就能用来实现实时排名。    

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习