排行榜是游戏中重要的功能，如何才能实现一个高效的排行榜呢？我所在的项目组做的是SLG游戏，我们游戏的很多活动都有排行榜。上周接到一个跨服排行榜的功能案，需求是让现有的排行榜支持跨服。
一、问题描述
目前每个服的玩家大概4W人，如果战力排行榜做成跨服，开到300个服时，上榜人数会超过1kw。虽然很少有游戏能开到300个服，但作为服务器程序设计功能时必须要考虑极端情况，选择适合的方案，不然可能有推倒重来的风险。下面介绍2种实现排行榜的方案，一是快速排序，另一种是redis实现。
二、快速排序实现
实现方式如下：
- 玩家分数变化时，更新到内存缓存，比如map。
- 用快速排序定时对内存中的数据排序，生成成榜单。
- 把排序生成的榜单推送到对应的区服。
优化：
假如配置榜单只显示前1k名的玩家，除首次排序外，我们可以只让分数>最后一名的玩家参与排名，避免每次都全量排。排完名把1k名以外的玩家移除排序缓存，以保证参与排序的玩家不会越来越多。这样做可以解决排序基数大的问题，把每次需要排序的玩家从1kw减少到1k左右。
但这种方式还是很有局限，比如，不管玩家不上不榜，都要显示自己的名次。这是不是要对所有玩家名排序呢？或者有一个GM需求是从后台查看某榜单前N名的玩家，那又该如何应对呢？
游戏中排行榜比较主流的做法是用redis排序，那么redis内部是如何实现的呢？下面我们结合源码来一探究竟。
三、跳表实现
排行榜的另一种实现方式是使用redis中的有序集合SortedSet，其底层是通过跳跃表实现的。跳跃表拥有非常好的查找、插入、删除性能(logn)，而且可以很方便的获取名次区间内的节点，这恰好是排行榜需要的功能。
1.1 基本思想
跳表非常像一个有序双向链表，它的插入，删除操作都跟双向链表操作类似，需要更新当前节点前驱和后继节点的指针。不同在于，比链表的节点多了层高和跨度的概念。
层高：节点的层数，插入节点时随机生成。 查找节点时，从层高最高的节点开始查找，如果查找score > 当前层下一个节点的score，则继续在当前层查找，否则进入下一层用同样的方法查找，直到查找成功或失败。
跨度：也叫跳数，第i层当前节点到第i层下一个节点的距离，这是跳表的核心。 当查找一个节点时，从当前节点到下一个节点可能直接跳过N个节点，查找路径上的跳数和就是节点在跳表中的名次(升序)。
1.1 数据结构
本文使用的源码版本为redis 6.0跳表结构由2部分组成：
-
跳表节点：跳表是由节点组成的双向链表
-
跳表节点信息：记录了跳表节点的基本信息
1.2 查找
下图是一个节点数为10，层高为4的跳表结构。
绿色箭头为查找score为19的节点需要经历的路径，步骤如下：
- 从header节点不为NULL的最高层开始查找，本例为level4。
- level4的forward指向的节点score为21， 21 > 19, 则查找下一层（level3）
- level3指向的节点score为 9， 9 < 19, 则当前指针指向score为9的节点
- score为9节点的forward节点值为21, 21 > 19, 则查找下一层（level2）
- level2的forward节点值为17， 17 < 19, 则当前指针指向score为17的节点
- score为17节点的forward节点值为21, 21 > 19, 则查找下一层（level1）
- score为17节点(level1)的forward节点值为19, 查找成功
源码：
1.3 插入
1.4 删除
例：通过玩家ID而非分数来查询排行榜中玩家的排名,可以采用如下方法:
- 在redis的跳表结构中,同时以分数score和玩家ID作为键存入记录。
比如:
- 为每个玩家创建一个索引键,值为分数。
比如:
- 查询玩家排名时:
-
首先通过ID键获取玩家的分数值
-
再通过分数值在跳表中查找排名
例如:
这样就可以通过玩家ID直接获取其排名,同时利用跳表保持基于分数的排名有效。