欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Redis源码解析-基础数据-ziplist(压缩列表)

程序员文章站 2022-05-19 18:20:16
...

太长不看版

  • 压缩列表是一种为节约空间而实现的线性数据结构,本质是字节数组。
  • 压缩列表元素可以为整数或字符串。
  • 压缩列表在快速列表、列表对象和哈希对象中都有使用。
  • 压缩列表添加(平均复杂度O(n))与删除节点(平均复杂度O(n)),可能会触发连锁更新(平均复杂度O(n^2)),因为触发机率不高所以不影响性能。
  • 因为节点存在字符串,字符串匹配为O(n)复杂度,所以压缩列表查找节点平均复杂度为O(n^2)。

本篇解析基于redis 5.0.0版本,本篇涉及源码文件为ziplist.c, ziplist.h。

什么是压缩列表

/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
    unsigned char *zl = zmalloc(bytes);
    // ...
    return zl;
}

从上述创建代码中可以看出,压缩列表本质上就是一个字节数组,其是redis使用字节数组实现的线性数据结构,其元素可以是整数或者字符串。在快速列表、列表对象和哈希对象中都有使用,一般用在元素较少且元素字节数较小的情况下。

为什么要实现压缩列表?

因为为了尽可能的节约内存。设想下现在有两个元素: 整数1和字符串’123’,两个节点 数据本身只有占8个字节(64位机器中)。
使用单向链表的话需要多加两个向后指针,占用24个字节,其中链表节点数据占用16个字节是数据本身大小的两倍。
而此例中压缩列表存储只需要每个节点记录前一节点长度(1字节)、节点本身编码信息(1字节)(具体规则后边解释),总共占用10个字节。

压缩列表的构成

#define ZIP_END 255         /* Special "end of ziplist" entry. */
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))
/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
    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;
    // 255特殊结尾值
    zl[bytes-1] = ZIP_END;
    return zl;
}

压缩列表由总字节长度(4字节),尾节点偏移量(4字节),节点数量(2字节),节点以及值为255的特殊结束符(1字节)组成,通过列表的开始地址向后偏移尾节点偏移量个字节,可以以O(1)时间复杂度获取尾节点信息。

压缩列表自身的信息只占用了11个字节,而链表光是头指针和尾指针存储就需要16个字节,所以针对数据量少的情况(节点少节点小)采用压缩列表会比较划算。
Redis源码解析-基础数据-ziplist(压缩列表)

intrev32ifbe函数为大小端转换,统一转换为小端存储。为什么要进行转换?

因为压缩列表的操作中涉及到的位运算很多,如果不统一的话会出现混乱。后续的所有位运算都是在小端存储的基础上进行的。大小端知识点戳此了解

压缩列表节点的构成

typedef struct zlentry {
    // 前一节点长度信息的长度
    unsigned int prevrawlensize;
    // 前一节点长度
    unsigned int prevrawlen;
    // 当前节点长度信息长度
    unsigned int lensize;  
    // 当前节点长度
    unsigned int len;
    // 当前节点头部信息长度
    unsigned int headersize;
    // 当前节点数据编码
    unsigned char encoding;     
    unsigned char *p;           
} 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;
}

如前所述,压缩列表本质上是字节数组,redis为了操作计算方便定义了zlentry结构体。进行操作计算时,将字节数组中包含的信息按照规则解析到zlentry结构体中,方便后续的计算。从存储角度来看,压缩列表节点分为三部分:

  • 前一节点长度信息
  • 当前节点数据长度与编码信息
  • 节点数据

下图为压缩列表节点各部分组成与zlentry结构体长度字段示意图:

Redis源码解析-基础数据-ziplist(压缩列表)

前一节点长度信息

#define ZIP_BIG_PREVLEN 254 
#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);

前一节点长度小于254时,使用1个字节保存前一节点的长度信息。

前一节点长度大于254时,使用5个字节保存前一节点的长度信息。首个字节固定为254,后续的4个字节用来存储长度信息。

