Redis数据结构之quicklist

本文及后续文章,Redis版本均是v3.2.8

我们在使用Redis对外暴露的list数据结构时,给我们带来极大的便利性。其底层实现所依赖的内部数据结构就是quicklist。

我们先来回忆下list这种数据结构的特点:

  • 表list是一个能维持数据项先后顺序的双向链表

  • 在表list的两端追加和删除数据极为方便,时间复杂度为O(1)

  • 表list也支持在任意中间位置的存取操作,时间复杂度为O(N)

  • 表list经常被用作队列使用

本篇文章我们来讨论下quicklist,

先来看下Redis官方quicklist.c和quicklist.h对quicklist的描述

A doubly linked list of ziplists

A generic doubly linked quicklist implementation

quicklist是一个ziplist的双向链表(双向链表是由多个节点Node组成的)。也就是说quicklist的每个节点都是一个ziplist。ziplist本身也是一个能维持数据项先后顺序的列表(按插入位置),而且是一个各个数据项在内存上前后相邻的列表。

一、quicklist结构定义

  • 双向链表在表的两端进行push和pop操作十分的便节,但是它的内存开销比较大。

    首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;

    其次,双向链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片。

  • ziplist由于是一整块连续内存,所以存储效率很高。

    首先,它不利于修改操作,每次数据变动都会引发一次内存的realloc。

    其次,当ziplist长度很长的时候,一次realloc可能会导致大批量的数据拷贝,进一步降低性能。

Redis基于空间和时间的考虑,于是quicklist结合双向链表和ziplist的优点。

/* Node, quicklist, and Iterator are the only data structures used currently. */

/* quicklist is a 32 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 {

// 指向quicklist的头部

quicklistNode *head;

// 指向quicklist的尾部

quicklistNode *tail;

unsigned long count;        /* total count of all entries in all ziplists */

unsigned int len;           /* number of quicklistNodes */

// ziplist大小限定,由list-max-ziplist-size给定

int fill : 16;              /* fill factor for individual nodes */

// 节点压缩深度设置,由list-compress-depth给定

unsigned int compress : 16; /* depth of end nodes not to compress;0=off */

} quicklist;

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.

* We use bit fields keep the quicklistNode at 32 bytes.

* count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).

* encoding: 2 bits, RAW=1, LZF=2.

* container: 2 bits, NONE=1, ZIPLIST=2.

* recompress: 1 bit, bool, true if node is temporarry decompressed for usage.

* attempted_compress: 1 bit, boolean, used for verifying during testing.

* extra: 12 bits, free for future use; pads out the remainder of 32 bits */

typedef struct quicklistNode {

// 指向上一个ziplist节点

struct quicklistNode *prev;

// 指向下一个ziplist节点

struct quicklistNode *next;

// 数据指针,如果没有被压缩,就指向ziplist结构,反之指向quicklistLZF结构

unsigned char *zl;

// 表示指向ziplist结构的总长度(内存占用长度)

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 */

// 预留字段,存放数据的方式,1--NONE,2--ziplist

unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */

// 解压标记,当查看一个被压缩的数据时,需要暂时解压,标记此参数为1,之后再重新进行压缩

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 {

// LZF压缩后占用的字节数

unsigned int sz; /* LZF size in bytes*/

// 柔性数组,存放压缩后的ziplist字节数组

char compressed[];

} quicklistLZF;

注意点:

quicklistNode 中sz,如果ziplist被压缩了,那么这个sz的值仍然是压缩前的ziplist大小。

从上述的定义中,我们了解到quicklist 在64位系统中占用32字节的空间,quicklistNode 是一个32字节的结构。

上面提到了两个重要参数配置:

list-max-ziplist-size

list-compress-depth

list-max-ziplist-size

1、list-max-ziplist-size取值,可以取正值,也可以取负值。

当取正值的时候,表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如,当这个参数配置成5的时候,表示每个quicklist节点的ziplist最多包含5个数据项。

当取负值的时候,表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时,它只能取-1到-5这五个值,每个值含义如下:

  • -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。(注:1kb => 1024 bytes)

  • -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。

  • -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。

  • -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。(-2是Redis给出的默认值)

  • -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

2、list-max-ziplist-size配置产生的原因?

  • 每个quicklist节点上的ziplist越短,则内存碎片越多。内存碎片多了,有可能在内存中产生很多无法被利用的小碎片,从而降低存储效率。这种情况的极端是每个quicklist节点上的ziplist只包含一个数据项,这就蜕化成一个普通的双向链表了。

  • 每个quicklist节点上的ziplist越长,则为ziplist分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间(它们加起来很多),但却找不到一块足够大的空闲空间分配给ziplist的情况。这同样会降低存储效率。这种情况的极端是整个quicklist只有一个节点,所有的数据项都分配在这仅有的一个节点的ziplist里面。这其实蜕化成一个ziplist了。

可见,一个quicklist节点上的ziplist要保持一个合理的长度。那到底多长合理呢?Redis提供了一个配置参数list-max-ziplist-size,就是为了让使用者可以来根据实际应用场景进行调整优化。

list-compress-depth

其表示一个quicklist两端不被压缩的节点个数。注:这里的节点个数是指quicklist双向链表的节点个数,而不是指ziplist里面的数据项个数。实际上,一个quicklist节点上的ziplist,如果被压缩,就是整体被压缩的。

1、list-compress-depth的取值:

  • 0: 是个特殊值,表示都不压缩。这是Redis的默认值。

  • 1: 表示quicklist两端各有1个节点不压缩,中间的节点压缩。

  • 2: 表示quicklist两端各有2个节点不压缩,中间的节点压缩。

  • 3: 表示quicklist两端各有3个节点不压缩,中间的节点压缩。

  • 依此类推…

由于0是个特殊值,很容易看出quicklist的头节点和尾节点总是不被压缩的,以便于在表的两端进行快速存取。

2、list-compress-depth配置产生原因?

当表list存储大量数据的时候,最容易被访问的很可能是两端的数据,中间的数据被访问的频率比较低(访问起来性能也很低)。如果应用场景符合这个特点,那么list还提供了一个选项,能够把中间的数据节点进行压缩,从而进一步节省内存空间。Redis的配置参数list-compress-depth就是用来完成这个设置的。

二、quicklist典型基本操作函数

当我们使用lpush或rpush等命令第一次向一个不存在的list里面插入数据的时候,Redis会首先调用quicklistCreate接口创建一个空的quicklist。

1、quicklist的创建

/* Create a new quicklist.

* Free with quicklistRelease(). */

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;

return quicklist;

}

