利用Redis的有序集合实现排行榜功能实例代码

前言

游戏中存在各种各样的排行榜,比如玩家的等级排名、分数排名等。玩家在排行榜中的名次是其实力的象征,位于榜单前列的玩家在虚拟世界中拥有无尚荣耀,所以名次也就成了核心玩家的追求目标。

一个典型的游戏排行榜包括以下常见功能:

  1. 能够记录每个玩家的分数;
  2. 能够对玩家的分数进行更新;
  3. 能够查询每个玩家的分数和名次;
  4. 能够按名次查询排名前N名的玩家;
  5. 能够查询排在指定玩家前后M名的玩家。

更进一步,上面的操作都需要在短时间内实时完成,这样才能最大程度发挥排行榜的效用。

由于一个玩家名次上升x位将会引起x+1位玩家的名次发生变化(包括该玩家),如果采用传统数据库(比如MySQL)来实现排行榜,当玩家人数较多时,将会导致对数据库的频繁修改,性能得不到满足,所以我们只能另想它法。

Redis作为NoSQL中的一员,近年来得到广泛应用。与Memcached相比,Redis拥有更多的数据类型和操作接口,具有更大的适用范围,其中的有序集合(sorted set,也称为zset)就非常适合于排行榜的构建。下面简要总结一下。

1. Redis的安装

Ubuntu下安装Redis非常简单,执行如下命令即可:

$ sudo apt-get install redis-server

安装完毕,运行命令行客户端redis-cli就可以访问本地redis服务器。

$ redis-cli
redis 127.0.0.1:6379>

如果要使用最新版本,需要到Redis官网(redis.io)下载最新的代码自行编译,步骤略。

2. ZSet的常用命令

有序集合首先是集合,其成员(member)具有唯一性,其次,每个成员关联了一个分数(score),使得成员可以按照分数排序。关于有序集合的介绍见redis.io/topics/data…,其命令见redis.io/commands#so…。

下面介绍几个能用于排行榜的命令。

假设lb为排行榜名称,user1、user2等为玩家唯一标识。

1) zadd——设置玩家分数

命令格式:zadd 排行榜名称 分数 玩家标识 时间复杂度:O(log(N))

下面设置了4个玩家的分数,如果玩家分数已经存在,则会覆盖之前的分数。

redis 127.0.0.1:6379> zadd lb 89 user1
(integer) 1
redis 127.0.0.1:6379> zadd lb 95 user2
(integer) 1
redis 127.0.0.1:6379> zadd lb 95 user3
(integer) 1
redis 127.0.0.1:6379> zadd lb 90 user4
(integer) 1

2) zscore——查看玩家分数

命令格式:zscore 排行榜名称 玩家标识 时间复杂度:O(1)
下面是查看user2这个玩家在lb排行榜中的分数。

redis 127.0.0.1:6379> zscore lb user2
“95”

3) zrevrange——按名次查看排行榜

命令格式:zrevrange 排行榜名称 起始位置 结束位置 [withscores] 时间复杂度:O(log(N)+M)

由于排行榜一般是按照分数由高到低排序的,所以我们使用zrevrange,而命令zrange是按照分数由低到高排序。

起始位置和结束位置都是以0开始的索引,且都包含在内。如果结束位置为-1则查看范围为整个排行榜。

带上withscores则会返回玩家分数。

下面为查看所有玩家分数。

redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores

“user3”
“95”
“user2”
“95”
“user4”
“90”
“user1”
“89”

下面为查询前三名玩家分数。

redis 127.0.0.1:6379> zrevrange lb 0 2 withscores

“user3”
“95”
“user2”
“95”
“user4”
“90”

4) zrevrank——查看玩家的排名

命令格式:zrevrank 排行榜名称 玩家标识 时间复杂度:O(log(N))

与zrevrange类似,zrevrank是以分数由高到低的排序返回玩家排名(实际返回的是以0开始的索引),对应的zrank则是以分数由低到高的排序返回排名。

下面是查询玩家user3和user4的排名。

redis 127.0.0.1:6379> zrevrank lb user3
(integer) 0
redis 127.0.0.1:6379> zrevrank lb user1
(integer) 3

5) zincrby——增减玩家分数

命令格式:zincrby 排行榜名称 分数增量 玩家标识 时间复杂度:O(log(N))

