【Redis】集合(Hash、List、Set、ZSet)的底层实现原理

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 【Redis】集合(Hash、List、Set、ZSet)的底层实现原理

根据视频【动力节点】Redis入门到高级教程,全网最新最全redis缓存教程,redis百科大全 进行整理

视频对应资料 https://pan.baidu.com/s/1IlM4LAU2gQqUMeN_B48t8w?pwd=egl7 提取码:egl7


Redis 相关文章汇总归纳整理于:https://www.yuque.com/u27599042/ckgabz


  • Redis 中对于 Set 类型的底层实现,直接采用了 hashTable。
  • 对于 Hash、ZSet、List 集合的底层实现进行了特殊的设计,使其保证了 Redis 的高性能。

Hash 与 ZSet 两种实现的选择

  • 对于 Hash 与 ZSet 集合,其底层的实现实际有两种:
  • 压缩列表 zipList
  • 跳跃列表 skipList
  • 这两种实现对于用户来说是透明的,但用户写入不同的数据,系统会自动使用不同的实现。
  • 只有同时满足配置文件 redis.conf 中相关集合元素数量阈值与元素大小阈值两个条件,使用的就是压缩列表 zipList,只要有一个条件不满足使用的就是跳跃列表 skipList。
  • 例如,对于 ZSet 集合中这两个条件如下:
  • 集合元素个数小于 redis.conf 中 zset-max-ziplist-entries 属性的值,其默认值为 128
  • 每个集合元素大小都小于 redis.conf 中 zset-max-ziplist-value 属性的值,其默认值为 64 字节

控制台查询配置文件中的配置

config get <配置项>

zipList

  • zipList,通常称为压缩列表,是一个经过特殊编码的用于存储字符串或整数的双向链表。
  • 其底层数据结构由三部分构成:head、entries 与 end。这三部分在内存上是连续存放的。

head

  • head 又由三部分构成:
  • zlbytes:占 4 个字节,用于存放 zipList 列表整体数据结构所占的字节数,包括 zlbytes 本身的长度。
  • zltail:占 4 个字节,用于存放 zipList 中最后一个 entry 在整个数据结构中的偏移量(字节)。该数据的存在可以快速定位列表的尾 entry 位置,以方便操作。
  • zllen:占 2 字节,用于存放列表包含的 entry 个数。由于其只有 16 位,所以 zipList 最多可以含有的 entry 个数为 2^16 -1 = 65535 个。
  • zipList 可以拥有的 entry 的个数,最大不止 65535 个,只是如果大于 65535 会导致 zllen 失效

entries

  • entries 是真正的列表,由很多的列表元素 entry 构成。
  • 由于不同的元素类型、数值的不同,从而导致每个 entry 的长度不同。
  • zipList 可以根据元素的类型和数值的不同动态使用相应的长度大小,体现了压缩
  • 每个 entry 由三部分构成:
  • prevlength:该部分用于记录上一个 entry 的长度,以实现逆序遍历。默认长度为 1 字节,只要上一个 entry 的长度<254 字节,prevlength 就占 1 字节,否则其会自动扩展为 3 字节长度。
  • 255 的二进制为 11111111,用于 zipList 的结束标志 end
  • 254 的二进制为 11111110,用于 prevlength 的扩展标志
  • encoding:该部分用于标志后面的 data 的具体类型。如果 data 为整数类型 encoding 固定长度为 1 字节。如果 data 为字符串类型,则 encoding 长度可能会是 1 字节、2 字节或 5 字节。data 字符串不同的长度,对应着不同的 encoding 长度。
  • data:真正存储的数据。数据类型只能是整数类型或字符串类型。不同的数据占用的字节长度不同。

end

  • end 只包含一部分,称为 zlend。
  • 占 1 个字节,值固定为 255,即二进制位为全 1,表示一个 zipList 列表的结束。

