https://blog.csdn.net/ldw201510803006/article/details/122420585

前言

从 ziplist 到 quicklist，再到 listpack 结构；可以看到，初衷都是设计一款数据结构能够高效的使用内存。

ziplist 设计出的紧凑型数据块可以有效利用内存，但在更新上，由于每一个 entry 都保留了前一个 entry 的 prevlen 长度，因此在插入或者更新时可能会出现连锁更新，这是一个影响效率的大问题。

因此，接着又设计出 「链表 + ziplist」组成的 quicklist 结构来避免单个 ziplist 过大，可以有效降低连锁更新的影响面。

但 quicklist 本质上不能完全避免连锁更新问题，因此，又设计出与 ziplist 完全不同的内存紧凑型结构 listpack，继续往下看～

一、listpack是什么？

listpack 也叫紧凑列表，它的特点就是用一块连续的内存空间来紧凑地保存数据，同时为了节省内存空间，listpack 列表项使用了多种编码方式，来表示不同长度的数据，这些数据包括整数和字符串。

Redis源码对于listpack的解释为 A lists of strings serialization format，一个字符串列表的序列化格式，也就是将一个字符串列表进行序列化存储。Redis listpack可用于存储字符串或者整型

二、原理分析

1. 结构

listpack结构：

<tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>

listpack由4部分组成：total Bytes、Num Elem、Entry以及End

• Total Bytes为整个listpack的空间大小，占用4个字节，每个listpack最多占用4294967295Bytes。
• Num Elem为listpack中的元素个数，即Entry的个数，占用2个字节，值得注意的是，这并不意味着listpack最多只能存放65535个Entry，当Entry个数大于等于65535时，Num Elem被设置为65535，此时如果需要获取元素个数，需要遍历整个listpack。
• Entry为每个具体的元素。
• End为listpack结束标志，占用1个字节，内容为0xFF。

entry结构：

Entry为listpack中的具体元素，其内容可以为字符串或者整型，每个Entry由3部分组成：

<encoding-type><element-data><element-tot-len>
|                                            |
+--------------------------------------------+
            (This is an element)

从组成上可以看出，和 ziplist 列表项类似，listpack 列表项也包含了元数据信息和数据本身。

不过，为了避免 ziplist 引起的连锁更新问题，listpack 中的每个列表项不再像 ziplist 列表项那样，保存其前一个列表项的长度，它只会包含三个方面内容，分别是当前元素的编码类型（encoding）、元素数据 (data)，以及编码类型和元素数据这两部分的长度 (len)。

其中 type 和 tot-len 一定有值；有时 data 可能会缺失，因为对于一些小的元素可以直接将data放在type字段中。

element-tot-len记录了这个Entry的长度（encoding + data），注意并不包括 element-tot-len 自身的长度，占用的字节数小于等于5。

• element-tot-len 所占用的每个字节的第一个 bit 用于标识；0代表结束，1代表尚未结束，每个字节只有7 bit 有效。
• 值得一提的是，element-tot-len 主要用于从后向前遍历，当我们需要找到当前元素的上一个元素时，我们可以从后向前依次查找每个字节，找到上一个Entry的 element-tot-len 字段的结束标识，进而可以计算出上一个元素的长度。
• 例如 element-tot-len 为0000000110001000，代表该元素的长度为00000010001000，即136字节。通过计算即可算出上一个元素的首地址（entry的首地址）。

需要注意的是，在整型存储中，并不实际存储负数，而是将负数转换为正数进行存储。例如，在13位整型存储中，存储范围为[0, 8191]，其中[0, 4095]对应非负的[0, 4095]（当然，[0, 127]将会采用7位无符号整型存储），而[4096, 8191]则对应[-4096, -1]。

2. 编码方式

encoding-type是理解数据类型的基础，为了节省内存空间，listpack针对不同的数据做了不同的编码：

小的数字

0|xxxxxxx

表示7位无符号整型，后7位为数据。

我们知道，int类型占4字节，字符类型占1字节；因此较小的整型数用字符串表示就可以节省一定的空间；比如，65、1这样的整数，因此，该编码可以用于表示0～127之间的整数。

小的字符串

10|xxxxxx <string-data>

6位字符串长度，后6位为字符串长度，再之后则是字符串内容（0 ~ 63 bytes）

多字节编码

如果第一个字节的最高2bit被设置为1，采用如下两种编码方式

110|xxxxx yyyyyyyy -- 13 bit signed integer，即13位整型，后5位及下个字节为数据内容
1110|xxxx yyyyyyyy -- string with length up to 4095，即12位长度的字符串，后4位及下个字节为字符串长度，再之后的为字符串数据。

