Redis底层数据结构与内部实现

一、RedisDB结构

1、RedisDB在Redis实例中的位置

2、RedisDB结构与核心组件

二、RedisObject结构

1、核心数据结构

1.1 简单动态字符串 (Simple Dynamic String - SDS)

1.2 字典 (Dict / Hash Table)

1.3 双端链表 (Linked List)

1.4 跳跃表 (Skip List)

1.5 压缩列表 (ZipList) - Redis 7.0 起被 Listpack 取代

1.6 紧凑列表 (Listpack) - *Redis 5.0 引入，7.0 成为小规模列表/哈希/有序集合的默认*

1.7 整数集合 (IntSet)

1.8 快速列表 (QuickList) - Redis 3.2 引入

2、对象系统（RedisObject）

2.1 结构信息概览

2.2 核心作用

2.3 类型与编码映射

2.3.1 字符串 (String)

2.3.2 列表 (List)

2.3.3 哈希 (Hash)

2.3.4 集合 (Set)

2.3.5 有序集合 (Sorted Set)

一、RedisDB结构

Redis 的数据库由 redisDb 结构体表示，它是 Redis 存储键值对、管理过期时间、实现阻塞操作、事务以及维护数据库状态的核心数据结构。每个 Redis 实例默认有 16 个独立的数据库（编号 0-15），可通过 SELECT 命令切换。

SELECT <db_index>  # <db_index> 为目标数据库编号（整数）

1、RedisDB在Redis实例中的位置

一个 Redis 服务器实例 (redisServer 结构) 包含一个 redisDb 数组：

struct redisServer {...redisDb *db;       /* 指向一个 dbnum 大小的 redisDb 数组 */int dbnum;         /* 数据库数量 (默认 16) */...
};

客户端状态 (client 结构) 中有一个指针指向其当前选择的数据库：

typedef struct client {...redisDb *db;    /* 指向当前客户端选择的数据库 */...
} client;

当客户端执行 SELECT 2 时，其 db 指针就被设置为指向 server.db[2]。

2、RedisDB结构与核心组件

Redis结构：

typedef struct redisDb {dict *dict;                 /* 核心：键空间（Keyspace），存储所有键值对 */dict *expires;              /* 过期字典：存储键的过期时间（毫秒时间戳） */dict *blocking_keys;        /* 阻塞键：记录因 B[L/R]POP 等命令阻塞的键及等待的客户端 */dict *ready_keys;           /* 就绪键：记录有数据 PUSH 进来、可解除客户端阻塞的键 */dict *watched_keys;         /* 被 WATCH 监视的键：用于事务 CAS 乐观锁 */int id;                     /* 数据库 ID (0-15) */long long avg_ttl;          /* 平均 TTL（统计用） */unsigned long expires_cursor; /* 过期键扫描游标（用于周期性删除） */list *defrag_later;         /* 后续尝试内存碎片整理的键列表 */
} redisDb;

核心组件：

1> dict *dict (键空间 - Keyspace)

作用： 存储该数据库中所有键值对的核心字典。
键 (Key)： Redis 字符串对象（内部是 SDS）。
值 (Value)： 指向 redisObject 结构的指针。redisObject 封装了实际的数据类型（String, List, Hash, Set, ZSet）及其底层实现（SDS, QuickList, Dict, IntSet, SkipList 等）。
操作： 所有对键的增删改查（SET, GET, DEL, EXISTS, KEYS 等）都直接作用于这个字典。

2> dict *expires (过期字典 - Expires Dictionary)

作用： 存储设置了过期时间 (TTL) 的键及其过期时间戳（毫秒精度的 UNIX 时间戳）。
键 (Key)： 与 dict 中的键共享同一个 SDS 对象（指针相同，节省内存）。
值 (Value)： long long 类型的整数，表示键的绝对过期时间戳（pexpireat 设置的时间点）。
关键机制：
- 惰性删除 (Lazy Expiration)： 当访问一个键时（GET, HGET, LRANGE 等命令），Redis 会先检查 expires 字典。如果该键存在且当前时间已超过其存储的时间戳，则立即删除该键（从 dict 和 expires 中移除），然后返回 nil 或错误。这保证了访问到的键总是未过期的。
- 定期删除 (Active Expiration)： Redis 的事件循环 (serverCron 函数) 会周期性（默认每秒 10 次，可配置 hz）地主动扫描 expires 字典：
  - 每次随机抽取一定数量（默认 20 个）的过期键。
  - 删除其中已过期的键。
  - 如果过期键比例超过 25%，则重复此过程。
  - 使用 expires_cursor 记录扫描位置，确保所有键都能被扫描到。