listPack

  • 对于 ziplist,实现复杂,为了逆序遍历,每个 entry 中包含前一个 entry 的长度,这样会导致在 ziplist 中间修改或者插入 entry 时需要进行级联更新。在高并发的写操作场景下会极度降低 Redis 的性能。
  • 为了实现更紧凑、更快的解析,更简单的实现,重写实现了 ziplist,并命名为 listPack。
  • 在 Redis 7.0 中,已经将 zipList 全部替换为了 listPack,但为了兼容性,在配置中也保留了 zipList 的相关属性。
  • listPack 也是一个经过特殊编码的用于存储字符串或整数的双向链表。其底层数据结构也由三部分构成:head、entries 与 end,且这三部分在内存上也是连续存放的。
  • listPack 与 zipList 的重大区别在 head 与每个 entry 的结构上,表示列表结束的 end 与 zipList 的 zlend 是相同的,占一个字节,且 8 位全为 1。

head

  • head 由两部分构成:
  • totalBytes:占 4 个字节,用于存放 listPack 列表整体数据结构所占的字节数,包括 totalBytes 本身的长度。
  • elemNum:占 2 字节,用于存放列表包含的 entry 个数。其意义与 zipList 中 zllen 的相同。
  • 与 zipList 的 head 相比,没有了记录最后一个 entry 偏移量的 zltail。

entries

  • entries 也是 listPack 中真正的列表,由很多的列表元素 entry 构成。
  • 由于不同的元素类型、数值的不同,从而导致每个 entry 的长度不同。但与 zipList 的 entry 结构相比,listPack 的 entry 结构发生了较大变化。 其中最大的变化就是没有了记录前一个 entry 长度的 prevlength,而增加了记录当前 entry 长度的 element-total-len。而这个改变仍然可以实现逆序遍历,但却避免了由于在列表中间修改或插入 entry 时引发的级联更新。
  • 每个 entry 仍由三部分构成:
  • encoding:该部分用于标志后面的 data 的具体类型。如果 data 为整数类型,encoding 长度可能会是 1、2、3、4、5 或 9 字节。不同的字节长度,其标识位不同。如果 data 为字符串类型,则 encoding 长度可能会是 1、2 或 5 字节。data 字符串不同的长度,对应着不同的 encoding 长度。
  • data:真正存储的数据。数据类型只能是整数类型或字符串类型。不同的数据占用的字节长度不同。
  • element-total-len:该部分用于记录当前 entry 的长度,用于实现逆序遍历。由于其特殊的记录方式,使其本身占有的字节数据可能会是 1、2、3、4 或 5 字节。

skipList

  • skipList,跳跃列表,简称跳表,是一种随机化的数据结构,基于并联的链表,实现简单,查找效率较高。简单来说跳表也是链表的一种,只不过它在链表的基础上增加了跳跃功能。也正是这个跳跃功能,使得在查找元素时,能够提供较高的效率。

skipList 原理

  • 在该链表中,如果要查找某个数据,需要从头开始逐个进行比较,直到找到包含数据的那个节点,或者找到第一个比给定数据大的节点,或者找到最后尾结点,后两种都属于没有找到的情况。同样,当我们要插入新数据的时候,也要经历同样的查找过程,从而确定插入位置。
  • 为了提升查找效率,在偶数结点上增加一个指针,让其指向下一个偶数结点。
  • 这样所有偶数结点就连成了一个新的链表(简称高层链表),当然,高层链表包含的节点个数只是原来链表的一半。此时再想查找某个数据时,先沿着高层链表进行查找。当遇到第一个比待查数据大的节点时,立即从该大节点的前一个节点回到原链表中进行查找。
  • 例如,若想插入一个数据 20,则先在(8,19,31,42)的链表中查找,找到第一个比 20 大的节点 31,然后再在高层链表中找到 31 节点的前一个节点 19,然后再在原链表中获取到其下一个节点值为 23。比 20 大,则将 20 插入到 19 节点与 23 节点之间。若插入的是 25,比节点23 大,则插入到 23 节点与 31 节点之间。
  • 该方式明显可以减少比较次数,提高查找效率。如果链表元素较多,为了进一步提升查找效率,可以将原链表构建为三层链表,或再高层级链表。
  • 层级越高,查找效率就会越高。

