当前位置: 首页 > article >正文

redis zset基本介绍以及底层实现

ZSet(Sorted Set)有序集合

介绍

Redis 中的有序集合(Sorted Set)是在集合(Set)的基础上,为每个成员关联了一个分数(score)。这个分数可以用来对集合中的成员进行排序。
  • 有序集合保留了集合不能有重复成员的特性(成员不能重复,分值可以重复)
  • 元素会自动按照分数从小到大排序,如果多个元素的分数相同,会根据成员的字典序进行排序。

使用场景

有序集合比较典型的使用场景就是排行榜。例如学生成绩的排名榜、游戏积分排行榜、视频播放排名、电商系统中商品的销量排名等。
我们以博文点赞排名为例,小林发表了五篇博文,分别获得赞为 200、40、100、50、150。
# arcticle:1 文章获得了200个赞
> ZADD user:xiaolin:ranking 200 arcticle:1
(integer) 1
# arcticle:2 文章获得了40个赞
> ZADD user:xiaolin:ranking 40 arcticle:2
(integer) 1
# arcticle:3 文章获得了100个赞
> ZADD user:xiaolin:ranking 100 arcticle:3
(integer) 1
# arcticle:4 文章获得了50个赞
> ZADD user:xiaolin:ranking 50 arcticle:4
(integer) 1
# arcticle:5 文章获得了150个赞
> ZADD user:xiaolin:ranking 150 arcticle:5
(integer) 1

文章 arcticle:4 新增1个赞,可以使用 ZINCRBY 命令(为有序集合key中元素member的分值加上increment):

> ZINCRBY user:xiaolin:ranking 1 arcticle:4
"51"

查看某篇文章的赞数,可以使用 ZSCORE 命令(返回有序集合key中元素个数):

> ZSCORE user:xiaolin:ranking arcticle:4
"50"

内部实现

Zset 类型的底层数据结构是由 压缩列表或跳表实现的:
  • 如果有序集合的成员个数小于 128 个,并且每个成员的值小于 64 字节时,Redis 会使用压缩列表作为 Zset 类型的底层数据结构;
  • 如果有序集合的元素不满足上面的条件,Redis 会使用跳表作为 Zset 类型的底层数据结构;
在 Redis 7.0 中,压缩列表数据结构已经废弃了,交由 listpack 数据结构来实现了

skiplist 跳表

引入
先从链表开始,如果是一个单链表,那么我们知道在链表中查找一个元素的话,需要将整个链表遍历一次,时间复杂度为O(n)。
如果说我们把在原有链表的基础上,对部分结点增加一层,且每个第二层结点指向下一个第二层结点,那么在查找一个结点时,仅仅需要遍历N/2个结点即可。这样就实现了跳过一些不必要的结点,从而加快查找、删除等操作。查找的时间复杂度降低为O(n/2)。
对于一个链表内每一个结点包含多少个指向后续元素的指针(多少层),这个过程是通过一个 随机函数得到。
随机函数的工作流程:从第一层开始,逐层往上,每层利用随机函数决定是否“晋升”到更高一层。每次晋升的概率通常设定为 50%,即:
  • 如果随机函数结果为“成功”,则节点层数增加一层;
  • 如果结果为“失败”或达到预设的最大层数,则停止晋升。
结构
跳表的结构定义如下:
  1. 由多层结构组成;
  2. 每一层都是一个有序的链表;
  3. 最底层为原始链表,里面包含完整的所有元素;
  4. 非底层的每个节点都包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。
  5. 如果一个结点存在k个指向后续元素指针的话,那么称该结点是一个k层结点。
  6. 一个跳表的层意为所有结点中层数最大的结点。
查找操作遵循的原则:
  1. 从上到下、从左到右进行。(这条适用于跳表的所有操作)
  2. 向右查找的优先级高于向下查找
