本文主要是介绍Redis quicklist源码+listpack源码（5.0版本以上的优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
ziplist设计上的问题，每一次增删改都需要计算前面元素的空间和长度（prevlen），这种设计缺陷非常明显，因此引入了quicklist的设计。
quicklist
quicklist实际就是双端链表，链表里的每一个节点都是ziplist，这样就可以避免减少了数据插入时内存空间的重新分配，以及内存数据的拷贝。同时每一个节点都会限制ziplist的大小，如果ziplist里面插入的entry过多，就会转化为quicklist增加node方式来存储。
基础结构（其实就是双向链表增删改查结构，没有太吸引人的地方）
typedef struct quicklistNode {struct quicklistNode *prev;struct quicklistNode *next;unsigned char *zl;unsigned int sz; /* ziplist size in bytes */unsigned int count : 16; /* count of items in ziplist */unsigned int encoding : 2; /* RAW==1 or LZF==2 */unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */unsigned int recompress : 1; /* was this node previous compressed? */unsigned int attempted_compress : 1; /* node can't compress; too small */unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.* 'sz' is byte length of 'compressed' field.* 'compressed' is LZF data with total (compressed) length 'sz'* NOTE: uncompressed length is stored in quicklistNode->sz.* When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
typedef struct quicklistLZF {unsigned int sz; /* LZF size in bytes*/char compressed[];
} quicklistLZF;/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.* 'count' is the number of total entries.* 'len' is the number of quicklist nodes.* 'compress' is: -1 if compression disabled, otherwise it's the number* of quicklistNodes to leave uncompressed at ends of quicklist.* 'fill' is the user-requested (or default) fill factor. */
typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count; /* total count of all entries in all ziplists */unsigned long len; /* number of quicklistNodes */int fill : 16; /* fill factor for individual nodes */unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;/* Create a new quicklist with some default parameters. */
quicklist *quicklistNew(int fill, int compress) {quicklist *quicklist = quicklistCreate();quicklistSetOptions(quicklist, fill, compress);return quicklist;
}/* Add new entry to tail node of quicklist.*追加元素* Returns 0 if used existing tail.* Returns 1 if new tail created. */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {quicklistNode *orig_tail = quicklist->tail;assert(sz < UINT32_MAX); /* TODO: add support for quicklist nodes that are sds encoded (not zipped) */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);
}/* Delete one element represented by 'entry'*删除元素* 'entry' stores enough metadata to delete the proper position in* the correct ziplist in the correct quicklist node. */
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {quicklistNode *prev = entry->node->prev;quicklistNode *next = entry->node->next;int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist,entry->node, &entry->zi);/* after delete, the zi is now invalid for any future usage. */iter->zi = NULL;/* If current node is deleted, we must update iterator node and offset. */if (deleted_node) {if (iter->direction == AL_START_HEAD) {iter->current = next;iter->offset = 0;} else if (iter->direction == AL_START_TAIL) {iter->current = prev;iter->offset = -1;}}/* else if (!deleted_node), no changes needed.* we already reset iter->zi above, and the existing iter->offset* doesn't move again because:* - [1, 2, 3] => delete offset 1 => [1, 3]: next element still offset 1* - [1, 2, 3] => delete offset 0 => [2, 3]: next element still offset 0* if we deleted the last element at offet N and now* length of this ziplist is N-1, the next call into* quicklistNext() will jump to the next node. */
}listpack
quicklist链表里的每一个node都会指向ziplist，内存占用极大。
listpack沿用ziplist的基础数据结构，采用的连续内存布局，不会去计算前一项的空间长度，只会计算自己的长度，这样可以完全避免连续更新的缺陷，并且做了双向索引的优化。
编码方式：
整型编码
字符串编码
遍历方式：
正向遍历：lpFirst-->lpNext-->lpSkip 调用两个函数lpCurrentEncodedSize 和 lpEncodeBacklen
lpCurrentEncodedSize 函数是根据当前列表项第 1 个字节的取值，来计算当前项的编码类型，并根据编码类型，计算当前项编码类型和实际数据的总长度。然后，lpEncodeBacklen 函数会根据编码类型和实际数据的长度之和，进一步计算列表项最后一部分 entry-len 本身的长度。这样一来，lpSkip 函数就知道当前项的编码类型、实际数据和 entry-len 的总长度了，也就可以将当前项指针向右偏移相应的长度，从而实现查到下一个列表项的目的。
反向遍历
这篇关于Redis quicklist源码+listpack源码（5.0版本以上的优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
