游戏中经常有排行榜的需求，例如对玩家的战力进行全服排行，跨服排行，竞技场段位积分排行，副本伤害排行等。设计一个排行榜系统一般来说需要能提供以下接口：

  1. Add：增加或更新键值对（key，score），并能按照score排序；
  2. Remove：根据key删除一个键值对；
  3. Rank：根据key获取排行名次；
  4. TopN：返回前N名（key，score）列表；
  5. Reset：重置；

redis的zset数据结构很契合这个需求，事实上也有很多排行榜是用redis来实现的，这里想基于redis-like zset数据结构，深入分析下游戏中排行榜的特性，探讨一种优化和简单的实现方式。

去除redis的依赖

仅仅是为了使用zset引入redis依赖有些不那么经济，zset本身是skiplist+hashmap的实现，移植到游戏进程内实现并不需要花多少代价，毕竟skiplist相比平衡二叉树一大优势就是实现简单。zset中skiplist的作用是按照score排序，可以认为是一个有序表，以score作key，支持range，rank操作；hashmap的作用则是建立真正的key到score的映射，对外的接口都是以key做参数，需要首先通过hashmap索引到score，再使用score作key去skiplist操作。附上关于redis作者Antirez关于为什么用skiplist而不是平衡二叉树（比如红黑树，AVL）来实现zset的解释：

They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

对zset定制化的改进

skiplist作为有序表，增删查找及rank操作的平均时间复杂度都可以达到O(logn)，原理上用到了冗余的层数加速搜索，也是一种空间换时间的方法，实际使用上当有多个几十万量级的排行榜时，消耗内存很可观。

几乎所有排行榜只需要排出名次靠前的一些玩家（比如前1500名，后面都以1500名举例），超过名次的玩家既不需要展示在排行榜中，亦无需显示名次，那么对于这部分玩家也应用相同代价的排序是否是浪费呢？

有些排行榜的score是只增不减的，比如战斗伤害数值排行，对于这种情况，无需zset这种复杂数据结构，甚至只要维护一个固定长度的有序数组，更新操作就是往后找到比自己大的项，一边比较一边交换，rank操作可以通过维护一个key到数组index的map来达到O(1)的平均时间复杂度，得益于只排前面1500名的玩家，低于1500名分数的可以略过不处理， 整个实现内存紧凑，实现简单，运行高效。

但是，大部分的排行榜score允许增加和降低，基于后1500名无rank需求但有顺序需求，把前1500的玩家放在skiplist进行排行，后面的玩家则放在最大堆中进行排序，前面的人掉下来会移动到堆中并把堆中最大值顶上去，堆的实现可以是数组，所用到的操作pop，push，remove，时间复杂度都是O（logn），另外堆是按照score排序的，需要一个hashmap建立score对应数组的index，方便在O（logn）时间内完成remove操作。得益于heap无需提供rank操作，及实现上紧密的内存结构和O（logn）的最差时间复杂度，性能比全量的skiplist排序无论是时间花费和空间花费都有可观的降低，后面会有详细的benchmark数据比较。

对于同分score的处理，几乎所有排行榜都要求先上榜的排在前面，实现上可以用真实score和一个自增的计数器作为排序的组合key，score相同的计数器值小的优先级高，自增计数器每新添加一个元素则增加1，以此区分加入排行榜的先后顺序。

评测

按照本文所述的代码实现在https://github.com/longzhiri/gozset，实际压测的结果如下：

BenchmarkZSetAdd-4                       1278654               862 ns/op             377 B/op          1 allocs/op
BenchmarkZSetAddNoHeapMap-4               926547              4383 ns/op            1207 B/op          4 allocs/op
BenchmarkZSetRemove-4                    1229588               936 ns/op              43 B/op          1 allocs/op
BenchmarkZSetRemoveNoHeapMap-4           1000000              3270 ns/op             256 B/op          1 allocs/op
BenchmarkZSetRank-4                      3538854               298 ns/op               0 B/op          0 allocs/op
BenchmarkZSetRankNoHeampMap-4            1405663               974 ns/op               0 B/op          0 allocs/op
BenchmarkZSetTopN-4                       132181              8300 ns/op            4912 B/op          2 allocs/op
BenchmarkZSetTopNNoHeapMap-4              133660              9044 ns/op            4912 B/op          2 allocs/op
BenchmarkZSetMarshal-4                     10000            220510 ns/op          229425 B/op          3 allocs/op
BenchmarkZSetMarshalNoHeapMap-4            10000            663226 ns/op          163888 B/op

可以看到使用heap优化后比优化前大致上Add平均快了5倍，内存消耗确只有原来的1/3，Remove快了3倍，内存消耗确只有原来的1/6，Rank快了3倍。