示例:查找24结点:
示例:插入一个18结点
步骤:
1、找到底层链表中插入结点的前置节点
2、在前置节点后插入结点(也就是链表的插入操作)
3、进行随机算法生成索引结点
4、视情况添加索引层
  1. 按照上方的查找方法,找到底层链表中的该节点
  2. 删除该节点
  3. 从下往上依次删除该结点的索引结点
  4. 视情况删除索引层
为什么需要跳表?
在实际开发中经常遇到需要在数据集中查找一个指定数据的场景,而常用的支持高效查找算法的实现方式有以下几种:
  1. 有序数组。插入时可以先对数据排序,查询时可以采用二分查找算法降低查找操作的复杂度。缺点是插入和删除数据时,为了保持元素的有序性,需要进行大量数据的移动操作。
  2. 二叉查找树。既支持高效的二分查找算法,又能快速的进行插入和删除操作的数据结构,理想的时间复杂度为 O($log^n$),但是在某些极端情况下,二叉查找树有可能变成一个线性链表,即退化成链表结构。
  3. 平衡二叉树。基于二叉查找树的优点,对其缺点进行了优化改进,引入了平衡的概念。为了维持二叉树的平衡衍生出了多种平衡算法,根据平衡算法的不同具体实现有AVL树 /B树(B-Tree)/ B+树(B+Tree)/红黑树 等等。但是平衡算法的实现大多数比较复杂且较难理解。
针对大体量、海量数据集中查找指定数据有更好的解决方案,我们得评估时间、空间的成本和收益。
跳表同样支持对数据进行高效的查找,插入和删除数据操作时间复杂度能与平衡二叉树媲美,最重要的是跳表的实现比平衡二叉树简单几个级别。缺点就是“以空间换时间”方式存在一定数据冗余。
如果存储的数据是大对象,跳表冗余的只是指向数据的指针,几乎可以不计使用的内存空间。
所以zset最终选择使用跳表。

ziplist 压缩列表

结构介绍
压缩列表是 Redis 为了节约内存而开发的,用一块 连续的内存空间来紧凑地保存数据,并且为了节省内存的开销,listpack 节点会采用不同的编码方式保存不同大小的数据。(保存大数据时,该结点长度会变大,保存小数据时,该结点长度会变小)
压缩列表在表头有三个字段:
  • zlbytes,记录整个压缩列表占用对内存字节数;
  • zltail,记录压缩列表尾部节点地址距离起始地址有多少字节,也就是列表尾的偏移量;
  • zllen,记录压缩列表包含的节点数量;
  • zlend,标记压缩列表的结束点。
压缩列表节点(entry)的构成如下:
压缩列表节点包含三部分内容:
  • prevlen,记录了前一个节点的长度,目的是为了实现从后向前遍历;
  • encoding,记录了当前节点实际数据的类型和长度,类型主要有两种:字符串和整数。
  • data,记录了当前节点的实际数据
当我们往压缩列表中插入数据时,压缩列表就会根据插入数据的类型(字符串or整数)和大小,来决定使用不同空间大小的 prevlen 和 encoding 保存数据的信息。 这种设计思想,正是 Redis 为了节省内存而采用的
分别说下,prevlen 和 encoding 是如何根据数据的大小和类型来进行不同的空间大小分配。
prevlen:
  • 如果前一个节点的长度小于 254 字节,那么 prevlen 部分需要用 1 字节的空间来保存这个长度值;
  • 如果前一个节点的长度大于等于 254 字节,那么 prevlen 部分需要用 5 字节的空间来保存这个长度值;
encoding :
encoding部分的空间大小跟数据是字符串还是整数,以及字符串的长度有关,具体如下图
  • 如果当前节点的数据是整数,则 encoding 会使用 1 字节的空间进行编码,也就是 encoding 长度为 1 字节。
  • 如果当前节点的数据是字符串,根据字符串的长度大小,encoding 会使用 1 字节/2字节/5字节的空间进行编码,encoding 编码的前两个 bit 表示数据的类型,后续的其他 bit 标识字符串数据的实际长度,即 data 的长度。
