0%

【Redis数据结构】ziplist的实现

ziplist(压缩列表) 和 listNode(双端链表) 共同组成了列表的底层结构 quicklist,同时也是 哈希、有序集合 在数据量较小时的底层实现, 可以看做是一个特殊的数组, 数组中的每一项的长度不固定

ziplist在内存中是一整块的连续内存, 所有节点在内存中是紧挨着的,因此不需要和双端链表一样保存前进指针和后退指针。

相对双端链表的优点:

  • 整块连续内存, 存储效率高
  • 不需要前进指针和后退指针,占用内存少

缺点:

  • 操作不方便,每次数据变动都会引发内存的分配和数据拷贝

ziplist 结构示意图:

ziplist结构图

属性 类型 长度 描述
zlbytes uint32_t 4字节 保存整个压缩列表的字节长度。因此压缩列表最多有 2^32 - 1 字节
zltail uint32_t 4字节 表示压缩列表表尾元素相对于压缩列表起始地址的偏移量
zllen uint16_t 2字节 表示压缩列表节点的数量
如果压缩列表的长度超过2^16-1则需要遍历整个压缩列表才能知道具体长度
entryX unsigned char * 未知 压缩列表节点
zlend uint8_t 1字节 表示压缩列表的结尾, 永远是 0xff

相关的宏定义

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
// 返回压缩列表的字节数
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))

// 返回压缩列表表尾相对的压缩列表起始地址的偏移量 (zl的地址 + 4字节 就是zltail的地址)
// 列表为空时最后一个节点为0xff, 非空时为0xff前一个节点
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

// 返回压缩列表的长度,如果遍历一遍才能确定长度则返回 UINT16_MAX
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

/* 返回 ZIPLIST 头部的长度: zlbytes(4字节) + zltail(4字节) + zllen(2字节) = 10 字节*/
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))

/* 返回 zllen 的长度 (1字节) */
#define ZIPLIST_END_SIZE (sizeof(uint8_t))

/* 返回第一个 ziplist 节点的指针 */
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)

/*
* 返回最后一个 ziplist 节点的指针
* intrev32ifbe函数为大小端转换函数,统一转换为小端存储。因为压缩列表的操作中涉及到的位运算很多,如果不统一的话会出现混乱。
*/
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

/* 返回ziplist表尾节点的指针
Return the pointer to the last byte of a ziplist, which is, the end of ziplist FF entry. */
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

ziplist节点的构成:

ziplist_entry结构

属性 字节数 说明
prevlen 1或5 存储前一个节点的长度, 1 < 前一个字节长度 < 254时, 为 1 字节, 否则为 5 字节
为5字节时第一字节为 0xFE, 剩下4字节存储真正的长度
如果长度大于65535, 需要遍历才能知道真正的长度
encoding 1/2/5 字节 记录了entry-data的类型和长度
entry-data 未知 节点真正的数据, encoding为小整数时 entry-data 可能不存在

encoding 的编码类型如下表:

编码 编码长度 保存的值
00pppppp 1 byte 高2位的00表示节点类型为0~63位的字节数组
低6位表示 entry-data 的真正长度
01pppppp qqqqqqqq 2 bytes 01表示类型是 长度 < 2^14 的字符数组长度
后14位保存正真的长度
10000000 qqqqqqqq rrrrrrrr ssssssss tttttttt 5 bytes 10表示类型是 长度 < 2^32 的字节数组
后32位保存真正的长度
11000000 1 bytes int16_t 类型的整数, 只后2字节为int16_t类型的整数
11010000 1 bytes int32_t 类型的整数
11100000 1 bytes int64_t 类型的整数
11110000 1 bytes 后3字节是24位整数, -2^24 ~ 2^23 - 1
11111110 1 bytes 8 位整数 -128 ~ 127
1111xxxx 1 bytes xxxx 在0001~1101之间, 表示 0~12 之间的整数, 拿到xxxx后还要减1才是真正表示的值
此类型没有 entry-data, 整数的值直接保存在低4位
11111111 1 bytes ziplist结尾字符

