Redis `LIST` 实现：快速列表（quicklist）的链表与压缩列表混合结构

好的，没问题。

各位观众，各位朋友，大家好！我是今天的讲师，江湖人称“Redis百晓生”。今天咱们要聊聊Redis中LIST的底层实现——快速列表（quicklist）。

先别急着打瞌睡，我知道提到“底层实现”这四个字，很多人就开始头疼。但今天我保证，用最接地气的方式，把这个quicklist给您掰开了揉碎了讲清楚。

什么是Redis LIST？

简单来说，Redis LIST就是一个有序的字符串列表。你可以把它想象成一个双向链表，链表里的每个节点都存储着一个字符串。

LPUSH mylist "world"
LPUSH mylist "hello"
RPUSH mylist "!"
LRANGE mylist 0 -1  # 输出：hello, world, !

上面这段Redis命令，就创建了一个名为mylist的LIST，并往里面插入了三个字符串。

为什么要用quicklist？

如果LIST的数据量不大，直接用链表实现也没啥问题。但是，如果LIST的数据量非常大，比如几百万甚至几千万，那链表的缺点就暴露出来了：

• 内存碎片化严重： 每个节点都需要单独分配内存，容易产生大量的内存碎片，导致内存利用率降低。
• 指针开销大： 每个节点都需要存储指向前后节点的指针，浪费空间。

为了解决这些问题，Redis引入了quicklist。

quicklist：链表 + 压缩列表的混合体

quicklist并不是一个纯粹的链表，也不是一个纯粹的压缩列表，而是它们的结合体。你可以把quicklist想象成一个链表，只不过链表里的每个节点不再直接存储字符串，而是存储一个压缩列表（ziplist）。

[quicklistNode 1] <-> [quicklistNode 2] <-> [quicklistNode 3] ...

[quicklistNode 1]  ---->  [ziplist 1: item1, item2, item3, ...]
[quicklistNode 2]  ---->  [ziplist 2: item4, item5, item6, ...]
[quicklistNode 3]  ---->  [ziplist 3: item7, item8, item9, ...]

压缩列表（ziplist）是什么？

ziplist是一种特殊的线性数据结构，它被设计用来尽可能地节省内存。它通过紧凑地存储数据，减少了内存碎片和指针开销。

ziplist的结构比较复杂，但是核心思想很简单：

• 连续存储： 所有数据都存储在一块连续的内存区域中，避免了指针的开销。
• 变长编码： 根据数据的大小，采用不同的编码方式，尽可能地减少存储空间。

quicklist的优势

• 减少内存碎片： 多个字符串存储在同一个ziplist中，减少了内存分配的次数，从而减少了内存碎片。
• 节省内存空间： ziplist采用紧凑的存储方式和变长编码，可以有效地节省内存空间。
• 折中性能： 相比于纯链表，quicklist的插入和删除操作可能会更慢一些，但是由于ziplist的长度通常不会太大，所以性能损失是可以接受的。

quicklist的结构

让我们深入了解quicklist的结构。它主要由以下几个部分组成：

字段	类型	描述
head	quicklistNode *	指向quicklist的头节点
tail	quicklistNode *	指向quicklist的尾节点
count	long	quicklist中所有ziplist包含的entry的总个数
len	long	quicklist中ziplist节点的个数
fill	int	每个ziplist节点最多包含的entry个数，或者ziplist的最大大小，取决于list-max-ziplist-size配置
compress	int	是否压缩ziplist节点，0表示不压缩，1表示压缩，取决于list-compress-depth配置

quicklistNode的结构

每个quicklistNode节点都包含一个ziplist：

字段	类型	描述
prev	quicklistNode *	指向上一个quicklistNode节点
next	quicklistNode *	指向下一个quicklistNode节点
zl	ziplist *	指向ziplist
sz	size_t	ziplist占用的总字节数
count	int	ziplist中entry的数量
encoding	int	存储方式，RAW表示ziplist未压缩，LZF表示使用LZF压缩算法压缩
container	int	节点使用的容器类型，目前只支持ziplist
recompress	unsigned int	标记，当使用LZF压缩时，如果节点临时需要解压，则设置该值为1，表示下次访问时需要重新压缩

重要配置参数

有两个重要的配置参数会影响quicklist的行为：

• list-max-ziplist-size： 指定ziplist的最大大小。可以设置为正数或者负数。
  • 正数：表示ziplist中最多可以包含的entry个数。比如设置为5，表示每个ziplist最多包含5个entry。
  • 负数：表示ziplist的最大大小，单位是KB。比如设置为-2，表示每个ziplist的最大大小为2KB。可选项为 -5, -4, -3, -2, -1。-5是特殊情况，代表4KB，-4,-3,-2,-1代表 8KB,16KB,32KB,64KB。
