Redis底层数据构造与内在运作剖析

文章标题：

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检查：

  5. 遍历客户端WATCH的所有键。

  6. 检查这些键在watched_keys中的链表是否存在（即键是否被修改？）。

  7. 检查键自WATCH后是否被其他客户端修改过（通过redisObject的lru字段或专门的dirty标志）。

  8. 如果至少有一个被WATCH的键被修改过，服务器拒绝执行事务队列（EXEC返回nil），客户端需要重试。

  9. 如果没有被修改，则执行事务队列中的所有命令。

• 键修改触发： 任何成功修改键值的命令（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：分布迁移数据（每次操作迁移一个桶链/链表