encoding 相关的宏定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
#define ZIP_END 255
#define ZIP_BIG_PREVLEN 254

#define ZIP_STR_MASK 0xc0
#define ZIP_INT_MASK 0x30
#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

压缩列表的创建于增删改查

创建一个空的 ziplist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
// 分配空间为头部大小 + 尾部大小(11字节)
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;
}

压缩列表插入新节点

插入新元素分为三步:

  1. 将元素内容编码
  2. 重新分配空间
  3. 复制数据
插入新节点用到的函数以及宏定义
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
/* 设置 prevlensize 变量为 ptr 指向的节点的 prevlen 属性的字节长度(编码前一节点所需的字节数) */
#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \
if ((ptr)[0] < ZIP_BIG_PREVLEN) { \
(prevlensize) = 1; \
} else { \
(prevlensize) = 5; \
} \
} while(0);

/* 设置 prevlensize 和 prevlen 变量的值
* prevlensize 值调用 ZIP_DECODE_PREVLENSIZE 函数
* 设置 prevlen 变量为 ptr 的前一个节点的总字节数 (保存在ptr指向的地址上, 直接拷贝prevlensize长度的内存)
*/
#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);

/*返回保存 encoding 编码的整数值所需的字节数量 */
unsigned int zipIntSize(unsigned char encoding) {
switch(encoding) {
case ZIP_INT_8B: return 1;
case ZIP_INT_16B: return 2;
case ZIP_INT_24B: return 3;
case ZIP_INT_32B: return 4;
case ZIP_INT_64B: return 8;
}
if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
return 0; /* 4 bit immediate */
panic("Invalid integer encoding 0x%02X", encoding);
return 0;
}

/* 从 ptr 中取出节点值的编码类型,并将它保存到 encoding 变量中。
* ZIP_STR_MASK = 11000000,
* (encoding) < ZIP_STR_MASK 说明是字符串类型, 否则就是整数类型
*/
#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \
(encoding) = (ptr[0]); \
if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
} while(0)

/* 解码 ptr 指向的节点, 取出列表节点的相关信息,并将它们保存在以下变量中:
* - encoding 保存节点值的编码类型。
* - lensize 保存编码节点长度所需的字节数 (encoding 的字节数)
* - len 保存节点的长度 (entry-data 的字节数, 字符串保存在 encoding 里面直接取, 整数根据类型也是直接获取)
*/
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \
ZIP_ENTRY_ENCODING((ptr), (encoding)); \
if ((encoding) < ZIP_STR_MASK) { \
if ((encoding) == ZIP_STR_06B) { \
(lensize) = 1; \
(len) = (ptr)[0] & 0x3f; \
} else if ((encoding) == ZIP_STR_14B) { \
(lensize) = 2; \
(len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \
} else if ((encoding) == ZIP_STR_32B) { \
(lensize) = 5; \
(len) = ((ptr)[1] << 24) | \
((ptr)[2] << 16) | \
((ptr)[3] << 8) | \
((ptr)[4]); \
} else { \
panic("Invalid string encoding 0x%02X", (encoding)); \
} \
} else { \
(lensize) = 1; \
(len) = zipIntSize(encoding); \
} \
} while(0);

/* 返回指针 p 指向的节点的字节总数 */
unsigned int zipRawEntryLength(unsigned char *p) {
unsigned int prevlensize, encoding, lensize, len;
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
return prevlensize + lensize + len;
}

/* 检查 entry 中指向的字符串能否被编码为整数。
*
* 如果可以的话,
* 将编码后的整数保存在指针 v 的值中,并将编码的方式保存在指针 encoding 的值中。
*
* 注意,这里的 entry 和前面代表节点的 entry 不是一个意思。 */
int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
long long value;

