redis源码学习-quicklist篇
0 条评论redis源码学习-quicklist篇
quicklist介绍
quicklist为基于zpilist做了一层优化的链表结构，quicklist为双端链表，每个节点指向独自的ziplist，在有着ziplist高效内存效率的情况下，适当优化了ziplist的增删效率。
本篇部分依赖ziplist，忘记的同学先移步回顾下
quicklist分析
quicklist出现的原因在于，ziplist虽然有着极高的内存使用率，但也因此，在查找时只能单循环遍历，增删的时候有着极高的连锁更新的可能，最坏情况下的时间复杂度在O(n^2)。这种操纵效率相对比sds，dict或zskiplist等其他底层数据结构来说，实在是对不起‘redis’的名头。也因此，引入quicklist对这个数据结构做部分优化，降低更新复杂度，保持内存使用率。
如图
每个quicklistnode都会指向一个单独的ziplist，同时包含next和last的quicklistnode地址，
看图的话，会发现quicklist非常简单，总体实现来说也很简单，就不多做介绍了
quicklist数据结构
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 : QL_FILL_BITS; /* fill factor for individual nodes */
unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];
} quicklist;
head为头节点，tail为尾节点，count记录的是所有的ziplist中的entry总数，len为quicklist节点总数。fill为16位，代表每个节点的最大容量，compress为16位，quicklist的压缩深度，与之后的LZF压缩相关。bookmark_count为4位，代表bookmarks数组的大小。bookmarks用来给quicklist重新分配内存空间时使用，不使用的时候不占空间
从这里看出，quicklist只保留首位两quicklistnode的地址，之后就是count等辅助字段了
quicklistnode数据结构
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;
prev和next是双向链表的标准配置，指向上一个或下一个quicklistnode节点。*zl就是这个node所使用的ziplist了。sz为这个ziplist的字节数。count为这个ziplist的item数。encoding代表这个zpilist的类型，raw1，就算标准ziplist，lzf2，LZF代表着对这个ziplist进行了lzf压缩。attempted_compress则是记录这个list是否被压缩过。
上述中出现了LZF压缩，在这里只讲下概念。LZF压缩主要做两件事，一是对重复值进行压缩二是通过hash来判断是否为重复数据。
数据结构讲完，来看具体操作函数
create：
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;
}
非常简单，分配空间，字段初始化
insert：
/* Wrapper to allow argument-based switching between HEAD/TAIL pop */
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
int where) {
if (where == QUICKLIST_HEAD) {
quicklistPushHead(quicklist, value, sz);
} else if (where == QUICKLIST_TAIL) {
quicklistPushTail(quicklist, value, sz);
}
}
在这里根据where字段决定是使用头插法还是尾插法。头插和尾插区别不大，这里只看头插法。
头插法：
/* Add new entry to head node of quicklist.
*
* Returns 0 if used existing head.
* Returns 1 if new head created. */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
quicklistNode *orig_head = quicklist->head;
if (likely(
//_quicklistNodeAllowInsert这个负责判断当前quicklistnode的ziplist是否太大了
_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
quicklist->head->zl =
ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
quicklistNodeUpdateSz(quicklist->head);
} else {
//如果_quicklistNodeAllowInsert说当前的quictlistnode中ziplist过大无法再插入，就new一个新的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);
}
delete：
/* 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 offset N and now
* length of this ziplist is N-1, the next call into
* quicklistNext() will jump to the next node. */
}
/* Delete one entry from list given the node for the entry and a pointer
* to the entry in the node.
*
* Note: quicklistDelIndex() *requires* uncompressed nodes because you
* already had to get *p from an uncompressed node somewhere.
*
* Returns 1 if the entire node was deleted, 0 if node still exists.
* Also updates in/out param 'p' with the next offset in the ziplist. */
REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node,
unsigned char **p) {
int gone = 0;
node->zl = ziplistDelete(node->zl, p);
node->count--;
if (node->count == 0) {
gone = 1;
__quicklistDelNode(quicklist, node);
} else {
quicklistNodeUpdateSz(node);
}
quicklist->count--;
/* If we deleted the node, the original node is no longer valid */
return gone ? 1 : 0;
}
REDIS_STATIC void __quicklistDelNode(quicklist *quicklist,
quicklistNode *node) {
/* Update the bookmark if any */
quicklistBookmark *bm = _quicklistBookmarkFindByNode(quicklist, node);
if (bm) {
bm->node = node->next;
/* if the bookmark was to the last node, delete it. */
if (!bm->node)
_quicklistBookmarkDelete(quicklist, bm);
}
if (node->next)
node->next->prev = node->prev;
if (node->prev)
node->prev->next = node->next;
if (node == quicklist->tail) {
quicklist->tail = node->prev;
}
if (node == quicklist->head) {
quicklist->head = node->next;
}
/* Update len first, so in __quicklistCompress we know exactly len */
quicklist->len--;
quicklist->count -= node->count;
/* If we deleted a node within our compress depth, we
* now have compressed nodes needing to be decompressed. */
__quicklistCompress(quicklist, NULL);
zfree(node->zl);
zfree(node);
}
删除代码虽然长，但是逻辑相当简单，仅仅是将这个节点从节点剔除，然后分别zfree node->zl和node。
总体来说，从quicklist的名字来说，quick应该是对ziplist的操作复杂度说的，quicklist本身没什么难度，重点放在ziplist，看懂之后ziplist，quicklist只需明白数据结构就足够了。
