深入浅出Redis之ziplist

Ziplist是Redis中为了节约内存空间而实现的顺序性数据结构,通过一系列特殊编码,将数据与其编码信息存储在连续内存中,一个ziplist可以包含多个节点,每个节点可存储一个字节数组或一个整数值,其中对于节点值类型存储还采用了变长的编码方式。具体实现在ziplist.c和ziplist.h文件中。

Redis3.2版本前,ziplist与adlist作为列表对象的底层实现,而3.2后列表对象的底层实现改为quciklist,而ziplist则在quicklist中被应用,除了quicklist,ziplist还被用于zset的底层实现。

数据结构

列表构成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
#define ZIP_END 255

unsigned char *ziplistNew(void) {
/* 内存申请 */
unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
unsigned char *zl = zmalloc(bytes);
/* 默认值赋值 */
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
ZIPLIST_LENGTH(zl) = 0;
zl[bytes-1] = ZIP_END;
return zl;
}

通过初始化函数ziplistNew,可知压缩列表本质上是一个字节数组。初始化ziplist过程,一共申请了11字节的内存空间,其中包括两个uint32_t,一个uint16_t,一个uint8_t。初始化后压缩列表内部内存分布如下

组成部分含义:

  • zlbytes,表示整个压缩列表占用字节数,包括其自身4字节
  • zltail,表示到最后一位节点的偏移量,从而能O(1)复杂度获取末尾节点
  • zllen,表示压缩列表中节点个数。
  • entry,压缩列表中的每个节点,其中节点长度由保存内容定义
  • zlend,用于标记压缩列表结尾,使用特殊值255

其中,因为zllen只有两个字节,当压缩列表中节点数大于65534(2^16 - 2)时,都记为65535,而节点的真实数量需要遍历整个压缩列表,此时获取元素个数的时间复杂度从O(1)上升为O(n)。

列表节点构成

列表节点entry,其中逻辑结构如下:

1
<prevlen> <encoding> <content>

prevlen

prevlen表示前节点的节点长度,方便反向遍历。根据前一个节点的长度,分为两种情况:

  • 前节点长度小于254时,占用1字节,用来表示前节点长度
  • 前节点长度大于等于254时,占用5字节,其中第1个字节为特殊值0xFE(254),后面3字节用来表示实际长度

如下源码所示,判断节点的第1个字节,如果其小于254,则该值为前节点长度,否则后4字节的值,为前节点长度。

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

/* prevlen内存占用字节数 */
#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \
if ((ptr)[0] < ZIP_BIG_PREVLEN) { \
(prevlensize) = 1; \
} else { \
(prevlensize) = 5; \
} \
} while(0);

/* 前节点内存占用 */
#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \
ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \
if ((prevlensize) == 1) { \
(prevlen) = (ptr)[0]; \
} else if ((prevlensize) == 5) { \
assert(sizeof((prevlen)) == 4); \
memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \
memrev32ifbe(&prevlen); \
} \
} while(0);

content

节点的content负责保存节点的值,节点值可以是一个字节数组或者整数,值得类型和长度由节点的encoding属性决定

encoding

encoding表示当前节点的数据类型以及长度,其中整数节点,encoding均为1字节,而字符串根据长度不同,可能为1,2,5字节。具体的encoding值与数据类型对照表如下

字节值 占用字节 数据长度 特别说明
11000000 1 int16_t类型的整数
11010000 1 int32_t类型的整数
11100000 1 int64_t类型的整数
11110000 1 24位有符号整数
11111110 1 8位有符号整数
1111xxxx 1 0-12的无符号整数 数据存储在encoding部分的后4位,使用0001-1101表示0-12
00xxxxxx 1 <=6bits的字节数组 前两位表示类型,后6位为数据长度
01xxxxxx+<1 bytes> 2 <=14bits的字节数组 前两位表示类型,后14位为数据长度
10000000+<4 bytes> 5 <=32bits的字节数组 前两位表示类型,接着6位留空,后32位为数据长度

zlentry

因为压缩列表本质只是字节数组,为了方便操作,redis还定义了zlentry结构体,操作时,将每个节点包含信息按照一定规则写入zlentry中。

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

/* 将包含节点信息的字节数组属性 写入zlentry结构体中 */
void zipEntry(unsigned char *p, zlentry *e) {

ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
e->headersize = e->prevrawlensize + e->lensize;
e->p = p;
}

连锁更新

每个节点会存在prevlen属性,用来记录前置节点的长度,根据前置节点长度还分为两种情况,当长度大于等于254时,占用空间会从1字节扩大到5字节。所谓连锁更新,就是多个长度处于250字节~253字节之间的连续节点,当一个节点更新后,导致下一个节点prevlen由1字节变为5字节,而又导致下下一个节点prevle属性值增大,产生连锁反应。因为连锁更新在最坏情况下需要对压缩列表执行N次空间预分配,而每次空间预分配的最坏复杂度为O(n),所以连锁更新的最坏复杂度为O(n^2)。不过,虽然连锁更新的复杂度高,但出现的几率较低,需要多个特殊长度的节点,所以插入删除命令的平均复杂度均为O(n),最坏复杂度为O(n^2)。
以下是连锁更新的部分源码:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
size_t offset, noffset, extra;
unsigned char *np;
zlentry cur, next;

/* 是否到末尾 */
while (p[0] != ZIP_END) {
/* 解析当前节点信息 */
zipEntry(p, &cur);
/* 当前节点长度 */
rawlen = cur.headersize + cur.len;
/* 当前节点长度信息需要的长度 */
rawlensize = zipStorePrevEntryLength(NULL,rawlen);

/* 列表末尾 */
if (p[rawlen] == ZIP_END) break;
/* 解析下一个节点信息 */
zipEntry(p+rawlen, &next);

/* 下一个节点prevlen未发生更新 */
if (next.prevrawlen == rawlen) break;

/* prevlen发生更新 */
if (next.prevrawlensize < rawlensize) {
/* 当前节点与ziplist的偏移量 */
offset = p-zl;
/* 重新更大的内存空间 */
extra = rawlensize-next.prevrawlensize;
zl = ziplistResize(zl,curlen+extra);
/* p新内存地址 */
p = zl+offset;

/* 下一个节点 */
np = p+rawlen;
noffset = np-zl;

/* 如果下一个节点还不是末尾节点,则更新ziplist的zltail属性*/
if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
}

/* 内存向后移动 */
memmove(np+rawlensize,
np+next.prevrawlensize,
curlen-noffset-next.prevrawlensize-1);
/* 记录新的prevlen */
zipStorePrevEntryLength(np,rawlen);

/* 向下一个节点移动 */
p += rawlen;
curlen += extra;
} else {
/* 如果下一个节点原本的prevlen字段可以容纳新节点长度信息,则直接写入 */
if (next.prevrawlensize > rawlensize) {
zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
} else {
zipStorePrevEntryLength(p+rawlen,rawlen);
}

/* 更新结束,退出遍历 */
break;
}
}
return zl;
}

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

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

小结

ziplist是Redis为了节省内存而自定义的一种特殊编码的顺序性数据结构,与双端链表adlist相比,具有以下特点:

  • 整个ziplist存在一个连续内存中
  • 通过固定内存偏移量获取头节点,保留与尾节点的偏移量zltail,而不像双端链表存储头尾节点
  • 每个节点保留前置节点的长度,从而实现反向遍历,而不像双端链表存储前置节点指针
  • 每个节点采用变长的编码方式,存储字符串或整数值
  • 在特定条件下,ziplist会发生连锁更新,导致增删操作时间复杂度由O(n)变为O(n^2)

参考