前言:
最近想实现一个网页闯关游戏的排行榜设计, 相对而言需求比较简单. 秉承前厂长的训导: “做一件事之前, 先看看别人是怎么做的”. 于是乎网上搜索并参考了不少排行榜的实现机制, 很多人都推荐了redis的有序集(sorted set). 我觉得十分的赞, 技术方案很难在超越已有的模型了, 就看业务上的需求, 做些小改动.
相关文章系列:
记得大概在一年前吧, 写过两篇关于排行榜的文章, 不过那是针对游戏平台(类似微信, 手Q等)而言的. 每个用户都有自己的排行榜, 不是全局性的.
• 社交游戏的排行榜设计和实现(1)
• 社交游戏的排行榜设计和实现(2)
有序集初体验:
先来看几个后续会使用的redis命令语法:
ZADD key score1 member1 [score2 member2]
添加一个或多个成员到有序集合，或者如果它已经存在更新其分数 ZRANGE key start stop [WITHSCORES]
由索引返回一个成员范围的有序集合。 ZSCORE key member
获取给定成员相关联的分数在一个有序集合 ZRANK key member
确定成员的索引中有序集合
更详细和完整的命令, 请点击该链接.
• 案例设计
输入5个学生的成绩(name, score), 实现top-3的查询, 修改某个同学的得分, 再次查询top-3.
1). 添加成绩记录
添加 (lucy, 61), (lily 60), (uncle wang, 10), (lilei, 98), (hanmeimei, 99) 这5人的成绩, 并假定class_rank 为sorted set的name.
2). 第一次top-3查询
3). 更新uncle wang的分数
注: zadd命令既可以添加, 也可以更新
4). 再次top-3查询
场景的设计, 以及最后输出的结果与预期符合.看来redis的sorted set满足需求, 而且特别的方便.
原理浅析:
有了前文的直观体验, 再来研究redis中的有序集合(sorted set), 究竟是何种数据结构, 它能提供什么样的接口, 以及满足什么样的需求呢?
我们来探究下它支持的功能, 首先当然就是支持按分值排序的功能. 由此可以猜测它底层是按score为key, name为value的tree结构(因为支持范围查询, 以及按分值排序). 但是该有序集又支持按name来修改score. 这样需求下, 又演变成name为key, score为value的map结构了. 单独的一种数据结构, 无法满足其需求, 两个都不可或缺. 那答案究竟是什么?
redis源码的定义如下:
typedef struct zset {
// 字典
dict *dict;
// 跳跃表
zskiplist *zsl;
} zset;
这样就比较清晰了, 它采用了复合结构, 字典维护了name=>score的映射表, 而跳跃表则维护了按score排序的列表. 按name和按score的范围查询都天然支持.
具体的解读,可参考<<redis 设计和实现--有序集>>.同时引用官文文档的一张示意图:
总结:
其实我很早就想这篇文章,作为一个游戏编程的爱好者而言,排行榜作为一个基础服务,必然会接触到.早做准备必然是好事,后续如果有机会.我想依据实际的项目,来具体阐述一下,毕竟理论和实战, 还是有所差异.
公众号&游戏站点:
个人微信公众号: 木目的H5游戏世界
个人游戏作品集站点, www.mmxfgame.com, 请点击访问: http://120.26.221.54/.