- 过期策略： Redis 结合了惰性删除（确保访问准确性）和定期删除（回收内存）两种策略。

3> dict *blocking_keys (阻塞键字典)

作用： 管理因执行 阻塞式列表弹出命令（如 BLPOP, BRPOP, BRPOPLPUSH）而等待数据的客户端。
键 (Key)： 被阻塞客户端等待的列表键名（SDS）。
值 (Value)： 一个指向链表的指针。该链表中存放了所有因等待这个键的数据而被阻塞的 client 结构（客户端状态）。
原理： 当客户端执行 BLPOP key1 key2 ... timeout 时，如果所有指定列表都为空，客户端会被阻塞。Redis 会将该客户端添加到 blocking_keys 中每个指定 key 对应的阻塞客户端链表中，并设置超时计时器。

4> dict *ready_keys (就绪键字典)

作用： 作为 blocking_keys 的辅助结构，用于高效地处理阻塞解除。
键 (Key)： 一个列表键名（SDS）。
值 (Value)： 通常为 NULL（不重要），存在即表示该键有数据到达。
工作流程：
1. 当有客户端向一个空列表执行 LPUSH, RPUSH 等命令添加数据时，该列表键会被标记为就绪（添加到 ready_keys 字典）。
2. 在 Redis 的事件循环中（beforeSleep 函数），会检查 ready_keys 字典。
3. 对于其中每个就绪键，Redis 会查找 blocking_keys 中该键对应的阻塞客户端链表。
4. 从链表中取出一个（或多个，取决于命令）客户端，向其返回新添加的数据，并解除其阻塞状态。
优点： 避免了在每次 PUSH 命令执行时直接遍历阻塞客户端链表带来的性能开销，将解除阻塞的操作集中处理。

5> dict *watched_keys (监视键字典)

作用： 实现 WATCH 命令，为 Redis 事务提供乐观锁 (CAS - Check And Set) 机制。
键 (Key)： 被客户端 WATCH 的键名（SDS）。
值 (Value)： 一个指向链表的指针。该链表中存放了所有 WATCH 了这个键的 client 结构（客户端状态）。
事务流程：
1. 客户端使用 WATCH key1 key2 ... 监视一个或多个键。
2. 客户端开启事务 (MULTI) 并发送命令队列 (SET, INCR 等)。
3. 客户端提交事务 (EXEC)。
4. 执行 EXEC 前，Redis 检查：
  - 遍历客户端 WATCH 的所有键。
  - 检查这些键在 watched_keys 中的链表是否存在（即键是否被修改？）。
  - 检查键自 WATCH 后是否被其他客户端修改过（通过 redisObject 的 lru 字段或专门的 dirty 标志）。
5. 如果至少有一个被 WATCH 的键被修改过，服务器拒绝执行事务队列 (EXEC 返回 nil)，客户端需要重试。
6. 如果没有被修改，则执行事务队列中的所有命令。
键修改触发： 任何成功修改键值的命令（SET, INCR, LPUSH, DEL 等）在执行后，会遍历 watched_keys 找到该键对应的链表，将其中所有客户端的 REDIS_DIRTY_CAS 标志置位，表示该客户端监视的键已被改动，其事务将在 EXEC 时失败。

6> int id (数据库 ID)

标识该数据库的编号，范围是 0 到 server.dbnum - 1（默认 0 到 15）。
客户端通过 SELECT id 命令在不同数据库间切换。

7> long long avg_ttl (平均 TTL)

数据库所有设置了 TTL 的键的平均剩余生存时间（毫秒）。这是一个统计值，并非实时精确计算，主要用于 INFO 命令输出，帮助管理员了解数据库过期键的大致情况。

8> unsigned long expires_cursor (过期键扫描游标)

用于实现定期删除策略中的渐进式扫描。记录当前扫描 expires 字典的桶索引 (bucket index)，确保每次 serverCron 调用时扫描不同的部分，避免集中扫描导致延迟。