存在的问题

  • 这种对链表分层级的方式从原理上看确实提升了查找效率,但在实际操作时就出现了问题:由于固定序号的元素拥有固定层级,所以列表元素出现增加或删除的情况下,会导致列表整体元素层级大调整,但这样势必会大大降低系统性能。
  • 例如,对于划分两级的链表,可以规定奇数结点为高层级链表,偶数结点为低层级链表。 对于划分三级的链表,可以按照节点序号与 3 取模结果进行划分。但如果插入了新的节点, 或删除的原来的某些节点,那么定会按照原来的层级划分规则进行重新层级划分,那么势必会大大降低系统性能

算法优化

  • 为了避免前面的问题,skipList 采用了随机分配层级方式。
  • 即在确定了总层级后,每添加一个新的元素时会自动为其随机分配一个层级。
  • 这种随机性就解决了节点序号与层级间的固定关系问题。
  • 从这个 skiplist 的创建和插入过程可以看出,每一个节点的层级数都是随机分配的,而且新插入一个节点不会影响到其它节点的层级数。只需要修改插入节点前后的指针,而不需对很多节点都进行调整。这就降低了插入操作的复杂度。
  • skipList 指的就是除了最下面第 1 层链表之外,它会产生若干层稀疏的链表,这些链表里面的指针跳过了一些节点,并且越高层级的链表跳过的节点越多。在查找数据的时先在高层级链表中进行查找,然后逐层降低,最终可能会降到第 1 层链表来精确地确定数据位置。在这个过程中由于跳过了一些节点,从而加快了查找速度。

quickList

  • quickList,快速列表,quickList 本身是一个双向无循环链表,它的每一个节点都是一个 zipList。
  • 从 Redis 3.2 版本开始,对于 List 的底层实现,使用 quickList 替代了 zipList 和 linkedList。
  • zipList 与 linkedList 都存在有明显不足,而 quickList 则对它们进行了改进:吸取了 zipList 和 linkedList 的优点,避开了它们的不足。
  • quickList 本质上是 zipList 和 linkedList 的混合体。其将 linkedList 按段切分,每一段使用 zipList 来紧凑存储若干真正的数据元素,多个 zipList 之间使用双向指针串接起来。当然,对于每个 zipList 中最多可存放多大容量的数据元素,在配置文件中通过 list-max-ziplist-size 属性可以指定。

检索操作

  • 对于 List 元素的检索,都是以其索引 index 为依据的。
  • quickList 由一个个的 zipList 构成,每个 zipList 的 zllen 中记录的就是当前 zipList 中包含的 entry 的个数,即包含的真正数据元素的个数。
  • 根据要检索元素的 index,从 quickList 的头节点开始,逐个对 zipList 的 zllen 做 sum 求和,直到找到第一个求和后 sum 大于 index 的 zipList,那么要检索的这个元素就在这个zipList 中

插入操作

  • 由于 zipList 是有大小限制的,所以在 quickList 中插入一个元素在逻辑上相对就比较复杂一些。
  • 假设要插入的元素的大小为 insertBytes,而查找到的插入位置所在的 zipList 当前的大小为 zlBytes,那么具体可分为下面几种情况:
  • 情况一:当 insertBytes + zlBytes <= list-max-ziplist-size 时,直接插入到 zipList 中相应位置即可
  • 情况二:当 insertBytes + zlBytes > list-max-ziplist-size,且插入的位置位于该 zipList 的首部位置,此时需要查看该 zipList 的前一个 zipList 的大小 prev_zlBytes。
  • 若 insertBytes + prev_zlBytes<= list-max-ziplist-size 时,直接将元素插入到前一个 zipList 的尾部位置即可
  • 若 insertBytes + prev_zlBytes> list-max-ziplist-size 时,直接将元素自己构建为一个新的 zipList,并连入 quickList 中
  • 情况三:当 insertBytes + zlBytes > list-max-ziplist-size,且插入的位置位于该 zipList 的尾部位置,此时需要查看该 zipList 的后一个 zipList 的大小 next_zlBytes。
  • 若 insertBytes + next_zlBytes<= list-max-ziplist-size 时,直接将元素插入到后一个 zipList 的头部位置即可
  • 若 insertBytes + next_zlBytes> list-max-ziplist-size 时,直接将元素自己构建为一个新的 zipList,并连入 quickList 中
  • 情况四:当 insertBytes + zlBytes > list-max-ziplist-size,且插入的位置位于该 zipList 的中间位置,则将当前 zipList 分割为两个 zipList 连接入 quickList 中,然后将元素插入到分割后的前面 zipList 的尾部位置

