Redis 数据类型丨Hash&Set

本文旨在对 Redis 的两种核心数据结构——Hash 与 Set——进行一次从外部应用到内部源码实现的完整、贯通的深度分析。文章将首先介绍其数据模型与应用场景，然后深入到底层的数据结构与编码方式，并直接以 Redis 8.2.1 源码为参照，逐字段解析 dict、dictEntry 及 intset 等核心结构，最终阐明渐进式 Rehash、编码转换等关键机制。本文的目标是为需要深度理解和使用 Redis 的开发者提供一份精确、详尽的技术参考。

Hash

Hash 类型是一种键值（Key-Value）数据结构，其顶层键（key）映射到一个包含多个字段-值（field-value）对的集合。此结构非常适用于对结构化数据（如对象）的建模，因为它允许对单个字段进行原子化的读写操作（HGET, HSET），而无需读取或重写整个对象。

典型应用场景：缓存数据库行记录、存储用户画像、购物车等。

命令清单

标准编码：hashtable

为在不同负载下实现性能与空间的最优平衡，Hash 采用了双重编码策略。其标准实现是 hashtable 编码，即字典结构。

构成 Redis 哈希表的核心是 dict 及其节点 dictEntry 结构，源码可看：dict.c。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 哈希表节点
struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    struct dictEntry *next;   /* 同一哈希桶中的下一个节点 */
};

// 字典/哈希表
struct dict {
    dictType *type;

    dictEntry **ht_table[2]; // 两个哈希表
    unsigned long ht_used[2]; // 已用节点数

    long rehashidx; /* rehash 游标, -1 表示未进行中 */

    /* ... 其他元数据字段 ... */
    signed char ht_size_exp[2]; /* 哈希表大小的指数 (size = 1<<exp) */
    /* ... */
};

dictEntry 构成了哈希表的最小数据单元，即一个键值对。

• void *key：该指针指向实际的键对象，在 Redis 中通常是一个 sds (动态字符串) 结构。
• union v：这是一个关键的性能优化。union 在 C 语言中允许多个成员共享同一块内存。在这里：
  • 当值为指针类型（如另一个 sds 或 Redis 对象）时，使用 void *val。
  • 当值可以被一个 64 位整型或双精度浮点数表示时，Redis 会直接将数据存储在 u64, s64, 或 d 字段中。这避免了一次额外的内存分配和一次指针解引用，对于存储大量小整数值的 Hash 来说，能带来显著的性能提升。
• struct dictEntry *next：这是链地址法解决哈希冲突的直接实现。当多个 key 哈希到同一个桶 (bucket) 时，它们会通过 next 指针形成一个单向链表。

graph LR
    subgraph "哈希桶 (Hash Bucket)"
        Bucket["ht_table[0][i] (指针)"]
    end

    subgraph "dictEntry 1 (链表头)"
        Node1_Key["key: 'user:name'"]
        Node1_Val["v (union): 'Alice'"]
        Node1_Next["next (指针)"]
    end

    subgraph "dictEntry 2 (冲突节点)"
        Node2_Key["key: 'user:email'"]
        Node2_Val["v (union): 'a@b.com'"]
        Node2_Next["next (指针)"]
    end

    Bucket --> Node1_Key;
    Node1_Key -- " " --> Node1_Val;
    Node1_Val -- " " --> Node1_Next;

    Node1_Next --> Node2_Key;
    Node2_Key -- " " --> Node2_Val;
    Node2_Val -- " " --> Node2_Next;

    Node2_Next --> NULL["NULL"];

dict 结构是哈希表的管理器，其设计完全服务于高性能和动态伸缩。

• dictEntry **ht_table[2]：这是整个字典结构的核心。它是一个包含两个元素的数组，每个元素都是一个 dictht (哈希表) 的指针。
  • ht_table[0] 是主哈希表，正常情况下所有数据都存储于此。
  • ht_table[1] 是备用哈希表，仅在进行渐进式 rehash 时使用，用于存放从 ht_table[0] 迁移过来的数据和新写入的数据。
• unsigned long ht_used[2]：这两个字段分别精确地计数 ht_table[0] 和 ht_table[1] 中已有的 dictEntry 数量。
• long rehashidx：这是渐进式 rehash 机制的命脉。
  • 当 rehashidx == -1 时，系统处于非 rehash 状态。
  • 当 rehashidx > -1 时，表示 rehash 正在进行中，其值是当前正在从 ht_table[0] 往 ht_table[1] 迁移的桶的索引。每次迁移一部分数据后，rehashidx 就会递增，直到所有桶迁移完毕，rehashidx 重置为 -1。