9> list *defrag_later (后续碎片整理列表)

Redis 的内存碎片整理 (MEMORY PURGE / CONFIG SET activedefrag ...) 可能无法一次性完成所有工作。
此列表保存了需要稍后进行碎片整理尝试的键（指向 dict 中键的指针）。
碎片整理过程会逐步遍历这个列表，尝试对键指向的 redisObject 及其底层数据结构（如包含大量小元素的 Hash、List、ZSet）进行内存重排，减少碎片。

二、RedisObject结构

1、核心数据结构

1.1 简单动态字符串 (Simple Dynamic String - SDS)

用途： 存储字符串值、整型数据、键名、缓冲区等。

设计目标： 解决 C 语言原生字符串的缺陷，提高安全性和效率。

关键结构 (简化)：

struct sdshdr {int len;      // 已使用字节长度 (字符串实际长度，不含'\0')int alloc;    // 分配的总字节长度 (不包括 header 和 null terminator)char flags;   // SDS 类型标识 (sdshdr5, sdshdr8, sdshdr16, sdshdr32, sdshdr64)char buf[];   // 柔性数组，存放实际字符串 + '\0'
};

优势：

O(1) 复杂度获取长度： 直接访问 len 字段。C字符串是O(n)。
杜绝缓冲区溢出： 修改前检查 alloc，空间不足自动扩容。
减少内存重分配： 空间预分配 (alloc = len + newlen) 和惰性空间释放策略优化性能。
二进制安全： 可以存储包含 '\0' 的任意二进制数据，靠 len 判断结束。由于二进制数据包括空字符串\0，C没有办法存取二进制数据。
兼容 C 字符串： buf 末尾保留 '\0'，可直接使用部分 C 字符串函数。

1.2 字典 (Dict / Hash Table)

用途： 存储所有键值对、哈希类型数据、Set 类型数据（当元素为字符串且非整数时）等。Redis整个数据库是用字典来存储的。

核心结构：

字典 (dict):

typedef struct dict {dictType *type; // 该字典对应的特定操作函数 (hash, keyDup, keyCompare, ...)void *privdata; // 上述类型函数对应的可选参数dictht ht[2];   // 两张哈希表，存储键值对数据，ht[0]为原生哈希表，ht[1]为 rehash 哈希表long rehashidx; // rehash标识 当等于-1时表示没有在rehash，否则表示正在进行rehash操作，存储的值表示hash表 ht[0]的rehash进行到哪个索引值(数组下标)int iterators;  // 当前运行的迭代器数量
} dict;// 包含对该字典操作的函数指针
typedef struct dictType {// 计算哈希值的函数unsigned int (*hashFunction)(const void *key);// 复制键的函数void *(*keyDup)(void *privdata, const void *key);// 复制值的函数void *(*valDup)(void *privdata, const void *obj);// 比较键的函数int (*keyCompare)(void *privdata, const void *key1, const void *key2);// 销毁键的函数void (*keyDestructor)(void *privdata, void *key);// 销毁值的函数void (*valDestructor)(void *privdata, void *obj);
} dictType;

哈希表 (dictht):

typedef struct dictht {dictEntry **table;      // 哈希桶数组指针（哈希表数组）unsigned long size;     // 哈希表数组大小 (桶的数量，总是 2^n)，初始容量为4，随着k-v增加，新扩容量为当前量的一倍（4，8，16，32）unsigned long sizemask; // 用于映射位置的掩码，值永远等于 (size - 1)，索引值=Hash值&掩码值unsigned long used;     // 已有节点数量，包含next单链表的数据
} dictht;

哈希表节点 (dictEntry):

typedef struct dictEntry {void *key;              // 键union {                 // 值v的类型可以是以下4种类型void *val;uint64_t u64;int64_t s64;double d;} v; struct dictEntry *next; // 指向下一个节点，形成链表 (解决哈希冲突)
} dictEntry;

关键机制：

哈希冲突解决： 链地址法。相同桶内的节点用链表连接。
Rehash：
- 触发条件：
  - 负载因子超标：
    - 当 ht[0].used / ht[0].size > dict_force_resize_ratio（默认 5）时强制扩容
    - 或 used / size > 1 且允许 rehash（无迭代器运行）时建议扩容
  - BGSAVE/BGREWRITEAOF 优化：若正在进行子进程持久化操作，负载因子阈值提升至 5（避免父进程 COW 内存复制）