有的排行榜是在变更时重新设置玩家的分数,而还有的排行榜则是以增量方式修改玩家分数,增量可正可负。如果执行zincrby时玩家尚不在排行榜中,则认为其原始分数为0,相当于执行zdd。

下面将user4的分数增加6,使其名次上升到第一位。

redis 127.0.0.1:6379> zincrby lb 6 user4
“96”
redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores

“user4”
“96”
“user3”
“95”
“user2”
“95”
“user1”
“89”

6) zrem——移除某个玩家

命令格式:zrem 排行榜名称 玩家标识 时间复杂度:O(log(N))

下面移除玩家user4。

redis 127.0.0.1:6379> zrem lb user4
(integer) 1
redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores

“user3”
“95”
“user2”
“95”
“user1”
“89”

7) del——删除排行榜

命令格式:del 排行榜名称

排行榜对象在我们首次调用zadd或zincrby时被创建,当我们要删除它时,调用redis通用的命令del即可。

redis 127.0.0.1:6379> del lb
(integer) 1
redis 127.0.0.1:6379> get lb
(nil)

3. 相同分数问题

免费的方案总有那么一些不完美。从前面的例子我们可以看到,user2和user3具有相同的分数,但在按分数逆序排序时,user3排在了user2前面。而在实际应用场景中,我们更希望看到user2排在user3前面,因为user2比user3先加入排行榜,也就是说user2先到达该分数。

但Redis在遇到分数相同时是按照集合成员自身的字典顺序来排序,这里即是按照”user2″和”user3″这两个字符串进行排序,以逆序排序的话user3自然排到了前面。

要解决这个问题,我们可以考虑在分数中加入时间戳,计算公式为:

带时间戳的分数 = 实际分数*10000000000 + (9999999999 – timestamp)

timestamp我们采用系统提供的time()函数,也就是1970年1月1日以来的秒数,我们采用32位的时间戳(这能坚持到2038年),由于32位时间戳是10位十进制整数(最大值4294967295),所以我们让时间戳占据低10位(十进制整数),实际分数则扩大10^10倍,然后把两部分相加的结果作为zset的分数。考虑到要按时间倒序排列,所以时间戳这部分需要颠倒一下,这便是用9999999999减去时间戳的原因。当我们要读取玩家实际分数时,只需去掉后10位即可。

初步看起来这个方案还不错,但这里面有两个问题。

第一个问题是小问题,采用秒为时间戳可能区分度还不够,如果同一秒出现两个分数相同的仍然会出现前面的问题,当然我们可以选择精度更高的时间戳,但在实际场景中,同一秒谁排前面已经无关紧要。

第二个问题是大问题,因为Redis的分数类型采用的是double,64位双精度浮点数只有52位有效数字,它能精确表达的整数范围为-2^53到2^53,最高只能表示16位十进制整数(最大值为9007199254740992,其实连16位也不能完整表示)。这就是说,如果前面时间戳占了10位的话,分数就只剩下6位了,这对于某些排行榜分数来说是不够用的。我们可以考虑缩减时间戳位数,比如从2015年1月1日开始计时,但这仍然增加不了几位。或者减少区分度,以分钟、小时来作为时间戳单位。

如果Redis的分数类型为int64,我们就没有上面的烦恼。说到这里,其实Redis真应该再额外提供一个int64类型的ZSet,但目前只能是幻想,除非自己改其源码。

既然Redis也不能完美解决排行榜问题,那最终是不是有必要自己实现一个专门的排行榜数据结构呢?毕竟实际应用中的排行榜有很多可以优化的地方,比玩家呈金字塔分布,越是低分段玩家数量越多,同一分数拥有大量玩家,玩家增加一分都可能超越很多玩家,这就为优化提供了可能。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。

(0)

