Redis源码剖析之快速列表(quicklist) @TOC何为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;从上文中我们已经了解了一个quicklist某个时刻在内存中的样子，接下我们来看下它是如何在数据插入删除时变化的。
quicklist的操作创建/* 创建一个新的quicklist. * 使用quicklistRelease()释放quicklist. */quicklist *quicklistCreate(void) {struct quicklist *quicklist;quicklist = zmalloc(sizeof(*quicklist));quicklist->head = quicklist->tail = NULL;quicklist->len = 0;quicklist->count = 0;quicklist->compress = 0;quicklist->fill = -2;quicklist->bookmark_count = 0;return quicklist;}create就没啥好说的了，但这里需要提醒下， fill值默认是-2 ，也就是说每个quicklistNode中的ziplist最长是8k字节，可以更具自己业务需求调整具体配置。
头插和尾插对于list而已，头部或者尾部插入是最常见的操作了，但其实头插和尾插还算是比较简单。
/* 在quicklist的头部插入一条数据* 如果在已存在节点插入，返回0 * 如果是在新的头结点插入，返回1 */int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {quicklistNode *orig_head = quicklist->head;if (likely(_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {quicklist->head->zl =ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);// 在头结点对应的ziplist中插入quicklistNodeUpdateSz(quicklist->head);} else { // 否则新建一个头结点，然后插入数据quicklistNode *node = quicklistCreateNode();node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);quicklistNodeUpdateSz(node);_quicklistInsertNodeBefore(quicklist, quicklist->head, node);}quicklist->count++;quicklist->head->count++;return (orig_head != quicklist->head);}/* 在quicklist的尾部插入一条数据* 如果在已存在节点插入，返回0 * 如果是在新的头结点插入，返回1 */int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {quicklistNode *orig_tail = quicklist->tail;if (likely(_quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {quicklist->tail->zl =ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);quicklistNodeUpdateSz(quicklist->tail);} else {quicklistNode *node = quicklistCreateNode();node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);quicklistNodeUpdateSz(node);_quicklistInsertNodeAfter(quicklist, quicklist->tail, node);}quicklist->count++;quicklist->tail->count++;return (orig_tail != quicklist->tail);} 上一页 1 2 3 下一页 Python源码阅读-基础1 3天时间，我是如何解决redis bigkey 删除问题的？什么是建造者模式？他在jdk、MyBatis源码怎么运用？ Django实战016：django中使用redis详解 CANopen源码简单讲二视频|短视频源码开发，一套成熟的短视频源码应该是这样的你不知道的Redis：入门？数据结构？常用指令？ Python操作Redis大全为什么 Redis 单线程能支撑高并发？ Martian框架发布 3.0.3 版本，Redis分布式锁