游戏排行榜算法设计实现比较

以前在音乐领域做过一些实时投票、积分排名，以及单曲、专辑等排行榜相关工作；在游戏中也有战斗力排行，SNS 游戏还有好友排行等。在此，对这类排行榜算法做一个总结。

需求背景

• 查看前 top N 的排名用户。
• 查看自己的排名。
• 用户积分变更后，排名及时更新。

方案一：利用 MySQL 实现

实现方式

存放一张用户积分表 user_score。取前 top N 和自己的排名都可以通过简单的 SQL 语句实现。

优缺点分析

• 优点：算法简单，利用 SQL 的功能，不需要其他复杂逻辑。
• 缺点：对于数据量较少、性能要求不高的场景可以使用，但对于海量数据，其性能无法接受。

方案二：积分排名数组实现

实现方式

若有 100 万用户进行排名，使用一个大小为 1,000,000 的数组表示积分和排名的对应关系，其中 rank 表示积分 s 所对应的排名。初始化时，rank 数组可以由 user_score 表在 $O(n)$ 的复杂度内计算而来。用户排名的查询和更新基于这个数组进行。查询积分 s 所对应的排名直接返回 rank 即可，复杂度为 $O(1)$；当用户积分从 s 变为 s + n，只需要把 rank[s] 到 rank[s + n - 1] 这 n 个元素的值增加 1 即可，复杂度为 $O(n)$。

方案三：使用 GCC 的 pb_ds 库中的 assoc_container 实现

实现方式

参考 tree_order_statistics.cc 进行实现。

优缺点分析

• 优点：存取效率都可以达到 $O(log(n))$。
• 缺点：程序重启后数据会丢失。

方案四：自己实现排序树

实现思路

把 [0, 1,000,000) 作为一级区间，再将一级区间分为两个二级区间 [0, 500,000) 和 [500,000, 1,000,000)，然后把二级区间二分为 4 个三级区间 [0, 250,000)、[250,000, 500,000)、[500,000, 750,000)、[750,000, 1,000,000)，依此类推，最终会得到 1,000,000 个 21 级区间 [0,1)、[1,2) … [999,999, 1,000,000)。这实际上是把区间组织成了一种平衡二叉树结构，根结点代表一级区间，每个非叶子结点有两个子结点，左子结点代表低分区间，右子结点代表高分区间。树形分区结构需要在更新时保持一种不变量，非叶子结点的 count 值总是等于其左右子结点的 count 值之和。

每次用户积分有变化所需要更新的区间数量和积分变化量有关系，积分变化越小更新的区间层次越低。总体上，每次所需要更新的区间数量是用户积分变量的 $log(n)$ 级别的，也就是说如果用户积分一次变化在百万级，更新区间的数量在二十这个级别。

在这种树形分区积分表的辅助下查询积分为 s 的用户排名，实际上是一个在区间树上由上至下、由粗到细一步步明确 s 所在位置的过程。例如，对于积分 499,000，用一个初值为 0 的排名变量来做累加；首先，它属于 1 级区间的左子树 [0, 500,000)，那么该用户排名应该在右子树 [500,000, 1,000,000) 的用户数 count 之后，把该 count 值累加到该用户排名变量，进入下一级区间；其次，它属于 3 级区间的 [250,000, 500,000)，这是 2 级区间的右子树，所以不用累加 count 到排名变量，直接进入下一级区间；再次，它属于 4 级区间的…；直到最后把用户积分精确定位在 21 级区间 [499,000, 499,001)，整个累加过程完成，得出排名。

优缺点分析

• 优点：结构稳定，不受积分分布影响；每次查询或更新的复杂度为积分最大值的 $O(log(n))$ 级别，且与用户规模无关，可以应对海量规模；不依赖于 SQL，容易改造为 NoSQL 或内存数据结构。
• 缺点：算法相对更复杂。

性能优化

虽然该算法的更新和查询都涉及到若干个操作，但如果为区间的 from_score 和 to_score 建立索引，这些操作都是基于键的查询和更新，不会产生表扫描，因此效率更高。另外，该算法并不依赖于关系数据模型和 SQL 运算，可以轻易地改造为 NoSQL 等其他存储方式，而基于键的操作也很容易引入缓存机制进一步优化性能。进一步估算，树形区间的数目大约为 2,000,000，考虑每个结点的大小，整个结构只占用几十 M 空间。所以，可以在内存建立区间树结构，并通过 user_score 表在 $O(n)$ 的时间内初始化区间树，然后排名的查询和更新操作都可以在内存进行。一般来讲，同样的算法，从数据库到内存算法的性能提升常常可以达到 $10^5$ 以上，因此该算法可以达到非常高的性能。

方案五：skiplist 的实现

实现方式

在实现方案四时，发现代码比较复杂，调试起来不方便。游戏有同事实现的代码地址为：http://km.oa.com/articles/show/158740 。于是想到了跳表，用 hashmap 来存储具体的对象，用 skiplist 用来排序，也可以简单地用一个 map 和 set 来实现，Map 内存放具体对象，set 用来排序。

skip list 是链表的一种特殊形式，是对链表的一种优化，保证 INSERT 和 REMOVE 操作是 $O(logn)$，而通用链表的复杂度为 $O(n)$。

优缺点分析

• 优点：实现较简单，效率基本上为 $O(log(N))$。
• 缺点：当数据达到亿级别时，性能会急剧下降。

方案六：基于 redis 的 sort set 的实现

实现方式

redis 的 zset 天生适用于排行榜、好友列表、去重、历史记录等业务需求，接口使用非常简单且丰富，基本上能满足所需的实现。具体接口复杂度说明如下：

• ZAdd/ZRem 是 $O(log(N))$。
• ZRangeByScore/ZRemRangeByScore 是 $O(log(N)+M)$，其中 N 是 Set 大小，M 是结果/操作元素的个数。

ZSET 的实现用到了两个数据结构：hash table 和 skip list（跳跃表），其中 hash table 是具体使用 redis 中的 dict 来实现的，主要是为了保证查询效率为 $O(1)$，而 skip list（跳跃表）主要是保证元素有序并能够保证 INSERT 和 REMOVE 操作是 $O(logn)$ 的复杂度。音乐现在的通用投票排名系统就是基于 redis 来实现的，运行效果不错。

优缺点分析

• 优点：基于 redis 开发，速度快；可以使用 redis 相关特性。
• 缺点：当数据达到亿级别时，性能会急剧下降。

总结

实现排行榜的方法有很多，可以根据自己的具体需求参考选用合适的算法。