查找复杂度高
在压缩列表中,如果我们要查找定位第一个元素和最后一个元素,可以通过表头三个字段(zllen)的长度直接定位,复杂度是 O(1)。而 查找其他元素时,就没有这么高效了,只能逐个查找,此时的复杂度就是 O(N) 了,因此压缩列表不适合保存过多的元素
容易触发内存重新分配
压缩列表紧凑型的内存布局能节省内存开销,但是如果保存的元素数量增加了,或是元素变大了,会导致内存重新分配,降低访问性能。重新分配中最糟糕的情况是「连锁更新」。
连锁更新
压缩列表新增某个元素或修改某个元素时,如果原有的空间不够,压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时,可能会导致后续元素的 prevlen 占用空间都发生变化,从而引起「连锁更新」问题,导致压缩列表占用的内存空间要多次重新分配,这就会直接影响到压缩列表的访问性能
前面提到,压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配:
  • 如果前一个节点的长度小于 254 字节,那么 prevlen 属性需要用 1 字节的空间来保存这个长度值;
  • 如果前一个节点的长度大于等于 254 字节,那么 prevlen 属性需要用 5 字节的空间来保存这个长度值;
现在假设一个压缩列表中有多个连续的、长度在 250~253 之间的节点,如下图:
因为这些节点长度值小于 254 字节,所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。
这时,如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点,即新节点将成为 e1 的前置节点,如下图:
这使得 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小,但因为 e1 节点的 prevlen 属性原本只有 1 个字节大小,此时无法保存新节点的长度,所以需要对压缩列表的空间重分配操作
多米诺牌的效应就此开始。
这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」,就像多米诺牌的效应一样, 造成访问压缩列表性能的下降。
结论
压缩列表只适用于保存的节点数量不多的场景,只要节点数量足够少,即使发生连锁更新,也是能接受的。
虽说如此,Redis 针对压缩列表在设计上的不足,在后来的版本中,新增设计了两种数据结构:quicklist(Redis 3.2 引入) 和 listpack(Redis 5.0 引入)。这两种数据结构的设计目标,就是尽可能地保持压缩列表节省内存的优势,同时解决压缩列表的内存重新分配的问题
参考文章:
Redis 数据结构 | 小林coding
Redis 常见数据类型和应用场景 | 小林coding
数据结构学习——skiplist跳表-腾讯云开发者社区-腾讯云
跳表(SkipList)原理篇 - Laymen - 博客园

http://www.kler.cn/a/589120.html

相关文章:

  • 【网络】Caddy 服务器如何提供 TLS(Transport Layer Security)(传输层安全协议)
  • 短视频下载去水印,用什么工具好?
  • 使用 Chrome Flags 设置(适用于 HTTP 站点开发)
  • Spring WebSocket 像写http接口一样处理WebSocket消息(Stomp协议)
  • iOS底层原理系列02-深入了解Objective-C
  • LInux基础--apache部署网站
  • rust 的Clone
  • 基于SpringBoot的“考研互助平台”的设计与实现(源码+数据库+文档+PPT)
  • 深度学习中的向量的样子-DCN
  • Leetcode hot 100 191.对称二叉树
  • 2025站群泛目录程序秒收优化新策略(关键词布局与流量分配)
  • 鸿蒙模拟器运行NDK项目失败 9568347
  • 麒麟服务器操作系统Redis部署手册
  • Javaweb后端全局异常处理器
  • Elasticsearch-07-Elasticsearch Java API Client-Elasticsearch 8.0 的高阶api
  • C#的委托Action
  • CSS Table (表格)
  • 批量将多个 Excel 合并成单个文件|批量按文件夹合并 Excel
  • 【Go | 从0实现简单分布式缓存】-7:增加etcd和gRPC功能
  • 【MySQL篇】MySQL内置函数