您当前的位置:首页 > 电脑百科 > 数据库 > Redis

Redis List 底层三种数据结构原理剖析

时间:2023-03-06 12:03:43  来源:微信公众号  作者:就是码哥呀
redis 的 List 与 JAVA 中的 LinkedList 类似,是一种线性的有序结构,可以按照元素被推入列表中的顺序来存储元素,能满足先进先出的需求,这些元素既可以是文字数据,又可以是二进制数据。

 

 

1、Redis List 是什么

作为 Java 开发者的你,看到这个词并不陌生。在 Java 开发中几乎每天都会使用这个数据结构。

Redis 的 List 与 Java 中的 LinkedList 类似,是一种线性的有序结构,可以按照元素被推入列表中的顺序来存储元素,能满足先进先出的需求,这些元素既可以是文字数据,又可以是二进制数据。

你可以把他当做队列、栈来使用。

2、修炼心法

我叫 Redis,在 C 语言中,并没有现成的链表结构,所以 antirez 为我专门设计了一套实现方式。

关于 List 类型的底层数据结构,可谓英雄辈出,antirez 大佬一直在优化,创造了多种数据结构来保存。

从一开始早期版本使用 linkedlist(双端列表)和 ziplist(压缩列表)作为 List 的底层实现,到 Redis 3.2 引入了由 linkedlist + ziplist 组成的 quicklist,再到 7.0 版本的时候使用 listpack 取代 ziplist。

MySQL:“为何弄了这么多数据结构呀?”

antirez 所做的这一切都是为了在内存空间开销与访问性能之间做取舍和平衡,跟着我去吃透每个类型的设计思想和不足,你就明白了。

linkedlist(双端列表)

在 Redis 3.2 版本之前,List 的底层数据结构由 linkedlist 或者 ziplist 实现,优先使用 ziplist 存储。

当列表对象满足以下两个条件的时候,List 将使用 ziplist 存储,否则使用 linkedlist。

  • List 的每个元素的占用的字节小于 64 字节。
  • List 的元素数量小于 512 个。

链表的节点使用 adlist.h/listNode结构来表示。

typedef struct listNode {
    // 前驱节点
    struct listNode *prev;
    // 后驱节点
    struct listNode *next;
    // 指向节点的值
    void *value;
} listNode;

listNode 之间通过 prev 和 next 指针组成双端链表。除此之外,我还提供了 adlist.h/list 结构提供了头指针 head、尾指针 tAIl 以及一些实现多态的特定函数。

typedef struct list {
    // 头指针
    listNode *head;
    // 尾指针
    listNode *tail;
    // 节点值的复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值比对是否相等
    int (*match)(void *ptr, void *key);
    // 链表的节点数量
    unsigned long len;
} list;

linkedlist 的结构如图 2-5 所示。

图片

Redis 的链表实现的特性总结如下。

  • 双端:链表节点带有 prev 和 next 指针,获取某个节点的前置节点和后继节点的复杂度都是 O(1)。
  • 无环:表头节点的 prev 指针和尾节点的 next 指针都指向 NULL,对链表的访问以 NULL 为结束。
  • 带表头指针和表尾指针:通过 list 结构的 head 指针和 tail 指针,程序获取链表的头节点和尾节点的复杂度为 O(1)。
  • 使用 list 结构的 len 属性来对记录节点数量,获取链表中节点数量的复杂度为 O(1)。

MySQL:“看起来没啥问题呀,为啥还要 ziplist 呢?”

你知道的,我在追求快和节省内存的方向上无所不及,有两个原因导致了 ziplist 的诞生。

  • 普通的 linkedlist 有 prev、next 两个指针,当存储数据很小的情况下,指针占用的空间会超过数据占用的空间,这就离谱了,是可忍孰不可忍。
  • linkedlist 是链表结构,在内存中不是连续的,遍历的效率低下。

ziplist(压缩列表)

为了解决上面两个问题,antirez 创造了 ziplist 压缩列表,是一种内存紧凑的数据结构,占用一块连续的内存空间,提升内存使用率。

当一个列表只有少量数据的时候,并且每个列表项要么是小整数值,要么就是长度比较短的字符串,那么我就会使用 ziplist 来做 List 的底层实现。

ziplist 中可以包含多个 entry 节点,每个节点可以存放整数或者字符串,结构如图 2-6 所示。

