Redis源码、面试指南（2）内存编码数据结构（上）：https://developer.aliyun.com/article/1508225
节点细节
由上文节点定义代码可知，压缩节点信息可以分为三个部分：previous_entry_length，encoding，content，如下图：
现在就来详细看看这三个部分。
1.previous_entry_lentry:记录前一个节点的长度，1或5字节——前一节点小于254字节，那么就用1字节保存前一节点信息否则用五字节表示（第一字节设置为0xFE（254）后四字节为长度）。
当前节点指针和previous字段可以实现快速访问上一节点，从而实现列表节点回溯。
2.encoding字段：表示content所保存的数据类型及长度。可选1/2/5字节，分别表示字节数组或整形。详细编码可见下表：
字节数组编码如下：
| 编码 | 编码长度 | content 属性保存的值 |
| 00bbbbbb | 1 字节 | 长度小于等于 63 字节的字节数组。 |
| 01bbbbbb xxxxxxxx | 2 字节 | 长度小于等于 16383 字节的字节数组。 |
| 10______ aaaaaaaa bbbbbbbb cccccccc dddddddd | 5 字节 | 长度小于等于 4294967295 的字节数组。 |
整数编码如下：
| 编码 | 编码长度 | content 属性保存的值 |
| 11000000 | 1 字节 | int16_t 类型的整数。 |
| 11010000 | 1 字节 | int32_t 类型的整数。 |
| 11100000 | 1 字节 | int64_t 类型的整数。 |
| 11110000 | 1 字节 | 24 位有符号整数。 |
| 11111110 | 1 字节 | 8 位有符号整数。 |
| 1111xxxx | 1 字节 | 使用这一编码的节点没有相应的 content 属性， 因为编码本身的 xxxx 四个位已经保存了一个介于 0 和12 之间的值， 所以它无须 content 属性。 |
3.content：负责保存节点的值，可以为一个字节数组或整数。如下两个例子分别表示一个11字节的字节数组和一个保存int16的整数值，不妨猜猜看哪一个是表示11字节的字节数组呢？
有关压缩列表指针所指地址的示例如下：
API接口
总览
| 函数 | 作用 | 算法复杂度 |
| ziplistNew | 创建一个新的压缩列表。 | O(1) |
| ziplistPush | 创建一个包含给定值的新节点， 并将这个新节点添加到压缩列表的表头或者表尾。 | 平均 O(N^2) 。 |
| ziplistInsert | 将包含给定值的新节点插入到给定节点之后。 | 平均 O(N^2) 。 |
| ziplistIndex | 返回压缩列表给定索引上的节点。 | O(N) |
| ziplistFind | 在压缩列表中查找并返回包含了给定值的节点。 | 因为节点的值可能是一个字节数组， 所以检查节点值和给定值是否相同的复杂度为 O(N^2) 。 |
| ziplistNext | 返回给定节点的下一个节点。 | O(1) |
| ziplistPrev | 返回给定节点的前一个节点。 | O(1) |
| ziplistGet | 获取给定节点所保存的值。 | O(1) |
| ziplistDelete | 从压缩列表中删除给定的节点。 | 平均 O(N^2) 。 |
| ziplistDeleteRange | 删除压缩列表在给定索引上的连续多个节点。 | 平均 O(N^2) 。 |
| ziplistBlobLen | 返回压缩列表目前占用的内存字节数。 | O(1) |
| ziplistLen | 返回压缩列表目前包含的节点数量。 | 节点数量小于 65535 时 O(N)。 |
创建压缩列表
unsigned char *ziplistNew(void); /*创建空的压缩列表，只需要分配初始存储空间（11=4+4+2+1个字节），并对zlbytes、zltail、zllen和zlend字段初始化即可。*/ unsigned char *ziplistNew(void) { //ZIPLIST_HEADER_SIZE = zlbytes + zltail + zllen; //最后这个加1表示bytes本身 unsigned int bytes = ZIPLIST_HEADER_SIZE+1; unsigned char *zl = zmalloc(bytes); ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); ZIPLIST_LENGTH(zl) = 0; //结尾标识0XFF zl[bytes-1] = ZIP_END; return zl; }
插入元素
函数输入参数zl表示压缩列表首地址，p指向新元素的插入位置，s表示数据内容，slen表示数据长度，返回参数为压缩列表首地址。
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);
插入元素时，可以简要分为三个步骤：第一步需要将元素内容编码为压缩列表的元素，第二步重新分配空间，第三步拷贝数据。下面分别讨论每个步骤的实现逻辑。
1)编码
编码即计算previous_entry_length字段、encoding字段和content字段的内容。如何获取前一个元素的长度呢？这时候就需要根据插入元素的位置分情况讨论了，如图所示：
当压缩列表为空插入位置为P0时，此时不存在前一个元素，即前一个元素的长度为0；
当插入位置为P1时，此时需要获取entryX元素的长度，而entryX+1元素的previous_entry_length字段存储的就是entryX元素的长度，比较容易获取；
当插入位置为P2时，此时需要获取entryN元素的长度，entryN是压缩列表的尾元素，计算其元素长度需要将其三个字段长度相加，函数实现如下：
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; }
encoding字段标识的是当前元素存储的数据类型以及数据长度，编码时首先会尝试将数据内容解析为整数，如果解析成功则按照压缩列表整数类型编码存储，解析失败的话按照压缩列表字节数组类型编码存储。
if (zipTryEncoding(s,slen,&value,&encoding)) { reqlen = zipIntSize(encoding); } else { reqlen = slen; } reqlen += zipStorePrevEntryLength(NULL,prevlen); reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
2）重分配空间
空间大小是否是添加元素前的压缩列表长度与新添加元素元素长度之和呢？并不完全是，如图中所示的例子。
插入元素前，entryX元素长度为128字节，entryX+1元素的previous_entry_length字段占1个字节；
添加元素entryNEW元素，元素长度为1024字节，此时entryX+1元素的previous_entry_length字段需要占5个字节；
即压缩列表的长度不仅仅是增加了1024字节，还有entryX+1元素扩展的4字节。
很容易知道，entryX+1元素长度可能增加4字节，也可能减小4字节，也可能不变。而由于重新分配空间，新元素插入的位置指针P会失效，因此需要预先计算好指针P相对于压缩列表首地址的偏移量，待分配空间之后再偏移即可。
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)); int forcelarge = 0; nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0; if (nextdiff == -4 && reqlen < 4) { nextdiff = 0; forcelarge = 1; } //存储偏移量 offset = p-zl; //调用realloc重新分配空间 zl = ziplistResize(zl,curlen+reqlen+nextdiff); //重新偏移到插入位置P p = zl+offset;
那么nextdiff与forcelarge在这里有什么用呢？
分析ziplistResize函数的3个输入参数，curlen表示插入元素前压缩列表的长度，reqlen表示插入元素元素的长度，而nextdiff表示的是entryX+1元素长度的变化，取值可能为0（长度不变）、4（长度增加4）和-4（长度减小4）。
我们再思考下，当nextdiff等于-4，而reqlen小于4时会发生什么呢？没错，插入元素导致压缩列表所需空间减少了，即函数ziplistResize底层调用realloc重新分配的空间小于指针zl指向的空间。这可能会存在问题，我们都知道realloc重新分配空间时，返回的地址可能不变，当重新分配的空间大小反而减少时，realloc底层实现可能会将多余的空间回收，此时可能会导致数据的丢失。因此需要避免这种情况的发生，即重新赋值nextdiff等于0，同时使用forcelarge标记这种情况。
可以再思考下，nextdiff等于-4时，reqlen会小于4吗？答案是可能的，连锁更新可能会导致这种情况的发生。连锁更新将在之后介绍。
3）数据拷贝
重新分配空间之后，需要将位置P后的元素移动到指定位置，将新元素插入到位置P。我们假设entryX+1元素的长度增加4（即nextdiff等于4），此时数据拷贝示意图如图所示：
从图中可以看到，位置P后的所有元素都需要移动，移动的偏移量是插入元素entryNew的长度，移动的数据块长度是位置P后所有元素长度之和再加上nextdiff的值，数据移动之后还需要更新entryX+1元素的previous_entry_length字段。
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); //更新entryX+1元素的previous_entry_length字段字段 if (forcelarge) //entryX+1元素的previous_entry_length字段依然占5个字节; //但是entryNEW元素长度小于4字节 zipStorePrevEntryLengthLarge(p+reqlen,reqlen); else zipStorePrevEntryLength(p+reqlen,reqlen); //更新zltail字段 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen); zipEntry(p+reqlen, &tail); if (p[reqlen+tail.headersize+tail.len] != ZIP_END) { ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); } //更新zllen字段 ZIPLIST_INCR_LENGTH(zl,1);
思考一下，第一次更新尾元素偏移量之后，为什么指向的元素可能不是尾元素呢？很显然，当entryX+1元素就是尾元素时，只需要更新一次尾元素的偏移量；但是当entryX+1元素不知尾元素，且entryX+1元素长度发生了改变，此时尾元素偏移量还需要加上nextdiff的值。
以上参考链接：(强烈推荐)
https://segmentfault.com/a/1190000017328042
连锁更新
当往ziplist中插入或删除节点时，由于previous节点字节数可为1或5，保存的前置节点大小不一致，可能就会引发后续节点依次影响，从而发生多次空间重分配，这就是连锁更新。
比如插入的new恰好大于254字节，而原本entry都是介于250-253之间：
那么插入是如何导致的呢？先想再看：
解释——当e1-en都是250-253字节时，big大于254，small小于254，那么删除small就会造成e1之后节点的连锁更新。
T(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
//更新zllen字段
ZIPLIST_INCR_LENGTH(zl,1);
思考一下，第一次更新尾元素偏移量之后，为什么指向的元素可能不是尾元素呢？很显然，当entryX+1元素就是尾元素时，只需要更新一次尾元素的偏移量；但是当entryX+1元素不知尾元素，且entryX+1元素长度发生了改变，此时尾元素偏移量还需要加上nextdiff的值。 以上参考链接：(强烈推荐) https://segmentfault.com/a/1190000017328042 ### **连锁更新** 当往ziplist中插入或删除节点时，**由于previous节点字节数可为1或5，保存的前置节点大小不一致，可能就会引发后续节点依次影响**，从而发生多次空间重分配，这就是连锁更新。 比如插入的new恰好大于254字节，而原本entry都是介于250-253之间： [外链图片转存中...(img-xEtQQmdf-1618293277751)] 那么插入是如何导致的呢？先想再看： [外链图片转存中...(img-FL7AXQRL-1618293277752)] 解释——当e1-en都是250-253字节时，big大于254，small小于254，那么删除small就会造成e1之后节点的连锁更新。 在最坏的情况下，需要执行N次重分配操作，所以每次空间重分配的**最坏复杂度为O(n^2）**。虽然有如此严重的性能损耗，但是实际场景中发生的概率极低，所以ziplistPush等命令平均复杂度为O(n)。
