背景

在引入 quicklist 之前，Redis 采用压缩链表（ziplist）以及双向链表（adlist）作为 List 的底层实现

面临的问题：

ziplist：内存紧凑，但插入/删除需要重新分配内存，性能差
adlist：插入/删除性能好，但每个节点都有指针开销，内存利用率低

quicklist的解决方案

结合双向链表和ziplist的优点，保持链表的灵活性，又通过ziplist提高内存效率

实际上是 zipList 和 linkedList 的混合体，将 linkedList 按段切分，每段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来

Quicklist 主体结构

typedef struct quicklist {
    quicklistNode *head;        // 头节点指针
    quicklistNode *tail;        // 尾节点指针
    unsigned long count;        // 所有ziplist中的总条目数
    unsigned long len;          // quicklist节点的数量
    int fill : 16;              // 单个节点的填充因子
    unsigned int compress : 16; // 不压缩的端节点深度
} quicklist;

QuicklistNode 节点结构

typedef struct quicklistNode {
    struct quicklistNode *prev; // 前驱节点
    struct quicklistNode *next; // 后继节点
    unsigned char *zl;          // 指向ziplist的指针
    unsigned int sz;            // ziplist的字节大小
    unsigned int count : 16;    // ziplist中的条目数
    unsigned int encoding : 2;  // 编码方式：RAW=1, LZF=2
    unsigned int container : 2; // 容器类型：NONE=1, ZIPLIST=2
    unsigned int recompress : 1; // 是否临时解压缩
    unsigned int attempted_compress : 1; // 是否尝试过压缩
    unsigned int extra : 10;    // 预留位
} quicklistNode;

核心特性

混合存储

链表结构：使用双向链表连接多个节点
节点内容：每个节点内部使用ziplist存储实际数据
动态调整：根据fill参数动态调整节点大小

智能压缩

LZF压缩：对符合条件的节点进行LZF压缩
压缩策略：只压缩中间节点，保持头尾节点可快速访问
压缩深度：通过compress参数控制不压缩的端节点数量

填充因子控制

static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536};

支持多种预定义的填充级别
根据fill参数自动选择最优的节点大小

性能优势

内存效率

减少指针开销：相比纯链表，减少了指针占用的内存
局部性原理：相关数据存储在连续的ziplist中，提高缓存命中率
压缩存储：通过LZF压缩进一步减少内存占用

操作效率

快速访问：头尾操作O(1)复杂度
批量操作：在单个ziplist内的操作效率高
平衡策略：通过fill参数平衡内存使用和操作性能

内存布局

adlist

listNode1 -> listNode2 -> listNode3 -> ...
   |           |           |
 value1      value2      value3

quicklist

quicklistNode1 -> quicklistNode2 -> quicklistNode3 -> ...
      |               |               |
   ziplist1        ziplist2        ziplist3
   [elem1,2,3]     [elem4,5,6]     [elem7,8,9]

历史演进

早期版本：List使用ziplist + adlist
Redis 3.2+：引入quicklist，结合了双向链表和ziplist的优点
Redis 7.0+：ziplist被listpack替代，quicklist现在使用listpack

关键实现细节

节点大小控制

使用预定义的优化级别来控制节点大小
设置安全限制避免单个ziplist过大

插入策略

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    if (likely(_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        // 在现有头节点中插入
        quicklist->head->zl = ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
    } else {
        // 创建新节点
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
}

压缩机制

REDIS_STATIC int __quicklistCompressNode(quicklistNode *node) {
    if (node->sz < MIN_COMPRESS_BYTES) return 0;
    
    quicklistLZF *lzf = zmalloc(sizeof(*lzf) + node->sz);
    if (lzf_compress(node->zl, node->sz, lzf->compressed, node->sz) == 0 ||
        lzf->sz + MIN_COMPRESS_IMPROVE >= node->sz) {
        zfree(lzf);
        return 0;
    }
    // 压缩成功，更新节点
    zfree(node->zl);
    node->zl = (unsigned char *)lzf;
    node->encoding = QUICKLIST_NODE_ENCODING_LZF;
}

配置参数

Fill 因子

正数：限制每个ziplist的最大条目数
负数：使用预定义的优化级别（-1到-5对应不同大小）

它决定了单个ziplist节点能够容纳多少数据。这个参数直接影响着：

内存使用效率
插入/删除操作的性能
遍历操作的性能
压缩效果

参数取值范围

#define FILL_MAX (1 << 15)  // 32768

void quicklistSetFill(quicklist *quicklist, int fill) {
    if (fill > FILL_MAX) {
        fill = FILL_MAX;
    } else if (fill < -5) {
        fill = -5;
    }
    quicklist->fill = fill;
}

正值范围：0 到 32768
负值范围：-1 到 -5
默认值：-2

两种工作模式

Compress 深度

0：禁用压缩
N：保留头尾N个节点不压缩，中间节点自动压缩

Quicklist 从4.0到最新版本的变化

底层数据结构的重大变革

Redis 4.0 (引入quicklist)

底层容器: 使用 ziplist 作为节点内容
节点字段: zl 指针指向ziplist
容器类型: ZIPLIST=2 (只有ziplist一种类型)

Redis 7.0+ (重大升级)

底层容器: 从ziplist全面迁移到 listpack
节点字段: entry 指针指向listpack (更通用的命名)
容器类型: 新增 PLAIN=1 (单个大元素) 和 PACKED=2 (listpack多元素)

节点结构字段的变化

quicklistNode 结构体变化

// Redis 4.0
typedef struct quicklistNode {
    unsigned char *zl;          // 指向ziplist
    unsigned int sz;            // ziplist大小
    unsigned int container : 2; // ZIPLIST=2
    unsigned int extra : 10;    // 10位扩展位
} quicklistNode;

// Redis 7.0+
typedef struct quicklistNode {
    unsigned char *entry;       // 指向listpack或plain数据
    size_t sz;                  // 使用size_t类型
    unsigned int container : 2; // PLAIN=1, PACKED=2
    unsigned int dont_compress : 1; // 新增：防止压缩标志
    unsigned int extra : 9;     // 减少到9位扩展位
} quicklistNode;

新增的容器类型支持

PLAIN 容器类型

用途: 存储单个大元素，避免listpack开销
优势: 对于大元素，避免listpack的元数据开销
触发条件: 当元素大小超过阈值时自动使用

PACKED 容器类型

用途: 存储多个元素的listpack
优势: 继承listpack的高效内存布局

API接口的变化

函数签名变化

// Redis 4.0
void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl);

// Redis 7.0+
void quicklistAppendListpack(quicklist *quicklist, unsigned char *zl);
void quicklistAppendPlainNode(quicklist *quicklist, unsigned char *data, size_t sz);

新增功能函数

quicklistSetPackedThreshold(): 设置PACKED节点阈值
quicklistAppendPlainNode(): 添加PLAIN类型节点

redis quicklist

背景