Redis源码学习:quicklist的设计与实现

2024-06-23 10:36

本文主要是介绍Redis源码学习:quicklist的设计与实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

为什么需要quicklist

假设你已经知道了ziplist的缺陷:

  • 虽然节省空间,但是申请内存必须是连续的,如果内存占用比较多,申请效率低
  • 要存储大量数据,超过了ziplist的最佳上限后,性能有影响

借鉴分片思想,可以把大量的数据分片存储到多个ziplist中,每个ziplist的长度和大小都在最佳上限之下,这样虽然解决了单个ziplist空间申请和数据存储的问题,但是又有了新的挑战:数据拆分后比较分散,不方便查找和管理,多个ziplist如何建立连接呢?这就是下面要说的quicklist。

什么是quicklist

quicklist是一个双端链表结构,链表的每一个节点都是ziplist。

quicklist的结构

// quicklistNode 节点
typedef struct quicklistNode {struct quicklistNode *prev;     //前一个quicklistNodestruct quicklistNode *next;     //后一个quicklistNodeunsigned char *zl;              //quicklistNode指向的ziplistunsigned int sz;                //ziplist的字节大小unsigned int count : 16;        //ziplist中的元素个数 unsigned int encoding : 2;   //编码格式,原生字节数组或压缩存储unsigned int container : 2;  //存储方式unsigned int recompress : 1; //数据是否被压缩unsigned int attempted_compress : 1; //数据能否被压缩unsigned int extra : 10; //预留的bit位
} quicklistNode;typedef struct quicklist {quicklistNode *head;      //quicklist的链表头quicklistNode *tail;      //quicklist的链表尾unsigned long count;     //所有ziplist中的总元素个数unsigned long len;       //quicklistNodes的个数...
} quicklist;

quicklist作为链表结构,它定义了整个链表的头、尾指针,这样一来,就可以O(1)的时间复杂度快速定位链表头和尾了。从quicklist的定义,可以画出quicklist的结构如下:

image.png

为了避免quicklist每个节点下的ziplist的entry过多,在Redis.conf中提供了一个配置项list-max-ziplist-size用来限制数量。如果为正数,则表示ziplist允许的entry的个数的最大值;如果为负数,则表示ziplist的最大内存大小,分下面5种情况:

每个ziplist的内存占用限制(不超过)
-14kb
-28kb,默认值
-316kb
-432kb
-564kb

除了控制ziplist的大小,quicklist还可以对节点的ziplist进行压缩,在Redis.conf种提供了配置项list-compress-depth进行控制。因为quicklist是双端链表,首尾一般访问较多,所以首尾不压缩。这个参数用来控制首尾不压缩的个数。

  • 0:特殊值,代表不压缩。默认值
  • 1:表示首尾各有一个节点不压缩,中间节点压缩
  • 2:表示首尾各有两个节点不压缩,中间节点压缩

插入操作

_quicklistNodeAllowInsert函数用来完成新节点的插入,源码如下:

REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,const int fill, const size_t sz) {// new_sz 是新插入元素后 quicklistNode 的总大小,加上 ziplist 的额外开销unsigned int new_sz = node->sz + sz + ziplist_overhead;// 如果新大小符合优化要求,则允许插入if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill)))return 1;// 如果不符合优化要求,进一步检查大小是否安全// 如果不安全,则不允许插入else if (!sizeMeetsSafetyLimit(new_sz))return 0;// 如果节点中的元素个数少于填充因子,允许插入else if ((int)node->count < fill)return 1;// 否则不允许插入elsereturn 0;
}

_quicklistNodeAllowInsert函数会计算新插入元素后的大小(new_sz),等于 quicklistNode 的当前大小(node->sz)、插入元素的大小(sz),以及插入元素后 ziplist 的 prevlen 占用大小。然后依次判断新插入的数据大小是否满足要求,即单个 ziplist 是否不超过 8KB,或是单个 ziplist 里的元素个数是否满足要求。只要这里面的一个条件能满足,quicklist 就可以在当前的 quicklistNode 中插入新元素,否则 quicklist 就会新建一个 quicklistNode,以此来保存新插入的元素。

这样一来,quicklist通过控制每个节点种ziplist 的大小或是元素个数,可以有效减少在 ziplist 中新增或修改元素后,发生连锁更新的情况。

总结

本文主要讲解了为了解决ziplist的缺陷,quicklist通过对ziplist进行“分片”存储,限制每个节点的大小或数量来提供性能的方法,希望对你有帮助。

这篇关于Redis源码学习:quicklist的设计与实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1086915

相关文章

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

使用Python实现可恢复式多线程下载器

《使用Python实现可恢复式多线程下载器》在数字时代,大文件下载已成为日常操作,本文将手把手教你用Python打造专业级下载器,实现断点续传,多线程加速,速度限制等功能,感兴趣的小伙伴可以了解下... 目录一、智能续传:从崩溃边缘抢救进度二、多线程加速:榨干网络带宽三、速度控制:做网络的好邻居四、终端交互

java实现docker镜像上传到harbor仓库的方式

《java实现docker镜像上传到harbor仓库的方式》:本文主要介绍java实现docker镜像上传到harbor仓库的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 前 言2. 编写工具类2.1 引入依赖包2.2 使用当前服务器的docker环境推送镜像2.2

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Java easyExcel实现导入多sheet的Excel

《JavaeasyExcel实现导入多sheet的Excel》这篇文章主要为大家详细介绍了如何使用JavaeasyExcel实现导入多sheet的Excel,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录1.官网2.Excel样式3.代码1.官网easyExcel官网2.Excel样式3.代码

python实现对数据公钥加密与私钥解密

《python实现对数据公钥加密与私钥解密》这篇文章主要为大家详细介绍了如何使用python实现对数据公钥加密与私钥解密,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录公钥私钥的生成使用公钥加密使用私钥解密公钥私钥的生成这一部分,使用python生成公钥与私钥,然后保存在两个文

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景