宏定义为什么要写成do {} while(0);

写成do {} while(0); 是为了保证不管在调用代码中怎么使用分号和大括号,该宏总是能确保其行为是一致的。错误示例如下:

#define TEST() test1(); test2();
// 此时test2必然被执行,不符合预期
if (a > 0)
    TEST();
#define TEST() { test1(); test2(); }
// 此时就会出现语法错误
if (a > 0)
    TEST();

当前节点数据长度与编码信息

/* Different encoding/length possibilities */
#define ZIP_STR_MASK 0xc0         /* 11000000 */
#define ZIP_STR_06B (0 << 6)      /* 00000000 */
#define ZIP_STR_14B (1 << 6)      /* 01000000 */
#define ZIP_STR_32B (2 << 6)      /* 10000000 */
#define ZIP_INT_16B (0xc0 | 0<<4) /* 11000000 */
#define ZIP_INT_32B (0xc0 | 1<<4) /* 11010000 */
#define ZIP_INT_64B (0xc0 | 2<<4) /* 11100000 */
#define ZIP_INT_24B (0xc0 | 3<<4) /* 11110000 */
#define ZIP_INT_8B 0xfe           /* 11111110 */

/* 4 bit integer immediate encoding |1111xxxx| with xxxx between
 * 0001 and 1101. */
#define ZIP_INT_IMM_MASK 0x0f   /* 00001111 */
#define ZIP_INT_IMM_MIN 0xf1    /* 11110001 */
#define ZIP_INT_IMM_MAX 0xfd    /* 11111101 */

#define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
    (encoding) = (ptr[0]); \
    if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
} while(0)

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

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

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)) {
        if (value >= 0 && value <= 12) {
            *encoding = ZIP_INT_IMM_MIN+value;
        // ...
        return 1;
    }
    return 0;
}

编码与对应数据长度如下表所示:

编码 长度信息的长度 数据长度
ZIP_STR_06B(00bbbbbb)(前两位标记编码,后6位存储长度) 1个字节 长度<=63的字节数组
ZIP_STR_14B(01bbbbbb xxxxxxxx)(前2位为编码后14位为长度) 2个字节 长度<=16383的字节数组
ZIP_STR_06B(10______ aaaaaaaa bbbbbbbb cccccccc)(前2位标记编码之后6位留空,后24位为长度) 5字节 长度<=4294967295的字节数组
ZIP_INT_16B(11000000) 2字节 int16_t(short)类型整数
ZIP_INT_32B(11010000) 4字节 int32_t(int)类型整数
ZIP_INT_64B(11100000) 8字节 int64_t(long long)类型整数
ZIP_INT_24B(11110000) 3字节 3字节长的有符号整数
ZIP_INT_8B(11111110) 1字节 1字节长的有符号整数
1111 xxxx 4位 0-12的无符号整数(此时该节点没有content部分,数据存储在encoding部分)

按照数据的类型和大小,匹配不同的编码,思路和之前分析过的基础类型sds使用5中头部信息一样,都是为了最大化压缩占用空间。

压缩列表相关操作

更新节点

#define ZIPLIST_HEAD 0
#define ZIPLIST_TAIL 1
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
    unsigned char *p;
    // 头部或尾部插入节点
    p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
    return __ziplistInsert(zl,p,s,slen);
}

unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    /// 插入节点至p指针指向元素前方
    return __ziplistInsert(zl,p,s,slen);
}

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; 

    /* Find out prevlen for the entry that is inserted. */
    if (p[0] != ZIP_END) {
        // 插入位置不在尾部
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {
        // 插入位置在尾部
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        // 尾节点存在取长度,不存在长度为0(列表为空时不存在)
        if (ptail[0] != ZIP_END) {
            prevlen = zipRawEntryLength(ptail);
        }
    }
    // s指针指向新增节点数据 slen为数据长度
    // 确定数据编码。数据长度,为整数时返回对应固定长度,为字符串使用slen
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        reqlen = zipIntSize(encoding);
    } else {
        reqlen = slen;
    }
    // 加上前一节点长度信息的长度
    reqlen += zipStorePrevEntryLength(NULL,prevlen);
    // 加上编码与长度信息的长度
    // 此时reqlen为新加入节点的整体长度
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

    int forcelarge = 0;
    // 
    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;
    }

    offset = p-zl;
    // 调整内存大小
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    p = zl+offset;

    // 非空列表插入
    if (p[0] != ZIP_END) {
        // 将p节点后移(没有移动p节点前一节点长度信息),留出当前节点位置
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

        // 写入p节点前一节点长度信息(要插入节点的长度)
        if (forcelarge)
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
        else
            zipStorePrevEntryLength(p+reqlen,reqlen);

        // 更新尾节点偏移量
        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);
        }
    } else {
        // 空列表插入,只更新尾节点偏移量
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
    }

    // 连锁更新
    if (nextdiff != 0) {
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }

    // 写入前一节点长度信息
    p += zipStorePrevEntryLength(p,prevlen);
    // 写入节点编码与长度信息
    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;
}

连锁更新

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

        /* Abort when "prevlen" has not changed. */
        if (next.prevrawlen == rawlen) break;

        if (next.prevrawlensize < rawlensize) {
            /* The "prevlen" field of "next" needs more bytes to hold
             * the raw length of "cur". */
            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;

            // 如果下一节点不是尾节点,则需要更新 尾部节点偏移量
            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. */
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);
            zipStorePrevEntryLength(np,rawlen);


            p += rawlen;
            curlen += extra;
        } else {
            // 如果 next节点原本的 前一节点长度信息 字段长度可以容纳新插入节点的长度信息,则直接写入并退出遍历
            if (next.prevrawlensize > rawlensize) {
                /* This would result in shrinking, which we want to avoid.
                 * So, set "rawlen" in the available bytes. */
                zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
            } else {
                zipStorePrevEntryLength(p+rawlen,rawlen);
            }

            /* Stop here, as the raw length of "next" has not changed. */
            break;
        }
    }
    return zl;
}

前边我们看到了压缩列表节点的各个字段都是变长的,如果前一节点长度发生变化,可能会引起后一节点的长度发生变化(如果前一节点的长度之前小于254,变更后大于254,则后一节点的 前一节点长度信息占用字节会从1个字节变为5个字节)。考虑一种极端情况,插入节点后续的节点长度都是介于250~253之间,此时插入一个节点长度大于254的节点,会引发连锁更新,如下图所示:

Redis源码解析-基础数据-ziplist(压缩列表)

Redis源码解析-基础数据-ziplist(压缩列表)
图中每行都代表了一次内存重新分配,红框框出的是每次扩张的字节。此时插入节点的时间复杂度为O(n^2)(n 次空间重分配操作,每次空间重分配的最坏复杂度为 O(n) )。

连锁更新最坏情况下带来的性能消耗是灾难性的,为什么还可以放心的使用?
  • 触发的条件(恰好存在多个连续的长度介于250~253之间的节点 )使得其触发的概率很低
  • 压缩列表的应用场景(节点数量较少且节点数据长度较小)以及长度恰好介于250-~253之间的情况出现情况较低使得即便出现了连锁更新,需要更新的节点也没有几个。

所以压缩列表插入节点的平均复杂度为O(n)。

查找节点

unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
    int skipcnt = 0;
    unsigned char vencoding = 0;
    long long vll = 0;
    // 遍历压缩列表 skip为查找前跳过skip个节点
    while (p[0] != ZIP_END) {
        unsigned int prevlensize, encoding, lensize, len;
        unsigned char *q;

        ZIP_DECODE_PREVLENSIZE(p, prevlensize);
        ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
        q = p + prevlensize + lensize;

        if (skipcnt == 0) {
            /* Compare current entry with specified entry */
            if (ZIP_IS_STR(encoding)) {
                // 数据为字符串,判断字符串相等复杂度为O(n)
                if (len == vlen && memcmp(q, vstr, vlen) == 0) {
                    return p;
                }
            } else {
                if (vencoding == 0) {
                    // 首次比对时,对传入值进行解码
                    if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
                        /* If the entry can't be encoded we set it to
                         * UCHAR_MAX so that we don't retry again the next
                         * time. */
                        vencoding = UCHAR_MAX;
                    }
                    /* Must be non-zero by now */
                    assert(vencoding);
                }

                /* Compare current entry with specified entry, do it only
                 * if vencoding != UCHAR_MAX because if there is no encoding
                 * possible for the field it can't be a valid integer. */
                if (vencoding != UCHAR_MAX) {
                    long long ll = zipLoadInteger(q, encoding);
                    if (ll == vll) {
                        return p;
                    }
                }
            }

            /* Reset skip count */
            skipcnt = skip;
        } else {
            /* Skip entry */
            skipcnt--;
        }

        /* Move to next entry */
        p = q + len;
    }

    return NULL;
}

因为节点中存在字符串,且字符串相等比对的复杂度为O(n), 所以压缩列表查找节点的复杂度为O(n^2)。

删除节点

unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
    size_t offset = *p-zl;
    zl = __ziplistDelete(zl,*p,1);

    /* Store pointer to current element in p, because ziplistDelete will
     * do a realloc which might result in a different "zl"-pointer.
     * When the delete direction is back to front, we might delete the last
     * entry and end up with "p" pointing to ZIP_END, so check this. */
    *p = zl+offset;
    return zl;
}

/* Delete a range of entries from the ziplist. */
unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num) {
    unsigned char *p = ziplistIndex(zl,index);
    return (p == NULL) ? zl : __ziplistDelete(zl,p,num);
}

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;
    // 删除的首个节点
    zipEntry(p, &first);
    for (i = 0; p[0] != ZIP_END && i < num; i++) {
        // 跳过所有要删除的节点
        p += zipRawEntryLength(p);
        deleted++;
    }
    // first.p指向第一个要被删除节点的首地址
    // p指向的是最后一个删除节点的下一节点的首地址, totlen大于0表示需要删除节点
    totlen = p-first.p; /* Bytes taken by the element(s) to delete. */
    if (totlen > 0) {
        if (p[0] != ZIP_END) {
            // 获取p节点 【前一节点长度信息】 字段与首个被删除节点 【前一个节点长度信息】 字段的差值
            // zipPrevLenByteDiff 的返回值有三种可能:
            // 1)新旧两个节点的【前一个节点长度信息】字段长度 相等,返回 0
            // 2)新节点【前一个节点长度信息】字段长度 > 旧节点【前一个节点长度信息】字段长度,返回 5 - 1 = 4
            // 3)旧节点【前一个节点长度信息】字段长度 > 新节点【前一个节点长度信息】字段长度,返回 1 - 5 = -4
            nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
            // 根据差值,向前向后偏移 p指针
            p -= nextdiff;
            // 将首个被删除节点【前一节点长度信息】写入p指针指向的节点
            zipStorePrevEntryLength(p,first.prevrawlen);

            // 更新尾节点偏移量
            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. */
            zipEntry(p, &tail);
            /* 如果p节点不是尾节点, 则尾节点偏移量需要加上nextdiff的变更量
               因为尾节点偏移量是指列表首地址到尾节点首地址的距离
               p节点的 【前一节点长度信息】 字段的长度变化只影响它字段之后的信息地址。
               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 */
            memmove(first.p,p,
                intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
        } else {
            /* The entire tail was deleted. No need to move memory. */
            // 一直删除到尾节点,不需要变更中间节点,只需要调整下尾节点偏移量
            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;

        // 如果最后一个被删除节点的下一节点的【前一个节点长度信息】字段长度 需要变更,则可能会触发连锁更新
        if (nextdiff != 0)
            zl = __ziplistCascadeUpdate(zl,p);
    }
    return zl;
}

因为可能会触发连锁更新,所以删除操作最坏复杂度为O(n^2),平均复杂度为O(n)。