- 渐进式rehash过程： 渐进式 rehash。分配 ht[1]，将 rehashidx 从 0 开始递增，每次增删改查操作时，顺带将 ht[0] 中 rehashidx 桶的所有键值对迁移到 ht[1]。完成后 ht[1] 变为 ht[0]，重置 ht[1] 和 rehashidx。
  - 步骤1：初始化rehash
    - 分配ht[1] 空间：新容量 = 第一个大于等于 ht[0].used × 2 的 2^n（如 6 → 8，10 → 16）
    - 设置 rehashidx = 0（标记 rehash 开始）
  - 步骤2：分布迁移数据（每次操作迁移一个桶链/链表，分散到多次操作中完）
    - 写操作触发迁移：新增加的数据在新的hash表h[1]
    - 定时任务迁移：将老数据重新计算索引值后迁移到h[1]。
  - 步骤3：完成迁移
    - 当 ht[0].used == 0 时：
      - 释放 ht[0].table
      - 将 ht[1] 赋值给 ht[0]
      - 重置 ht[1] 为空表
      - 设置 rehashidx = -1（标记 rehash 结束）
- 优点： 避免一次性迁移大量数据导致服务停顿。
  
  扩容方式 平均延迟内存峰值适用场景
  传统一次性 rehash 高 1x 小数据集
  Redis 渐进式 rehash 低 2x 生产环境大数据实时服务
- 缩容机制：当 used < size/10 时触发缩容（避免内存浪费）；流程与扩容相同
- 并发安全策略：
  - 查找：同时在 ht[0] 和 ht[1] 中搜索
  - 插入：直接写入 ht[1]（避免重复迁移）
  - 删除/更新：需同时操作两个表
- 扩容过程示例

扩容方式	平均延迟	内存峰值	适用场景
传统一次性 rehash	高	1x	小数据集
Redis 渐进式 rehash	低	2x	生产环境大数据实时服务

假设初始状态：
ht[0]：size=4，used=3（负载因子 0.75）
插入新键值对 → used=4（负载因子=1）触发扩容

操作	ht[0] (size=4)	ht[1] (size=8)	rehashidx
初始状态	[k1,k2,k3,k4]	空	-1
触发扩容	[k1,k2,k3,k4]	分配 size=8	0
迁移桶0（k1,k2）	[NULL,k3,k4]	[k1,k2]	1
迁移桶1（k3）	[NULL,NULL,k4]	[k1,k2,k3]	2
迁移桶2（k4）	全空	[k1,k2,k3,k4]	-1 (完成)

1.3 双端链表 (Linked List)

用途： 列表类型数据、发布订阅、慢查询、监视器、保存多个客户端状态等。

核心结构 (listNode, list):

typedef struct listNode {struct listNode *prev;struct listNode *next;void *value;
} listNode;typedef struct list {listNode *head;listNode *tail;void *(*dup)(void *ptr);    // 节点值复制函数void (*free)(void *ptr);     // 节点值释放函数int (*match)(void *ptr, void *key); // 节点值对比函数unsigned long len;           // 链表长度
} list;

特点： O(1) 复杂度访问头尾节点，支持双向遍历。内存开销相对较高 (每个节点需要 prev/next 指针)。

1.4 跳跃表 (Skip List)

用途： 有序集合 (Sorted Set) 类型数据的底层实现之一。

设计目标： 在链表基础上提供接近平衡树的查找效率 (平均 O(logN))，且实现更简单，范围查询更高效。

基本思想：将有序链表中的部分节点分层，每一层都是一个有序链表。

核心结构 (zskiplistNode, zskiplist):

//跳跃表节点
typedef struct zskiplistNode {sds ele;                    // 成员值 (字符串SDS)double score;               // 分值（排序依据）struct zskiplistNode *backward; // 后退指针 (双向链表)struct zskiplistLevel {struct zskiplistNode *forward; // 前进指针，指向本层的下一个节点unsigned long span;      // 跨度 (到下一个节点的距离)，用于排名} level[];                  // 柔性数组，动态定义层数
} zskiplistNode;typedef struct zskiplist {struct zskiplistNode *header, *tail; // 头尾节点unsigned long length;        // 节点总数 (不包括头节点)int level;                  // 当前最大层数 (不包括头节点层)
} zskiplist;