图片

  • zlbytes,占用 4 个字节,记录了整个 ziplist 占用的总字节数。
  • zltail,占用 4 个字节,指向最后一个 entry 偏移量,用于快速定位最后一个 entry。
  • zllen,占用 2 字节,记录 entry 总数。
  • entry,列表元素。
  • zlend,ziplist 结束标志,占用 1 字节,值等于 255。

因为 ziplist 头尾元数据的大小是固定的,并且在 ziplist 头部 zllen 记录了最后一个元素的位置,所以,当在 ziplist 中查找第一个或最后一个元素的时候,能以 O(1) 时间复杂度找到。

而查找中间元素时,只能从列表头或者列表尾遍历,时间复杂度就是 O(N)。

接下来看真正存储数据的 entry 结构长啥样。

图片

正常来说有三部分构成 <prevlen> <encoding> <entry-data>。

prevlen

记录前一个 entry 占用字节数,能实现逆序遍历就是靠这个字段确定往前移动多少字节拿到上一个 entry 首地址。

这部分会根据上一个 entry 的长度进行变长编码(为了节省内存操碎了心),变长方式如下。

  • 前一个 entry 的字节大小小于 254(255 用于 zlend),prevlen 长度为 1 字节,值等于上一个 entry 的长度。
  • 前一个 entry 的字节大小大于等于 254,prevlen 占用 5 字节,第一个字节设置为 254 作为一个标识,后面四字节组成一个 32 位的 int 值,用于存放上一个 entry 的字节长度。

encoding

简言之用于表示当前 entry 的类型和长度,当前 entry 的长度和值是根据保存的是 int 还是 string 以及数据的长度共同来决定。

前两位用于表示类型,当前两位值为 “11” 则表示 entry 存放的是 int 类型数据,其他表示存储的是 string。

entry-data

实际存放数据的区域,需要注意的是,如果 entry 中存储的是 int 类型,encoding 和 entry-data 会合并到 encoding 中,没有 entry-data 字段。

此刻结构就变成了 <prevlen> <encoding>。

MySQL:“为什么说 ziplist 省内存?”

  1. 与 linkedlist 相比,少了 prev、next 指针。
  2. 通过 encoding 字段针对不同编码来细化存储,尽可能做到按需分配,当 entry 存储的是 int 类型时,encoding 和 entry-data 会合并到 encoding ,省掉了 entry-data 字段。
  3. 每个 entry-data 占据内存大小不一样,为了解决遍历问题,增加了 prevlen 记录上一个 entry 长度。遍历数据时间复杂度是 O(1),但是数据量很小的情况下影响不大。

MySQL:“听起来很完美,为啥还搞什么 quicklist ”

既要又要还要的需求是很难实现的,ziplist 节省了内存,但是也有不足。

  • 不能保存过多的元素,否则查询性能会大大降低,O(N) 时间复杂度。
  • ziplist 存储空间是连续的,当插入新的 entry 时,内存空间不足就需要重新分配一块连续的内存空间,引发连锁更新的问题。

连锁更新

每个 entry 都用 prevlen 记录了上一个 entry 的长度,从当前 entry B 前面插入一个新的 entry A 时,会导致 B 的 prevlen 改变,也会导致 entry B 大小发生变化。entry B 后一个 entry C 的 prevlen 也需要改变。以此类推,就可能造成了连锁更新。

图片

连锁更新会导致 ziplist 的内存空间需要多次重新分配,直接影响 ziplist 的查询性能。于是乎在 Redis 3.2 版本引入了 quicklist。

quicklist

quicklist 是综合考虑了时间效率与空间效率引入的新型数据结构。结合了原先 linkedlist 与 ziplist 各自的优势,本质还是一个链表,只不过链表的每个节点是一个 ziplist。

数据结构定义在 quicklist.h​ 文件中,链表由 quicklist​ 结构体定义,每个节点由 quicklistNode 结构体定义(源码版本为 6.2,7.0 版本使用 listpack 取代了 ziplist)。

quicklist 是一个双向链表,所以每个 quicklistNode 都有前序指针(*prev​)、后序指针(*next​)。每个节点是 ziplist,所以还有一个指向 ziplist 的指针 *zl。

