redis之list源码分析

redis

list的数据结构

redis的list的结构为quicklist，并非简单的类似java的LinkedList链表或者ArrayList数组，而是将链表和数值结合的一种数据结构。

宏观上list是一个quicklist链表，通过双向指针前后连接，但是链表的每一个节点是一个ziplist字节数组，在字节数组上保存list的数据。默认配置下，每个ziplist最大为8K字节，在向满了的ziplist插入新数据时或拆分或新建ziplist来存放新数据。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;
    unsigned long len;
    int fill : 16;
    unsigned int compress : 16;
} quicklist;


typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;
    unsigned int count : 16;
    unsigned int encoding : 2;
    unsigned int container : 2;
    unsigned int recompress : 1;
    unsigned int attempted_compress : 1;
    unsigned int extra : 10;
} quicklistNode;


unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); // 4字节
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); // 4字节
    ZIPLIST_LENGTH(zl) = 0; // 2字节
    zl[bytes-1] = ZIP_END;
    return zl;
}

ziplist

ziplist是一个紧凑的数据结构，redis为了节省内存空间没有定义结构体而直接使用字节数值，减少了指针的空间大小。

ziplist的数据结构如下图所示，zlbytes记录了ziplist的字节数组长度；zltail记录了ziplist中最后一个节点距离起始位的偏移量，可以通过该值直接定位到ziplist的最后一个元素；zllen表示ziplist中的节点数量；zlend则为固定值0xff表示ziplist的结尾。

image

ziplist元素节点

ziplist的每个节点由3个部分组成：prev_entry_length、entry_encoding和value。

1
2
3
4
5
6
7
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
if (ZIP_IS_STR(encoding)) {
	memcpy(p,s,slen);
} else {
	zipSaveInteger(p,value,encoding);
}

prev_entry_length

prev_entry_length表示前一个节点的长度，且prev_entry_length本身的字节长度不固定：

  • 当前一个节点的长度小于254时：prev_entry_length占用1个字节长度，表示节点的字节长度；
  • 当前一个节点的长度大于等于254时：prev_entry_length占用5个字节长度，第一个字节固定值为0xfe，后四个字节表示字节的长度；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define ZIP_BIG_PREVLEN 254 
unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
    if (p == NULL) {
        return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(len)+1;
    } else {
        if (len < ZIP_BIG_PREVLEN) {
            p[0] = len;
            return 1;
        } else {
            return zipStorePrevEntryLengthLarge(p,len);
        }
    }
}

int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) {
    if (p != NULL) {
        p[0] = ZIP_BIG_PREVLEN;
        memcpy(p+1,&len,sizeof(len));
        memrev32ifbe(p+1);
    }
    return 1+sizeof(len);
}

entry_encoding

entry_encoding表示节点的编码格式，且entry_encoding本身的字节长度不固定：

  • value为整数值时占用1个字节；
  • value为字符串值时：
    • 如果字节长度小于等于63则占用1个字节；
    • 如果字节长度大于63且小于等于16383则占用2个字节；
    • 如果字节长度大于16383则占用5个字节；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
unsigned int zipStore
entry_encoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
    unsigned char len = 1, buf[5];

    if (ZIP_IS_STR(encoding)) { // 字符串值
        if (rawlen <= 0x3f) { // 63
            if (!p) return len;
            buf[0] = ZIP_STR_06B | rawlen;
        } else if (rawlen <= 0x3fff) {	// 16383
            len += 1;
            if (!p) return len;
            buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
            buf[1] = rawlen & 0xff;
        } else {
            len += 4;
            if (!p) return len;
            buf[0] = ZIP_STR_32B;
            buf[1] = (rawlen >> 24) & 0xff;
            buf[2] = (rawlen >> 16) & 0xff;
            buf[3] = (rawlen >> 8) & 0xff;
            buf[4] = rawlen & 0xff;
        }
    } else {	// 整数值
        if (!p) return len;
        buf[0] = encoding;
    }

    memcpy(p,buf,len);
    return len;
}

临界值

默认配置下，每个ziplist最大为8K字节，在向满了的ziplist插入新数据时或拆分或新建ziplist来存放新数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define OBJ_LIST_MAX_ZIPLIST_SIZE -2
lobj = createQuicklistObject();
// quicklist->fill = server.list_max_ziplist_size = -2
quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,
					server.list_compress_depth);

static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536};
// 判断ziplist是否能插入新节点
REDIS_STATIC int
_quicklistNodeSizeMeetsOptimizationRequirement(const size_t sz,
                                               const int fill) {
    if (fill >= 0)
        return 0;

    // 默认offset为1即ziplist的最大长度为8192字节
    size_t offset = (-fill) - 1;
    if (offset < (sizeof(optimization_level) / sizeof(*optimization_level))) {
        if (sz <= optimization_level[offset]) {
            return 1;
        } else {
            return 0;
        }
    } else {
        return 0;
    }
}
>