redis之list源码分析

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_lengthentry_encodingvalue

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