四川省住房和城乡建设厅官网站网,义乌哪里做网站好,新版爱美眉网站源码,推广运营是什么工作Redis List
在Redis3.2版之前#xff0c;Redis使用压缩列表和双向链表作为List的底层实现。当元素个数比较少并且元素长度比较小时#xff0c;Redis使用压缩列表实现#xff0c;否则Redis使用双向链表实现。
ziplist存在问题 不能保存过多的元素#xff0c;否则查找复杂度…Redis List
在Redis3.2版之前Redis使用压缩列表和双向链表作为List的底层实现。当元素个数比较少并且元素长度比较小时Redis使用压缩列表实现否则Redis使用双向链表实现。
ziplist存在问题 不能保存过多的元素否则查找复杂度高性能降低。 由于每个节点保存了前一个节点的长度不同长度使用的字节数不一样所以在更新节点的时候有可能引起长度的变化导致连锁更新问题。
为了解决上面两个问题在Redis3.2版之后引入了quicklist。
quicklist
quicklist可以理解为是ziplist和链表的结合体一个quicklist是一个双向链表链表中的每一个节点是一个ziplist。 quicklist结构定义
typedef struct quicklist {// 头指针quicklistNode *head;// 尾指针quicklistNode *tail;unsigned long count; /* 列表中的元素总个数也就是所有ziplist中包含的元素数量之和 */unsigned long len; /* 链表中节点的个数 */int fill : QL_FILL_BITS; /* 表示ziplist的大小 */unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0off */unsigned int bookmark_count: QL_BM_BITS;quicklistBookmark bookmarks[];
} quicklist;head指向头结点的指针 tail指向尾节点的指针 count列表中的元素总个数等于所有节点的ziplist中包含的元素数量之和 lenquicklist中quicklistNode节点的个数 fill用来限制quicklistNode中ziplist的大小为正数时代表ziplist中最多能包含的元素个数为负数时有以下几种情况 数值含义-1表示ziplist的字节数不能超过4KB-2表示ziplist的字节数不能超过8KB-3表示ziplist的字节数不能超过16KB-4表示ziplist的字节数不能超过32KB-5表示ziplist的字节数不能超过64KB
除此之外也可以通过list-max-ziplist-size参数配置最大的字节数。
quicklistNode结构定义
typedef struct quicklistNode {// 前一个节点struct quicklistNode *prev;// 下一个节点struct quicklistNode *next;// 指向ziplist压缩列表的指针unsigned char *zl;unsigned int sz; /* ziplist压缩列表的字节数 */unsigned int count : 16; /* ziplist压缩列表的元素个数 */unsigned int encoding : 2; /* 编码格式RAW1 or LZF2 */unsigned int container : 2; /* NONE1 or ZIPLIST2 */unsigned int recompress : 1; /* 是否被压缩 */unsigned int attempted_compress : 1; /* 是否可以被压缩 */unsigned int extra : 10; /* 预留bit位*/
} quicklistNode;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;// 默认为-2表示ziplist的字节数最大不能超过8KBquicklist-fill -2;quicklist-bookmark_count 0;return quicklist;
}添加元素
添加元素的时候可以在链表的头部或者尾部进行添加以头部添加为例
首先调用_quicklistNodeAllowInsert方法判断是否允许添加元素到ziplist如果允许调用ziplistPush方法进行添加如果_quicklistNodeAllowInsert不允许添加元素则需要新创建一个quicklistNode然后将元素添加到新创建的quicklistNode的压缩列表中
// 从头部添加元素
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {quicklistNode *orig_head quicklist-head;// 判断是否允许添加if (likely(_quicklistNodeAllowInsert(quicklist-head, quicklist-fill, sz))) {// 将元素添加到ziplitquicklist-head-zl ziplistPush(quicklist-head-zl, value, sz, ZIPLIST_HEAD);quicklistNodeUpdateSz(quicklist-head);} else {// 新创建quicklistNode节点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);
}_quicklistNodeAllowInsert
_quicklistNodeAllowInsert方法用于判断是否允许在某个quicklistNode指向的压缩列表中添加元素。
在quicklist的结构体定义中fill指定了ziplist中能包含的最大元素个数或者ziplist最大的字节数_quicklistNodeAllowInsert方法就是判断ziplist中的元素个数或者ziplist的字节数是否超过了限制
// node当前的quicklistNode节点
// fillziplist中能包含的最大元素个数或者ziplist最大的字节数
// sz要添加元素的大小
REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,const int fill, const size_t sz) {if (unlikely(!node))return 0;int ziplist_overhead;/* 判断要添加元素的大小是否小于254 */if (sz 254)ziplist_overhead 1;elseziplist_overhead 5;/* 判断要添加元素的大小是否小于64 */if (sz 64)ziplist_overhead 1;else if (likely(sz 16384))ziplist_overhead 2;elseziplist_overhead 5;/* 计算添加元素后的当前的quicklistNode的大小 新加入元素的大小 插入元素后ziplit的prevlen占用大小 */unsigned int new_sz node-sz sz ziplist_overhead;// 判断添加元素后的ziplist的字节数是否超过了fill中设置的大小if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill)))return 1;else if (!sizeMeetsSafetyLimit(new_sz))return 0;else if ((int)node-count fill) // 判断ziplist的元素个数是否超过了fill设置的大小return 1;elsereturn 0;
}总结 在Redis3.2版之前Redis使用压缩列表和双向链表作为List的底层实现。当元素个数比较少并且元素长度比较小时Redis使用压缩列表实现否则Redis使用双向链表实现。 为了解决压缩列表在节点多的时候查找效率低的问题以及连锁更新问题在Redis3.2版之后引入了quicklistquicklist是一个双向链表链表中的每一个节点是一个ziplist。 quicklist中限定了ziplist的大小如果超过了限制的大小新加入元素的时候会生成一个新的quicklistNode节点。 quicklist通过限定ziplist的大小来保证一个ziplist中的元素个数不会太多如果需要连锁更新也只在某个quicklistNode节点指向的ziplist中更新不会引发整个链表的更新以此来解决压缩列表存在的问题。
参考
陈雷《Redis5设计与源码分析》
极客时间 - Redis源码剖析与实战(蒋德钧)
Redis版本redis-6.2.5
