likes
comments
collection
share

Redis 底层数据结构 listpack

作者站长头像
站长
· 阅读数 66

为什么需要 Listpack

Listpack 是怎么避免连锁更新的？

  • 我们知道，ZipList 会有连锁更新的问题，最根本的原因就是因为 prevlen 的存在，当 ZipList 新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起连锁更新问题。
  • 既然这样，prelen 是留不得了！那么，Listpack 的结构长什么样子的？没有了 prelen 它又怎么实现遍历操作呢？

Listpack 的底层结构

Listpack

我们先来看看 listpack 整体长什么样子，这里看到 lpNew**(size_t capacity) 这个函数

/* Create a new, empty listpack.
 * On success the new listpack is returned, otherwise an error is returned.
 * Pre-allocate at least `capacity` bytes of memory,
 * over-allocated memory can be shrunk by `lpShrinkToFit`.
 * */
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，其中各个成员变量的值如下：

  • lpSetTotalBytes，用于保存 listpack 的总字节数

  • lpSetNumElements，用于保存 listpack 的元素总数

  • lp[LP_HDR_SIZE] = LP_EOF，设置 listpack 结尾标识为 LP_EOF

    • LP_EOF：默认为 255，也就是 0xFF
    • LP_HDR_SIZE：默认6

因此，listpack 的结构如下

Redis 底层数据结构 listpack 这里可以看出来，其实他和 ZipList 的差别并不大。下面我们再看看中间的 entry 长什么样子

listpackEntry

这给出 listpackEntry 的结构体，如下：

/* Each entry in the listpack is either a string or an integer. */
typedef struct {
    /* When string is used, it is provided with the length (slen). */
    unsigned char *sval;
    uint32_t slen;
    /* When integer is used, 'sval' is NULL, and lval holds the value. */
    long long lval;
} listpackEntry;
  • slen，不同于ziplist，listpackEntry 中的 len 记录的是当前 entry 的编码类型和长度，而非上一个entry的长度。
  • *sval，当存储的数据为字符串时，使用该成员变量
  • lval，当存储的数据为整数，使用该成员变量

listpackEntry的编码类型

为了节省空间，listpackEntry 会对不同长度的整数和字符串进行编码。也就是说，对于不同长度的 *sval(lval) 会有不同的编码方式。因此在 *sval(lval) 内部其实可以视为两个部分，一部分用于标识编码方式，另一部分用于记录数据，至此，我们终于可以将 istpackEntry 内部结构图画出来了。 Redis 底层数据结构 listpack

整数编码

小数字，例如 0 和 65，它们非常常见，因此有特殊的编码方式（LP_ENCODING_7BIT_INT ），可以将表示 0 到 127 之间数字的字符串表示为单个字节。这个字节的最高位为 0，表示编码类型，后续的 7 位用来存储 7 bit 的无符号整数，如下图所示 Redis 底层数据结构 listpack 当编码类型为 LP_ENCODING_13BIT_INT 时，这表示元素的实际数据是 13 bit 的整数。同时，因为 LP_ENCODING_13BIT_INT 的宏定义值为 0xC0，转换为二进制值是 1100 0000，所以，这个二进制值中的后 5 位和后续的 1 个字节，共 13 位，会用来保存 13bit 的整数。而该二进制值中的前 3 位 110，则用来表示当前的编码类型。如图所示，

Redis 底层数据结构 listpack 此外，还有 LP_ENCODING_16BIT_INT、LP_ENCODING_24BIT_INT、LP_ENCODING_32BIT_INT 和 LP_ENCODING_64BIT_INT ，与上面两种同理，这里不再赘述。

字符串编码

  • 对于字符串编码来说，一共有三种类型，分别是 ***LP_ENCODING_6BIT_STR LP_ENCODING_12BIT_STR 和 LP_ENCODING_32BIT_STR，***与整数编码类似，字符串编码类型名称中 BIT 前的数字（LP_ENCODING_XXBIT_STR 中的 XX），表示的就是 表示字符串长度的空间。

  • 比如，当编码类型为 LP_ENCODING_6BIT_STR 时，也即是 XX = 6 。这时，编码类型占 1 字节。该类型的宏定义值是 0x80，对应的二进制值是 1000 0000，这其中的前 2 位是用来标识编码类型本身，而后 6 位保存的是字符串长度。然后，列表项中的数据部分保存了实际的字符串。这是该字符串长度不能超过 63 bit（因为用来保存字符串长度的位置有 6 个 bit 位，也即能表示从 0 ~ 63 的范围）。如图所示， Redis 底层数据结构 listpack

  • 其他字符串编码方式类似，不再赘述。