如果第一个字节的最高4bit被设置为1，将采用以下几种方式编码

1111|0000 <4 bytes len> <large string>，即32位长度字符串，后4字节为字符串长度，再之后为字符串内容
1111|0001 <16 bits signed integer>，即16位整型，后2字节为数据
1111|0010 <24 bits signed integer>，即24位整型，后3字节为数据
1111|0011 <32 bits signed integer>，即32位整型，后4字节为数据
1111|0100 <64 bits signed integer>，即64位整型，后8字节为数据
1111|0101 to 1111|1110 are currently not used.   当前不用编码
1111|1111 End of listpack，结尾标识

3. listpack 避免连锁更新的实现方式

在 listpack 中，因为每个列表项只记录自己的长度，而不会像 ziplist 中的列表项那样，会记录前一项的长度。所以，当在 listpack 中新增或修改元素时，实际上只会涉及每个列表项自己的操作，而不会影响后续列表项的长度变化，这就避免了连锁更新。

如果 listpack 列表项只记录当前项的长度，那么 listpack 支持从左向右正向查询列表，或是从右向左反向查询列表吗？

来，继续往下看～

4. 查询

正向查询

首先，listpack 保存了 LP_HDR_SIZE，通过该参数可以直接将指针移动到第一个 entry 列表项

• 先计算 encoding + data 的总长度 len1
• 通过 len1 可计算出 element-tot-len 的长度
• len1 + element-tot-len 之和即为 entry 总长度 total-len
• 向后移动 total-len 即为下一个列表项的起始位置

这就是正向查询的过程。

反向查询

为了支持反向查询，特意设计了参数element-tot-len，怎么说呢？因为对于正向查询，encoding保存了数据类型及数据长度，就可以知道整个entry的长度

element-tot-len的特殊编码方式：element-tot-len 每个字节的最高位，是用来表示当前字节是否为 element-tot-len 的最后一个字节，这里存在两种情况，分别是：

• 最高位为 1，表示 element-tot-len 还没有结束，当前字节的左边字节仍然表示 element-tot-len 的内容；
• 最高位为 0，表示当前字节已经是 element-tot-len 最后一个字节了。而 element-tot-len 每个字节的低 7 位，则记录了实际的长度信息。

这里需要注意的是，element-tot-len 每个字节的低 7 位采用了大端模式存储，也就是说，entry-len 的低位字节保存在内存高地址上。

正是因为有了 element-tot-len 的特别编码方式，lpDecodeBacklen 函数就可以从当前列表项起始位置的指针开始，向左逐个字节解析，得到前一项的 element-tot-len 值，也就可以得到encoding + data的总长度，从而得出entry的总长度；减去entry的总长度，就得到了前一个entry的地址～

源码分析

1、初始化

lpNew 函数创建了一个空的 listpack，一开始分配的大小是 LP_HDR_SIZE 再加 1 个字节。LP_HDR_SIZE 宏定义是在 listpack.c 中，它默认是 6 个字节，其中 4 个字节是记录 listpack 的总字节数，2 个字节是记录 listpack 的元素数量。

此外，listpack 的最后一个字节是用来标识 listpack 的结束，其默认值是宏定义 LP_EOF。和 ziplist 列表项的结束标记一样，LP_EOF 的值也是 255

unsigned char *lpNew(void) {
    unsigned char *lp = lp_malloc(LP_HDR_SIZE+1);
    if (lp == NULL) return NULL;
    lpSetTotalBytes(lp,LP_HDR_SIZE+1);
    lpSetNumElements(lp,0);
    lp[LP_HDR_SIZE] = LP_EOF;
    return lp;
}

来，再来回顾下listpack组成结构：

<tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>
|------ LP_HDR_SIZE -----|                             |---- 末尾标志 -----|

2、增删改操作

listpack提供了2种添加元素的方式：一种是在任意位置插入元素，一种是在末尾插入元素。在末尾插入元素的底层实现通过调用任意位置插入元素进行，具体实现为lpInsert函数。

listpack的删除操作被转换为用空元素替换的操作。

listpack的替换操作（即改操作）的底层实现也是通过lpInsert函数实现的。函数定义如下：

unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, unsigned char *p, int where, unsigned char **newp) 

其中：

• lp为当前待操作的 listpack；
• ele 为待插入的新元素或者待替换的新元素，ele 为空时，也就是删除操作；
• size 为 ele 的长度；
• p为待插入的位置或者带替换的元素位置；
• where 有 LP_BEFORE（前插）、LP_AFTER（后插）、LP_REPLACE（替换）；
• *newp 用于返回插入的元素、替换的元素、删除元素的下一个元素。

来，具体看看源码实现：

unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, unsigned char *p, int where, unsigned char **newp) {
    unsigned char intenc[LP_MAX_INT_ENCODING_LEN];
    unsigned char backlen[LP_MAX_BACKLEN_SIZE];

    uint64_t enclen; /* The length of the encoded element. */
    // 当ele为null时意味着删除, 也就是用null替换原来的ele
    if (ele == NULL) where = LP_REPLACE;
    
    // 如果是在当前元素之后插入的话，那么可以将指针移动到下一个元素，也就是变成了下一个元素的LP_BEFORE操作；因此实际上只剩两种操作，LP_BEFORE and LP_REPLACE
    if (where == LP_AFTER) {
        p = lpSkip(p);
        where = LP_BEFORE;
        ASSERT_INTEGRITY(lp, p);
    }
    
    // 先存下元素的offset，当内存重分配之后可以重新定位p
    unsigned long poff = p-lp
    
    // 得到编码类型，LP_ENCODING_INT or LP_ENCODING_STR
    int enctype;
    if (ele) {
        enctype = lpEncodeGetType(ele,size,intenc,&enclen);
    } else {
        enctype = -1;
        enclen = 0;
    }

    /* We need to also encode the backward-parsable length of the element
     * and append it to the end: this allows to traverse the listpack from
     * the end to the start. */
    // backlen_size也就是element-tot-size，得到backlen_size占用的字节数
    unsigned long backlen_size = ele ? lpEncodeBacklen(backlen,enclen) : 0;
    uint64_t old_listpack_bytes = lpGetTotalBytes(lp);
    uint32_t replaced_len  = 0;
    if (where == LP_REPLACE) {
        replaced_len = lpCurrentEncodedSizeUnsafe(p);
        replaced_len += lpEncodeBacklen(NULL,replaced_len);
        ASSERT_INTEGRITY_LEN(lp, p, replaced_len);
    }

    // 计算新空间大小
    uint64_t new_listpack_bytes = old_listpack_bytes + enclen + backlen_size
                                  - replaced_len;
    if (new_listpack_bytes > UINT32_MAX) return NULL;

    // 接下来将会进行内存重分配，扩容或缩容
    unsigned char *dst = lp + poff; /* May be updated after reallocation. */
    if (new_listpack_bytes > old_listpack_bytes) {
        if ((lp = lp_realloc(lp,new_listpack_bytes)) == NULL) return NULL;
        dst = lp + poff;
    }

    if (where == LP_BEFORE) {
        memmove(dst+enclen+backlen_size,dst,old_listpack_bytes-poff);
    } else { /* LP_REPLACE. */
        long lendiff = (enclen+backlen_size)-replaced_len;
        memmove(dst+replaced_len+lendiff,
                dst+replaced_len,
                old_listpack_bytes-poff-replaced_len);
    }

    /* Realloc after: we need to free space. */
    // 缩容
    if (new_listpack_bytes < old_listpack_bytes) {
        if ((lp = lp_realloc(lp,new_listpack_bytes)) == NULL) return NULL;
        dst = lp + poff;
    }

    /* Store the entry. */
    if (newp) {
        *newp = dst;
        /* In case of deletion, set 'newp' to NULL if the next element is
         * the EOF element. */
        if (!ele && dst[0] == LP_EOF) *newp = NULL;
    }
    if (ele) {
        if (enctype == LP_ENCODING_INT) {
            memcpy(dst,intenc,enclen);
        } else {
            lpEncodeString(dst,ele,size);
        }
        dst += enclen;
        memcpy(dst,backlen,backlen_size);
        dst += backlen_size;
    }

    /* Update header. */
    if (where != LP_REPLACE || ele == NULL) {
        uint32_t num_elements = lpGetNumElements(lp);
        if (num_elements != LP_HDR_NUMELE_UNKNOWN) {
            if (ele)
                lpSetNumElements(lp,num_elements+1);
            else
                lpSetNumElements(lp,num_elements-1);
        }
    }
    lpSetTotalBytes(lp,new_listpack_bytes);
 
    ...

    return lp;
}

该函数返回null或者插入的元素，替换的元素，删除元素的下一个元素。删除或者替换的主要过程如下：

• 计算需要插入的新元素或者替换旧元素的新元素需要的空间；
• 计算进行插入或者替换后整个 listpack 所需的空间，通过 realloc 申请空间；
• 调整新的 listpack 中的老的元素的位置，为待操作元素预留空间；
• 释放旧的 listpack；
• 在新的 listpack 中进行插入或替换的操作；
• 更新新的 listpack 结构头部的统计信息。

3、遍历操作

