前沿
在上一篇中，我们着重分析了dict字典的底层数据结构；本篇学习压缩列表，这是一种神奇的数据类型，其底层的数据结构相当简单，就是一个字符数组
ziplist简述
-
ziplist本质就是一个字节数组，是为了节约内存而设计的一种线性数据结构，可以包含任意多个元素，每个元素可以是一个字节数组或一个整数
-
redis的有序集合、哈希以及列表内数据较少时都直接或间接使用压缩列表作为其底层数据；
ziplist结构
| zlbytes | zltail | zllen | zlend |
|---|---|---|---|
| 4 bytes | 4 bytes | 2 bytes | 1 bytes |
| ziplist内存字节总数 | tail entry距离ziplist起始点字节数 | total entry nums | 0xff |
entry的结构
| PrevEntryLength | encoding | content |
|---|---|---|
| 5/1bytes | 5bytes | max 16384bytes |
| 用来从后往前遍历list | 当前节点content长度，及使用的编码 | max 16384bytes |
-
prevEntryLength(前一个元素的字节长度): 占1/5字节，当元素content长度<254时，用1个字节表示；当>254时，用5个字节表示，第一自己为0xFE,后面4字节才真正表示元素长度；
-
encoding(当前元素编码、数据长度)：由于content内容可以为字节数组、整数；前两个byte表示是字符数组还是整数，后面的bytes表示长度；通过下面表格来说明如何解析encoding
| encoding编码 | encoding长度 | content类型 |
|---|---|---|
| 00xxxxxx(6bits表示content长度) | 1byte | 最大长度63的字节数组 |
| 01xxxxxx xxxxxxxx(6+8bits表示content长度) | 2bytes | 最大长度2^14-1的字节数组 |
| 10__ 4bytes(4bytes表示content长度) | 5bytes | 最大长度2^32-1的字节数组 |
| 1100 0000 | 1byte | int16整数 |
| 1101 0000 | 1byte | int32整数 |
| 1110 0000 | 1byte | int64整数 |
| 1111 0000 | 1byte | 24bits整数 |
| 1111 1110 | 1byte | 8bites整数 |
| 1111 __ | 1byte | 没有content字段 |
ziplist一些特性
-
ziplist是 redis 为了节省内存，提升存储效率自定义的一种紧凑的数据结构
-
ziplist保存着尾节点的偏移量，可以方便的拿到头尾节点
-
每一个entry都保存着前一个entry的长度，可以很方便的从尾遍历
-
每个entry中都可以保存一个字节数组或整数，不同类型和大小的数据有不同的编码方式
-
添加和删除节点可能会引发连锁更新，极端情况下会更新整个ziplist，但是概率很小
代码分析
ziplistNew
/* 创建一个空的ziplist，size=11为管理空间
* 0->4: zlbytes，压缩列表占用的内存字节总数
* 5->8: zltail，压缩列表表尾节点距离压缩列表起始地址字节数，空表的话则为10(4+4+2)
* 9->10: zllen，压缩列表节点数，当节点数大于65535时，则需要遍历全表计算真实长度
* 11：zlend，0xff，表尾标志位
*/
unsigned char *ziplistNew(void) {
unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
unsigned char *zl = zmalloc(bytes);
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
/* 初始化zltail长度为10 */
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
ZIPLIST_LENGTH(zl) = 0;/* 初始化zllen长度为0 */
zl[bytes-1] = ZIP_END;/* 初始化zlend为0xff */
return zl;
}
__ziplistInsert
/* 在初始化ziplist后，可以往里添加数据，主要是两种方法(push, insert)
* push操作只能在list头、尾插入新节点; 不管是push、insert最终底层函数是一致的
*/
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
unsigned char *p;
/* ZIPLIST_ENTRY_END:通过zlbytes, 获得zlend指针
* ZIPLIST_ENTRY_HEAD:偏移head长度，获得第一个entry起始指针
*/
p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
return __ziplistInsert(zl,p,s,slen);
}
/* 插入节点的最终实现函数
* 1. 计算prevlen，即要插入位置上一个节点的内存总长度prevlen
* 2. 尝试对新节点进行整数编码encoding，关键是string2ll是否成功；因为整数编码更节省内存;并计算content长度
* 3. reqlen: 有了prelen，encoding, content后就可以计算本entry所需的总内存大小
* 4. 如果插入点不在尾部则需要更新其下一个节点的prevlen；这时可能会要求额外的内存空间
* 5. 计算出所有需要增加的内存后，通过realloc+memmove进行内存扩张，内存剪贴
* 6. 完事后还要进行连锁更新
* 7. 最后通过zipStorePrevEntryLength，zipStoreEntryEncoding更新新entry的PrevEntryLength|encoding,并将数据拷贝到content中
* 8. 更新ziplist的total entry num + 1
*/
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;/* curlen为当前ziplist总长度 */
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789; /* initialized to avoid warning. Using a value
that is easy to see if for some reason
we use it uninitialized. */
zlentry tail;
/* Find out prevlen for the entry that is inserted. */
if (p[0] != ZIP_END) {
/* 如果不是在list tail插入节点；则可以通过p指针指向的element，获取目前的prevlen */
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
/* 如果p指向的zlend，则需要先获得last entry指针，再获取目前的prevlen */
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);/* 通过zltail，获得尾节点的起始点指针 */
if (ptail[0] != ZIP_END) {/* 如果entry非null */
prevlen = zipRawEntryLength(ptail);/* 计算最后一个entry占内存大小，包括管理内存 */
}
}
/* 尝试对value进行整数编码
* 关键方法是string2ll: 尝试将s转成longlong类型，如果不成功，则不能进行整数编码
*/
if (zipTryEncoding(s,slen,&value,&encoding)) {/* 尝试对value进行整数编码 */
/* 'encoding' is set to the appropriate integer encoding */
reqlen = zipIntSize(encoding);/* 计算数据长度 */
} else {
/* 'encoding' is untouched, however zipStoreEntryEncoding will use the
* string length to figure out how to encode it. */
reqlen = slen;/* 如果无法转成整型，则slen即为content长度 */
}
/* We need space for both the length of the previous entry and
* the length of the payload. */
reqlen += zipStorePrevEntryLength(NULL,prevlen);/* 获取新节点pre编码长度 */
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;
/* 如果不在尾部插入，需要判断当前prelen是否能表达新element占内存的大小 */
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {//当前节点prelen == 5 or 新element长度只需要1个字节表达
nextdiff = 0;
forcelarge = 1;
}
/* 记录偏移量，realloc可能会改变ziplist地址. */
offset = p-zl;
/* 使用realloc增加ziplist内存；并修改相应的管理数据. */
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
p = zl+offset;
/* Apply memory move when necessary and update tail offset. */
if (p[0] != ZIP_END) {
/* 批量剪贴ziplist数据；相当于将原来的p指针后的数据整体后移了 reqlen 长度
* 当然，要预留出nextdiff长度，补齐原来prelen长度不够
*/
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* 当下一个节点的prelen空间已经够用时，不需要压缩，防止连锁更新. */
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else // 将reqlen保存到后一个节点中
zipStorePrevEntryLength(p+reqlen,reqlen);
/* 更新尾部节点的地址 */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
zipEntry(p+reqlen, &tail);
/* 如果下一个节点的prelen扩展了, 则zlend长度需要加上nextdiff */
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
/* 如果新节点是加在ziplist尾部，则处理简单很多, 不需要考虑next entry的prevlen. */
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
/* 连锁更新：从next entry开始 */
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;/* 连锁更新完成后，重新将p指针定位到插入点 */
}
/* 更新新加入entry的PrevEntryLength */
p += zipStorePrevEntryLength(p,prevlen);
/* 更新新加入entry的encoding */
p += zipStoreEntryEncoding(p,encoding,slen);
/* 更新新加入entry的content */
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
zipSaveInteger(p,value,encoding);
}
/* ziplist total entry num +1 */
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}
__ziplistCascadeUpdate
连锁更新
-
由于每个节点都保存着前一个节点的长度，并且 redis 出于节省内存的考量，针对254这个分界点上下将prelen的长度分别设为1和5字节
-
当我们插入一个节点时，后一个节点的prelen可能就需要进行扩展，由于prelen的扩展，导致再后一个节点也需要进行扩展
-
在最极端情况下会将整个ziplist都进行更新
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);/* 获取当前节点，填充结构体zlentry */
rawlen = cur.headersize + cur.len;/* 获取本entry占内存总大小 */
rawlensize = zipStorePrevEntryLength(NULL,rawlen);/* 计算prevlen大小，1 or 5 */
/* 如果下一个节点为zend，则结束. */
if (p[rawlen] == ZIP_END) break;
zipEntry(p+rawlen, &next);/* 获取下一个节点储存在next中. */
/* 如果next.prevrawlen == rawlen，则连锁更新中断. */
if (next.prevrawlen == rawlen) break;
if (next.prevrawlensize < rawlensize) {
/* 触发连锁更新：这种情况就需要扩张next的长度，增加4byte，用于储存上一节点的总长度. */
offset = p-zl;
extra = rawlensize-next.prevrawlensize;/* 需要增加的长度 */
zl = ziplistResize(zl,curlen+extra);
p = zl+offset;
/* Current pointer and offset for next element. */
np = p+rawlen;
noffset = np-zl;
/* 更新zltail. */
if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
}
/* np之后留出rawlensize，用于在next entry中保存本entry的总长度. */
memmove(np+rawlensize,
np+next.prevrawlensize,
curlen-noffset-next.prevrawlensize-1);
zipStorePrevEntryLength(np,rawlen);
/* Advance the cursor */
p += rawlen;
curlen += extra;
} else {
/* 当ziplist收缩可能会触发本路径. */
if (next.prevrawlensize > rawlensize) {
/* 当原有的prelensize大于当前所需时，不进行收缩直接赋值减少后续连锁更新的可能性 */
zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
} else {
/* next.prevrawlensize == rawlensize. */
zipStorePrevEntryLength(p+rawlen,rawlen);
}
/* 小于之前的size或者想等都不会引起连锁更新，直接结束. */
break;
}
}
return zl;
}
附录
zlentry结构体
/* 本结构体并不是zipentry在内存中的真实布局；仅仅是为了操作数据方便，通过zipentry生成的.
* PrevEntryLength|encoding|content
*/
typedef struct zlentry {
unsigned int prevrawlensize; /* 在本entry中保存previous entry length的内存大小： 1/5 */
unsigned int prevrawlen; /* PrevEntryLength. */
unsigned int lensize; /* 本entry encoding长度.*/
unsigned int len; /* 数据占内存大小,即content长度. */
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; /* 标识是整形、字符数组. */
unsigned char *p; /* 指向本entry的内存起始点. */
} zlentry;
一些重要的宏
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) // 获取ziplist的bytes指针
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) // 获取ziplist的tail指针
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2))) // 获取ziplist的len指针
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t)) // ziplist头大小
#define ZIPLIST_END_SIZE (sizeof(uint8_t)) // ziplist结束标志位大小
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE) // 获取第一个元素的指针
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) // 获取最后一个元素的指针
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1) // 获取结束标志位指针
#define ZIP_STR_06B (0 << 6) // 小于63字节字节数组
#define ZIP_STR_14B (1 << 6) // 小于2^14-1字节的字节数组
#define ZIP_STR_32B (2 << 6) // 小于2^32-1字节的字节数组
#define ZIP_INT_16B (0xc0 | 0<<4) // int16_t整数
#define ZIP_INT_32B (0xc0 | 1<<4) // int32_t整数
#define ZIP_INT_64B (0xc0 | 2<<4) // int64_t整数
#define ZIP_INT_24B (0xc0 | 3<<4) // 3个字节长度的整数
#define ZIP_INT_8B 0xfe // 1个字节长度的整数