Redis源码剖析之快速列表(quicklist)
@TOC何为quicklist , 上次说到ziplist每次变更的时间复杂度都非常高 , 因为必须要重新生成一个新的ziplist来作为更新后的list , 如果一个list非常大且更新频繁 , 那就会给redis带来非常大的负担 。 如何既保留ziplist的空间高效性 , 又能不让其更新复杂度过高? redis的作者给出的答案就是quicklist 。
其实说白了就是把ziplist和普通的双向链表结合起来 。 每个双链表节点中保存一个ziplist , 然后每个ziplist中存一批list中的数据(具体ziplist大小可配置) , 这样既可以避免大量链表指针带来的内存消耗 , 也可以避免ziplist更新导致的大量性能损耗 , 将大的ziplist化整为零 。
数据结构quicklist一图胜千言 , 我们来看下一个实际的quicklist在内存中长啥样 。
文章插图
大致介绍下上图中不同的节点 , 所有redis中list其实都是quicklist , 所以像pop push等命令中的list参数都是quicklist 。 quicklist各字段及其含义如下 。
typedef struct quicklist {quicklistNode *head;/* 头结点 */quicklistNode *tail;/* 尾结点 */unsigned long count;/* 在所有的ziplist中的entry总数 */unsigned long len;/* quicklist节点总数 */int fill : QL_FILL_BITS;/* 16位 , 每个节点的最大容量 */unsigned int compress : QL_COMP_BITS; /* 16位 , quicklist的压缩深度 , 0表示所有节点都不压缩 , 否则就表示从两端开始有多少个节点不压缩 */unsigned int bookmark_count: QL_BM_BITS;/*4位 , bookmarks数组的大小 , bookmarks是一个可选字段 , 用来quicklist重新分配内存空间时使用 , 不使用时不占用空间*/quicklistBookmark bookmarks[];} quicklist;
可以看出quicklist其实就是简单的双链表 , 但这里多出来几个字段 , 先重点介绍下compress 。 在上图中我用了两种不同颜色的节点 , 其中绿色是普通的ziplist节点 , 而红色是被压缩后的ziplist节点(LZF节点) , LZF是种无损压缩算法 。 redis为了节省内存空间 , 会将quicklist的节点用LZF压缩后存储 , 但这里不是全部压缩 , 可以配置compress的值 , compress为0表示所有节点都不压缩 , 否则就表示从两端开始有多少个节点不压缩 , 像我上图图示中 , compress就是1 , 表示从两端开始 , 有1个节点不做LZF压缩 。 *compress默认是0(不压缩) , 具体可以根据你们业务实际使用场景去配置 。*
为什么不全部节点都压缩 , 而是流出compress这个可配置的口子呢?其实从统计而已 , list两端的数据变更最为频繁 , 像lpush,rpush,lpop,rpop等命令都是在两端操作 , 如果频繁压缩或解压缩会代码不必要的性能损耗 。 从这里可以看出 redis其实并不是一味追求性能 , 它也在努力减少存储占用、在存储和性能之间做trade-off 。
这里还有个fill字段 , 它的含义是每个quicknode的节点最大容量 , 不同的数值有不同的含义 , 默认是-2 , 当然也可以配置为其他数值 , 具体数值含义如下:
- -1: 每个quicklistNode节点的ziplist所占字节数不能超过4kb 。 (建议配置)
- -2: 每个quicklistNode节点的ziplist所占字节数不能超过8kb 。 (默认配置struct quicklistNode *next;unsigned char *zl;/* quicklist节点对应的ziplist */unsigned int sz;/* ziplist的字节数 */unsigned int count : 16;/* ziplist的item数*/unsigned int encoding : 2;/* 数据类型 , RAW==1 or LZF==2 */unsigned int container : 2;/* NONE==1 or ZIPLIST==2 */unsigned int recompress : 1; /* 这个节点以前压缩过吗? */unsigned int attempted_compress : 1; /* node can't compress; too small */unsigned int extra : 10; /* 未使用到的10位 */} quicklistNode;
- 次世代大作标配 光线追踪DLSS深度剖析
- java 从零实现属于你的 redis 分布式锁
- Redis集群做法的难点,百万并发客户端「实战」
- C语言火车订单管理源码
- HFL Redis_10_set类型底层存储数据结构
- 为什么 Redis 单线程能支撑高并发?
- 清华教授整理535本编程电子书+视频教程+项目源码限时领取
- Redis流行的原因
- 掌握会用了,为什么还要源码学习?
- 阿里爆款SpringBoot项目实战PDF+源码+视频分享