Redis底层数据结构实现原理详细介绍（源码+图解）
压缩列表的连锁更新是指在 Ziplist 中插入或删除元素时，由于每个 Entry 记录前一个节点的长度（，导致后续多个节点的字段需要连续修改，从而引发多次内存重分配和数据迁移的现象。触发场景：插入或删除元素：当某个 Entry 的长度变化后，后续所有 Entry 的字段都需要更新。长度变化阈值：当某个 Entry 的长度从小于 254 字节变为大于等于 254 字节（或反之），其字段的存储方式会
·
文章目录
- 一、简单动态字符串（SDS, Simple Dynamic String）
- 二、链表（Linked List）
- 三、字典（Dictionary）
- 四、跳跃表（Skip List）
- 五、整数集合（IntSet）
- 六、压缩列表（Ziplist）
- 七、ListPack
- 八、快速链表（QuickList）
- 九、Redis 的数据结构优化
- 总结
Redis 速度为什么快？Redis 对象类型那么多，都是怎么实现的？今天我们就来探探 Redis 的底层数据结构，了解Redis的底层设计。废话不多说，我们来一个个看。
一、简单动态字符串（SDS, Simple Dynamic String）
1. SDS 的概念
SDS 是 Redis 中字符串的底层实现，用于替代 C 语言的传统字符串（以 \0 结尾的字符数组）。SDS 通过优化内存管理、支持二进制数据和高效操作，成为 Redis 字符串的核心数据结构。
2. SDS 的结构
Redis 的 SDS 并不是直接使用 C 语言的字符数组（char[]），而是通过一个结构体来管理字符串的元数据和实际数据。以下是 SDS 的基本结构：
2.1 SDS 基本结构
struct sdshdr {
int len; // 当前字符串的实际长度（不包含末尾的 '\0'）
int free; // 当前字符串的未使用空间（剩余可追加的空间）
char flags; // 不同SDS的头类型，用来控制SDS的头大小
char buf[]; // 实际存储字符串内容的字符数组（柔性数组）
};
-
len：记录buf数组中已使用的字节数，即字符串的实际长度。 -
free：记录buf数组中未使用的字节数，用于后续的字符串拼接或修改操作。 -
flags：记录 SDS 头类型，用来控制SDS的头大小。# flags对应的SDS头类型如下： #define SDS_TYPE_5 0 #define SDS_TYPE_8 1 #define SDS_TYPE_16 2 #define sDS_TYPE_32 3 #define sDS_TYPE_64 4 -
buf[]：字符数组，存储字符串内容，并以\0结尾（兼容部分 C 字符串函数）。
2.2 不同版本的 SDS 结构
Redis 根据字符串长度的不同，定义了多种 SDS 结构体（sdshdr5 到 sdshdr64），根据字符串长度选择不同的 Header 结构，减少内存浪费：
sdshdr5：适用于非常短的字符串（长度小于 32 字节）。sdshdr8：适用于长度小于 2^8（256）的字符串。sdshdr16：适用于长度小于 2^16（65536）的字符串。sdshdr32：适用于长度小于 2^32 的字符串。sdshdr64：适用于超长字符串（最大支持 2^64 字节）。
这些结构体的字段类型不同，但核心思想一致：通过 len 和 free 管理字符串的动态扩展。
2.3 SDS 结构图
3. 为什么实现 SDS 结构
Redis 底层是基于C语言开发，选择实现 SDS 而非直接使用 C 字符串，主要是为了解决以下问题：
3.1 获取字符串长度的性能问题
- C 字符串：获取长度需要遍历字符数组直到遇到
\0，时间复杂度为 O(n)。 - SDS：通过
len字段直接获取长度，时间复杂度为 O(1)。
3.2 缓冲区溢出风险
- C 字符串：在拼接操作（如
strcat）时，如果未分配足够的内存，可能导致缓冲区溢出，破坏相邻内存数据。 - SDS：在 API 操作中会检查内存是否足够，自动扩容以避免溢出。
3.3 内存分配的频繁性
- C 字符串：每次修改字符串（如拼接、截断）都可能需要重新分配内存。
- SDS：通过 空间预分配 和 惰性空间释放 策略，减少内存重分配的次数。
3.4 二进制安全性
- C 字符串：以
\0作为字符串结束标志，无法存储包含\0的二进制数据（如图片、视频）。 - SDS：通过
len字段判断字符串结束，支持存储任意二进制数据。
3.5 兼容 C 字符串函数
- SDS：保留
buf数组的\0结尾，兼容部分 C 字符串函数（如strlen、memcpy），方便与 C 库集成。
4. SDS 的核心特性
4.1 O(1) 时间复杂度获取长度
通过 len 字段直接获取字符串长度，无需遍历字符数组。例如：
// 获取 SDS 字符串长度
size_t sdslen(const sds s) {
struct sdshdr *sh = (void*)(s - sizeof(struct sdshdr));
return sh->len;
}
4.2 空间预分配（Space Preallocation）
当字符串需要扩容时，SDS 会分配额外的未使用空间，减少后续操作的内存分配次数：
- 小字符串（< 1MB）：分配与当前长度相等的未使用空间。例如，字符串长度从 10B 扩展到 20B，
free会增加 10B。 - 大字符串（≥ 1MB）：固定分配 1MB 的未使用空间。
这种策略减少了频繁的内存分配，提高了性能。
4.3 惰性空间释放（Lazy Space Free）
当字符串被缩短时，SDS 不会立即释放多余的空间，而是通过 free 字段记录未使用空间，等待后续操作复用。例如：
// 截断字符串后，free 增加
sds s = sdsempty();
s = sdscat(s, "hello"); // len=5, free=0
s = sdstrim(s, "h"); // len=4, free=1
4.4 二进制安全
SDS 的 buf 数组以 len 字段为判断依据，而非 \0，因此可以安全存储任意二进制数据（如图片、音频）。例如：
// 存储包含 \0 的二进制数据
sds s = sdsnewlen("\x00\x01\x02", 3); // len=3, free=0
4.5 兼容 C 字符串函数
SDS 的 buf 数组以 \0 结尾，可以直接调用部分 C 字符串函数（如 printf、strlen），但需注意：
strlen：返回的是buf中实际字符数（包含\0），而非len。strcpy：需确保目标缓冲区足够大，否则可能导致溢出。
5. SDS 在 Redis 中的应用
SDS 是 Redis 的核心数据结构之一，广泛应用于以下场景：
- 键值对存储：Redis 中所有字符串键和值均基于 SDS 实现。
- AOF 缓冲区：Redis 的 AOF（Append-Only File）持久化机制使用 SDS 缓存写入命令。
- 客户端输入缓冲区：客户端发送的命令和参数通过 SDS 解析和处理。
- 其他数据结构的底层实现：如哈希表、列表、集合等，均可能依赖 SDS 存储字符串类型的键或值。
二、链表（Linked List）
1. Linked List 的概念
Redis链表是一种基于双向无环链表结构实现的高效数据结构，支持O(1)时间复杂度的头尾节点快速访问与增删操作，通过多态设计，链表可以存储任意类型的数据（如字符串、整数等）。
2. Linked List 的结构
Redis 的链表由 listNode 和 list 两个结构体组成：
2.1 链表节点（listNode）
typedef struct listNode {
struct listNode *prev; // 指向前一个节点
struct listNode *next; // 指向后一个节点
void *value; // 节点值（可以是任意类型）
} listNode;
prev和next：双向链表的指针，允许正向和反向遍历。value：节点存储的值，使用void*指针实现多态，支持存储任意类型的数据（如字符串、整数、其他结构体等）。
2.2 链表结构（list）
typedef struct list {
listNode *head; // 指向链表头节点
listNode *tail; // 指向链表尾节点
unsigned long len; // 链表长度（节点数量）
void *(*dup)(void *ptr); // 节点值复制函数
void (*free)(void *ptr); // 节点值释放函数
int (*match)(void *ptr, void *key); // 节点值比较函数
} list;
head和tail：指向链表的头节点和尾节点，支持 O(1) 的头尾操作。len：记录链表的节点数量，获取长度的时间复杂度为 O(1)。dup：此函数用于复制链表节点所保存的值。free：此函数用于释放链表节点所保存的值。match：此函数则用于对比链表节点所保存的值和另一个输入值是否相
等。
2.3 Linked List 的结构图
下图为一个list结构和三个listNode结构组成的链表结构体：
3. Linked List 的实现原理
Redis 的链表基于 listNode 和 list 结构实现，以下是关键操作的实现逻辑：
3.1 插入操作
LPUSH/RPUSH：- 向链表头部（
head）或尾部（tail）插入新节点。 - 更新
head或tail指针，并增加len计数。
- 向链表头部（
LINSERT：- 在指定节点前后插入新节点，需遍历链表查找目标节点。
3.2 删除操作
LPOP/RPOP：- 从链表头部（
head）或尾部（tail）删除节点。 - 更新
head或tail指针，并减少len计数。
- 从链表头部（
LREM：- 删除指定值的节点，需遍历链表并调整指针。
3.3 遍历操作
LRANGE：- 返回指定范围内的节点值，需从
head开始遍历。
- 返回指定范围内的节点值，需从
LINDEX：- 根据索引获取节点值，需从
head或tail遍历。
- 根据索引获取节点值，需从
3.4 阻塞操作
BLPOP/BRPOP：- 当链表为空时，客户端进入阻塞状态，等待新元素插入。
- 实现基于 Redis 的事件驱动模型（如 I/O 多路复用）。
4. Linked List 的核心特性
Redis 链表的设计目标是高效、灵活，以下是其核心特性：
4.1 双向链表
- 双向指针：每个节点包含
prev和next指针，支持正向和反向遍历。 - 无环结构：链表的头节点
prev和尾节点next指向NULL，链表访问以NULL为终点。
4.2 O(1) 时间复杂度操作
- 头尾插入/删除：通过
head和tail指针，插入和删除操作的时间复杂度为 O(1)。 - 长度获取：通过
len字段直接获取链表长度，无需遍历节点。
4.3 多态性
- 通用值类型：节点值使用
void*指针，支持存储任意类型的数据。 - 自定义操作函数：通过
dup、free、match函数，用户可以定义节点值的复制、释放和比较逻辑。
4.4 内存管理
- 动态分配：每个节点独立分配内存，适合存储大小不一的数据。
- 内存碎片：由于节点内存不连续，可能加剧内存碎片化，影响缓存效率。
5. Linked List 的优化
为了优化内存占用和性能，Redis 在 Redis 3.2 版本引入了 QuickList 数据结构，将链表与压缩列表（Ziplist）结合：
5.1 QuickList 的结构
- 双向链表 + Ziplist：
- 每个链表节点（
quicklistNode）存储一个 Ziplist。 - Ziplist 是紧凑的连续内存结构，节省内存。
- 每个链表节点（
- 节点压缩：
- 支持中间节点的压缩（通过 LZF 算法），进一步减少内存占用。
5.2 QuickList 的优势
- 内存效率：Ziplist 减少了链表节点指针的内存开销。
- 性能平衡：避免了传统链表的高内存碎片问题，同时保留双向链表的高效操作。
- 动态调整：
- 通过配置参数（如
list-max-ziplist-size和list-compress-depth）控制 Ziplist 的大小和压缩深度。
- 通过配置参数（如
6. Linked List 在 Redis 中的应用
Redis 链表广泛应用于以下场景：
- 列表对象（List）：Redis 的
LPUSH、RPOP等命令的底层实现。 - 发布订阅（Pub/Sub）消息队列：支持消息的快速入队和出队。
- 任务调度（Task Scheduling）：任务按优先级或时间顺序插入链表，调度器按需执行任务（如延迟队列）。
- 聊天记录存储（Chat History）：聊天室中，新消息追加到链表尾部，用户可读取最新的 N 条消息。
- 缓存最近访问记录（LRU Cache）：缓存最近访问的页面或数据，使用 LRU（Least Recently Used）算法淘汰旧记录。
- 实现栈和队列（Stack & Queue）：
- 栈（Stack）：后进先出（LIFO），通过
LPUSH和LPOP实现。 - 队列（Queue）：先进先出（FIFO），通过
RPUSH和LPOP实现。
- 栈（Stack）：后进先出（LIFO），通过
- 慢查询日志（Slow Log）：Redis 使用链表存储慢查询日志，便于后续分析和监控。
- 客户端输出缓冲区（Output Buffer）：Redis 服务器使用链表构建客户端的输出缓冲区，存储待发送的响应数据。
三、字典（Dictionary）
1. Dictionary 的概念
字典是 Redis 的核心数据结构之一，用于实现键空间（Key Space）和哈希对象（Hash）。通过哈希表（dictht）和渐进式 Rehash 优化性能。
2. Dictionary 的结构
Redis 的字典由三个主要结构体组成：dictEntry、dictht 和 dict。
2.1 dictEntry（哈希表节点）
每个 dictEntry 结构体表示一个键值对（Key-Value Pair），用于解决哈希冲突。
typedef struct dictEntry {
void *key; // 键（可以是字符串、整数等）
union {
void *val; // 值（可以是任意类型）
uint64_t u64; // 无符号64位整数
int64_t s64; // 有符号64位整数
double d; // 浮点数
} v;
struct dictEntry *next; // 指向下一个节点的指针（解决哈希冲突）
} dictEntry;
key：键的指针，支持任意类型（字符串、整数等）。v：值的联合体，支持多种数据类型。next：指针，用于链式存储（解决哈希冲突）。
2.2 dictht（哈希表）
dictht 是哈希表的主体结构，包含一个数组和元数据。
typedef struct dictht {
dictEntry **table; // 哈希表数组（每个元素指向一个 dictEntry 链表）
unsigned long size; // 哈希表大小（数组长度）
unsigned long sizemask; // 大小掩码，用于计算索引，值总是等于size-1
unsigned long used; // 已使用的键值对数量
} dictht;
table：哈希表数组，每个元素是一个dictEntry*指针，指向链表头节点。size：哈希表容量（必须是 2 的幂次）。sizemask：掩码，用于快速计算键的哈希值对应的索引（index = hash & sizemask），sizemask的值总是等于size-1。used：已存储的键值对数量。
2.3 dict（字典）
dict 是字典的主体结构，包含两个哈希表和相关配置。
typedef struct dict {
dictType *type; // 类型特定函数（如哈希函数、键值复制/释放函数）
void *privdata; // 私有数据（传递给类型特定函数的参数）
dictht ht[2]; // 两个哈希表（ht[0] 和 ht[1]，用于渐进式 rehash）
long rehashidx; // rehash 进度（-1 表示未进行 rehash）
unsigned long iterators; // 当前运行的迭代器数量
} dict;
type：指向dictType结构的指针，定义了字典的操作函数（如哈希函数、键值复制/释放函数）。privdata：私有数据，传递给type中的函数。ht[2]：两个哈希表，ht[0]是当前使用的哈希表，ht[1]用于 rehash。rehashidx：rehash 进度，-1表示未进行 rehash。iterators：当前运行的迭代器数量（用于 rehash 时的并发控制）。
2.4 Dictionary 的结构图
- 每个dict包含2个dictht，ht[0]和ht[1]。
- 每个dictht包含一个dictEntry数组，数组内每个元素为一个dictEntry链表。
- 每个dictEntry链表由dictEntry连接组成，每个dictEntry为一个具体的键值，以及指向下一个dictEntry的指针。
3. Dictionary 的哈希算法实现
3.1 MurmurHash2 算法
- 特点：
- 速度快：MurmurHash2 是一种非加密型哈希算法，计算效率高。
- 散列均匀：即使输入的键有规律（如连续数字），也能生成分布均匀的哈希值。
- 32 位或 64 位输出：Redis 通常使用 64 位哈希值（在 64 位系统上）。
- 适用场景：
- Redis 的字典（用于键值对存储）、集合（Set）、哈希（Hash）等数据类型均依赖此算法。
3.2 索引计算
Redis 通过 按位与操作 将哈希值映射到哈希表数组的索引位置：
// 根据情况不同，ht[x]，可以是ht[0]，或者ht[1]
index = hash & dict->ht[x].sizemask;
hash：键的哈希值（通过 MurmurHash2 计算）。sizemask：哈希表的掩码，等于size - 1（size必须是 2 的幂次）。x：当前使用的哈希表（ht[0]或ht[1]，用于渐进式 rehash）。
3.3 哈希与索引计算过程
假设我们有一个键 k0，需要将其插入到 Redis 字典中。
步骤 1：计算哈希值
Redis 使用 MurmurHash2 计算键的哈希值：
hash = dict->type->hashFunction(k0);
假设 k0 的哈希值为 8。
步骤 2：计算索引
哈希表的当前大小为 8，因此 sizemask = 7（即 8 - 1）。通过按位与操作计算索引：
// 根据情况不同，ht[x]，可以是ht[0]，或者ht[1]
index = hash & dict->ht[x].sizemask = 8 & 7 = 0;
此时，键 k0 会被映射到哈希表数组的索引 0 位置。
步骤 3：处理哈希冲突
Redis 使用 链地址法（Separate Chaining） 解决哈希冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来：
- 当两个键的哈希值映射到同一个索引时，新的键值对会以链表形式追加到该索引对应的链表中。
- 插入新键值对时，新节点会插入链表头部（O(1) 时间复杂度）。
- 查找时，需遍历链表比较键是否匹配（最坏情况下 O(N) 时间复杂度）。
// 哈希表数组索引 0 的链表
dictEntry *entry = dict->ht[0].table[0];
while (entry != NULL) {
if (dictCompareKeys(dict, entry->key, k0) == 0) {
// 找到匹配的键
break;
}
entry = entry->next;
}
4. Dictionary 渐进式 Rehash
为了避免一次性扩容或缩容导致的性能问题，Redis 采用 渐进式 rehash 策略：
- 触发条件：
- 插入键值对时，若负载因子（
used / size）超过阈值（默认为 1），触发扩容。 - 删除键值对时，若负载因子过低（默认为 0.1），触发缩容。
- 插入键值对时，若负载因子（
- rehash 步骤：
- （1）rehash初始化：计算并为
ht[1]分配内存空间，让字典同时持有ht[0]和ht[1]两个哈希表。这个哈希表ht[1]的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）。- 如果是扩容操作，那么ht[1]的大小为第一个大于等于
ht[0].used + 1的2^n。（+1是因为当前插入一个key）； - 如果是缩容操作，那么ht[1]的大小为第一个大于等于
ht[0].used的2^n （不得小于4）。
- 如果是扩容操作，那么ht[1]的大小为第一个大于等于
- （2）rehash开始：在字典中维持一个索引计数器变量
rehashidx，并将它的值设置为0，表示rehash工作正式开始。 - （3）rehash执行：将保存在ht[0]中的所有键值对rehash到ht[1]上面，rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
- （4）rehash过程中：在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，会将索引计数器变量
rehashidx+1，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]。- 如果是新增操作，则直接写入ht[1]。
- 如果是查询、修改和删除操作，则会在ht[0]和ht[1]依次查找并执行，确保ht[0]的数据只减不增，随着rehash最终为空。
- （5）rehash结束：随着字典操作的不断执行，当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，最后程序将rehashidx属性的值设为-1，表示rehash操作已完成。
- （1）rehash初始化：计算并为
渐进式 rehash 的优势：
- 分散 rehash 开销，避免阻塞主线程。
- 在迁移过程中，读写操作会同时访问
ht[0]和ht[1]，确保一致性。
5. Dictionary 的核心特性
- 高效率查找：平均时间复杂度为 O(1)。
- 渐进式 Rehash：减少扩容/缩容对性能的影响。
- 链地址法解决冲突：避免哈希冲突导致性能下降。
- 支持多种键值类型：键为字符串，值可以是任意 Redis 对象（如字符串、列表等）。
6. Dictionary 在 Redis 中的应用
Redis 的字典在以下场景中广泛应用：
- Redis 数据库的核心存储：Redis 的数据库本质上是一个字典，用于存储所有的键值对数据。
- 哈希（Hash）数据类型的实现：Redis 的 Hash 类型（如 HSET key field value）底层依赖字典实现。
- 集合（Set）和有序集合（ZSET）：Redis 使用字典实现集合（Set），键为集合元素，值为 NULL（仅表示存在性）；有序集合（ZSET）结合了字典和跳表（Skip List）。
- 过期键管理：Redis 使用字典管理键的过期时间（TTL）。每个数据库维护一个字典 expires，键是用户定义的 key，值是过期时间戳（毫秒）。
- Lua 脚本缓存：Redis 使用字典缓存已加载的 Lua 脚本。键是脚本的 SHA1 哈希值，值是脚本内容。
- 哨兵模式中的主从节点管理：在 Redis 哨兵（Sentinel）模式中，字典用于管理主从节点的状态。键是主节点的名称，值是主节点及其从节点的信息。
四、跳跃表（Skip List）
1. Skip List 的概念
跳跃表（Skip List） 是一种基于 多级链表 的概率型数据结构，通过在有序链表的基础上添加多级索引来加速查找。其核心思想是：
- 分层索引：每一层是一个有序链表，最底层（第0层）包含所有元素，越往上层的元素越稀疏。
- 随机化层数：每个节点的层数通过随机算法生成（如抛硬币法），保证索引分布均匀。
- 快速跳跃：查找时从最高层开始，通过索引快速跳过大量不相关的元素，逐步缩小范围。
2. Skip List 的结构
Redis 的跳跃表通过两个核心结构体实现：zskiplistNode（跳跃表节点）和 zskiplist（跳跃表）。
2.1 节点结构（zskiplistNode）
typedef struct zskiplistNode {
sds ele; // 成员对象（字符串）
double score; // 分值（用于排序）
struct zskiplistNode *backward; // 后退指针（指向前一个节点）
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针（指向下一个节点）
unsigned int span; // 跨度（到下一个节点的距离）
} level[]; // 层级数组（柔性数组）
} zskiplistNode;
ele：存储有序集合的成员（member）。score：成员的分数（用于排序）。backward：后退指针，指向当前节点的前一个节点（仅用于底层链表的反向遍历）。level[]：层级数组，每个层级包含：forward：指向同一层级的下一个节点。span：记录到下一个节点的跨度（用于计算排名）。
2.2 跳跃表结构（zskiplist）
typedef struct zskiplist {
struct zskiplistNode *header; // 表头节点
struct zskiplistNode *tail; // 表尾节点
unsigned long length; // 跳跃表长度（节点数量）
int level; // 当前最大层级（表头节点不计入）
} zskiplist;
header：指向跳跃表的表头节点（始终存在，但不存储数据）。tail：指向跳跃表的表尾节点。length：跳跃表中实际存储的节点数量。level：跳跃表当前的最高层级（用于动态调整层级）。
2.3 Skip List 的结构图
如下图，跳跃表在查询score=2.0的SDS2对象时，跳跃表从header指针指向的表头开始，level[1]沿途经过了2个span跨度为1的节点，所以目标节点在跳跃表中的排名为2。同理，level[4]沿途经过了1个跨度为3的节点，所以排名为3。
- NULL的跨度：指向NULL的所有前进指针的跨度都为0，因为它们没有连向任何节点。
- 节点的后退指针（backward属性）：后退指针用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。
- 节点的分值（score属性）：score是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序。
- 节点、分值与对象的关系：在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）。
3. Skip List 的操作
3.1 插入操作
- 确定层级：通过随机算法（如抛硬币法）生成新节点的层级
level。 - 查找插入位置：从最高层开始，逐层向下查找，直到找到插入位置。
- 更新指针：将新节点插入到对应层级的链表中，并更新前后节点的指针。
- 调整跨度：根据插入位置更新相邻节点的跨度（
span），以支持排名计算。
3.2 查找操作
- 从最高层开始：沿着当前层级的
forward指针向右移动。 - 比较值：若当前节点的值小于目标值，则继续向右；若大于目标值，则下降到下一层。
- 循环直至底层：直到在最底层找到目标节点或确认不存在。
3.3 删除操作
- 查找目标节点：通过查找操作定位到待删除节点。
- 更新指针：逐层删除节点的
forward指针，并更新相邻节点的跨度。 - 清理资源：释放节点占用的内存。
4. Skip List 的随机化设计
跳跃表的层级通过 概率化算法 生成，确保索引分布均匀：
- 随机层级生成规则：
- 最大层级
ZSKIPLIST_MAXLEVEL默认为 32。 - 初始层级为 1。
- 以概率
p=0.25（默认值）决定是否增加层级：若随机数小于p，则层级加 1，直到达到最大层级。
- 最大层级
- 幂次定律：越大的层级出现的概率越低（如层级 1 的概率为 100%，层级 2 为 25%，层级 3 为 6.25%，依此类推）。
这种设计使得跳跃表在平均情况下具有与平衡树（如红黑树）相当的性能，但实现更简单。
Redis 选择跳跃表而非平衡树的原因：
- 实现简单：跳跃表的代码量比平衡树少 50% 以上，维护成本低。
- 范围查询友好：跳跃表的底层链表天然支持顺序遍历。
- 概率化设计：通过随机层级生成，避免复杂的旋转操作。
5. Skip List 的核心特性
- 高效性：插入、删除、查找的时间复杂度均为 O(log N)（平均情况下）。
- 实现简单：相比平衡树（如红黑树），跳跃表的代码实现更简洁。
- 支持范围查询：通过顺序遍历底层链表，可高效处理范围操作（如
ZRANGE）。 - 缓存友好：链表的连续内存布局比树结构更利于 CPU 缓存命中。
6. Skip List 在 Redis 中的应用
Skip List是 Redis 有序集合（ZSet）的底层实现之一，适用于以下场景：
- 有序集合（ZSet）
- ZSet 的混合结构：Redis 的有序集合由 跳跃表 + 哈希表 共同实现：
- 跳跃表：按
score排序，支持范围查询（如ZRANGE、ZREVRANK）。 - 哈希表：存储
member -> score的映射，支持快速查找和更新。
- 跳跃表：按
- 内存共享：
ele和score在跳跃表和哈希表中共享，避免冗余存储。
- 集群节点管理
- Redis 集群使用跳跃表管理主从节点的状态，支持快速查找和排序。
五、整数集合（IntSet）
1. IntSet 的概念
整数集合（IntSet） 是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时（默认不超过 512 个，由 set-max-intset-entries 配置控制），Redis就会使用整数集合作为集合键的底层实现。集合内所有元素按值从小到大有序排列，且无重复。
2. IntSet 的结构
2.1 IntSet 的基本结构
typedef struct intset {
uint32_t encoding; // 编码类型（INTSET_ENC_INT16/INTSET_ENC_INT32/INTSET_ENC_INT64）
uint32_t length; // 元素个数
int8_t contents[]; // 存储元素的连续数组（实际类型由 encoding 决定）
} intset;
encoding：表示元素的存储类型（16位、32位或64位整数）。length：记录了整数集合包含的元素数量，也即是contents数组的长度。contents[]：一个连续的内存块，存储所有元素。元素按值从小到大有序排列，且无重复。- 虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值。
2.2 IntSet 的结构图
假设现在有一个encoding=INTSET_ENC_INT16编码的整数集合，集合中包含五个int16_t类型的元素，其结构图如下：
3. IntSet 的核心特性
3.1 紧凑存储
- 连续内存布局：
contents是一个紧凑的数组，避免了指针开销。 - 变长编码：根据元素的实际大小选择最小的编码方式（如小整数用
int16_t，大整数用int64_t），节省内存。 - 有序性：元素按升序排列，支持二分查找（时间复杂度
O(log N)）。
3.2 自动升级（Upgrade）
当插入的元素类型超出当前编码范围时，IntSet 会自动升级：
- 升级条件：
- 插入的元素值超出了当前编码的最大范围（例如，向
int16_t集合插入32768）。
- 插入的元素值超出了当前编码的最大范围（例如，向
- 升级步骤：
- 扩容数组：根据新元素类型扩展
contents的内存空间。 - 转换类型：将原有元素转换为新类型，并重新排序以保持有序性。
- 更新编码：修改
encoding字段为新的类型。
- 扩容数组：根据新元素类型扩展
- 示例：
// 原 IntSet 存储 int16_t（范围：-32768 ~ 32767） intset *is = intsetNew(); is = intsetAdd(is, 32767, NULL); // 正常插入 is = intsetAdd(is, 32768, NULL); // 触发升级到 int32_t
3.3 不支持降级
整数集合不支持降级操作，一旦对数组进行了升级，即使删除元素后集合满足较小编码的条件，IntSet 也不会降级。这是为了避免频繁的内存分配和数据迁移开销。
4. IntSet 在 Redis 中的应用
IntSet 是 Redis 集合（Set）的底层实现之一，适用于以下场景：
- 小规模整数集合：
- 当集合元素数量 ≤ 512 且全为整数时，Redis 优先使用 IntSet。
- 比如：用户积分、排行榜、用户点赞功能（用户ID为整数）。
- 内存敏感场景：
- 需要极低内存占用的集合操作（如缓存高频访问的整数集合）。
- 触发 IntSet 转换的条件，自动切换到哈希表：
- 元素数量超过
set-max-intset-entries（默认 512）。 - 插入非整数元素（如字符串）。
- 元素数量超过
六、压缩列表（Ziplist）
1. Ziplist 的概念
压缩列表（Ziplist） 是 Redis 6.x 之前的列表（List）和哈希（Hash）对象的底层实现之一，通过紧凑的内存布局优化存储效率。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。
2. Ziplist 的结构
压缩列表（Ziplist ）由 固定头 + 动态节点 + 结尾标记 组成，具体如下：
2.1 固定头（Header）
| 字段名 | 类型 | 长度 | 用途说明 |
|---|---|---|---|
zlbytes |
uint32_t |
4字节 | 整个 Ziplist 占用的字节数。最大值为 2³² - 1。 |
zltail |
uint32_t |
4字节 | 表尾节点相对于起始地址的偏移量，用于快速定位尾部节点。 |
zllen |
uint16_t |
2字节 | 元素个数。若元素数量超过 65535，则需遍历整个 Ziplist 才能计算真实数量。 |
2.2 动态节点（Entry）
每个 Entry 存储实际数据，结构如下：
typedef struct zlentry {
unsigned int prevrawlensize; // 前驱节点长度字段占用字节数
unsigned int prevrawlen; // 前驱节点实际长度
unsigned int lensize; // 当前节点长度字段占用字节数
unsigned int len; // 当前节点实际长度
unsigned int headersize; // 节点头部总大小（prevrawlensize + lensize）
unsigned char *encoding; // 编码类型
unsigned char *p; // 节点数据起始指针
} zlentry;
prevrawlensize和prevrawlen：记录前一个 Entry 的长度，用于反向遍历。- 若前一个 Entry 长度 ≤ 254 字节，
prevrawlensize为 1 字节。 - 若前一个 Entry 长度 ≥ 254 字节，
prevrawlensize为 5 字节（首字节为0xFE，后 4 字节为真实长度）。
- 若前一个 Entry 长度 ≤ 254 字节，
encoding：数据类型和长度编码，支持以下类型：- TINY：0~12 的无符号整数（直接存储在
encoding的低 4 位）。 - STRING：短字符串（长度 ≤ 63 字节）→ 1 字节编码。
- LONG：长字符串（长度 64~4GB）→ 5 字节编码。
- INT16/INT32/INT64：整数类型（直接存储数值）。
- TINY：0~12 的无符号整数（直接存储在
content：实际存储的数据（字符串或整数）。
2.3 结尾标记（zlend）
- 固定值：
0xFF（1 字节），十进制255，标识 Ziplist 的结束。
2.4 Ziplist 的结构图
虽然定义了这个结构体，但是根本就没有使用zlentry结构体来作为压缩列表中用来存储数据节点中的结构，因为，这个结构存小整数或短字符串实在是太浪费空间了。这个结构总共在32位机占用了28个字节(32位机)，在64位机占用了32个字节。这不符合压缩列表的设计目的：提高内存的利用率。因此，在redis中，并没有定义结构体来进行操作，而是定义了一些宏，压缩列表的节点真正的结构如下图ziplistEntry所示：
-
previous_entry_length：记录前一个 Entry 的长度，用于反向遍历。- 若前一个 Entry 长度 ≤ 254 字节，
previous_entry_length为 1 字节。 - 若前一个 Entry 长度 ≥ 254 字节，
previous_entry_length为 5 字节（首字节为0xFE，后 4 字节为真实长度）。
- 若前一个 Entry 长度 ≤ 254 字节，
-
encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节。注：以下表格中的下划线“_”表示留空，而a、b、c、x等变量则代表实际的二进制数据，为了方便阅读，多个字节之间用空格隔开。-
字节数组编码：
编码 编码长度 content 属性保存的值 00xxxxxx 1 字节 长度小于等于63字节的字节数组 01xxxxxx bbbbbbbb 2 字节 长度小于等于16383字节的字节数组 10______ aaaaaaaa bbbbbbbb cccccccc dddddddd 5 字节 长度小于等于4294967295字节的字节数组 -
整数编码：
编码 编码长度 content 属性保存的值 11000000 1 字节 int16_t类型的整数 11010000 1 字节 int32_t类型的整数 11100000 1 字节 int64_t类型的整数 11110000 1 字节 24位有符号整数 11111110 1 字节 8位有符号整数 1111xxxx 1 字节 使用这一编码的节点没有相应的content属性，因为编码本身的xxxx四个位已经保存了一个介于0和12之间的值，所以它无需content属性
-
-
content：负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。
3. Ziplist 连锁更新
3.1 什么是连锁更新？
压缩列表的连锁更新是指在 Ziplist 中插入或删除元素时，由于 每个 Entry 记录前一个节点的长度（previous_entry_length），导致后续多个节点的 previous_entry_length 字段需要连续修改，从而引发多次内存重分配和数据迁移的现象。
触发场景：
- 插入或删除元素：当某个 Entry 的长度变化后，后续所有 Entry 的
previous_entry_length字段都需要更新。 - 长度变化阈值：当某个 Entry 的长度从 小于 254 字节变为大于等于 254 字节（或反之），其
previous_entry_length字段的存储方式会发生变化（1 字节 → 5 字节）。
3.2 连锁更新的触发示例
假设 Ziplist 中有多个连续的 Entry，每个 Entry 的长度为 250~253 字节（previous_entry_length 用 1 字节表示）：
Entry1 (250B) → Entry2 (250B) → Entry3 (250B) → ... → EntryN (250B)
插入操作触发连锁更新：
- 插入新 Entry：在 Entry1 前插入一个长度为 254 字节 的新 Entry（
NewEntry）。 - Entry1 的
previous_entry_length变化：- 原 Entry1 的
previous_entry_length为 1 字节（表示前一个 Entry 长度为 250B）。 - 插入
NewEntry后，Entry1 的previous_entry_length需要变为 5 字节（因为NewEntry长度为 254B ≥ 254）。
- 原 Entry1 的
- Entry1 的长度增加：
previous_entry_length从 1 字节变为 5 字节，导致 Entry1 的总长度增加 4 字节。 - 连锁反应：Entry2 的
previous_entry_length需要更新以反映 Entry1 的新长度（从 1 字节变为 5 字节），进而导致 Entry2 的长度也增加，依此类推，直到最后一个 EntryN。
最终结果：
- 所有后续 Entry 的
previous_entry_length字段都需要修改。 - 每次修改都需要重新分配内存并迁移数据，而每次空间重分配的最坏复杂度为 O(N) ，所以连锁更新的最坏复杂度为 O(N²)。
3.3 连锁更新的影响
- 性能下降：每次插入/删除操作可能需要多次内存重分配和数据迁移，导致操作时间显著增加。
- 最坏情况：当 Ziplist 中有 N 个连续的 Entry 需要更新时，时间复杂度为 O(N²)（每次更新都涉及后续所有 Entry）。
- 内存碎片：频繁的内存重分配可能导致内存碎片，降低内存利用率。
3.4 连锁更新的解决方案
为了解决 Ziplist 的连锁更新问题，Redis 引入了以下优化方案：
3.4.1 QuickList（Redis 3.2+）替代
- 结构：QuickList 是 Ziplist 和双向链表的结合体，将 Ziplist 分片存储在多个节点中。
- 优势：
- 避免单个 Ziplist 太大：通过限制每个 Ziplist 的最大长度（
list-max-ziplist-size），减少连锁更新的可能性。 - 链表节点独立：每个链表节点是一个独立的 Ziplist，插入/删除操作仅影响当前节点内的 Entry，不会波及整个链表。
- 避免单个 Ziplist 太大：通过限制每个 Ziplist 的最大长度（
- 配置项：
list-max-ziplist-size = 512 # 每个 Ziplist 最多存储 512 个 Entry
3.4.2 ListPack（Redis 7.0+）替代
- 改进机制：ListPack 是 Ziplist 的升级版，每个 Entry 仅记录自己的长度，而非前一个 Entry 的长度。
- 优势：
- 消除连锁更新：修改一个 Entry 的长度不会影响后续 Entry 的存储。
- 更高效的插入/删除：无需级联更新，时间复杂度降低到 O(1)（尾部操作）或 O(N)（中间操作，但无级联）。
- 适用场景：Redis 7.0 开始默认使用 ListPack 替代 Ziplist，作为 List、Hash、ZSet 的底层实现。
3.5 如何避免连锁更新？
-
配置优化：
- 限制 Ziplist 大小：
- 通过
list-max-ziplist-size配置项控制每个 Ziplist 的最大长度（或内存大小）。 - 示例：
list-max-ziplist-size = 512 # 最多存储 512 个 Entry
- 通过
- 避免存储大对象：
- 避免在 Ziplist 中存储长度接近 254 字节的 Entry，减少
prevlen字段长度变化的概率。
- 避免在 Ziplist 中存储长度接近 254 字节的 Entry，减少
- 限制 Ziplist 大小：
-
数据结构选择：
- 使用 QuickList 或 ListPack：对于 List、Hash、ZSet 等数据类型，优先使用 Redis 3.2+ 的 QuickList 或 Redis 7.0+ 的 ListPack。
- 避免直接使用 Ziplist：如果数据量较大或频繁更新，应通过上层数据结构（如 List）间接使用 Ziplist，而非直接操作底层 Ziplist。
4. Ziplist 的核心特性
4.1 内存高效
- 连续内存块：所有 Entry 存储在一块连续内存中，避免指针开销。
- 变长编码：根据数据大小动态调整存储长度（如整数直接编码，字符串按长度压缩）。
- 无冗余字段：不存储前后指针，仅通过
previous_entry_length实现双向遍历。
4.2 双向遍历
- 正向遍历：从
zlbytes开始，逐个解析 Entry。 - 反向遍历：利用
zltail定位尾部节点，通过previous_entry_length反向查找前一个节点。
4.3 插入与删除的复杂性
- 插入操作：需要重新分配内存并移动后续数据，时间复杂度为
O(N)。 - 删除操作：直接截断内存，但可能引发 连锁更新（Cascading Update）：
- 当某个 Entry 的
previous_entry_length从 1 字节变为 5 字节时，后续所有 Entry 的previous_entry_length都需更新。 - 例如：插入一个超长字符串，导致相邻节点的
previous_entry_length变化，触发级联修改。
- 当某个 Entry 的
4.4 小端字节序
- 所有字段（如
zlbytes、zltail、zllen）均采用 小端序 存储（低位字节在前）。- 例如：数值
0x1234实际存储为0x34 0x12。
- 例如：数值
5. Ziplist 在 Redis 中的应用
Ziplist 是 Redis 的底层数据结构，广泛用于以下场景：
- 哈希表（Hash）：
- 当键值对数量 ≤ 512 且所有字段为短字符串时，Redis 使用 Ziplist 存储 Hash。
- 列表（List）：
- 在 Redis 3.2 之前，List 直接使用 Ziplist；3.2 之后改为 Quicklist（Ziplist + 双向链表）。
- 有序集合（ZSet）：
- 当元素数量 ≤ 128 且所有成员为短字符串时，ZSet 使用 Ziplist 存储。
七、ListPack
1. ListPack 的概念
ListPack 是一种紧凑且高效的序列化数据结构，专为 小规模数据集合 设计，广泛应用于 Redis 的 Hash、ZSet、List 和 Stream 等数据类型中。
它是 Redis 6.x 引入的新数据结构，逐步取代 Ziplist，在Redis 7.x版本完全替代Ziplist。相比 Ziplist，ListPack 支持更灵活的编码方式（如变长整数编码），优化内存效率和操作性能。
2. ListPack 的结构
ListPack 的结构由 头部（Header） + 动态条目（Entries） + 结尾标记（End Marker） 组成，具体如下：
2.1 头部（Header）
| 字段名 | 类型 | 长度 | 用途说明 |
|---|---|---|---|
tot-bytes |
uint32_t |
4字节 | 整个 ListPack 占用的字节数。 |
num-elements |
uint16_t |
2字节 | 元素个数。若元素数量超过 65535，则需遍历整个 ListPack 才能计算真实数量。 |
2.2 条目（Entry）
每个 Entry 的结构如下：
struct listpackEntry {
unsigned int encoding; // 编码类型（1~5字节）
unsigned char *data; // 实际数据（字符串或整数）
unsigned int element_total_len; // 当前 Entry 的总长度（1~5字节）
};
-
encoding：编码类型，用于描述数据类型和长度。支持以下类型：注：以下表格中的下划线“_”表示留空，而a、b、c、x等变量则代表实际的二进制数据，为了方便阅读，多个字节之间用空格隔开。-
单字节编码：
编码 编码长度 data 属性保存的值 0xxxxxxx 1 字节 表示7位无符号整型，后7位为数据 10xxxxxx 1 字节 表示短字符串，后6位表示长度，最大可以表示63字节的字符串 -
多字节编码：
编码 编码长度 data 属性保存的值 110xxxxx bbbbbbbb 2 字节 表示13位有符号整数 1110xxxx bbbbbbbb 2 字节 后12位表示字符串长度，最大可以表示4095字节的字符串 11110000 aaaaaaaa bbbbbbbb cccccccc dddddddd 5 字节 后4个字节表示字符串长度，用来表示长字符串 11110001 aaaaaaaa bbbbbbbb 3 字节 后2个字节用来表示有符号整数 11110010 aaaaaaaa bbbbbbbb cccccccc 4 字节 后3个字节用来表示有符号整数 11110011 aaaaaaaa bbbbbbbb cccccccc dddddddd 5 字节 后4个字节用来表示有符号整数 11110100 aaaaaaaa bbbbbbbb cccccccc dddddddd eeeeeeee ffffffff gggggggg hhhhhhhh 9 字节 后8个字节用来表示有符号整数（最大 64 位） 11111111 1 字节 结束标记，仅用于 ListPack 结尾
-
-
data：实际存储的数据（字符串或整数）。 -
element_total_len：当前 Entry 的总长度，用于反向遍历时快速定位下一个 Entry 的起始位置。
2.3 结尾标记（end）
- 固定值：
0xFF（1 字节），十进制 255，标识 ListPack 的结束。
2.4 ListPack 的结构图
3. ListPack 的核心特性
3.1 解决连锁更新问题
- Ziplist 的缺陷：Ziplist 中每个 Entry 记录前一个 Entry 的长度（
previous_entry_length），插入或删除操作可能导致后续 Entry 的previous_entry_length字段连续修改（级联更新）。 - ListPack 的改进：ListPack 直接记录当前 Entry 的长度（
element_total_len），修改一个 Entry 不会影响其他 Entry，从而彻底消除连锁更新问题。
3.2 内存高效
- 紧凑编码：通过变长编码（1~9 字节）存储数据类型和长度，减少冗余。
- 无指针开销：所有 Entry 存储在一块连续内存中，避免指针和链表节点的额外开销。
- 小端字节序：字段存储采用小端序（低位字节在前），提升解析效率。
3.3 高性能
- 快速插入/删除：由于无需级联更新，插入/删除操作的时间复杂度为 O(1)（尾部操作）或 O(N)（中间操作，但无级联）。
- 双向遍历：通过
element_total_len可快速定位前后 Entry，支持正向和反向遍历。 - 原地更新：修改数据时，若新数据长度不超过原空间，可直接覆盖原数据区域，避免内存重分配。
3.4 灵活的数据类型支持
- 字符串：支持长度为 1~4GB 的字符串。
- 整数：支持 7 位、13 位、21 位、33 位、65 位等有符号整数。
- 混合类型：同一个 ListPack 可存储多种类型的数据（字符串 + 整数）。
4. ListPack 在 Redis 中的应用
ListPack 是 Redis 的底层数据结构，广泛应用于以下场景：
- Hash 类型：
- 当字段数量 ≤ 128 且每个字段值 ≤ 64 字节时，Redis 使用 ListPack 存储 Hash。
- ZSet（有序集合）：
- 当元素数量 ≤ 128 且每个成员值 ≤ 64 字节时，Redis 使用 ListPack 存储 ZSet。
- List 类型：
- Redis 7.0+ 的 List 默认使用 QuickList（ListPack + 双向链表）。
- Stream 类型：
- Stream 的消息列表使用 ListPack 存储。
5. ListPack 与 Ziplist 的对比
| 特性 | ListPack | Ziplist |
|---|---|---|
| 连锁更新 | 无 | 有（修改一个 Entry 可能引发级联更新） |
| 内存效率 | 更高（无冗余字段，紧凑编码） | 较高（连续内存，但存在 previous_entry_length 开销） |
| 插入/删除性能 | O(1)（尾部）或 O(N)（中间，无级联） | O(N)（需级联更新） |
| 数据类型支持 | 字符串、整数、混合类型 | 字符串、整数 |
| 适用场景 | 小规模数据集合（Hash、ZSet、List） | 小规模数据集合（旧版 Redis 6.x） |
| 兼容性 | Redis 7.0+ 默认使用 | Redis 6.x 及以下版本 |
八、快速链表（QuickList）
1. QuickList 的概念
QuickList 是 Redis 3.2 引入的一种混合数据结构，结合了 双向链表（Linked List） 和 压缩列表（Ziplist） 的优点。它的设计目标是在 内存效率 和 操作性能 之间取得平衡，特别适合实现 Redis 的 List 类型。
2. QuickList 的结构
Redis 的 QuickList 由 双向链表（quicklist）、 链表节点（quicklistNode）、压缩列表（ziplist）、LZF压缩列表（quicklistLZF） 结构体组成。
2.1 LZF压缩列表（quicklistLZF）
quicklistLZF 结构体是Redis QuickList实现压缩功能的核心组件，通过存储压缩ziplist后的数据和原始大小信息，在内存优化与访问性能之间取得了平衡。
头尾节点保留不压缩，保证高频的头尾操作（如LPUSH/RPUSH）不受压缩影响。仅在访问被压缩的中间节点时触发解压，且解压速度极快（LZF算法设计目标）。
typedef struct quicklistLZF {
unsigned int sz; // 原始ziplist未压缩时的总字节数
char compressed[]; // 压缩后的字节数组（使用LZF算法）
} quicklistLZF;
sz：记录原始ziplist未压缩时的总字节数。在解压缩时，用于验证解压后的数据是否完整（解压后的字节数应等于sz）。compressed[]：存储使用LZF算法压缩后的字节数据。
2.2 链表节点（quicklistNode）
typedef struct quicklistNode {
struct quicklistNode *prev; // 前驱节点指针
struct quicklistNode *next; // 后继节点指针
unsigned char *zl; // 指向ziplist或quicklistLZF的指针
unsigned int sz; // ziplist的总字节数（压缩前）
unsigned int count : 16; // ziplist中的元素数量（最多65535）
unsigned int encoding : 2; // 编码类型（1=RAW，2=LZF压缩）
unsigned int container : 2; // 容器类型（固定为2=ZIPLIST）
unsigned int recompress : 1; // 是否需要重新压缩
unsigned int attempted_compress : 1; // 测试用标志
unsigned int extra : 10; // 扩展字段（未使用）
} quicklistNode;
prev：指向链表上一个节点。next：指向链表下一个节点。zl：若未压缩，指向ziplist结构。若压缩，指向quicklistLZF结构（包含压缩后的数据）。sz：记录ziplist的总字节数（压缩前的大小，即使数据被压缩）。count：记录ziplist中的元素数量，最大支持65535个元素。encoding：表示节点数据是否被压缩。- 1：未压缩（RAW）。
- 2：使用LZF算法压缩（LZF）。
container：固定为2，表示使用ziplist作为容器。recompress：标记节点是否需要重新压缩。- 1：需要重新压缩（如数据被临时解压后需恢复压缩）。
attempted_compress：测试用标志，标记节点是否尝试过压缩但失败（如数据过小无法有效压缩）。extra：预留扩展字段，目前未使用。
2.3 双向链表（quicklist）
// QuickList 结构
typedef struct quicklist {
quicklistNode *head; // 指向链表头节点的指针
quicklistNode *tail; // 指向链表尾节点的指针
unsigned long count; // 所有节点中元素的总数
unsigned long len; // 链表中节点的数量
int fill : QL_FILL_BITS; // 节点填充因子（16位）
unsigned int compress : QL_COMP_BITS; // 压缩深度（16位）
unsigned int bookmark_count; // 快照节点数量
quicklistBookmark bookmarks[]; // 快照节点数组（可选）
} quicklist;
-
head：指向链表的头节点，支持O(1)时间复杂度的头部插入和删除。 -
tail：指向链表的尾节点，支持O(1)时间复杂度的尾部插入和删除。 -
count：记录所有节点中元素的总数（即所有ziplist中元素数量的总和）。 -
len：记录链表中节点的数量（即quicklistNode的数量）。 -
fill：控制每个ziplist节点的最大容量，通过list-max-ziplist-size参数配置，具体如下：fill 值 描述 -1 每个 quicklistNode 节点的 ziplist 所占字节数不能超过 4kb。 -2 默认值，每个 quicklistNode 节点的 ziplist 所占字节数不能超过 8kb。 -3 每个 quicklistNode 节点的 ziplist 所占字节数不能超过 16kb。 -4 每个 quicklistNode 节点的 ziplist 所占字节数不能超过 32kb。 -5 每个 quicklistNode 节点的 ziplist 所占字节数不能超过 64kb。 任意正数 表示：ziplist 结构所最多包含的 entry 个数，最大为 215215。 -
compress：控制节点的压缩深度，通过list-compress-depth参数配置。- 0：不压缩任何节点。
- n：n为正整数（最大65535），链表的前 n 个节点和后 n 个节点不压缩，剩余的中间节点使用 LZF 算法压缩。若 n 超过链表节点总数的一半，则所有节点均不压缩（避免压缩过小数据导致性能损失），等效于 compress=0。
-
bookmark_count：记录bookmarks[]数组的数量。 -
bookmarks[]：记录bookmarks[]数组存储快照节点。bookmarks[]是一个可选字段，quicklist 用来重新分配内存空间时使用，不使用时不占用空间。
2.4 QuickList 的结构图
3. QuickList 的核心特性
3.1 分段存储（Segmented Storage）
- 分段设计：QuickList 将大列表分割成多个 ziplist 节点，每个节点存储一定数量的数据项。
- 优点：
- 内存效率：ziplist 是紧凑的连续内存结构，减少指针和元数据的开销。
- 操作性能：链表结构允许快速插入/删除操作（O(1) 或 O(N)），而 ziplist 提供了高效的遍历能力。
3.2 配置参数
QuickList 的行为通过两个关键配置参数控制：
list-max-ziplist-size：- 正数：限制每个 ziplist 最多存储的元素个数（默认 8）。
- 负数：以内存大小限制 ziplist（例如
-1表示 4KB，-5表示 64KB）。 - 作用：控制单个 ziplist 的大小，避免因数据过多导致操作性能下降。
list-compress-depth：- 作用：指定从链表两端不压缩的节点数（默认 0，表示不压缩）。
- 压缩机制：中间的 ziplist 会被压缩存储，减少内存占用，但会增加访问时的解压开销。
3.3 插入与删除操作
- 头部/尾部插入（LPOP/RPUSH）：
- 时间复杂度为 O(1)，直接操作链表的头或尾节点。
- 中间插入/删除：
- 时间复杂度为 O(N)，需要定位到对应的 ziplist 并操作。
- 性能优化：通过 ziplist 的紧凑存储减少内存碎片，同时通过链表的分段设计降低操作对整个列表的影响。
3.4 内存优化
- 紧凑存储：ziplist 的连续内存布局减少了指针开销，比传统链表节省 50% 以上的内存。
- 压缩机制：中间节点的 ziplist 可被压缩（如 LZF 或 Snappy），进一步降低内存占用。
- 动态调整：当数据量超过配置阈值时，QuickList 会自动将 ziplist 拆分成多个节点。
4. QuickList 在 Redis 中的应用
QuickList 主要用于 Redis 的 List 类型，典型场景包括：
- 队列（Queue）：
- 高频的
LPUSH/RPOP操作（如消息队列、任务调度）。
- 高频的
- 日志聚合：
- 在尾部追加日志条目（
RPUSH），定期清理旧日志（LTRIM）。
- 在尾部追加日志条目（
- 排行榜（Leaderboard）：
- 虽然 ZSET 通常使用跳表（SkipList），但小规模排行榜可能使用 QuickList。
- 缓存标签：
- 存储标签集合（如用户兴趣标签、商品分类标签）。
5. QuickList 与 Ziplist 的对比
| 特性 | QuickList | Ziplist |
|---|---|---|
| 数据结构类型 | 双向链表 + ziplist | 紧凑的连续内存结构 |
| 内存效率 | 高（ziplist 紧凑存储 + 链表分段） | 高（无指针开销） |
| 操作性能 | 插入/删除 O(1)（两端），查找 O(N) | 插入/删除 O(N)（需移动元素），查找 O(N) |
| 连锁更新问题 | 无（QuickList 不依赖前一个节点的长度） | 有（修改一个 Entry 会级联更新后续 Entry） |
| 适用场景 | Redis List（默认实现） | Redis Hash、ZSet（旧版实现） |
| 动态扩展性 | 支持（自动拆分/合并 ziplist） | 不支持（固定大小） |
九、Redis 的数据结构优化
-
Listpack 替代 Ziplist：
- 从 Redis 5.1 引入
listpack，6.x 作为过渡阶段，7.0 完全替代ziplist。 listpack提供更高效的内存布局和操作性能。
- 从 Redis 5.1 引入
-
多线程 I/O：
- Redis 6.x 引入多线程处理网络 I/O，但数据操作仍为单线程，确保一致性。
- 提升高并发场景下的吞吐量。
-
RESP3 协议：
- 支持更复杂的数据类型（如流、映射），提升客户端与服务端的交互效率。
总结
Redis 的底层数据结构通过灵活的组合和优化，实现了高性能与内存效率的平衡。不同数据结构的选择取决于具体场景：
- 小数据：使用压缩列表（Ziplist）或 ListPack。
- 有序集合：使用跳跃表（Skip List）。
- 键值存储：使用字典（Hash Table）。
- 字符串操作：使用简单动态字符串（SDS）。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
5
0- 0
已为社区贡献6条内容
所有评论(0)