redis数据结构(三) 列表对象

前面说到,列表对象在3.2版本之前是由压缩列表(ziplist)或者双端链表(linkedlist)来作为底层数据结构的,而在3.2版本开始之后,双端链表被废弃,快速列表(quicklist)取而代之(甚至连源码中的linkedlist相关的文件也没了)。现在quicklist是list对象的默认数据结构了。

在本篇文章中,让我们一起探究一下Redis中的列表对象吧。

linkedlist的优缺点

虽然说linkedlist已经没了,但是知道linkedlist优缺点可以更好的帮助我们理解为什么要用quicklist来代替它。

在早期的设计中,当列表对象中元素的长度比较小(小于等于64)或者数量比较少(小于等于512)的时候,采用ziplist来存储,当列表对象中的元素长度超过一定值(超过64)或者数量超过一定值(超过512)的时候,采用linkedlist来存储。

这是因为ziplist是存储在一段连续的内存上,所以存储效率高。但是不利于修改操作,插入和删除都需要频繁的申请和释放内存。当list长度很长时,每一次realloc都会导致大批量的数据拷贝。

而linkedlist便于在表的两端进行push和pop操作,在插入节点上复杂度很低,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表的各个节点时单独的内存块,地址不连续,节点多了容易产生内存碎片。

ziplist探究

ziplist是一种为节约空间而实现的线形数据结构。那么它究竟是如何节省内存的呢?

假设现在有两个元素,以单向链表为例的话,每个元素都有一个向后的指针,在64位机器下每个指针8字节,即链表结构所占空间16字节,更不要说保存两个方向的linkedlist了。此时,链表中的元素,无论是整数还是字符,都只占4个字节(int类型)或者1个字节(char类型)。链表结构空间是数据的好几倍。

而压缩列表的列表空间已经确定好了,只占11个字节。下面我们一起看看源码。

压缩列表结构

在ziplist.c的注释中有写到,ziplist的结构如下:

 * ZIPLIST OVERALL LAYOUT
 * ======================
 *
 * The general layout of the ziplist is as follows:
 *
 * <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

如下代码创建一个空的ziplist:

#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
#define ZIP_END 255         /* Special "end of ziplist" entry. */

/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
    // 分配11个字节的空间
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    // 总字节长度,赋给zlbytes
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    // 尾部节点字节距离,赋给zltail。是列表实体节点的尾部,因为一开始为0个节点。
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    // 列表实体节点个数,赋给zllen
    ZIPLIST_LENGTH(zl) = 0;
    // 255复制给zlend
    zl[bytes-1] = ZIP_END;
    return zl;
}

压缩列表由总字节长度(4字节),尾节点偏移量(4字节),节点数量(2字节),节点以及值为255的特殊结束符(1字节)组成,通过列表的开始地址向后偏移尾节点偏移量个字节,可以以O(1)时间复杂度获取尾节点信息。

压缩列表自身的信息只占用了11个字节,而链表光是头指针和尾指针存储就需要16个字节,所以针对数据量少的情况(节点少且节点小)采用压缩列表会比较划算。

intrev32ifbe函数是大小端转换函数

同时注释中有example:

 *  [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
 *        |             |          |       |       |     |
 *     zlbytes        zltail    entries   "2"     "5"   end

zlbytes = 15
zltail = 12
entries = 2

压缩列表节点

同样是注释上有写:

 * ZIPLIST ENTRIES
 * ===============
 *
 * ...
 *
 * So a complete entry is stored like this:
 *
 * <prevlen> <encoding> <entry-data>
 *
 * Sometimes the encoding represents the entry itself, like for small integers
 * as we'll see later. In such a case the <entry-data> part is missing, and we
 * could have just:
 *
 * <prevlen> <encoding>

也就是说,一般zlentry包括前节点的长度prevlen,编码encoding以及实体数据entry-data。

那么我们看看源码:

/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. */
typedef struct zlentry {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;

大概就是这个样子:

其中prevrawlensizeprevrawlen的区别在于,prevrawlensize指的是编码prevrawlen需要多少个字节。这样,当我们访问前一个节点的时候,直接读前面的prevrawlensize个字节就行了。

encoding为当前节点的编码格式,编码格式有如下:

#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
#define ZIP_INT_16B (0xc0 | 0<<4)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
#define ZIP_INT_24B (0xc0 | 3<<4)
#define ZIP_INT_8B 0xfe

主要也就是搭配上面的prevrawlensizelensize使用

*p指向当前节点的指针。然而并没有使用这个结构体来存储数据节点中的结构,因为如果存储小整型或者短字符串就造成了不必要的内存浪费。

连锁更新问题

假设有以下压缩列表,且e1 ~ eN的长度都介于250字节到253字节之间:

<zlbytes> <zltail> <zllen> <e1> <e2> ... <eN> <zlend>

当我们在e1前面插入一个长度大于254字节的新节点时:

<zlbytes> <zltail> <zllen> <eNew> <e1> <e2> ... <eN> <zlend>

e1的prevrawlensize参数要改成5个字节,且第一个字节的值为254。这是就需要扩展e1的内存,从而导致e2,e3···eN都要扩展,这就叫做连锁更新问题。

因为每次空间重分配的最坏复杂度为O(N),所以连锁更新的最坏复杂度为O(2)。

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;

其中的每一个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;

这里要注意的是,quicklistNode封装了ziplist,有一个zl指针。因此quicklist实际上是将双端链表和压缩列表结合起来了。

列表对象

默认就是用的quicklist数据结构了。

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号