没有了 prelen 的 listpack 怎么实现遍历操作？

  • 在 listpack 中，因为每个列表项只记录自己的长度，而不会像 ziplist 中的列表项那样，会记录前一项的长度。所以，当我们在 listpack 中新增或修改元素时，实际上只会涉及每个列表项自己的操作，而不会影响后续列表项的长度变化，这就避免了连锁更新。
  • 但是，如果 listpack 列表项只记录当前项的长度，那么 listpack 支持从左向右正向查询列表，或是从右向左反向查询列表吗？

正向遍历

  • 实际上，实现正向遍历还是一件比较容易想到的事情，只需要根据当前列表项第 1 个字节的取值，来计算当前项的编码类型，并根据编码类型，计算当前项编码类型和实际数据的总长度。然后，lpEncodeBacklen 函数会根据编码类型和实际数据的长度之和，进一步计算列表项最后一部分 slen 本身的长度。
  • 这样一来，就能知道当前项的编码类型、实际数据和 entry-len 的总长度了，也就可以将当前项指针向右偏移相应的长度，从而实现查到下一个列表项的目的。

反向遍历

  • listpack 的反向遍历，主要的难点在于如何找到当前节点的上一个节点，而这一点主要是依靠 unsigned char *lpPrev(unsigned char *lp, unsigned char *p) 函数实现的，如下

    /* If 'p' points to an element of the listpack, calling lpPrev() will return
 * the pointer to the previous element (the one on the left), or NULL if 'p'
 * already pointed to the first element of the listpack. */
unsigned char *lpPrev(unsigned char *lp, unsigned char *p) {
    assert(p);
    if (p-lp == LP_HDR_SIZE) return NULL;
    p--; /* Seek the first backlen byte of the last element. */
    uint64_t prevlen = lpDecodeBacklen(p);
    prevlen += lpEncodeBacklen(NULL,prevlen);
    p -= prevlen-1; /* Seek the first byte of the previous entry. */
    lpAssertValidEntry(lp, lpBytes(lp), p);
    return p;
}

  • 在这个函数中，我们传入一个指针 p ，将会把 p 指向的当前指向的节点的上一个节点，具体步骤如下：

    • p--; ：将指针 p 往前移动一个字节，这使得 p 指向前一个节点的最后一个字节
    • uint64_t prevlen = lpDecodeBacklen(p); prevlen += lpEncodeBacklen(NULL,prevlen);：计算 prevlen 的值，也即计算前一个节点的长度。
    • p -= prevlen-1; ：将 p 移动到前一个节点第一个字节的位置。
    • 流程如下所示， Redis 底层数据结构 listpack lpPrev 函数中的关键一步就是调用 lpDecodeBacklen() 函数，计算前一个节点的长度。也就是说， lpDecodeBacklen() 函数会读取 slen（entry-len） 的值，它会从右向左，逐个字节地读取当前列表项的 slen 。

那么，lpDecodeBacklen 函数如何判断 entry-len 是否结束了呢？

这就依赖于 entry-len 的编码方式了。entry-len 每个字节的最高位，是用来表示当前字节是否为 entry-len 的最后一个字节，这里存在两种情况，分别是：

  • 最高位为 1，表示 entry-len 还没有结束，当前字节的左边字节仍然表示 entry-len 的内容；
  • 最高位为 0，表示当前字节已经是 entry-len 最后一个字节了。

例如，存储一个 slen = 512（二进制：10 0000 0000），编码如图所示。

Redis 底层数据结构 listpack 正是因为有了 entry-len 的特别编码方式，lpDecodeBacklen() 函数就可以从当前列表项起始位置的指针开始，向左逐个字节解析，得到前一项的 entry-len 值（编码类型和实际数据的长度之和）

然后，再调用 lpEncodeBacklen(NULL,prevlen)，来计算得到 entry-len 本身长度，并把它加到 prevlen 这样一来，我们就可以得到前一项的总长度，而 lpPrev 函数也就可以将指针指向前一项的起始位置了(p -= prevlen-1)。所以按照这个方法，listpack 就实现了从右向左的查询功能。

自此，我们了解了 listpack 为什么要存在，其底层实现是怎样的以及它是怎么进行遍历操作的。感谢每一位看到这里的朋友，如果文中出现什么错误欢迎在评论区指正！

转载自:https://juejin.cn/post/7240666488336007224
评论
请登录