if (entrylen >= 32 || entrylen == 0) return 0;
if (string2ll((char*)entry,entrylen,&value)) {
/* Great, the string can be encoded. Check what's the smallest
* of our encoding types that can hold this value. */
if (value >= 0 && value <= 12) {
*encoding = ZIP_INT_IMM_MIN+value;
} else if (value >= INT8_MIN && value <= INT8_MAX) {
*encoding = ZIP_INT_8B;
} else if (value >= INT16_MIN && value <= INT16_MAX) {
*encoding = ZIP_INT_16B;
} else if (value >= INT24_MIN && value <= INT24_MAX) {
*encoding = ZIP_INT_24B;
} else if (value >= INT32_MIN && value <= INT32_MAX) {
*encoding = ZIP_INT_32B;
} else {
*encoding = ZIP_INT_64B;
}
*v = value;
return 1;
}
return 0;
}

/* 对前置节点的的长度进行编码, 并写入 p 指向的地址. 编码字节长度为 5 时才会调用这个函数 */
int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) {
if (p != NULL) {
// p 指向的地址设置为 0xfe
p[0] = ZIP_BIG_PREVLEN;

// 将len的内存拷贝到 p + 1
memcpy(p+1,&len,sizeof(len));
memrev32ifbe(p+1);
}
return 1+sizeof(len);
}

/* 对前置节点的的长度进行编码, 并写入 p 指向的地址, 返回编码 len 所需要的字节长度 */
unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
if (p == NULL) {
// p 为NULL, 直接返回编码 len 所需要的字节长度
return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(len)+1;
} else {
// p 不为null, 将长度len编码后写入 p 指向的地址, 并返回编码需要的长度
if (len < ZIP_BIG_PREVLEN) {
p[0] = len;
return 1;
} else {
return zipStorePrevEntryLengthLarge(p,len);
}
}
}

/* 编码len所需要的长度 与 编码p的前置节点所需要的字节数之差
* @param unsigned char *p: 节点 p 的指针
* @param unsigned int len: 新节点的总字节长度
*/
int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
unsigned int prevlensize;
// prevlensize 为编码当前节点所需要的字节数
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
return zipStorePrevEntryLength(NULL, len) - prevlensize;
}

/* 压缩列表节点结构体, 取数据方便 */
typedef struct zlentry {
unsigned int prevrawlensize; /* 前一节点的字节长度 */
unsigned int prevrawlen; /* 前一节点的长度 */
unsigned int lensize; /* 节点的编码长度 */
unsigned int len; /* 节点的长度 */
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; /* 节点值所使用的编码类型, ZIP_STR_* or ZIP_INT_* */
unsigned char *p; /* 指向节点的指针 */
} zlentry;

/* 把 p 指向的压缩列表的信息保存到 结构体e 中 */
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;
}


/* 重新分配 ziplist 的内存 */
unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
zl = zrealloc(zl,len);

// 设置压缩列表总字节长度
ZIPLIST_BYTES(zl) = intrev32ifbe(len);

// 将最后的字节设置为 0xff
zl[len-1] = ZIP_END;

// 返回压缩列表头指针
return zl;
}
插入新节点函数
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* Insert item at "p". 
* @param unsigned char *zl: ziplist首地址
* @param unsigned char *p: 要插入的位置, 如插入到头结点就是ZIPLIST_ENTRY_HEAD(zl), 尾结点是ZIPLIST_ENTRY_END(zl)
* @param unsigned char *s: 要插入的字符串/整数
* @param unsigned int slen: 要插入的字符串长度
* @return 压缩列表的指针
*/
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
// curlen: 当前压缩列表的字节长度, reqlen: 插入新节点需要的字节数
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789; /*value保存整数,只有在整数编码时采用到, 使用一个很容易识别的数字来初始化value, 避免编译器的警告 */
zlentry tail;