• signed char ht_size_exp[2]; 这是一个空间优化。由于 Redis 的哈希表大小总是 2 的幂次方，这里不直接存储大小 size，而是存储其指数 exp (size = 1 << exp)。这使得仅用一个有符号字符就能表示非常大的哈希表尺寸，节省了元数据空间。

graph TD
    subgraph DictStruct ["dict 结构体 (Rehash 进行中)"]
        style DictStruct fill:#FEF9E7,stroke:#9A7D0A
        direction LR

        Field_ht0["ht_table[0] (指针)"]
        Field_ht1["ht_table[1] (指针)"]
        Field_used["ht_used: [5, 3]"]
        Field_rehashidx["rehashidx = 2"]
    end

    subgraph HT0 ["ht_table[0] (旧表)"]
        style HT0 fill:#FFDDDD,stroke:#900
        direction TB
        B0["Bucket 0
(已迁移)"]
        B1["Bucket 1
(已迁移)"]
        B2["Bucket 2"]
        B3["..."]
        BN["Bucket N-1"]
    end

    subgraph HT1 ["ht_table[1] (新表, 容量更大)"]
        style HT1 fill:#D4FCD7,stroke:#070
        direction TB
        NB0["..."]
        NBK["Bucket K
(已迁移数据)"]
        NBL["Bucket L
(新写入数据)"]
        NBM["..."]
    end

    Field_ht0 --> HT0;
    Field_ht1 --> HT1;

    subgraph Cursor["迁移游标"]
        style Cursor stroke-width:3px,stroke:#F39C12,color:#F39C12
        Field_rehashidx -.-> B2;
    end

紧凑编码：listpack 的内存优化

当 Hash 对象包含的元素较少且体积较小时，Redis 会采用 listpack 编码。listpack 是一块连续内存，它将字段和值序列化存储。相较于其前身 ziplist，listpack 通过在每个条目中存储自身长度而非前一节点的长度，从根本上解决了 ziplist 在更新时可能出现的 O(N2) 复杂度的连锁更新问题，保证了操作性能的稳定性。

这里的 listpack 和 ziplist 跟我们在 Redis 数据类型丨 List 丨从双向链表到 Listpack 的演进之路 说的就是一回事！

graph LR;
    subgraph sg1 ["user:1 (Hash Key)"]
        A[listpack encoding];
    end

    subgraph sg_mem ["连续的内存块 (Compact Memory Block)"]
        B("field: name") --> C("value: Alice");
        C --> D("field: age");
        D --> E("value: 30");
    end

    A --> B;

    style sg1 fill:#f9f,stroke:#333,stroke-width:2px

编码转换: listpack 到 hashtable 的转换是单向的，在满足以下任一条件时触发：

1. 元素数量超过 hash-max-listpack-entries（默认 512）
2. 任一值的长度超过 hash-max-listpack-value（默认 64 字节）

复杂度:

• hashtable: HSET/HGET/HDEL 的平均时间复杂度为 O(1)
• listpack: 上述操作的时间复杂度为 O(N)，N 为元素数量

渐进式 Rehash：rehashidx 的运作机制

渐进式 Rehash 是 Redis 为解决单线程模型下扩容阻塞问题的关键机制。该过程完全由 dict 结构中的 ht_table[1] 和 rehashidx 字段协同完成。

1. 启动: 当满足扩容条件，ht_table[1] 被分配空间，rehashidx 从 -1 置为 0。
2. 迁移: 在后续的每次修改型命令中，Redis 会检查 rehashidx。若其不为 -1，则从 ht_table[0] 的 rehashidx 索引位置的桶开始，将数据迁移至 ht_table[1]，然后 rehashidx++。同时，serverCron 周期性任务也会主动进行少量迁移。
3. 操作路由: 在此期间，新增操作直接写入 ht_table[1]，查询操作需检查 ht_table[0] 和 ht_table[1]。
4. 完成: 当 ht_table[0] 的所有数据迁移完毕（rehashidx 到达 ht_table[0] 的容量上限），ht_table[0] 被释放，ht_table[1] 成为新的 ht_table[0]，ht_table[1] 指针置 NULL，rehashidx 重置为 -1。

接下来我们创建一组三联图来尝试展示渐进式 Rehash 的三个关键阶段：开始前、进行中 和 完成后。

第一阶段：Rehash 开始前

此时，所有数据都存放在哈希表 ht[0] 中。随着数据不断写入，ht[0] 的负载因子升高，即将达到触发 rehash 的阈值。ht[1] 尚未被分配任何空间。

graph TD;
    subgraph dict ["字典对象 (dict)"]
        direction LR;
        ht0["ht[0] (旧哈希表)"];
        ht1["ht[1] (新哈希表)"];
    end

    subgraph ht0_buckets ["ht[0] Buckets (大小: N)"]
        direction LR;
        b0["Bucket 0"] -- "k1, v1" --> n1["(Data)"];
        b1["Bucket 1"] -- "k2, v2" --> n2["(Data)"];
        b2["..."];
        bn["Bucket N-1"] -- "kN, vN" --> nN["(Data)"];
    end

    ht0 --> ht0_buckets;
    ht1 --> NULL["NULL"];

    subgraph legend [状态说明]
        L1["ht[0] 已满，即将触发 Rehash"];
    end

    style dict fill:#eee,stroke:#333,stroke-width:2px

第二阶段：Rehash 进行中

这是整个过程的核心。Rehash 被触发后：

1. Redis 为 ht[1] 分配了一个更大的空间（通常是 ht[0] 容量的两倍）。
2. 字典被标记为 "rehash 进行中"。
3. 数据开始从 ht[0] 逐步迁移到 ht[1]。

图解展示了此阶段的关键行为:

• 迁移 (Migration): ht[0] 的 Bucket 0 中的数据 (k1, v1) 已被迁移到 ht[1] 的新位置。
• 查询 (Lookup): 必须先检查 ht[0]，如果不存在，再检查 ht[1]。
• 写入 (Insert): 新的键值对 (k_new, v_new) 被直接写入 ht[1]。
• 更新/删除 (Update/Delete): 对 ht[0] 中现有数据的操作，会顺便触发一小批数据的迁移。

graph TD
    subgraph "Rehash 进行中: 字典状态"
        direction LR

        subgraph dict ["字典对象 (dict)"]
            dht0["ht[0] (旧表指针)"]
            dht1["ht[1] (新表指针)"]
        end

        subgraph ht0 ["ht[0] Buckets (正在被迁移)"]
            style ht0 fill:#FFDDDD,stroke:#900
            b0["Bucket 0
(已迁移)"]
            b1["..."]
            bn["Bucket N-1
(剩余数据)"]
        end

        subgraph ht1 ["ht[1] Buckets (接收新数据和迁移数据)"]
            style ht1 fill:#D4FCD7,stroke:#070
            nb0["..."]
            nbk["Bucket K
(从 ht[0] 迁移而来)"]
            nbl["Bucket L
(新写入的数据)"]
            nb2n["..."]
        end

        dht0 --> ht0
        dht1 --> ht1
    end

    subgraph desc ["此阶段的操作规则"]
        direction LR

        lookup["查询 (Lookup)
1. 先在 ht[0] 中查找
2. 如果找不到，再去 ht[1] 中查找"]
        insert["写入 (Insert)
所有新键值对
一律写入 ht[1]"]
        migrate["迁移 (Migration)
对 ht[0] 中元素的
任何修改或删除操作，
都会触发该元素所在桶(bucket)
的整体迁移"]

    end

    style desc fill:#f5f5f5,stroke:#333

第三阶段：Rehash 完成后

当 ht[0] 中所有的数据都迁移到 ht[1] 后，rehash 过程结束。

1. ht[0] 的内存被释放。
2. ht[1] 成为新的 ht[0]。
3. 字典中的 ht[1] 指针重新指向 NULL，为下一次可能的 rehash 做准备。

graph TD;
    subgraph dict ["字典对象 (dict)"]
        direction LR;
        ht0["ht[0] (新哈希表)"];
        ht1["ht[1]"];
    end

    subgraph ht0_new_buckets ["ht[0] Buckets (大小: 2N)"]
        b1_0["Bucket 0"];
        b1_1["..."];
        b1_k["Bucket K"] -- "k1, v1" --> n1_new["(Data)"];
        b1_l["Bucket L"] -- "k_new, v_new" --> n_new["(Data)"];
        b1_m["..."];
        b1_2n["Bucket 2N-1"];
    end

    ht0 --> ht0_new_buckets;
    ht1 --> NULL["NULL"];

    subgraph legend [状态说明]
        L1["所有数据迁移完毕"];
        L2["ht[1] 成为新的 ht[0]"];
        L3["系统恢复正常状态，等待下一次扩容"];
    end

    style dict fill:#eee,stroke:#333,stroke-width:2px

Set

Set 是一个无序、唯一的字符串元素集合。其核心价值在于高效的成员关系判断（SISMEMBER）和服务器端的集合运算（SINTER, SUNION, SDIFF）。

典型应用场景：标签系统、用户关注/粉丝模型、独立访客统计。

命令清单

Set 同样采用了双重编码策略，分别是 hashtable 和 intset。

标准编码：hashtable

其中 hashtable 完全复用上文所述的 dict 结构。集合中的每个元素被存储为 dictEntry 中的 key，而 union v (值) 部分则被忽略（统一设为 NULL）。这种设计直接利用了 dict 键的唯一性来保证 Set 元素的唯一性，并继承了其 O(1) 的查找性能。

整数集合：intset

当一个 Set 满足以下两个条件时，会采用 intset 编码：

1. 集合中所有元素均为整数。
2. 元素数量未超过 set-max-intset-entries 配置项的阈值（默认为 512）。

intset 是一种自适应整数编码的有序数组。它可以根据存入整数的范围，将内部存储格式动态升级为 int16_t, int32_t 或 int64_t，以最小的内存空间存储数据。成员查找通过二分搜索算法实现。源码可参考：iniset.h。

1
2
3
4
5
6
7
8
9

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length;   // 元素数量
    int8_t contents[]; // 柔性数组成员，存放整数
} intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

• uint32_t encoding; 该字段决定了 contents 数组中每个整数的存储宽度。它的值是 INTSET_ENC_INT16, INTSET_ENC_INT32, 或 INTSET_ENC_INT64 之一。这是 intset 实现自适应编码的核心。

• uint32_t length; 记录集合中整数的个数。

• int8_t contents[]; 这是一个柔性数组成员 (Flexible Array Member)，是 C99 的一个特性。它本身不占用 intset 结构体的空间，仅作为一个指针指向紧随结构体分配的连续内存区域。实际访问时，代码会根据 encoding 字段的值，将 contents 指针强制转换为对应的整数类型指针（如 (int16_t *)is->contents）来读写数据。

  关键特性：contents 数组中的所有整数始终保持有序排列，这使得通过二分查找算法进行成员存在性判断成为可能，时间复杂度为 O(logN)。

graph LR;
    subgraph sg3 ["article:1:likes (Set Key)"]
        A[intset encoding];
    end

    subgraph sg_intset ["有序整数数组 (Sorted Integer Array)"]
        direction LR;
        B(101) --> C(256) --> D(1024) --> E(8192);
    end

    A --> B;

    style sg3 fill:#ccf,stroke:#333,stroke-width:2px

当向一个 intset 添加的新整数无法用当前的 encoding 表示时（例如，向一个 INTSET_ENC_INT16 的集合中添加 65535），会触发 intsetUpgradeAndAdd 函数。 该函数的核心逻辑是：

1. 确定新的、更高精度的编码（如 INTSET_ENC_INT32）。
2. 分配一块足够大的新内存，其大小足以容纳所有旧元素以新编码存储，并外加一个新元素。
3. 遍历旧的 contents 数组，将每个元素从旧编码（如 int16_t）读取出来，然后以新编码（如 int32_t）写入新内存块的相应位置。
4. 在合适的位置插入新元素，维持数组的有序性。
5. 释放旧的 intset 内存，并更新指针指向新的 intset。同时，结构体内的 encoding 和 length 字段也被更新。

结论

Redis 的 Hash 与 Set 数据结构是其高性能和高效率的集中体现。通过在 hashtable 与多种紧凑编码（listpack, intset）之间的动态转换，Redis 在不同数据规模和类型下实现了时空复杂度的优化。核心机制如渐进式 Rehash 则从根本上解决了单线程模型下可能出现的性能瓶颈。

在技术选型时，应基于以下原则：

• Hash: 适用于对实体对象的属性集合进行建模，尤其是需要频繁对单个属性进行读写的场景。
• Set: 适用于需要保证元素唯一性，或进行成员关系判断及集合代数运算的场景。

对这些底层实现的深入理解，是合理设计数据模型、优化 Redis 性能、以及进行精确故障诊断的基础。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章