• list-compress-depth： 指定quicklist的压缩深度。0表示不压缩，1表示只压缩首尾节点，2表示压缩首尾的两个节点，以此类推。默认值为0。这个参数的目的是为了在压缩率和访问性能之间找到一个平衡点。因为压缩和解压缩都会消耗CPU资源。

代码示例（简化版）

虽然我们不可能在这里把quicklist的完整代码都贴出来，但是我可以给你展示一些简化的代码片段，让你更好地理解quicklist的实现。

// quicklistNode结构体
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;      // 指向ziplist
    unsigned int sz;       // ziplist占用的字节数
    unsigned int count : 16; // ziplist中entry的数量
    unsigned int encoding : 2;  // RAW==1 or LZF==2
    unsigned int container : 2; // NONE==1 or ZIPLIST==2
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

// quicklist结构体
typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        // 所有ziplist中entry的总数
    unsigned long len;          // quicklistNode的数量
    int fill : 16;              // ziplist的最大entry数或最大大小
    int compress : 16;          // 压缩深度
} quicklist;

// 创建一个新的quicklist
quicklist *quicklistCreate(void) {
    quicklist *ql = zmalloc(sizeof(quicklist));
    ql->head = ql->tail = NULL;
    ql->count = 0;
    ql->len = 0;
    ql->fill = -2; // 默认ziplist大小为8KB
    ql->compress = 0; // 默认不压缩
    return ql;
}

// 向quicklist的头部添加一个元素
void quicklistPushHead(quicklist *ql, void *value, size_t sz) {
    if (!ql->head) {
        // 如果quicklist为空，则创建一个新的ziplist节点
        quicklistNode *node = quicklistCreateNode();
        ql->head = ql->tail = node;
        node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_HEAD);
        node->count = 1;
        ql->len = 1;
        ql->count = 1;
    } else {
        // 如果quicklist不为空，则尝试将元素添加到头节点的ziplist中
        if (ziplistLen(ql->head->zl) < ql->fill) {
            ql->head->zl = ziplistPush(ql->head->zl, value, sz, ZIPLIST_HEAD);
            ql->head->count++;
            ql->count++;
        } else {
            // 如果头节点的ziplist已满，则创建一个新的ziplist节点，并将其添加到quicklist的头部
            quicklistNode *node = quicklistCreateNode();
            node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_HEAD);
            node->count = 1;
            node->next = ql->head;
            ql->head->prev = node;
            ql->head = node;
            ql->len++;
            ql->count++;
        }
    }
}

// 简化的ziplistPush函数 (仅用于演示)
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
    // 在ziplist的头部或尾部添加一个新的entry
    // ... (省略ziplist的具体实现)
    return zl;
}

// 简化的ziplistLen函数 (仅用于演示)
unsigned int ziplistLen(unsigned char *zl) {
    // 返回ziplist中entry的数量
    // ... (省略ziplist的具体实现)
    return 0; // 实际应该返回ziplist中entry的数量
}

// 创建新的quicklistNode
quicklistNode *quicklistCreateNode(void) {
    quicklistNode *node = zmalloc(sizeof(quicklistNode));
    node->prev = node->next = NULL;
    node->zl = ziplistNew();
    node->sz = 0;
    node->count = 0;
    node->encoding = 0;
    node->container = 2; // ZIPLIST
    node->recompress = 0;
    return node;
}

// 创建新的ziplist
unsigned char *ziplistNew(void) {
    // 创建一个新的ziplist
    // ... (省略ziplist的具体实现)
    return NULL; // 实际应该返回指向新ziplist的指针
}

// 示例用法
int main() {
    quicklist *mylist = quicklistCreate();
    quicklistPushHead(mylist, "hello", strlen("hello"));
    quicklistPushHead(mylist, "world", strlen("world"));
    // ...
    return 0;
}

这段代码只是一个非常简化的示例，目的是帮助你理解quicklist的基本结构和操作。真正的quicklist实现要复杂得多，涉及到内存管理、压缩算法、迭代器等等。

总结

quicklist是Redis LIST的底层实现，它结合了链表和压缩列表的优点，既减少了内存碎片，又节省了内存空间。通过调整list-max-ziplist-size和list-compress-depth参数，可以根据实际应用场景，在内存占用和性能之间找到一个平衡点。

一点思考

quicklist的设计体现了Redis对于性能和内存效率的极致追求。它并不是一个“银弹”，而是一种根据特定场景进行优化的数据结构。在实际应用中，我们需要根据数据的特点和访问模式，选择合适的数据结构。

好了，今天的分享就到这里。希望大家对Redis quicklist有了更深入的了解。如果大家还有什么问题，欢迎提问。谢谢大家！