删除操作

  • 对于删除操作,只需要注意一点,在相应的 zipList 中删除元素后,该 zipList 中是否还有元素。如果没有其它元素了,则将该 zipList 删除,将其前后两个 zipList 相连接。

key 与 value 中元素的数量

  • 前面讲述的 Redis 的各种特殊数据结构的设计,不仅极大提升了 Redis 的性能,并且还使得 Redis 可以支持的 key 的数量、集合 value 中可以支持的元素数量可以非常庞大。
  • Redis 最多可以处理 2^32个 key(约 42 亿),并且在实践中经过测试,每个 Redis 实例至少可以处理 2.5 亿个 key。
  • 每个 Hash、List、Set、ZSet 集合都可以包含 2^32 个元素。
相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
2月前
|
消息中间件 NoSQL Redis
redis数据结构-List
redis数据结构-List
34 1
|
26天前
|
消息中间件 存储 NoSQL
剖析 Redis List 消息队列的三种消费线程模型
Redis 列表(List)是一种简单的字符串列表,它的底层实现是一个双向链表。 生产环境,很多公司都将 Redis 列表应用于轻量级消息队列 。这篇文章,我们聊聊如何使用 List 命令实现消息队列的功能以及剖析消费者线程模型 。
71 20
剖析 Redis List 消息队列的三种消费线程模型
|
6天前
|
消息中间件 存储 NoSQL
4)深度解密 Redis 的列表(List)
4)深度解密 Redis 的列表(List)
10 1
|
9天前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
|
6天前
|
存储 NoSQL 算法
5)深度解密 Redis 的哈希(Hash)
5)深度解密 Redis 的哈希(Hash)
12 0
|
2月前
|
存储 缓存 NoSQL
redis数据结构-hash
redis数据结构-hash
11 0
|
22天前
|
canal 缓存 NoSQL
Redis缓存与数据库如何保证一致性?同步删除+延时双删+异步监听+多重保障方案
根据对一致性的要求程度,提出多种解决方案:同步删除、同步删除+可靠消息、延时双删、异步监听+可靠消息、多重保障方案
Redis缓存与数据库如何保证一致性?同步删除+延时双删+异步监听+多重保障方案
|
2月前
|
缓存 NoSQL Java
Redis深度解析:解锁高性能缓存的终极武器,让你的应用飞起来
【8月更文挑战第29天】本文从基本概念入手,通过实战示例、原理解析和高级使用技巧,全面讲解Redis这一高性能键值对数据库。Redis基于内存存储,支持多种数据结构,如字符串、列表和哈希表等,常用于数据库、缓存及消息队列。文中详细介绍了如何在Spring Boot项目中集成Redis,并展示了其工作原理、缓存实现方法及高级特性,如事务、发布/订阅、Lua脚本和集群等,帮助读者从入门到精通Redis,大幅提升应用性能与可扩展性。
60 0
|
23天前
|
存储 NoSQL Redis
SpringCloud基础7——Redis分布式缓存,RDB,AOF持久化+主从+哨兵+分片集群
Redis持久化、RDB和AOF方案、Redis主从集群、哨兵、分片集群、散列插槽、自动手动故障转移
SpringCloud基础7——Redis分布式缓存,RDB,AOF持久化+主从+哨兵+分片集群
|
1天前
|
缓存 NoSQL Java
Springboot自定义注解+aop实现redis自动清除缓存功能
通过上述步骤,我们不仅实现了一个高度灵活的缓存管理机制,还保证了代码的整洁与可维护性。自定义注解与AOP的结合,让缓存清除逻辑与业务逻辑分离,便于未来的扩展和修改。这种设计模式非常适合需要频繁更新缓存的应用场景,大大提高了开发效率和系统的响应速度。
9 2
下一篇
无影云桌面