listpack 提供了一组接口用于遍历其所有元素，核心思想是利用每个 entry 的 encoding 或者element-tot-len 字段获取当前 entry 的长度，接口实现较为简单。

unsigned char *lpFirst(unsigned char *lp);
unsigned char *lpLast(unsigned char *lp);
unsigned char *lpNext(unsigned char *lp, unsigned char *p);
unsigned char *lpPrev(unsigned char *lp, unsigned char *p);

此处获取的仅仅是某个 entry 首地址的指针，如果要读取当前元素则需要使用 lpGet 接口，也就是说 lpFirst、lpLast 等接口负责定位 entry 首地址，lpGet 则负责实际读取操作；

4、读取元素

lpGet 用于获取 p 指向的 listpack 中真正存储的元素：

• 当元素采用字符串编码时，返回字符串的第一个元素位置，count 为元素个数；-

• 当采用整型编码时，若 intbuf 不为空，则将整型数据转换为字符串存储在 intbuf 中，count为元素个数，并返回 intbuf。若 intbuf 为空，直接将数据存储在 count 中，返回null。

  unsigned char *lpGet(unsigned char *p, int64_t *count, unsigned char *intbuf) {
  int64_t val;
  uint64_t uval, negstart, negmax;
  
  assert(p); /* assertion for valgrind (avoid NPD) */
  if (LP_ENCODING_IS_7BIT_UINT(p[0])) {
      negstart = UINT64_MAX; /* 7 bit ints are always positive. */
      negmax = 0;
      uval = p[0] & 0x7f;
  } else if (LP_ENCODING_IS_6BIT_STR(p[0])) { // 字符串编码类型
      *count = LP_ENCODING_6BIT_STR_LEN(p);
      return p+1;
  } else if (LP_ENCODING_IS_13BIT_INT(p[0])) {
      
      .....
  
  }
  
  /* We reach this code path only for integer encodings.
   * Convert the unsigned value to the signed one using two's complement
   * rule. */
  // 只有整型编码能走到这...
  if (uval >= negstart) {
      /* This three steps conversion should avoid undefined behaviors
       * in the unsigned -> signed conversion. */
      uval = negmax-uval;
      val = uval;
      val = -val-1;
  } else {
      val = uval;
  }
  
  /* Return the string representation of the integer or the value itself
   * depending on intbuf being NULL or not. */
  if (intbuf) {
      *count = snprintf((char*)intbuf,LP_INTBUF_SIZE,"%lld",(long long)val);
      return intbuf;
  } else {
      *count = val;
      return NULL;
  }
  }
  

lpGet的实现较为简单，主要是利用了每个entry的encode字段。

总结

可以看出，ziplist、quicklist 和 listpack 是 redis 是不断迭代优化的产物。

ziplist 的不足主要在于当 ziplist 中元素个数过多，它的查找效率就会降低。而且如果在 ziplist 里新增或修改数据，ziplist 占用的内存空间还需要重新分配；更糟糕的是，ziplist 新增某个元素或修改某个元素时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起连锁更新问题，导致每个元素的空间都要重新分配，这就会导致 ziplist 的访问性能下降。

因此，为解决 ziplist 以上问题，Redis 先是在 3.0 版本中设计实现了 quicklist。quicklist 结构在 ziplist 基础上，使用链表将 ziplist 串联起来，链表的每个元素就是一个 ziplist。这种设计减少了数据插入时内存空间的重新分配，以及内存数据的拷贝。同时，quicklist 限制了每个节点上 ziplist 的大小，一旦一个 ziplist 过大，就会采用新增 quicklist 节点的方法。

不过，又因为 quicklist 使用 quicklistNode 结构指向每个 ziplist，无疑增加了内存开销。为了减少内存开销，并进一步避免 ziplist 连锁更新问题，Redis 在 5.0 版本中，就设计实现了 listpack 结构。listpack 结构沿用了 ziplist 紧凑型的内存布局，把每个元素都紧挨着放置。

综上：

• 要想彻底解决 ziplist 连锁更新问题，本质上要修改 ziplist 的存储结构，也就是不要让每个元素保存「上一个」元素的长度，因此迭代出了 listpack
• listpack 每个元素项不再保存上一个元素的长度，而是通过记录entry长度以及element-tot-len中特殊的结束符，来保证既可以从前也可以向后遍历
• listpack 是为了替代 ziplist 为设计的，但因为 List/Hash/Set/ZSet 都严重依赖 ziplist，所以这个替换之路很漫长，目前只有 Stream 数据类型用到了 listpack

相关参考：

• listpack.md
• Redis source code analysis (26) listpack source code analysis
• 深入分析redis之quicklist，不一样的ziplist使用方式？
• [redis压缩列表ziplist，内存优化之路？](