工作原理：

多层链表结构。最底层 (L0) 包含所有元素，是有序链表。
上层链表是下层的"快速通道"，节点数更少。
插入时随机确定节点的层数 (幂次定律，越高层概率越低)。
查找从最高层开始，比较 score 和 ele，如果下一个节点大于目标值，则下降到下一层继续查找。

优点： 支持高效范围查询 (ZRANGE, ZREVRANGE)，插入删除相对平衡树更简单。

维度	跳跃表 (Skip List)	平衡树 (AVL/RB-Tree)
实现复杂度	✅ 简单（无旋转操作）	❗ 复杂（需处理旋转/再平衡）
范围查询	✅ 天然支持（链表顺序遍历）	🔶 需中序遍历
并发友好性	✅ 更易实现无锁并发	❗ 锁粒度大
内存占用	🔶 略高（存储多层指针）	✅ 更紧凑
性能稳定性	✅ 无最坏情况（概率平衡）	❗ 可能退化为 O(n)
调试与维护	✅ 可视化直观	🔶 结构复杂

1.5 压缩列表 (ZipList) - Redis 7.0 起被 Listpack 取代

用途 (历史)： 小规模列表、哈希、有序集合的紧凑存储。

结构： 一块连续内存，顺序存储多个元素。是一个字节数组，可以包含多个节点（entry）。每个节点可以保存一个字节数组或一个整数。

<zlbytes>: 4 字节，列表总字节数（字节长度）。
<zltail>: 4 字节，列表尾节点偏移量。
<zllen>: 2 字节，节点数量 (超过 65535 时需遍历)。
<entry>: 若干节点。每个节点包含：
- <prevlen>: 前一个节点的长度 (1 或 5 字节)。
- <encoding>: 内容编码 (类型和长度，1/2/5 字节)。
- <content>: 实际数据。
<zlend>: 1 字节，结束标志 0xFF（255）。

优点： 内存紧凑，减少碎片，适合小数据。

缺点 (连锁更新)： 修改中间节点可能导致后续所有节点的 <prevlen> 需要扩展 (1->5 字节)，引发多次内存重分配。这是被 Listpack 取代的主要原因。

1.6 紧凑列表 (Listpack) - Redis 5.0 引入，7.0 成为小规模列表/哈希/有序集合的默认

设计目标： 解决 ZipList 的连锁更新问题，更简单高效。

结构： 也是一块连续内存。

<总字节数>: 4 字节。
<元素数量>: 2 字节。
<元素项>: 若干项。每个元素项：
- <encoding+data>: 编码 (包含数据类型和长度信息) + 实际数据。
- <element-tot-len>: 反向保存 当前元素项的总长度 (从 <element-tot-len> 自身末尾到 <encoding> 开头)。这个长度字段是变长的 (1-5 字节)。
<结束符>: 1 字节 (0xFF)。

关键改进：

消除连锁更新： 每个元素项独立存储自身长度 (<element-tot-len>)，修改一个元素不会影响其他元素的长度字段。
反向长度： <element-tot-len> 存储的是从自己末尾到前一项开头的长度。遍历时从后向前遍历效率更高，查找时通常也是定位到某个位置再前后移动。

1.7 整数集合 (IntSet)

用途： 当集合 (Set) 类型的所有元素都是整数且数量不多时使用（保证元素不重复）。

结构： 一块连续内存。

<encoding>: 4 字节，指定元素类型 (INTSET_ENC_INT16, INT32, INT64)。
<length>: 4 字节，元素数量。
<contents>: 按值大小升序排列的整数数组，类型由 encoding 决定。

特点：

内存效率极高。
插入新元素可能导致升级 (upgrade)：如果新元素超出当前 encoding 的范围，则将整个集合升级到更大的 encoding (如 INT16 -> INT32)，重新分配内存并迁移数据。降级不支持。

1.8 快速列表 (QuickList) - Redis 3.2 引入

用途： 列表 (List) 类型的默认底层实现、发布与订阅、慢查询、监视器等功能。