从上述代码中,我们看到quicklist是一个不包含空余头节点的双向链表(head和tail都初始化为NULL)。

2、quicklist的push操作

/* 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);

}

}

/* 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(quicklist->head, quicklist->fill, sz))) {

quicklist->head->zl =

ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);

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);

}

/* 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;

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);

}

从上述的代码中,我们可以看到

不管是在头部还是尾部插入数据,都包含两种情况:

  • 如果头节点(或尾节点)上ziplist大小没有超过限制(即_quicklistNodeAllowInsert返回1),那么新数据被直接插入到ziplist中(调用ziplistPush)。

  • 如果头节点(或尾节点)上ziplist太大了,那么新创建一个quicklistNode节点(对应地也会新创建一个ziplist),然后把这个新创建的节点插入到quicklist双向链表中(调用_quicklistInsertNodeAfter)。

3、quicklist的pop操作

/* Default pop function

*

* Returns malloc'd value from quicklist */

int quicklistPop(quicklist *quicklist, int where, unsigned char **data,

unsigned int *sz, long long *slong) {

unsigned char *vstr;

unsigned int vlen;

long long vlong;

if (quicklist->count == 0)

return 0;

int ret = quicklistPopCustom(quicklist, where, &vstr, &vlen, &vlong,

_quicklistSaver);

if (data)

*data = vstr;

if (slong)

*slong = vlong;

if (sz)

*sz = vlen;

return ret;

}

quicklist的pop操作是调用quicklistPopCustom来实现的。

quicklistPopCustom的实现过程基本上跟quicklistPush相反:

首先,从头部或尾部节点的ziplist中把对应的数据项删除;

其次,如果在删除后ziplist为空了,那么对应的头部或尾部节点也要删除;

最后,删除后还可能涉及到里面节点的解压缩问题。

quicklist不仅实现了从头部或尾部插入,也实现了从任意指定的位置插入。quicklistInsertAfter和quicklistInsertBefore就是分别在指定位置后面和前面插入数据项。这种在任意指定位置插入数据的操作,情况比较复杂。

  • 当插入位置所在的ziplist大小没有超过限制时,直接插入到ziplist中就好了

  • 当插入位置所在的ziplist大小超过了限制,但插入的位置位于ziplist两端,并且相邻的quicklist链表节点的ziplist大小没有超过限制,那么就转而插入到相邻的那个quicklist链表节点的ziplist中

  • 当插入位置所在的ziplist大小超过了限制,但插入的位置位于ziplist两端,并且相邻的quicklist链表节点的ziplist大小也超过限制,这时需要新创建一个quicklist链表节点插入

  • 对于插入位置所在的ziplist大小超过了限制的其它情况(主要对应于在ziplist中间插入数据的情况),则需要把当前ziplist分裂为两个节点,然后再其中一个节点上插入数据

三、总结

quicklist将双向链表和ziplist两者的优点结合起来,在时间和空间上做了一个均衡,能较大程度上提高Redis的效率。push和pop等操作操作的时间复杂度也都达到了最优。

--EOF--

上一篇:MySQL锁机制


下一篇:POJ 1631 Bridging signals(LIS O(nlogn)算法)