Redis - listpack（紧凑列表）图文详解

一 前言

1.1 背景

在阅读本文前，需要了解下 ziplist（压缩列表），因为 listpack 的出现是用来代替 ziplist 的。

Redis 采用 ziplist ，是因为其为一种连续内存空间并且有序的压缩链表 。在数据节点不多的情况下，内存占用和查询复杂度得到一个相对较好的平衡。

但是 zip 有个一个致命的缺陷，就是极端情况下的连锁更新会带来不小的性能消耗。如下图所示：

1.2 方案

Redis 在后续的版本中也采用了 quicklist（快速链表），通过控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来减少连锁更新带来的性能影响，但是并没有完全解决连锁更新的问题，因为 quicklistNode 还是用了压缩列表来保存元素。

所以在 Redis5.0 出现了 listpack，目的是替代压缩列表，其最大特点是 listpack 中每个节点不再包含前一个节点的长度，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。

二 源码解读

鉴入 Redis7.0 已经将 listpack 完整替代 ziplist（Redis7.0 新特性） ，所以本文的源码是 7.0版本。

前文提到 listpack 最大特点是 listpack 中每个节点不再包含前一个节点的长度，所以直接对比 listpack 和 ziplist 的结构设计。

2.1 ziplist entry

typedef struct zlentry {
    unsigned int prevrawlensize; /* 用于编码前一个节点字节长度*/
    unsigned int prevrawlen;     
    unsigned int lensize;        /* 用于编码此节点类型/长度的字节。
    								例如，字符串有1、2或5个字节标题。
    								整数总是使用一个字节。
    							*/
    unsigned int len;            /* 用于表示节点实际的字节。
									对于字符串，这只是字符串长度
									而对于整数，它是1、2、3、4、8或
									0,具体取决于数字范围。 
								*/
    unsigned int headersize;     /* prevrawlensize + lensize. */
    unsigned char encoding;      /* 设置为ZIP_STR_*或ZIP_INT_*，具体取决于节点编码。*/
    unsigned char *p;            /* 第一个节点的地址指针，prev-entry-len */
} zlentry;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以明显看到 prevrawlensize 用于记录前一个节点的大小。

2.2 listpack entry

typedef struct {
    /* 当使用string时，它具有长度(slen)。 */
    unsigned char *sval;
    uint32_t slen;
    /* 当使用integer时，“sval”为 NULL，lval 保存该值。*/
    long long lval;
} listpackEntry;
1
2
3
4
5
6
7

不同于 zlentry，listpackEntry 中的 len 记录的是当前 entry 的长度，而非上一个 entry 的长度。listpackEntry 中可存储的为字符串或整型。

1. 当存储的为字符串，slen 记录大小。调用函数 lpInsertString() 。
2. 当存储的为整形，lval 记录实际值，sval 字段为 NULL。调用函数 lpInsertInteger()。

2.3 图文详解

下面的代码展示了如何创建一个新的 listpack。

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;
}
1
2
3
4
5
6
7
8

结合 lpNew() 和 listpackEntry ，不难得到 listpack 的内存结构图。

encoding ：定义该元素的编码类型，会对不同长度的整数和字符串进行编码。
data：实际存放的数据。
len：encoding + data 的总长度，len 代表当前节点的回朔起始地址长度的偏移量。

从上图不难得到这样的结论：listpack 没有记录前一个节点长度，只记录当前节点的长度，从而避免了压缩列表的连锁更新问题。

三 操作接口

3.1 新增

按照节点存储的数据类型分为整形和字符串两种方式包装，统一在 lpinsert() 进行处理。

unsigned char *lpInsertString(unsigned char *lp, unsigned char *s, uint32_t slen,
                              unsigned char *p, int where, unsigned char **newp);
unsigned char *lpInsertInteger(unsigned char *lp, long long lval,
                               unsigned char *p, int where, unsigned char **newp);



unsigned char *lpInsert(unsigned char *lp, unsigned char *elestr, unsigned char *eleint,
                        uint32_t size, unsigned char *p, int where, unsigned char **newp)
{

 代码就不罗列了，有兴趣的自己查阅。

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.2 删除

有个特别的地方是：listpack 把增删改统一成新增与修改两种模式，统一在lpinsert函数中实现。

unsigned char *lpDelete(unsigned char *lp, unsigned char *p, unsigned char **newp);
unsigned char *lpDeleteRangeWithEntry(unsigned char *lp, unsigned char **p, unsigned long num);
unsigned char *lpDeleteRange(unsigned char *lp, long index, unsigned long num);

# 最终都是调用 lpInsert 函数。
unsigned char *lpDelete(unsigned char *lp, unsigned char *p, unsigned char **newp) {
    return lpInsert(lp,NULL,NULL,0,p,LP_REPLACE,newp);
}

1
2
3
4
5
6
7
8
9

3.3 查找

列表类型的查找都是遍历，时间复杂度O(n)，listpack 也是如此。

unsigned char *lpFind(unsigned char *lp, unsigned char *p, unsigned char *s, uint32_t slen, unsigned int skip);

1
2

四 总结

4.1 区别

1. listpack 中每个节点不再包含前一个节点的长度，避免连锁更新的隐患发生。
2. listpack 相对于 ziplist，没有了指向末尾节点地址的偏移量，解决 ziplist 内存长度限制的问题。但一个 listpack 最大内存使用不能超过 1GB。

4.2 参数变动

• 新增 list-max-listpack-size 代替 list-max-ziplist-size。
• 新增 hash-max-listpack-entries 代替 hash-max-ziplist-entries。
• 新增 hash-max-listpack-value 代替 hash-max-ziplist-value。
• 新增 zset-max-listpack-entries 代替 zset-max-ziplist-entries。
• 新增 zset-max-listpack-value 代替 zset-max-ziplist-value。