typedef struct quicklistNode {
    // 前序节点指针
    struct quicklistNode *prev;
    // 后序节点指针
    struct quicklistNode *next;
    // 指向 ziplist 的指针
    unsigned char *zl;
    // ziplist 字节大小
    unsigned int sz;
    // ziplst 元素个数
    unsigned int count : 16;
    // 编码格式,1 = RAW 代表未压缩原生ziplist,2=LZF 压缩存储
    unsigned int encoding : 2;
    // 节点持有的数据类型,默认值 = 2 表示是 ziplist
    unsigned int container : 2;
    // 节点持有的 ziplist 是否经过解压, 1 表示已经解压过,下一次操作需要重新压缩。
    unsigned int recompress : 1;
    // ziplist 数据是否可压缩,太小数据不需要压缩
    unsigned int attempted_compress : 1;
    // 预留字段
    unsigned int extra : 10;
} quicklistNode;

quicklist 作为链表,定义了 头、尾指针,用于快速定位表表头和链表尾。

typedef struct quicklist {
    // 链表头指针
    quicklistNode *head;
    // 链表尾指针
    quicklistNode *tail;
    // 所有 ziplist 的总 entry 个数
    unsigned long count;
    // quicklistNode 个数
    unsigned long len;
    int fill : QL_FILL_BITS;
    unsigned int compress : QL_COMP_BITS;
    unsigned int bookmark_count: QL_BM_BITS;
    // 柔性数组,给节点添加标签,通过名称定位节点,实现随机访问的效果
    quicklistBookmark bookmarks[];
} quicklist;

结合 quicklist 和 quicklistNode定义,quicklist 链表结构如下图所示。

图片

从结构上看,quicklist 就是 ziplist 的升级版,优化的关键点在于控制好每个 ziplist 的大小或者元素个数。

  • quicklistNode 的 ziplist 越小,可能会造成更多的内存碎片,极端情况下是每个 ziplist 只有一个 entry,退化成了 linkedlist。
  • quicklistNode 的 ziplist 过大,极端情况下一个 quicklist 只有一个 ziplist,退化成了 ziplist。连锁更新的性能问题就会暴露无遗。

合理配置很重要,Redis 提供了 list-max-ziplist-size -2。

当 list-max-ziplist-size 为负数时表示限制每个 quicklistNode 的 ziplist 的内存大小,超过这个大小就会使用 linkedlist 存储数据,每个值有以下含义:

  • -5:每个 quicklist 节点上的 ziplist 大小最大 64 kb <--- 正常环境不推荐
  • -4:每个 quicklist 节点上的 ziplist 大小最大 32 kb <--- 不推荐
  • -3:每个 quicklist 节点上的 ziplist 大小最大 16 kb <--- 可能不推荐
  • -2:每个 quicklist 节点上的 ziplist 大小最大 8 kb <--- 不错
  • -1:每个 quicklist 节点上的 ziplist 大小最大 4kb <--- 不错

默认值为 -2,也是官方最推荐的值,当然你可以根据自己的实际情况进行修改。

MySQL:“搞了半天还是没能解决连锁更新的问题嘛”

别急,饭要一口口吃,路要一步步走,步子迈大了容易扯着蛋。

ziplist 是紧凑型数据结构,可以有效利用内存。但是每个 entry 都用 prevlen 保留了上一个 entry 的长度,所以在插入或者更新时可能会出现连锁更新影响效率。

于是 antirez 又设计出了“链表 + ziplist” 组成的 quicklist 来避免单个 ziplist 过大,降低连锁更新的影响范围。

可毕竟还是使用了 ziplist,本质上无法避免连锁更新的问题,于是乎在 5.0 版本设计出另一个内存紧凑型数据结构 listpack,于 7.0 版本替换掉 ziplist。

listpack

出现 listpack 的原因是因为用户上报了一个 Redis 崩溃的问题,但是 antirez 并没有找到崩溃的明确原因,猜测可能是 ziplist 结构导致的连锁更新导致的,于是就想设计一种简单、高效的数据结构来替换 ziplist 这个数据结构。

MySQL:“listpack 是啥?”

​listpack 也是一种紧凑型数据结构,用一块连续的内存空间来保存数据,并且使用多种编码方式来表示不同长度的数据来节省内存空间。

源码文件 listpack.h对 listpack 的解释:A lists of strings serialization format,意思是一种字符串列表的序列化格式,可以把字符串列表进行序列化存储,可以存储字符串或者整形数字。

先看 listpack 的整体结构。

图片

