Thinker Vision Blog - 一个专注于技术的、思考者视角下的技术博客

数据结构

listpack 由四个部分组成：

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

tot-bytes：当前 listpack 占用的实际字节长度（包含头部数据和末尾的终止符），固定占用4字节空间（最长可以表示2^32-1），通过这个字段和 listpack 头部指针，可以快速定位到 listpack 的表尾，便于逆向遍历整个列表；
num-elements：当前 listpack 中的元素数量，占用2字节，最多表示2^16-1=65535个元素，当 listpack 中包含的元素大于等于这个数值时候，这个字段会固定设为65535，同时，如果要获取listpack中的节点数量，需要遍历整个列表；
element-N：具体数据节点；
listpack-end-byte：当前紧凑列表的结束标志符，占用1字节，内容固定0xFF（十进制255）；

数据节点的结构组成为：

<encoding-type> <element-data> <element-tot-len>

可以发现 listpack 的数据节点只储存了当前节点的承载数据和元数据信息，没有像 ziplist 节点一样储存上个节点的长度信息，如果需要对整个 listpack 进行增删节点，不需要更新旧有节点中的数据信息，这就从根源上避免了连锁更新的问题。

listpack 节点中，encoding-type （编码类型）和 element-tot-len （当前节点总长度）是固定出现的，对于一些较小的元素，element-data 会直接存放在 encoding-type 中，这样可以节省内存空间。

encoding-type

为了节省内存，Redis 对节点 encoding-type 做了多种不同的解析格式来标识不同的数据类型：

小整型数字

对于 0~127 范围内的数字，或者可以等价转换成相同数值的字符串（如字符串“123”这样的值），按照以下格式储存 encoding-type :

0|xxxxxxx

即第一个字节的第一个bit固定为0，后7bit存储具体数值。

小字符串

10|xxxxxx <string-data>

即第1个字节的的前2个bit固定为10，后6bit记录字符串长度，最大长度记录63个字节，后续字节记录字符串内容。

多字节编码

如果首个字节的前2bit固定为11，并且第3、第四字节不是11，则按照以下规则解析编码：

110|xxxxx yyyyyyyy -- 表示是13位整型，后面5bit和下个字节的8bit合并存储整数值
1110|xxxx yyyyyyyy -- 表示12位（最大2^12-1=4095）长度的字符串，后面4bit和下个字节的8bit合并表示字符串长度，在之后的字节存储字符串内容

如果初始4bit固定为1111，按照以下规则解析：

1111|0000 <4 bytes len> <large string>
1111|0001 <16 bits signed integer>
1111|0010 <24 bits signed integer>
1111|0011 <32 bits signed integer>
1111|0100 <64 bits signed integer>
1111|0101 to 1111|1110 不再使用
1111|1111 结束标志

element-tot-len

每个 listpack 条目最右边通过记录当前节点长度来结束，这样设计的目的是方便自右向左地遍历整个列表。这个字段的长度被设计成是动态可变的：对于较小的字段，占用1字节来记录，而对于较大的节点，从右向左逐渐占用较多的字节数来表示节点长度。

listpack 被设计成从右向左逆向遍历，通过下个 entry 逆向向左依次查找每个字节来确定当前这个节点的长度值；
element-tot-len 的每个字节8bit中，第一个1bit用来表示是否还需要向左占用字节来表示长度，剩余7bit为有效数据。

例如，对于0~127之间的长度值，1个字节即可以表示：

0|1111111 ---- 第一bit为0，剩余7bit位表示长度未127

如果要表示长度为500的值，500转换成2进制为：

111110100

1个字节无法表示，先按照7bit的有效位置来分割：

0000011 1110100

各自补足初始1bit来表示左侧是否有更多字节：

[0]0000011       [1]1110100
 |                |
 `- 左侧不占用字节   `- 左侧需要继续解析字节

得到最终 element-tot-len 编码值：

00000011 11110100

根据上述编码规则，可以计算得出表示不同长度整型数值的 element-tot-len 字段占用的字节数：

0~127 -------------------------- 1 bytes
128~16383 --------------------- 2 bytes
16383~2097151 ---------------- 3 bytes
2097151~268435455 ---------- 4 bytes
268435455~34359738367 ---- 5 bytes

源码分析

listpack 的元素节点定义在https://github.com/redis/redis/blob/7.2.4/src/listpack.h#L49：

