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

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time