一共四部分组成,tot-bytes、num-elements、elements、listpack-end-byte。

  • tot-bytes,也就是 total bytes,占用 4 字节,记录 listpack 占用的总字节数。
  • num-elements,占用 2 字节,记录 listpack elements 元素个数。
  • elements,listpack 元素,保存数据的部分。
  • listpack-end-byte,结束标志,占用 1 字节,值固定为 255。

MySQL:“好家伙,这跟 ziplist 有啥区别?别以为换了个名字,换个马甲我就不认识了”

听我说完!确实有点像,listpack 也是由元数据和数据自身组成。最大的区别是 elements 部分,为了解决 ziplist 连锁更新的问题,element 不再像 ziplist 的 entry 保存前一项的长度。

图片

  • encoding-type,元素的编码类型,会不同长度的整数和字符串编码。
  • element-data,实际存放的数据。
  • element-tot-len,encoding-type + element-data 的总长度,不包含自己的长度。

​每个 element 只记录自己的长度,不像 ziplist 的 entry,记录上一项的长度。当修改或者新增元素的时候,不会影响后续 element 的长度变化,解决了连锁更新的问题。

从 linkedlist、 ziplist 到“链表 + ziplist” 构成的 quicklist,再到 listpack 结构。可以看到,设计的初衷都是能够高效的使用内存,同时避免性能下降。

本文转载自微信公众号「码哥字节」,可以通过以下二维码关注。转载本文请联系码哥字节公众号。