/* 数据节点可以同事记录字符串和整数类型 */
typedef struct {
    /* 字符串内容和长度 */
    unsigned char *sval;
    uint32_t slen;
    /* 整数值 */
    long long lval;
} listpackEntry;

一些有用的宏定义：

/* 记录listpack头部长度：total-bytes + num-elements，固定6个字节长 */
#define LP_HDR_SIZE 6

初始化创建一个空的 listpack 时候，首先为 total-bytes + num-elements + listpack-end 部分分配固定长度内存（4+2+1=7bytes）：

unsigned char *lpNew(size_t capacity) {
    unsigned char *lp = lp_malloc(capacity > LP_HDR_SIZE+1 ? capacity : 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 的遍历操作。listpack 通过巧妙的设计编码，同时支持了正向遍历和逆向遍历方式。

正向遍历（自左向右）

首先通过 listpack 初始指针和 LP_HDR_SIZE （即 total-bytes + num-elements 部分总长），可以定位到第一个元素节点；
对于具体的某个元素节点，首先自左向右按照规则解析 encoding-type 和 element-data，可以得出实际的 element-tot-len 值；
通过 element-to-len 的值，可以得出 element-tot-len 部分占用的字节数长度，机上 encoding-type 和 element-data 部分的长度可以得到当前节点的总长度；
指向当前节点初始位置的指针加上当前节点数总长度即可定位到下个节点的初始位置指针；

看代码 lpNext() 用于获取下个节点：

unsigned char *lpNext(unsigned char *lp, unsigned char *p) {
    assert(p);
    p = lpSkip(p);
    if (p[0] == LP_EOF) return NULL;
    lpAssertValidEntry(lp, lpBytes(lp), p);
    return p;
}

主要逻辑在 lpSkip()：

unsigned char *lpSkip(unsigned char *p) {
    // 获得 encoding-type + ele-data 总长度
    unsigned long entrylen = lpCurrentEncodedSizeUnsafe(p);
    // 获取element-tot-len部分长度
    // 计入总长度，得到当前节点总长度
    entrylen += lpEncodeBacklen(NULL,entrylen);
    // 定位到下个节点
    p += entrylen;
    return p;
}

逆向遍历（自右向左）

由于 listpack 中的每个节点都是紧凑排列的，指向当前节点的指针左移1位就是上个节点 element-tot-len 字段的最后一位;
通过每次7bit有效数据的规则，依次从右向左可以得出上个节点的 element-tot-len 值；
通过 element-tot-len 值可以得知这部分占用的字节数，通过指针继续往左回溯长度 size(element-tot-len) + element-tot-len 后即定位到上个节点的起始位置；

源码中通过 lpPrev() 来获取前一个节点内容：

unsigned char *lpPrev(unsigned char *lp, unsigned char *p) {
    assert(p);
    if (p-lp == LP_HDR_SIZE) return NULL;
    // 指针回退一步定位到上个节点末尾
    p--;
    // 解析上个节点的element-tot-len值，得到上个节点长度
    uint64_t prevlen = lpDecodeBacklen(p);
    // 再加上element-tot-len占用字节数
    prevlen += lpEncodeBacklen(NULL,prevlen);
    // 回退到上个节点起始位置
    p -= prevlen-1;
    lpAssertValidEntry(lp, lpBytes(lp), p);
    return p;
}

需要注意的是，由于 listpack 节点中的 element-tot-len 字段记录的节点长度没有包含 element-tot-len 自身占用的字节数量，所以每次需要计算一遍这个字段占用的字节数。

再来看一下用来回退指针逐个解析得到 element-tot-len 的代码：

static inline uint64_t lpDecodeBacklen(unsigned char *p) {
    // 记录最终得到的值
    uint64_t val = 0;
    // 当前指正每次回退的格数
    uint64_t shift = 0;
    do {
        // 位移后通过127掩码得到7bit
        val |= (uint64_t)(p[0] & 127) << shift;
        // 如果第1bit不是1，表示不占用左边字节，直接结束
        if (!(p[0] & 128)) break;
        // 否则继续解析7bit
        shift += 7;
        p--;
        // 最多回退4*7=28个字节，最长也就5bytes
        if (shift > 28) return UINT64_MAX;
    } while(1);
    return val;
}

可以看出这部分代码写的十分清晰优雅，通过得出的 element-tot-len 最后获取了上个节点的长度，相比于 ziplist 节点直接存储上个节点 prevlen 的办法，这种通过指针位移和运算可以优雅便捷地得出同样结果，从而在根源上解决了连锁更新的缺陷。