Redis中的List，底层采用了什么数据结构？

Redis中的List，底层采用了什么数据结构？

Redis的List数据结构是一个简单但功能强大的字符串列表，支持在两端进行高效的插入和删除操作。本文将从源码层面深入分析Redis List的内部实现机制，探讨其如何通过压缩列表和双端链表的结合使用，在节省内存和优化操作效率之间取得平衡。

1. Redis List 概述

Redis的List是一个简单的字符串列表，按照插入顺序排序。它支持在列表的两端插入或删除元素，具有以下特点：

• 有序：元素按照插入顺序排列，可以通过索引访问。
• 双端操作：支持从左端（头部）和右端（尾部）进行插入和删除操作。
• 高效：在两端插入和删除的时间复杂度为 O(1)。

常用的List命令包括LPUSH、RPUSH、LPOP、RPOP、LINDEX、LRANGE等。

2. Redis List 的内部实现

Redis的List数据结构内部实现主要依赖于两个数据结构：压缩列表（ziplist）和双端链表（quicklist）。根据List的大小和元素的长度，Redis会自动选择合适的数据结构，以优化存储空间和操作效率。

2.1 压缩列表

压缩列表是一种为节省内存而设计的紧凑数据结构。它将多个元素紧密存储在一个连续的内存块中，适用于小型的List。

• 结构：压缩列表由三个部分组成：ziplist header、entry list 和 ziplist end。
• 性能：适用于含有少量元素且每个元素较短的List，节省内存但在频繁插入和删除时性能较低。

2.2 双端链表

从Redis 3.2版本开始，List的内部实现改为使用quicklist，它结合了压缩列表和双向链表的优点。

• 结构：quicklist是由多个压缩列表（ziplist）组成的双向链表，每个压缩列表称为一个节点（node）。
• 优势：
• 高效插入与删除：在两端插入和删除元素时，只需要操作链表的头部或尾部节点，时间复杂度为 O(1)。
• 节省空间：每个节点内部仍然使用压缩列表存储元素，节省内存。
• 灵活性：适用于包含大量元素的List。

3. 源码分析

下面将通过源码分析Redis List的实现机制，重点关注quicklist相关的代码部分。

3.1 数据结构定义

Redis在src/quicklist.h文件中定义了quicklist相关数据结构：

typedef struct quicklistEntry {
    unsigned char *value; /* value of the entry */
    unsigned int sz; /* length of the value */
    long long longval; /* long representation, if applicable */
    unsigned int encoding:4;
    unsigned int attempted_float_conversion:1;
} quicklistEntry;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl; /* ziplist containing some entries */
    unsigned int sz; /* byte size of ziplist */
    unsigned int count:16;
    unsigned int encoding:4;
    unsigned int container:4;
    unsigned int recompress:1;
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    const quicklistCompress *compress;
    unsigned int count; /* total count of all entries in all the nodes */
    unsigned long len; /* count of all elements */
    unsigned long maxlevel;
    unsigned int fill:16;
    unsigned int compress_depth:4;
    unsigned int mem_compressed:1;
} quicklist;

主要的数据结构包括：

• quicklistEntry：表示quicklist中的一个条目（entry）。
• quicklistNode：表示quicklist中的一个节点，包含一个ziplist。
• quicklist：整个quicklist结构，包含头尾节点、统计信息等。

3.2 常用命令的实现

以下将以LPUSH、RPUSH、LPOP、RPOP、LINDEX、LRANGE等命令为例，分析它们在源码中的实现。

3.3 LPUSH 和 RPUSH

LPUSH和RPUSH用于在List的左端和右端插入元素。它们在quicklist中的实现主要涉及调用quicklistPush函数：

void quicklistPush(quicklist *quicklist, void *value, size_t sz, int where) {
    // 省略参数检查和类型转换
    if (where == QUICKLIST_HEAD) {
        // 插入到链表头部
        // 如果头节点已满，创建新节点
    } else {
        // 插入到链表尾部
        // 如果尾节点已满，创建新节点
    }
    // 使用ziplist插入元素
    // 更新统计信息
}

核心逻辑：

1. 判断插入的位置（头部或尾部）。
2. 检查对应位置的节点是否有足够空间插入新元素。
3. 如果节点已满，创建一个新的节点并插入。
4. 在对应节点的ziplist中插入新元素。
5. 更新quicklist的统计信息。

3.4 LPOP 和 RPOP

LPOP和RPOP用于从List的左端和右端弹出元素。它们主要调用quicklistPopCustom函数：

int quicklistPopCustom(quicklist *quicklist, int where, long long *v, unsigned char **sval, unsigned int *slen) {
    if (where == QUICKLIST_HEAD) {
        // 从头部节点的ziplist弹出元素
        // 如果节点为空，删除节点并移动到下一个节点
    } else {
        // 从尾部节点的ziplist弹出元素
        // 如果节点为空，删除节点并移动到前一个节点
    }
    // 更新统计信息和quicklist结构
}