Tags:Redis   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
Linux获取Redis 性能指标方法
一、监控指标&Oslash; 性能指标:Performance&Oslash; 内存指标: Memory&Oslash; 基本活动指标:Basic activity&Oslash; 持久性指标: Persistence&Oslash; 错误指标:Error二、监...【详细内容】
2024-04-11  Search: Redis  点击:(2)  评论:(0)  加入收藏
Redis 不再 “开源”,未来采用 SSPLv1 和 RSALv2 许可证
Redis 官方于21日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause...【详细内容】
2024-03-27  Search: Redis  点击:(12)  评论:(0)  加入收藏
如何使用 Redis 实现消息队列
Redis不仅是一个强大的内存数据存储系统,它还可以用作一个高效的消息队列。消息队列是应用程序间或应用程序内部进行异步通信的一种方式,它允许数据生产者将消息放入队列中,然...【详细内容】
2024-03-22  Search: Redis  点击:(18)  评论:(0)  加入收藏
手动撸一个 Redis 分布式锁
大家好呀,我是楼仔。今天第一天开工,收拾心情,又要开始好好学习,好好工作了。对于使用 Java 的小伙伴,其实我们完全不用手动撸一个分布式锁,直接使用 Redisson 就行。但是因为这些...【详细内容】
2024-02-19  Search: Redis  点击:(40)  评论:(0)  加入收藏
Redis 实现多规则限流的思考与实践
市面上很多介绍redis如何实现限流的,但是大部分都有一个缺点,就是只能实现单一的限流,比如1分钟访问1次或者60分钟访问10次这种,但是如果想一个接口两种规则都需要满足呢,我们的...【详细内容】
2024-01-03  Search: Redis  点击:(109)  评论:(0)  加入收藏
Redis Sentinel的监控和自动化处理Redis节点故障恢复机制
Redis Sentinel是一个分布式的监控系统,它可以监控多个Redis节点的健康状态,并在节点发生故障时自动进行故障转移和恢复。Redis Sentinel通过选举机制选择一个主节点,并将其他...【详细内容】
2023-12-25  Search: Redis  点击:(81)  评论:(0)  加入收藏
用 SpringBoot+Redis 解决海量重复提交问题
前言 一:搭建redis的服务Api 二:自定义注解AutoIdempotent 三:token创建和检验 四:拦截器的配置 五:测试用例 六:总结前言:在实际的开发项目中,一个对外暴露的接口往往会面临很多...【详细内容】
2023-12-20  Search: Redis  点击:(53)  评论:(0)  加入收藏
Redis 除了用作缓存还能干吗?
今天我们来聊聊 Redis 的使用案例。Redis 是一种内存键值数据库。它支持多种数据结构,如 String, Hash, List, Set 和 SortedSet。图片01 缓存Redis 的最常用的用例是缓存,以...【详细内容】
2023-12-11  Search: Redis  点击:(119)  评论:(0)  加入收藏
Redis 也支持全文搜索?这也太强了
在 2021 年我就了解到 RediSearch 这个项目,并已经把它用于我的开源项目 newbee-mall-pro 中。就我的使用体验来说,简单场景下,用来平替 Elasticsearch 的使用场景已经足够。像...【详细内容】
2023-12-11  Search: Redis  点击:(251)  评论:(0)  加入收藏
Redis 如何保证数据不丢失?
前段时间表妹收到了小米秋招补录的面试邀请,一面还算顺利,很快就通过了,但在看二面面试录屏的时候,我发现了一个问题,有一道面试题回答的不是很好,也就是我们今天要聊的这个问题:Re...【详细内容】
2023-11-27  Search: Redis  点击:(159)  评论:(0)  加入收藏
▌简易百科推荐
16个Redis常见使用场景总结
来源:blog.csdn.net/qq_39938758/article/details/105577370目录 缓存 数据共享分布式 分布式锁 全局ID 计数器 限流 位统计 购物车 用户消息时间线timeline 消息...【详细内容】
2024-04-11    书圈  Tags:Redis   点击:(2)  评论:(0)  加入收藏
Linux获取Redis 性能指标方法
一、监控指标&Oslash; 性能指标:Performance&Oslash; 内存指标: Memory&Oslash; 基本活动指标:Basic activity&Oslash; 持久性指标: Persistence&Oslash; 错误指标:Error二、监...【详细内容】
2024-04-11  上海天正信息科技有限    Tags:Redis   点击:(2)  评论:(0)  加入收藏
Redis与缓存一致性问题
缓存一致性问题是在使用缓存系统,如Redis时经常遇到的问题。当数据在原始数据源(如数据库)中发生变化时,如何确保缓存中的数据与数据源保持一致,是开发者需要关注的关键问题。一...【详细内容】
2024-04-11  后端Q    Tags:Redis   点击:(2)  评论:(0)  加入收藏
Redis 不再 “开源”,未来采用 SSPLv1 和 RSALv2 许可证
Redis 官方于21日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause...【详细内容】
2024-03-27  dbaplus社群    Tags:Redis   点击:(12)  评论:(0)  加入收藏
Redis“叛逃”开源,得罪了几乎所有人
内存数据库供应商Redis近日在开源界砸下了一块“巨石”。Redis即将转向双许可模式,并实施更为严格的许可条款。官方对此次变更的公告直截了当:从Redis 7.4版本开始,Redis将在Re...【详细内容】
2024-03-25    51CTO  Tags:Redis   点击:(10)  评论:(0)  加入收藏
如何使用 Redis 实现消息队列
Redis不仅是一个强大的内存数据存储系统,它还可以用作一个高效的消息队列。消息队列是应用程序间或应用程序内部进行异步通信的一种方式,它允许数据生产者将消息放入队列中,然...【详细内容】
2024-03-22  后端Q  微信公众号  Tags:Redis   点击:(18)  评论:(0)  加入收藏
Redis不再 “开源”
Redis 官方今日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause 开...【详细内容】
2024-03-21  OSC开源社区    Tags:Redis   点击:(9)  评论:(0)  加入收藏
在Redis中如何实现分布式锁的防死锁机制?
在Redis中实现分布式锁是一个常见的需求,可以通过使用Redlock算法来防止死锁。Redlock算法是一种基于多个独立Redis实例的分布式锁实现方案,它通过协调多个Redis实例之间的锁...【详细内容】
2024-02-20  编程技术汇    Tags:Redis   点击:(49)  评论:(0)  加入收藏
手动撸一个 Redis 分布式锁
大家好呀,我是楼仔。今天第一天开工,收拾心情,又要开始好好学习,好好工作了。对于使用 Java 的小伙伴,其实我们完全不用手动撸一个分布式锁,直接使用 Redisson 就行。但是因为这些...【详细内容】
2024-02-19  楼仔  微信公众号  Tags:Redis   点击:(40)  评论:(0)  加入收藏
工作中Redis有哪些好用的运维工具
工作中使用 Redis 时,如果大家公司没有专业运维,可能开发人员就会面临这些运维的工作,包括 Redis 的运行状态监控,数据迁移,主从集群、切片集群的部署和运维等等。本文我就从这三...【详细内容】
2024-02-06  waynaqua    Tags:Redis   点击:(56)  评论:(0)  加入收藏
站内最新
站内热门
站内头条