压缩列表是列表键和哈希键的底层实现之一。
1.压缩列表的构成
1.1.ziplist结构如图
- zlbytes(4字节) : 表示压缩表的总长；
- zltail(4字节)：表示压缩列表表尾节点距离列表的起始地点有多少字节；
- zllen(2字节)：表示压缩列表包含的节点数量(当值小于uint16_max 65535时，节点的真实数量需要遍历整个压缩列表才能得出)；
- entryX(不定)：表示压缩列表的各个节点节点的长度由节点保存的内容决定；
- zlend(1字节)：特殊值0xFF(255),用于标记压缩列表的末尾。
//将zl定义到前四个字节的bytes成员 记录整个压缩列表的内存字节数 #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) //将zl定位到4字节到8字节的tail_offset成员 记录整个压缩列表的内存字节数 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) //将zl定位到8字节到10字节的length成员，记录着压缩列表的节点数量 #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2))) //压缩列表表头的大小10个字节 #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t)) //返回压缩列表首节点的地址 #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE) //返回压缩列表尾节点的地址 #define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) //返回end成员的地址 一个字节 #define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
1.2.创建一个空的压缩列表
//压缩列表总共有11个字节的固定长度 //创建并返回一个新的压缩列表 unsigned char *ziplistNew(void) { //ZIPLIST_HEADER_SIZE 是压缩列表的表头 1字节是末端的end大小 unsigned int bytes = ZIPLIST_HEADER_SIZE+1; unsigned char *zl = zmalloc(bytes); //为表头和表尾end成员分配空间 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); //将bytes成员初始化为bytes=11 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); //空列表的tail_offset成员为表头大小为10字节 ZIPLIST_LENGTH(zl) = 0; //字节数量为0 zl[bytes-1] = ZIP_END; //将表尾end成员设置默认的255 return zl; }
2.压缩列表节点的构成
typedef struct zlentry { //prevrawlen 前驱节点的长度 //prevrawlensize 编码前驱节点的长度prevrawlen所需的字节大小 unsigned int prevrawlensize, prevrawlen; //len 当前节点值长度 //lensize 编码当前节点长度len所需的字节数 unsigned int lensize, len; //当前节点header的大小 = lensize + prevrawlensize unsigned int headersize; //当前节点的编码方式 unsigned char encoding; //指向当前节点的指针，以char *类型保存 unsigned char *p; } zlentry; //压缩列表节点信息的结构
压缩列表节点的定义是zlentry，但是实质上存储节点是利用了以下的结构
- previous_entry_length:记录前驱节点的长度；
- encoding：即记录当前节点的value成员的数据类型及长度；
- value：根据encoding来保存字节数组或者整数。
2.1 prevois_entry_length
记录前驱节点的长度，以字节为单位。长度可以是1字节或者5字节。
1>. 如果前一字节的长度小于254，那么previous_entry_length长度为1字节，
2>.如果前一字节的长度大于等于254，那么previous_entry_length长度为5字节，其中第一个字节是0XFE(254)，而之后的四个字节表示前一节点的长度。
2.2 encoding
记录了节点的content属性所保存数据的类型以及长度。
1.一字节、两字节或者五字节，值的最高位为00、01、10的字节数组编码，这种编码表示节点的content属性保存着字节数组，字节数组的长度由编码出掉最高两位之后的其他记录。
2.一字节长，值的最高位以11开头的是整数编码：这种编码表示节点的content属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他记录。
2.3 content
节点的content属性负责保存节点的值，节点值可以是一个节点数组或者整数，值的类型和长度由节点的encoding属性决定。
3.连锁更新
在压缩列表节点的结构里previous_entry_length是记录前一个节点的长度，如果前一个节点的长度小于254，那么previous_entry_length需要1个字节空间保存前驱节点的长度值，如果前一个节点的长度大于等于254，那么previous_entry_length需要5个节点空间保存前驱节点的长度值。
假设存在一种情况，压缩列表里面的节点长度都是小于254字节，e1～eN字节数都在250～253之间，这时有一个长度大于254字节的new节点，需要插入到e1前，插入之后由于e1节点的previoud_entry_length是一个字节的，不能保存new节点的字节长度，需要碎e1节点进行扩展，同理，e1扩展之后字节大小大于等于254，则e1的后继节点e2节点的previous_entry_length不能保存e1扩展知乎的字节长度，也需要对e2扩展，以此类推，之后的节点都需要扩展，所以连锁更新最坏的情况下需要对压缩列表执行N次空间重新分配操作，而每次空间分配操作的最坏的时间复杂度是O(n),所以连锁更新最坏的时间复杂度是O(N^2)。
如果e1～eN字节数都是大于254，此时有一个长度小于254的new节点需要插入到e1前，也会产生连锁更新，并且在删除节点也会有连锁更新。
连锁更新的代码如下：
//将列表zk的p指针针对的next节点进行移动 // static 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; //ZIP_END标识尾节点 while (p[0] != ZIP_END) { cur = zipEntry(p); rawlen = cur.headersize + cur.len; rawlensize = zipPrevEncodeLength(NULL,rawlen); //计算当前节点长度所需的字节数 /* Abort if there is no next entry. */ if (p[rawlen] == ZIP_END) break; next = zipEntry(p+rawlen); //获取p的next节点 /* Abort when "prevlen" has not changed. */ if (next.prevrawlen == rawlen) break; //如果next节点存储的前驱节点长度所需的字节大小 小于 前驱节点所需的字节大小 if (next.prevrawlensize < rawlensize) { /* The "prevlen" field of "next" needs more bytes to hold * the raw length of "cur". */ offset = p-zl; //p节点的偏移量 extra = rawlensize-next.prevrawlensize; //需要额外增长的字节大小 zl = ziplistResize(zl,curlen+extra); //resize 链表所需空间大小 p = zl+offset; /* Current pointer and offset for next element. */ np = p+rawlen; //next节点的新地址 noffset = np-zl; //next节点的偏移量 //调整列表zltail的大小 /* Update tail offset when next element is not the tail element. */ if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) { ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra); } /* Move the tail to the back. */ //更新 移动next节点除header的prevrawlensize之外的剩余list的内存 //从next节点的prev_entry_len字段之后的内存开始 到zlend之前的内容 memmove(np+rawlensize, np+next.prevrawlensize, curlen-noffset-next.prevrawlensize-1); //更新 将next节点的header以rawlen长度重新编码，更新prevrawlensize和prevrawlen //更新next节点的previous_entry_length字段为rawlen zipPrevEncodeLength(np,rawlen); /* Advance the cursor */ p += rawlen; curlen += extra; } else { if (next.prevrawlensize > rawlensize) { /* This would result in shrinking, which we want to avoid. * So, set "rawlen" in the available bytes. */ zipPrevEncodeLengthForceLarge(p+rawlen,rawlen); } else { zipPrevEncodeLength(p+rawlen,rawlen); } /* Stop here, as the raw length of "next" has not changed. */ break; } } return zl; }
是根据给定的zl节点，然后通过更新p节点针对的next节点进行移动。首先获取p节点的字节长度和长度，来和p的next节点保存的previous_entry_length比较大小，如果next.prevrawlensize < rawlensize，那么需要对next.prev_entry_len字段之后的内存开始,到zlend之前的内容，进行memmove,来为next节点记录其前驱节点获取到足够的字节大小。
4.删除节点
从ziplist中，p指向的节点开始，最多删除num个节点
//从p节点开始最多删除num个节点 static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) { unsigned int i, totlen, deleted = 0; size_t offset; int nextdiff = 0; zlentry first, tail; first = zipEntry(p); for (i = 0; p[0] != ZIP_END && i < num; i++) { p += zipRawEntryLength(p); //需要删除的总字节数 deleted++; //需要删除的节点数 } totlen = p-first.p; //需要删除的总字节数 if (totlen > 0) { if (p[0] != ZIP_END) { /* Storing `prevrawlen` in this entry may increase or decrease the * number of bytes required compare to the current `prevrawlen`. * There always is room to store this, because it was previously * stored by an entry that is now being deleted. */ nextdiff = zipPrevLenByteDiff(p,first.prevrawlen); p -= nextdiff; zipPrevEncodeLength(p,first.prevrawlen); /* Update offset for tail */ //更新zltail 表尾据压缩列表的起始地址的字节数 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen); /* 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. */ tail = zipEntry(p); if (p[tail.headersize+tail.len] != ZIP_END) { ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); } /* Move tail to the front of the ziplist */ //移动p节点到zlend节点至first.p memmove(first.p,p, intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1); } else { /* The entire tail was deleted. No need to move memory. */ //p节点之后的所有元素都删除了 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe((first.p-zl)-first.prevrawlen); } * Resize and update length */ offset = first.p-zl; zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff); ZIPLIST_INCR_LENGTH(zl,-deleted); p = zl+offset; /* When nextdiff != 0, the raw length of the next entry has changed, so * we need to cascade the update throughout the ziplist */ //表示p节点的prev_raw_len_size需要扩容或者缩容 需要连锁更新 if (nextdiff != 0) zl = __ziplistCascadeUpdate(zl,p); } return zl; }
删除节点，需要知道要删除的字节长度，和节点数，需要处理的是如果删除完之后的后续节点不是zlend，则要更新p节点的prevrawlen,并且更新zltail的长度。
5.插入节点
插入到p所指向的节点
/* Insert item at "p". */ //插入到p所指向的节点 static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { 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; /* 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. */ //获取p的前继节点的长度prevlen if (p[0] != ZIP_END) { ZIP_DECODE_PREVLEN(p, prevlensize, prevlen); } else { unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl); if (ptail[0] != ZIP_END) { prevlen = zipRawEntryLength(ptail); } } /* See if the entry can be encoded */ //计算s节点的value encoding if (zipTryEncoding(s,slen,&value,&encoding)) { /* 'encoding' is set to the appropriate integer encoding */ reqlen = zipIntSize(encoding); } else { /* 'encoding' is untouched, however zipEncodeLength will use the * string length to figure out how to encode it. */ reqlen = slen; } /* We need space for both the length of the previous entry and * the length of the payload. */ //获取新节点的总长度 reqlen += zipPrevEncodeLength(NULL,prevlen); reqlen += zipEncodeLength(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. */ //c节点要插入到p节点的前面 计算p的prev_entry_len 和要插入的s节点的节点长度的差值 nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0; /* Store offset because a realloc may change the address of zl. */ offset = p-zl; zl = ziplistResize(zl,curlen+reqlen+nextdiff); p = zl+offset; /* Apply memory move when necessary and update tail offset. */ if (p[0] != ZIP_END) { /* Subtract one because of the ZIP_END bytes */ //p+reqlen表示p节点的新地址 nextdiff表示前继节点是否需要增大或者减少 //curlen-offset-1+nextdiff 表示移动长度 memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); /* Encode this entry's raw length in the next entry. */ //更新移动之后的p节点的prev_raw_length zipPrevEncodeLength(p+reqlen,reqlen); /* Update offset for tail */ //更新 zltail 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. */ tail = zipEntry(p+reqlen); if (p[reqlen+tail.headersize+tail.len] != ZIP_END) { ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); } } else { /* This element will be the new tail. */ ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl); } /* When nextdiff != 0, the raw length of the next entry has changed, so * we need to cascade the update throughout the ziplist */ if (nextdiff != 0) { offset = p-zl; zl = __ziplistCascadeUpdate(zl,p+reqlen); p = zl+offset; } /* Write the entry */ p += zipPrevEncodeLength(p,prevlen); p += zipEncodeLength(p,encoding,slen); if (ZIP_IS_STR(encoding)) { memcpy(p,s,slen); } else { zipSaveInteger(p,value,encoding); } ZIPLIST_INCR_LENGTH(zl,1); return zl; }