相关推荐

  • 使用Redis实现用户积分排行榜的教程

    排行榜功能是一个很普遍的需求.使用 Redis 中有序集合的特性来实现排行榜是又好又快的选择. 一般排行榜都是有实效性的,比如"用户积分榜".如果没有实效性一直按照总榜来排,可能榜首总是几个老用户,对于新用户来说,那真是太令人沮丧了. 首先,来个"今日积分榜"吧,排序规则是今日用户新增积分从多到少. 那么用户增加积分时,都操作一下记录当天积分增加的有序集合. 假设今天是 2015 年 04 月 01 日,UID 为 1 的用户因为某个操作,增加了 5 个积分. Re

  • redis实现排行榜的简单方法

    1 前言 实现一个排版榜,我们通常想到的就是mysql的order by 简单粗暴就撸出来了.但是这样真的优雅吗? 数据库是系统的瓶颈,这是众所周知的.如果给你一张百万的表,让你排序做排行榜,花费的时间是十分可怕的. 不如缓存吧,order by的时候强制使用索引.但是这样真的优雅吗? 2 Redis的排行榜 我们分析一下排行榜,一个用户一个排名,意味着要去重,这时我们会想到Java的一种数据结构Set.不过Set又是无序的.有没有一种结构是可以保住元素唯一以及有序的呢. 幸运的是,还真的有.R

  • 基于redis实现世界杯排行榜功能项目实战

    题外话: 小编先给大家推荐一个不错的微信公众号: 感兴趣的朋友可以关注小编的微信公众号[码农那点事儿],更多网页制作特效源码及学习干货哦!!! 需求 前段时间,做了一个世界杯竞猜积分排行榜.对世界杯64场球赛胜负平进行猜测,猜对+1分,错误+0分,一人一场只能猜一次. 1.展示前一百名列表. 2.展示个人排名(如:张三,您当前的排名106579). 分析 一开始打算直接使用mysql数据库来做,遇到一个问题,每个人的分数都会变化,如何能够获取到个人的排名呢?数据库可以通过分数进行row_num排

  • 利用redis实现排行榜的小秘诀

    前言 排行榜作为互联网应用中几乎必不可少的一个元素,其能够勾起人类自身对比的欲望,从而来增加商品的销量. 对于排行榜的需求,redis有一个数据结构非常适合做这件事,那就是有序集合(sorted set). 在日常一些简单的活动开发中,我经常会碰到需要对用户的分值等进行排行,此时一般会选择redis的有序集合对用户的分数进行存储,但是不同的场景排行榜的方式也略有不同,以下根据自己日常的开发进行了一下归纳总结 Redis 有序集合(sorted set) 首先简单介绍下什么是有序集合. Redis

  • 利用Redis的有序集合实现排行榜功能实例代码

    前言 游戏中存在各种各样的排行榜,比如玩家的等级排名.分数排名等.玩家在排行榜中的名次是其实力的象征,位于榜单前列的玩家在虚拟世界中拥有无尚荣耀,所以名次也就成了核心玩家的追求目标. 一个典型的游戏排行榜包括以下常见功能: 能够记录每个玩家的分数: 能够对玩家的分数进行更新: 能够查询每个玩家的分数和名次: 能够按名次查询排名前N名的玩家: 能够查询排在指定玩家前后M名的玩家. 更进一步,上面的操作都需要在短时间内实时完成,这样才能最大程度发挥排行榜的效用. 由于一个玩家名次上升x位将会引起x+

  • php使用redis的有序集合zset实现延迟队列应用示例

    本文实例讲述了php使用redis的有序集合zset实现延迟队列.分享给大家供大家参考,具体如下: 延迟队列就是个带延迟功能的消息队列,相对于普通队列,它可以在指定时间消费掉消息. 延迟队列的应用场景: 1.新用户注册,10分钟后发送邮件或站内信. 2.用户下单后,30分钟未支付,订单自动作废. 我们通过redis的有序集合zset来实现简单的延迟队列,将消息数据序列化,作为zset的value,把消息处理时间作为score,每次通过zRangeByScore获取一条消息进行处理. <?php

  • 详解PHP多个进程配合redis的有序集合实现大文件去重

    1.对一个大文件比如我的文件为 -rw-r--r-- 1 ubuntu ubuntu 9.1G Mar 1 17:53 2018-12-awk-uniq.txt 2.使用split命令切割成10个小文件 split -b 1000m 2018-12-awk-uniq.txt -b 按照字节切割 , 支持单位m和k 3.使用10个php进程读取文件 , 插入redis的有序集合结构中 , 重复的是插不进去的 ,因此可以起到去重的作用 <?php $file=$argv[1]; //守护进程 uma

  • python redis连接 有序集合去重的代码

    python redis连接 有序集合去重的代码如下所述: # -*- coding: utf-8 -*- import redis from constant import redis_ip, redis_db, redis_pw, redis_zset_name pool = redis.ConnectionPool(host=redis_ip, db=redis_db, password=redis_pw) # pool = redis.ConnectionPool(db=6, passw

  • 利用Redis实现防止接口重复提交功能

    目录 前言 1.自定义注解 2.自定义拦截器 3.Redis工具类 4.其他想说的 前言 在划水摸鱼之际,突然听到有的用户反映增加了多条一样的数据,这用户立马就不干了,让我们要马上修复,不然就要投诉我们. 这下鱼也摸不了了,只能去看看发生了什么事情.据用户反映,当时网络有点卡,所以多点了几次提交,最后发现出现了十几条一样的数据. 只能说现在的人都太心急了,连这几秒的时间都等不了,惯的.心里吐槽归吐槽,这问题还是要解决的,不然老板可不惯我. 其实想想就知道为啥会这样,在网络延迟的时候,用户多次点击

  • Redis中有序集合的内部实现方式的详细介绍

    目录 有序集合的内部实现 以压缩列表作为内部实现 以跳跃表作为内部实现 内部实现的转换 总结 面试官:Redis中基本的数据类型有哪些? 我:Redis的基本数据类型有:字符串(string).哈希(hash).列表(list).集合(set).有序集合(zset). 面试官:有序集合的内部实现方式是什么? 我还沉浸在上一个问题的沾沾自喜中,顿时表情凝固了,手心开始冒出冷汗.“这个..没有太深入了解”,我支支吾吾的说到. 面试官:回去等消息吧. 这句话说的干净利落,然后就没有然后了.失败是成功的

  • springboot+redis实现微博热搜排行榜的示例代码

    目录 技术模拟思路: 步骤1:先初始化1个月的历史数据 步骤2:定时刷新数据 步骤3:排行榜查询接口 技术模拟思路: 采用26个英文字母来实现排行,随机为每个字母生成一个随机数作为score 为了更好的体验,先做几件事: 先初始化1个月的历史数据 定时5秒钟,模拟微博的热度刷新(例如模拟点赞 收藏 评论的热度值更新) 定时1小时合并统计 天.周.月的排行榜. 步骤1:先初始化1个月的历史数据 @Service @Slf4j public class InitService {     @Auto

  • JavaWeb实现用户登录注册功能实例代码(基于Servlet+JSP+JavaBean模式)

    下面通过通过图文并茂的方式给大家介绍JavaWeb实现用户登录注册功能实例代码,一起看看吧. 一.Servlet+JSP+JavaBean开发模式(MVC)介绍 Servlet+JSP+JavaBean模式(MVC)适合开发复杂的web应用,在这种模式下,servlet负责处理用户请求,jsp负责数据显示,javabean负责封装数据. Servlet+JSP+JavaBean模式程序各个模块之间层次清晰,web开发推荐采用此种模式. 这里以一个最常用的用户登录注册程序来讲解Servlet+JS

  • 使用JavaWeb webSocket实现简易的点对点聊天功能实例代码

    首先给大家声明一点:需要 jdk 7 , tomcat需要支持websocket的版本  1.InitServlet 该类主要是用来初始化构造将来存储用户身份信息的map仓库,利用其初始化方法Init 初始化仓库, 利用其静态方法getSocketList 获得对应的用户身份信息. webSocket ,我认为MessageInbound 用来识别登录人的信息,用它来找到对应的人,推送消息.每次登录都会产生一个MessageInbound. 这里的 HashMap<String,MessageI

  • C# 实现截图软件功能实例代码

    本文是利用C# 开发截图软件的小例子,以供学习分享使用. 思路: 截取屏幕图片. 获取要截取的范围,即左上角,右下角坐标 填充到PictureBox中. 笔触功能,荧光笔,矩形,橡皮擦,复制,保存功能 涉及的知识点: MenuStrip:为窗体提供菜单系统.以ToolStripMenuItem为菜单子选项 ToolStrip:为 Windows 工具栏对象提供容器.以ToolStripButton[表示包含文本和图像的可选]为工具栏子元素 PictureBox:表示用于显示图像的 Windows

随机推荐