设计目标： 平衡内存效率和操作性能，替代早期仅使用 ZipList 或 LinkedList 的方案。

结构： 一个由 ZipList (或 Listpack) 构成的双向链表。

typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count;        // 所有节点内元素总数unsigned long len;          // quicklistNode 节点数量，即ziplist的个数int fill: QL_FILL_BITS;     // 单个节点最大容量 (ziplist大小限定，由 list-max-ziplist-size 配置)unsigned int compress: QL_COMP_BITS; // 两端不压缩的节点数 (节点压缩深度设置，由 list-compress-depth 配置)...
} quicklist;typedef struct quicklistNode {struct quicklistNode *prev;    // 指向上一个ziplist节点struct quicklistNode *next;    // 指向下一个ziplist节点unsigned char *zl;          // 指向底层 ZipList 或 Listpack (Redis 7.0+)unsigned int sz;            // zl 指向的 ZipList/Listpack 的字节大小unsigned int count: 16;     // 该节点内元素个数unsigned int encoding: 2;   // 编码方式：1--ziplist，2--quicklistLZF压缩unsigned int container: 2;  // 容器类型（存放数据方式）：NONE, ZIPLIST, LISTPACK (Redis 7.0+)unsigned int recompress: 1; // 是否被压缩过 (临时状态)...
} quicklistNode;

工作原理：

每个 quicklistNode 节点包含一个 ZipList 或 Listpack。每个ZipList（或Listpack）都能存储多个元素。
fill 参数控制单个节点最大元素数或大小。超过限制时分裂节点。
compress 参数控制两端不压缩的节点数。中间节点可使用 LZF 压缩节省内存。
插入/删除操作尽量在节点内部的 ZipList/Listpack 完成。节点过大时分裂，过小时合并相邻节点。

优点： 综合了双向链表 (易于两端操作，节点分裂/合并) 和 ZipList/Listpack (内存局部性好，小数据高效) 的优势，并通过压缩进一步节省内存。

2、对象系统（RedisObject）

Redis 使用 redisObject 结构体来统一表示数据库中的所有值对象 (Value)。

2.1 结构信息概览

typedef struct redisObject {unsigned type:4;      // 对象类型 (REDIS_STRING, REDIS_LIST, REDIS_HASH, REDIS_SET, REDIS_ZSET)unsigned encoding:4;  // 底层数据结构编码 (如 REDIS_ENCODING_INT, REDIS_ENCODING_HT, REDIS_ENCODING_ZIPLIST...)unsigned lru:LRU_BITS; // LRU 时间戳 (或 LFU 计数与时间) - 用于内存淘汰int refcount;          // 引用计数 - 用于内存回收 (垃圾回收)void *ptr;            // 指向底层实现数据结构的指针 (SDS, dict, quicklist, zset...)
} robj;

1> 4位type

对象类型：REDIS_STRING(字符串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合)。

当执行type命令时，便是读取RedisObject的type字段获取对象类型（type key）。

2> 4位encoding：查看对象编码方式

3> 24位lru：lru记录的是对象最后一次被命令程序访问的时间。高16位存储最后被访问时间（分钟级），低8位存储最近访问次数。

4> refcount：记录对象被引用次数。对象创建时 refcount=1，被新程序使用时 +1，不再使用时 -1。当 refcount==0 时，对象占用的内存被回收。

5> ptr：指向具体的数据，比如：set hello world，ptr 指向包含字符串 world 的 SDS

2.2 核心作用

多态性： 相同类型的值对象 (type) 可以根据不同条件使用不同的底层数据结构 (encoding)。命令的实现只需关注 type 和 encoding，调用对应的底层操作函数。
内存管理： refcount 实现引用计数垃圾回收机制。lru 记录对象访问信息，支撑 LRU/LFU 内存淘汰策略。
共享对象： 引用计数允许共享对象 (如小整数 0-9999)，节省内存。

2.3 类型与编码映射

2.3.1 字符串 (String)

REDIS_ENCODING_INT: 整数值 (直接用 ptr 存储，ptr 被强制转换为 long)。
REDIS_ENCODING_EMBSTR: 短字符串 (<=44字节，Redis 3.2+)，redisObject 和 SDS 分配在连续内存。
REDIS_ENCODING_RAW: 长字符串，动态 SDS。