核心逻辑：

1. 根据弹出的位置，选择头部或尾部节点。
2. 从对应节点的ziplist中弹出元素。
3. 如果节点为空，删除节点并更新链表指针。
4. 更新quicklist的统计信息。

3.5 LINDEX

LINDEX用于获取List中指定索引的元素。它调用quicklistIndex函数：

quicklistEntry *quicklistIndex(quicklist *quicklist, long index) {
    // 处理负索引
    // 遍历quicklist中的节点，累加节点中元素的数量
    // 找到包含目标索引的节点
    // 在节点的ziplist中查找具体的元素
}

核心逻辑：

1. 处理负索引（从尾部开始计数）。
2. 遍历quicklist的节点，累加每个节点的元素数量。
3. 确定目标索引所在的节点。
4. 在该节点的ziplist中查找目标元素。

3.6 LRANGE

LRANGE用于获取List中指定范围的元素。它调用quicklistGetRange函数：

quicklistIter *quicklistGetIterator(quicklist *quicklist, int direction) {
    // 创建一个迭代器，从头部或尾部开始遍历quicklist
}

int quicklistNext(quicklistIter *i, quicklistEntry *entry) {
    // 通过迭代器遍历quicklist中的元素
}

核心逻辑：

1. 创建一个迭代器，指定遍历方向（从头到尾或从尾到头）。
2. 遍历quicklist的节点和节点内的ziplist，收集指定范围的元素。
3. 返回结果集合。

4. 性能优化与选择

Redis在List的内部实现中，通过quicklist结构在节省内存和提高操作效率之间取得了平衡。以下是一些性能优化的考虑：

• 节点大小（fill factor）：quicklist中每个节点的ziplist有一个填充因子（默认是4），决定了多少元素被存储在一个节点中。适当的填充因子可以减少节点数量，提高遍历效率。
• 压缩算法：quicklist支持多种压缩算法，通过配置可以进一步优化内存使用。
• 迭代器机制：通过迭代器遍历quicklist，提高了操作的灵活性和效率。

在选择使用List时，应根据实际需求和数据规模合理设计，避免在极大的List上进行频繁的中间位置插入和删除操作，因为这可能导致性能下降。

5. 为什么List底层有两种实现

List数据结构的底层采用了压缩列表（ziplist）和双端链表（quicklist），其实是内存效率与操作性能之间取得最佳平衡。主要原因如下：

1. 压缩列表

• 内存节省：压缩列表是一种为节省内存而设计的紧凑数据结构。它将多个元素紧密存储在一个连续的内存块中，避免了传统链表中每个节点需要额外指针（如前驱和后继指针）带来的内存开销。对于包含少量元素且每个元素较短的小型列表，压缩列表能够显著减少内存使用量。
• 缓存友好性：由于压缩列表将所有元素存储在一个连续的内存区域中，这种布局有助于提升缓存命中率。CPU在访问数据时，能够更高效地预取和缓存数据，从而提高访问速度。
• 简单数据结构：压缩列表的实现相对简单，适用于不需要频繁插入和删除操作的场景。对于静态或变化不大的小型列表，压缩列表提供了足够的性能和内存效率。

2. 双端链表

• 高效的两端操作：双端链表允许在列表的头部和尾部进行高效的插入和删除操作，时间复杂度为 O(1)。这对于需要频繁在两端进行操作的应用场景（如队列和栈）尤为重要。
• 动态扩展能力：与压缩列表相比，双端链表更适合处理动态变化较大的列表。它能够灵活地在任意位置插入和删除元素，而不会像压缩列表那样需要整体移动内存块。
• 分段存储与性能优化：Quicklist通过将列表分段存储，每个段使用压缩列表（ziplist）作为节点，实现了分块管理。这种设计兼具了压缩列表的内存效率和双端链表的操作性能。具体来说，每个quicklist节点内部是一个压缩列表，多个节点通过双端链表连接起来。这样，在需要进行插入或删除操作时，仅需操作相关的节点，而不影响整个列表结构。

Redis会根据列表的长度和元素的大小，自动决定使用压缩列表还是双端链表。这种智能选择机制确保了在不同场景下都能获得最佳的性能和内存使用率。例如：

• 小型列表：当列表较小且元素较短时，Redis会选择压缩列表，最大化内存节省和缓存效率。
• 大型列表：当列表变得较大或元素较长时，Redis会转而使用quicklist，以提升操作性能和扩展能力。

6. 总结

本文从源码角度分析了Redis的List数据结构，它是一个高效、灵活的数据结构，适用于多种应用场景，如消息队列、任务管理等。通过内部的quicklist结构，Redis在节省内存和优化操作效率方面做出了平衡。通过学习本文，我们也可以发现Redis对性能的追求。