后台网站模板下载,西服定制一般多少钱,阳山网站建设,赣州编程培训机构今天给大家简单聊聊 Redis Sorted Set 数据类型底层的实现原理和游戏排行榜实战。特别简单#xff0c;一点也不深入#xff0c;也就 7 张图#xff0c;粉丝可放心食用#xff0c;哈哈哈哈哈~~~~。 1. 是什么
Sorted Sets 与 Sets 类似#xff0c;是一种集合类型#xff…今天给大家简单聊聊 Redis Sorted Set 数据类型底层的实现原理和游戏排行榜实战。特别简单一点也不深入也就 7 张图粉丝可放心食用哈哈哈哈哈~~~~。 1. 是什么
Sorted Sets 与 Sets 类似是一种集合类型集合中不会出现重复的数据member。区别在于 Sorted Sets 元素由两部分组成分别是 member 和 score。
member 会关联一个 double 类型的分数scoresorted sets 默认会根据这个 score 对 member 进行从小到大的排序如果 member 关联的分数 score 相同则按照字符串的字典顺序排序。
这是规则得记下来。 2-24
常见的使用场景 排行榜比如维护大型在线游戏中根据分数排名的 Top 10 有序列表。 速率限流器根据排序集合构建滑动窗口速率限制器。 延迟队列score 存储过期时间从小到大排序最靠前的就是最先到期的数据。
2. 修炼心法
Sorted Sets 底层有两种方式来存储数据。 在 7.0 版本之前是 ziplist之后被 listpack 代替使用 listpack 存储的条件是集合元素个数小于等于 zset-max-listpack-entries 配置值默认 128且 member 占用字节大小小于 zset-max-listpack-value 配置值默认 64时使用 listpack 存储member 和 score 紧凑排列作为 listpack 的一个元素进行存储。 不满足上述条件使用 skiplist dict散列表 组合方式存储数据会插入 skiplist 的同时也会向 dict散列表中插入数据 是一种用空间换时间的思路。散列表的 key 存放的是元素的 membervalue 存储的是 member 关联的 score。
❝ MySQL“也就是说 listpack 适用于元素个数不多且元素内容不大的场景。” 对使用 listpack 存储的目的就是节省内存。
Sorted Sets 能支持高效的范围查询正是因为采用了 skiplist 跳表比如 ZRANGE 命令时时间复杂度为 O(log(n)) m n 是 member 个数m 是返回结果数。需要注意的是你应该避免命令会返回大量结果。
而使用 dict 的原因是实现 O(1) 时间复杂度查询单个元素。比如 ZSCORE key member 指令。
总结来说Sorted Sets 在插入或者更新的时候会同时往 skiplist 和 散列表中插入或者更新对应的数据。保证 skiplist 和散列表的数据一致。
❝ MySQL“这个方式很巧妙呀skiplist 用来根据 score 进行范范围查询或者单个查询dict 散列表则用于实现 O(1) 时间复杂度查根据数据查询对应 score满足高效范围查询和单元素查询。“ sorted sets 实现源码主要在以下两个文件中。 结构定义在 server.h。 功能实现在 t_zset.c。
先看 skiplist跳表 dict散列表数据结构如何存储数据。
skiplist dict
❝ MySQL“说说什么是跳表吧” 实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引通过索引来实现快速查找。
不仅能提高搜索性能还可以提高插入和删除操作的性能。它在性能上和红黑树、AVL 树不相上下但是跳表的原理和实现比红黑树简单。
回顾链表它的痛点就是查询很慢O(n) 时间复杂度作为唯快不破的 Redis 是不能忍的。 图2-25
如果在有序链表的每相邻两个节点增加一个“跳跃”指向下下个节点的指针那么查找的时间复杂度就可以降低为原来的一半如下图所示。 图 2-26
这样 level 0 和 level 1 分别形成两个链表level 1 层的链表节点个数只有 2 个6、26。
跳表节点查找
查找数据总是从最高层开始比较如果节点保存的值比待查数据小跳表就继续访问该层的下一个节点
如果碰到比待查数据值大的节点时那就跳到当前节点的下一层的链表继续查找。
比如现在想查找 17查找的路径如下图红色指向的方向进行。 从 level 1 开始17 与 6 比较值大于节点继续与下一个节点比较。 与 26 比较17 26回到原节点跳到当前节点的 level 0 层链表与下一个节点比较找到目标 17。
skiplist 正是受这种多层链表的想法启发设计出来的。按照上面的生成链表方式每次往上增加一层链表的节点个数是下面一层的一半这样的查找过程就类似于一个二分查找时间复杂度为 O(log n)。
但是这种方式在插入数据的时候有很大的问题每次新增一个节点就会打乱相邻的两层链表节点个数 2:1 的关系如果要维持这个关系就需要对链表调整事件复杂度是 O(n)。
为了避免这个问题它不要求上下相邻的两层链表节点个数有严格的比例关系而是为每个节点随机出一个层数这样插入节点只需要修改前后指针。
如下图是一个有 4 层链表的 skiplist假设我们要查找 26下图给出了查找经历过的路径。 对经典跳表有个直观的映像后来看看 Redis 中 skiplist 的实现细节Sorted Sets 数据结构定义如下。
typedef struct zset {dict *dict;zskiplist *zsl;
} zset;zset 结构体中有两个变量分别是散列表 dict 和跳表 zskiplist。dict 在前文已经讲过 重点看 zskiplist 。
typedef struct zskiplist {// 头、尾指针便于双向遍历struct zskiplistNode *header, *tail;// 当前跳表包含元素个数unsigned long length;// 表内节点的最大层级数int level;
} zskiplist;zskiplistNode *header, *tail两个头、尾指针用于实现双向遍历。 length链表包含的节点总数。需要注意的是新创建的 zskiplist 会生成一个空的头指针它不包含在 length 计数中。 level表示 skiplist 中所有节点层数的最大值。
接着继续看 skiplist 中每个节点的定义 zskiplistNode 结构体。
typedef struct zskiplistNode {sds ele;double score;struct zskiplistNode *backward;struct zskiplistLevel {struct zskiplistNode *forward;unsigned long span;} level[];} zskiplistNode;Sorted Set 既要保存元素又要保存元素的权重。所以对应了 sds 类型的 ele 存储实际内容 double 类型 score 用于保存权重。 *backward后退指针指向该节点的上一个节点便于从尾节点实现倒序查找。注意每个节点只有一个后向指针只有 level 0 层链表是一个双向链表。 level[]是一个 zskiplistLevel 结构体类型的柔性数组。跳表是一个多层的有序链表每一层的节点也是由指针链接起来的所以数组中每个元素代表着 skiplist 的一层。 *forward该层的前进指针。 span跨度用来记录节点在该层的 *forward 指针到指针指向的下一个节点之间跨越了 level0 层的节点数。span 用于计算元素排名(rank)例如查找 ele 肖菜鸡、score 17 的排名只需要把查找路径经过的节点的 span 相加即可如下图的红色路径的 span 累加rank (2 2) - 1 3减 1 是因为 rank 从 0 开始。如果要计算从大到小的排名只需要用 skiplist 长度减去查找路径上的 span 累加值即 4 - (2 2) 0。
下图展示了 Redis 中一个 skiplsit 的可能结构。 listpack
❝ MySQL“根据 zset 结构体定义可知分别使用了 dict、zskiplist 两种数据结构listpack 影子都见不着呀。“ 这个问题问得好使用 listpack 存储的细节在源码文件t_zset.c 中的zaddGenericCommand函数中体现部分代码如下内部会判断是否使用 listpack 来存储。·
void zaddGenericCommand(client *c, int flags) {// 省略部分代码// key 不存在则创建 sorted setzobj lookupKeyWrite(c-db,key);if (checkType(c,zobj,OBJ_ZSET)) goto cleanup;if (zobj NULL) {if (xx) goto reply_to_client;// 当 zset_max_listpack_entries 0 或者// 元素字节大小大于 zset_max_listpack_value 配置// 则使用 skiplist dict 存储否则使用 listpack。if (server.zset_max_listpack_entries 0 ||server.zset_max_listpack_value sdslen(c-argv[scoreidx1]-ptr)){zobj createZsetObject();} else {zobj createZsetListpackObject();}dbAdd(c-db,key,zobj);}// 省略部分代码
}我们知道listpack 是一块由多个数据项组成的连续内存。而 sorted set 每一项元素是由 member 和 score 两部分组成。
采用 listpack 存储插入一个member、score数据对的时候每个 member/score 数据对紧凑排列存储。
listpack 最大的优势就是节省内存查找元素的话只能按顺序查找时间复杂度是 O(n)。正是如此在少量数据的情况下才能做到既能节省内存又不会影响性能。每一步查找前进两个数据项也就是跨越一个 member/score 数据对。 3. 出招实战排行榜
很多地方都会用到排行榜功能比如微博热榜、知乎热榜、电影排行榜、游戏战力排行等。
以游戏排行榜为例我教你使用 Sorted Set 实现一个实时游戏高分排行榜。
玩家的得分越高排行越靠前如果分数相同则先达到该分数的玩家排在前面游戏排行榜的提供的功能如下。 按照分数从大到小排名查询前 N 位玩家信息。 新注册玩家需要把新玩家信息添加到排行榜中。 能查看某个玩家的排名和分数。
Sorted Set 每个元素有两部分组成member score可利用 score 进行排序正好满足我们的场景。用 score 保存玩家的游戏得分member 保存玩家 ID。
❝ 王架构“分数相同先达到该分数的排在前面也就是说游戏分数相同的情况下时间戳越小排名越靠前咋实现” 这个问题问得好既然时间也会影响排名那就把时间戳考虑到 score 中。
❝ 王架构“有问题分数越大排名越靠前而时间戳越小排名越靠前。两个规则相反的怎么结合在一起。” 好问题这时候你可以指定一个非常大的时间作为基准时间比如这个时间就是你当年信誓旦旦的对那个女孩说“如果非要在我们的爱上加一个期限我是希望……一万年”也就是 2023 10000 年。
执行时间排序值 基准时间 - 玩家达到分数时间/ 基准时间公式计算得到的结果值一定小于 1正好可作为 score 小数部分。越早达到这个值就越大满足排序。
最后score 玩家游戏分 ((基准时间 - 玩家获得某分数时间) / 基准时间)就实现了分数相同先达到该分数的排在前面的功能。
代码逻辑如下所示。
private double calcScore(int playerScore, long playerScoreTime) {return playerScore (BASE_TIME - playerScoreTime) * 1.0 / BASE_TIME;
}playerScore玩家游戏分。 playerScoreTime玩家获得分数的时间秒数。 BASE_TIME基准时间的时间秒数。
想要获取真正玩家游戏分数的时候取整数位即可。接下来我来演示一下如何使用 zset 的指令实现排行榜。
假设 BASE_TIME 为 12023 年 1 月 1 日 0 时 0 分 0 秒时间戳秒数 317242022400。
更新排行榜
使用指令 ZADD key score member [score member...] 用于新增或者更新玩家排行榜。如下指令表示新增了 4 个玩家信息到排行榜。leaderboard:339 作为 key表示区服 339 战力排行榜玩家 2 和玩家 3 的战力都是 500 分玩家 3 比玩家 2 先到达 500 战力。
redis ZADD leaderboard:339 2500.994707057989 player:1
(integer) 1
redis ZADD leaderboard:339 500.99470705798905 player:2
(integer) 1
redis ZADD leaderboard:339 500.9947097814618 player:3
(integer) 1
redis ZADD leaderboard:339 987770.994707058 player:4
(integer) 1假设某天玩家 4 的女朋友不在家他就天天玩游戏战力提升到 1987770。执行如下指令player:4 的 score 机会更新为 1987770.994707055。
ZADD leaderboard:339 1987770.994707055 player:4获取 Top 3 玩家排行信息
ZRANGE 命令可以按照排名、score、字典排序进行范围查询。语法使用规则
ZRANGE key start stop [BYSCORE | BYLEX] [REV] [LIMIT offset count] [WITHSCORES]默认排序是按照 score 由低到高分数相同则根据 member 字典排序。 REV可选参数按照 score 由高到低逆序排序。 LIMIT offset count 可选参数类似于 MySQL 的使用需要注意的是 count 为负数则返回所有符合数据。 WITHSCORES 可选参数返回 score 和 member返回的格式是 member 1,score 1,…memberN,scoreN。
你可以使用 REV 来实现逆序WITHSCORES返回 member 和 score。如下指令的一是是从 key 为 leaderboard:339 的 Sorted Set 中按照 score 逆序排序获取 3 个元素。 ZRANGE leaderboard:339 0 2 REV WITHSCORES
player:4
1987770.9947070549
player:1
2500.9947070579892
player:3
500.99470978146178获取指定玩家排名
我提供了 ZREVRANK指令用于返回指定 member 的排名需要注意的是排名从 0 开始。如下指令查找 player:4 的排名0 表示第一。 ZREVRANK leaderboard:339 player:4
0