/* Find out prevlen for the entry that is inserted. */
if (p[0] != ZIP_END) {
// 要插入的不是表尾节点 使用 prevlensize 用于在宏定义中保存前一节点 prevlen 属性的字节数(1或5), prevlen 保存前一节点的长度
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
// 1. 如果 ptail 也指向 ZIP_END ,那么 ziplist 为空, prevlen 还是0
// 2. 如果 ptail 不是指向 0xff, 那么就不为空, 需要取前一个节点的长度
if (ptail[0] != ZIP_END) {
// 计算前一节点的长度保存到 prevlen
// 最后的 0xff 没有 prevlen 的属性, 需要通过 zipRawEntryLength 函数计算获取到
prevlen = zipRawEntryLength(ptail);
}
}

// 尝试看能否将输入字符串转换为整数
if (zipTryEncoding(s,slen,&value,&encoding)) {
reqlen = zipIntSize(encoding);
} else {
// 没有成功编码成整数, reqlen 的初始长度就是字符串长度
reqlen = slen;
}

// reqlen 加上存储前一节点的长度以及存储当前节点的编码所需要的字节大小(新节点头部)
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

/* When the insert position is not equal to the tail, we need to
* make sure that the next entry can hold this entry's length in
* its prevlen field. */
int forcelarge = 0;

// p 保存的是前置节点的长度, 插入新节点后p的前置节点就变成了新节点
// nextdiff 保存的 编码新节点需要的字节数 和 编码前置节点的所需要的 字节差
// eg: 新节点长度为1024字节, 需要使用5字节(0xfe0000000400)来保存, 原先的前置节点长度为64, 只用了1字节(0x40)保存, 这时候 nextdiff 就是4
// 同理如果长度由5字节变成了1字节, nextdiff就是-4
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;

// 改bug, 详细分析见:https://segmentfault.com/a/1190000018878466?utm_source=tag-newest
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}

// 记录要插入的地址相对于首指针的偏移量, 重新分配内存可能改变原来的 zl 的地址
offset = p-zl;

// 重新分配内存
zl = ziplistResize(zl,curlen+reqlen+nextdiff);

// p的位置重新记录
p = zl+offset;

/* 插入非表尾节点 */
if (p[0] != ZIP_END) {
// 原先的p节点之后的内存都往后挪, 腾出空间给要插入的节点
// 从 p-nextdiff 开始拷贝到 p+reqlen 的地址, eg:nextdiff 为4时表示需要扩容, 把该节点的前4个字节也一起拷贝过去, 之后再重新赋值为新节点长度编码
// 拷贝长度: curlen-offset-1+nextdiff, 这里不拷贝0xff, 所以需要 - 1, 0xff 是在内存重分配的时候在结尾添加的
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

/* 更新下一节点的 prevlen 属性*/
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);

// 更新尾节点偏移量
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);

// 将 下一节点的信息写入到 tail 结构体中
zipEntry(p+reqlen, &tail);

// 如果新节点的后面有多于一个节点
// 那么需要将 nextdiff 记录的字节数也计算到表尾偏移量中
// 这样才能让表尾偏移量正确对齐表尾节点 */
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
// 插入到表尾节点, 只需要更新尾结点偏移量
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}

/* nextdiff != 0, 下一节点的字节数发生了变化, 可能会触发连锁更新(cascade update, 级联更新) */
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}

// 更新节点的 prevlen 属性, 并把 指针p 移到节点的 encoding 属性上
p += zipStorePrevEntryLength(p,prevlen);

// 更新节点的编码, 指针 p 往后移到 entry-data 上
p += zipStoreEntryEncoding(p,encoding,slen);

if (ZIP_IS_STR(encoding)) {
// 编码是字符串, 拷贝内存
memcpy(p,s,slen);
} else {
// 保存整数
zipSaveInteger(p,value,encoding);
}

// 更新列表的节点数量计数器
ZIPLIST_INCR_LENGTH(zl,1);

return zl;
}

连锁更新:

insert, delete, merge 都可能会引发连锁更新

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
90
91
92
93
94
95
96
97
98
99
100
101
/* When an entry is inserted, we need to set the prevlen field of the next
* entry to equal the length of the inserted entry. It can occur that this
* length cannot be encoded in 1 byte and the next entry needs to be grow
* a bit larger to hold the 5-byte encoded prevlen. This can be done for free,
* because this only happens when an entry is already being inserted (which
* causes a realloc and memmove). However, encoding the prevlen may require
* that this entry is grown as well. This effect may cascade throughout
* the ziplist when there are consecutive entries with a size close to
* ZIP_BIG_PREVLEN, so we need to check that the prevlen can be encoded in
* every consecutive entry.
*
* Note that this effect can also happen in reverse, where the bytes required
* to encode the prevlen field can shrink. This effect is deliberately ignored,
* because it can cause a "flapping" effect where a chain prevlen fields is
* first grown and then shrunk again after consecutive inserts. Rather, the
* field is allowed to stay larger than necessary, because a large prevlen
* field implies the ziplist is holding large entries anyway.
*
* The pointer "p" points to the first entry that does NOT need to be
* updated, i.e. consecutive fields MAY need an update.
*
* @param unsigned char *zl: 压缩列表
* @param unsigned char *p: 插入/删除的节点的下一节点
*/
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) {
// p指向的节点信息存在结构体cur中
zipEntry(p, &cur);

// 节点的长度
rawlen = cur.headersize + cur.len;

// 存储rawlen需要的字节数
rawlensize = zipStorePrevEntryLength(NULL,rawlen);

// 没有下一节点跳出循环
if (p[rawlen] == ZIP_END) break;

// p的下一节点的信息存到结构体next中
zipEntry(p+rawlen, &next);

// p的长度 = 下一节点中存的长度 跳出循环
// 第一次循环肯定不会出现这种情况, 因为是p的长度发送的变化才会调连锁更新的函数, 第二轮及循环后面的循环就会出现这种情况了
// eg: 第一轮循环: p: 252->256 np: 246->250 第二轮循环: p指向np, 保存np的字节数与np的下一字节的prevlen属性值相同, 这里就跳出了循环
if (next.prevrawlen == rawlen) break;

if (next.prevrawlensize < rawlensize) {
/* 1字节 -> 5字节 的情况 */
offset = p-zl;

// 需要多出的内存, 用来给 next 节点扩容, 这里是4字节
extra = rawlensize-next.prevrawlensize;

// 给 zl 多分配 extra 字节的内存
zl = ziplistResize(zl,curlen+extra);

// 重新指回原来那个p相对于zl的位置
p = zl+offset;

// np: p的下一节点的指针
np = p+rawlen;
noffset = np-zl;

// 下一节点后面还有节点, 更新尾节点偏移量
if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
}

// 内存拷贝, 把np+1(从np节点的encoding开始)及后面的数据统统挪到np+5的位置, 相当于腾出5字节的空间用来保存节点p的长度
memmove(np+rawlensize, np+next.prevrawlensize, curlen-noffset-next.prevrawlensize-1);

// 设置np的 prevlen 属性
zipStorePrevEntryLength(np,rawlen);

// p指向np, 开始下一轮更新
p += rawlen;
curlen += extra;
} else {
if (next.prevrawlensize > rawlensize) {
/* 5 字节 -> 1字节的情况
* 为了避免扩展-缩小-扩展-缩小这样的情况反复出现(flapping,抖动)
* 这种情况不会缩容, 直接把p节点的长度写入下一节点的1~4节点中
* 比如p的长度由于前一节点长度变小从 256(0xfe00000100, 5字节) 变成了252, p的下一节点的prevlen属性不会是变成252,依然是用5字节存储(0xfe000000fc)
*/
zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
} else {
// 节点p的长度长度发送了变化, 但是np的pervlen属性的字节数能存的下(eg: p的长度由 100 -> 96),
zipStorePrevEntryLength(p+rawlen,rawlen);
}

// p的下一节点np的字节数没有发生变化, 不继续循环
break;
}
}
return zl;
}

参考链接: