Redis数据结构底层实现详解

引言

Redis之所以能在内存中实现极高的读写性能，除了单线程事件驱动模型外，精心设计的底层数据结构功不可没。Redis对外暴露的五种数据类型（String、List、Hash、Set、Sorted Set）在内部有着多种不同的编码实现，会根据数据特征自动选择最优的底层结构。理解这些底层实现，有助于我们在实际使用中做出正确的设计决策。

Redis 对象系统

每个Redis键值对都通过redisObject结构体表示：

1
2
3
4
5
6
7

typedef struct redisObject {
    unsigned type:4;      // 数据类型: string, list, hash, set, zset
    unsigned encoding:4;  // 编码方式: int, embstr, raw, ziplist, quicklist, ...
    unsigned lru:24;      // LRU时间或LFU计数
    int refcount;         // 引用计数
    void *ptr;            // 指向底层数据结构的指针
} robj;

graph TD
    subgraph "Redis数据类型与编码"
        A[String] --> A1[int]
        A --> A2[embstr]
        A --> A3[raw]

        B[List] --> B1[listpack<br/>Redis 7.0+]
        B --> B2[quicklist]

        C[Hash] --> C1[listpack<br/>Redis 7.0+]
        C --> C2[hashtable]

        D[Set] --> D1[intset]
        D --> D2[listpack]
        D --> D3[hashtable]

        E[Sorted Set] --> E1[listpack]
        E --> E2[skiplist + hashtable]
    end

SDS（Simple Dynamic String）

Redis没有使用C语言原生的字符串（以\0结尾的char数组），而是自己实现了SDS。

SDS 结构

1
2
3
4
5
6
7

// Redis 6.0+ 使用不同头部节省内存
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;        // 已使用长度
    uint8_t alloc;      // 分配的总长度（不含头部和末尾\0）
    unsigned char flags; // 类型标志（sdshdr5/8/16/32/64）
    char buf[];          // 实际数据
};

SDS vs C字符串

SDS 空间预分配策略

1
2
3
4
5

修改后 SDS 长度 < 1MB:
    分配 2 * len + 1 字节

修改后 SDS 长度 >= 1MB:
    分配 len + 1MB + 1 字节

graph LR
    subgraph "SDS空间预分配示例"
        A["原始: len=5, alloc=5<br/>'hello'"] -->|APPEND ' world'| B["扩容后: len=11, alloc=22<br/>'hello world' + 11字节空闲"]
        B -->|APPEND '!'| C["无需扩容: len=12, alloc=22<br/>'hello world!' + 10字节空闲"]
    end

String 的三种编码

1
2
3
4
5
6
7
8
9
10
11

-- int编码: 值为整数且可以用long表示
SET counter 12345
OBJECT ENCODING counter  -- "int"

-- embstr编码: 字符串长度 <= 44字节
SET name "hello"
OBJECT ENCODING name  -- "embstr"

-- raw编码: 字符串长度 > 44字节
SET longstr "this is a very long string that exceeds 44 bytes limit..."
OBJECT ENCODING longstr  -- "raw"

embstr vs raw 的区别：

graph LR
    subgraph "embstr: redisObject和SDS连续内存"
        A[redisObject | SDS header | buf]
    end
    subgraph "raw: 两次内存分配"
        B[redisObject] --> C[SDS header | buf]
    end

embstr只需一次内存分配，且内存连续，对CPU缓存友好。但embstr是只读的，修改时会转为raw编码。

ziplist（压缩列表）

ziplist是一块连续的内存区域，Redis 7.0之前用于小数据量的List、Hash和Sorted Set。

ziplist 内存布局

1
2
3
4
5
6
7
8
9
10

+--------+------+-------+---------+---------+-----+---------+---------+
| zlbytes| zltail| zllen | entry1  | entry2  | ... | entryN  | zlend   |
| 4bytes | 4bytes|2bytes |         |         |     |         | 1byte   |
+--------+------+-------+---------+---------+-----+---------+---------+

每个entry的结构:
+--------------+----------+--------+
| prevlen      | encoding | data   |
| 1或5 bytes   | 1-5bytes |        |
+--------------+----------+--------+

• zlbytes：整个ziplist占用的字节数
• zltail：最后一个entry距起始地址的偏移（支持反向遍历）
• zllen：entry数量（<65535时为精确值）
• prevlen：前一个entry的长度（用于反向遍历）

连锁更新问题

ziplist的一个缺点是可能发生连锁更新（cascade update）：

sequenceDiagram
    participant Z as ziplist
    Note over Z: 所有entry的prevlen都是1字节(前一个entry<254字节)
    Z->>Z: 在头部插入一个>254字节的entry
    Note over Z: entry1的prevlen需要从1字节扩展为5字节
    Z->>Z: entry1长度增加4字节,可能>254字节
    Note over Z: entry2的prevlen也需要扩展...
    Z->>Z: 连锁更新传播到entryN
    Note over Z: 最坏情况O(N^2)

listpack（紧凑列表）

Redis 7.0引入listpack替代ziplist，解决了连锁更新问题：

1
2
3
4
5
6
7

listpack entry结构:
+---------+--------+--------+
| encoding| data   | backlen|
+---------+--------+--------+

关键区别: backlen记录的是当前entry自身的长度(而非前一个entry)
这样修改一个entry不会影响其他entry

quicklist（快速列表）

quicklist是Redis 3.2引入的List底层实现，它是一个由ziplist（或listpack）节点组成的双向链表。

graph LR
    A[quicklist head] --> B[quicklistNode<br/>ziplist/listpack<br/>entry1, entry2, entry3]
    B --> C[quicklistNode<br/>ziplist/listpack<br/>entry4, entry5]
    C --> D[quicklistNode<br/>ziplist/listpack<br/>entry6, entry7, entry8]
    D --> E[quicklist tail]
    B <--> C
    C <--> D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        // 所有entry总数
    unsigned long len;          // quicklistNode数量
    signed int fill : QL_FILL_BITS;  // 每个node的填充因子
    unsigned int compress : QL_COMP_BITS; // 压缩深度
    // ...
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;     // 指向ziplist/listpack
    size_t sz;                // ziplist/listpack的总字节数
    unsigned int count : 16;  // ziplist/listpack中entry的数量
    unsigned int encoding : 2; // RAW or LZF压缩
    // ...
} quicklistNode;

fill参数控制（list-max-ziplist-size）：

1
2
3
4
5
6

fill > 0: 每个ziplist/listpack最多fill个entry
fill = -1: 每个ziplist/listpack最大4KB
fill = -2: 每个ziplist/listpack最大8KB (默认)
fill = -3: 每个ziplist/listpack最大16KB
fill = -4: 每个ziplist/listpack最大32KB
fill = -5: 每个ziplist/listpack最大64KB

compress参数（list-compress-depth）： 压缩深度为N表示两端各N个节点不压缩，中间的节点使用LZF压缩。

1
2
3

compress = 0: 不压缩 (默认)
compress = 1: 两端各1个节点不压缩
compress = 2: 两端各2个节点不压缩

skiplist（跳跃表）

跳跃表是Sorted Set的底层实现之一，支持O(log n)的查找、插入和删除。

跳跃表结构

graph LR
    subgraph "skiplist示例"
        direction LR
        H[Header<br/>L4: →<br/>L3: →<br/>L2: →<br/>L1: →] --> N1["score=1.0<br/>L1: →"]
        H --> N2
        N1 --> N2["score=2.0<br/>L2: →<br/>L1: →"]
        H --> N3
        N2 --> N3["score=3.0<br/>L4: →<br/>L3: →<br/>L2: →<br/>L1: →"]
        N1 --> N2
        N2 --> N4
        N3 --> N4["score=5.0<br/>L1: →"]
        N3 --> N5
        N4 --> N5["score=8.0<br/>L3: →<br/>L2: →<br/>L1: →"]
        N5 --> T[NULL]
    end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef struct zskiplistNode {
    sds ele;                     // 成员值
    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;

层数的随机生成

1
2
3
4
5
6
7
8
9

// 每层的概率为 ZSKIPLIST_P = 0.25
// 最大层数 ZSKIPLIST_MAXLEVEL = 32 (Redis 7.0改为64)
int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
// 平均每个节点 1/(1-0.25) = 1.33 层

为什么Sorted Set用skiplist而不是红黑树

1. 实现简单：跳跃表的实现比红黑树简单得多，更容易调试和维护
2. 范围查询高效：找到起始节点后，沿前进指针遍历即可，时间复杂度O(log n + m)
3. 内存局部性：节点在内存中可以不连续，但通过指针跳跃访问
4. 并发友好：如果需要加锁，跳跃表只需对部分层加锁

intset（整数集合）

当Set的所有元素都是整数且数量较少时，使用intset编码。

1
2
3
4
5

typedef struct intset {
    uint32_t encoding;  // 编码方式: INTSET_ENC_INT16/32/64
    uint32_t length;    // 元素数量
    int8_t contents[];  // 有序整数数组
} intset;

graph TD
    A["SADD myset 1 5 10 3"] --> B["intset encoding=INT16<br/>contents: [1, 3, 5, 10]<br/>有序排列，二分查找O(log n)"]
    B -->|"SADD myset 65536<br/>超过INT16范围"| C["intset encoding=INT32<br/>contents: [1, 3, 5, 10, 65536]<br/>升级编码，所有元素扩展为INT32"]

intset的升级机制： 当新加入的元素类型比当前编码大时，intset会升级编码。升级过程： 1. 按新编码大小扩展数组空间 2. 从后向前将现有元素转换为新编码放到正确位置 3. 添加新元素 4. 更新encoding字段

注意：intset只能升级不能降级。

hashtable（字典）

Redis的字典使用链地址法处理哈希冲突，支持渐进式rehash。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

typedef struct dict {
    dictType *type;
    dictEntry **ht_table[2];   // 两个哈希表，用于rehash
    unsigned long ht_used[2];  // 每个哈希表已使用的节点数
    long rehashidx;            // rehash进度，-1表示未在rehash
    // ...
} dict;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;  // 链表法处理冲突
} dictEntry;

渐进式 Rehash

sequenceDiagram
    participant C as Client
    participant D as Dict

    Note over D: ht_table[0] 负载因子过高, 开始rehash
    D->>D: 分配 ht_table[1] (大小为 ht_table[0] 的 2 倍)
    D->>D: rehashidx = 0

    C->>D: GET key1
    D->>D: 从 ht_table[0] 的 bucket[0] 迁移到 ht_table[1]
    D->>D: rehashidx = 1
    D->>C: 在两个表中查找 key1 返回

    C->>D: SET key2 value2
    D->>D: 迁移 ht_table[0] 的 bucket[1]
    D->>D: rehashidx = 2
    D->>D: 新数据写入 ht_table[1]

    Note over D: ...每次操作迁移一个bucket...

    Note over D: rehash完成
    D->>D: 释放 ht_table[0]
    D->>D: ht_table[0] = ht_table[1]
    D->>D: ht_table[1] = NULL
    D->>D: rehashidx = -1

Rehash触发条件：

1
2
3
4
5
6
7

扩容:
  - 没有在执行 BGSAVE/BGREWRITEAOF 时: 负载因子 >= 1
  - 在执行 BGSAVE/BGREWRITEAOF 时: 负载因子 >= 5
  (负载因子 = ht_used[0] / ht_size[0])

缩容:
  - 负载因子 < 0.1

编码转换规则

flowchart TD
    subgraph String
        S1[int] -->|"不再是整数"| S2[embstr]
        S2 -->|"修改操作"| S3[raw]
        S2 -->|"长度>44"| S3
    end

    subgraph List
        L1[listpack] -->|"元素数>128<br/>或元素大小>64字节"| L2[quicklist]
    end

    subgraph Hash
        H1[listpack] -->|"字段数>128<br/>或值大小>64字节"| H2[hashtable]
    end

    subgraph Set
        T1[intset] -->|"元素非整数<br/>或数量>512"| T2[hashtable]
    end

    subgraph "Sorted Set"
        Z1[listpack] -->|"元素数>128<br/>或元素大小>64字节"| Z2["skiplist + hashtable"]
    end

相关配置参数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# List
list-max-listpack-size -2    # quicklist中每个node的大小限制
list-compress-depth 0         # 压缩深度

# Hash
hash-max-listpack-entries 128  # listpack->hashtable的元素数阈值
hash-max-listpack-value 64     # listpack->hashtable的值大小阈值

# Set
set-max-intset-entries 512     # intset->hashtable的元素数阈值
set-max-listpack-entries 128   # listpack->hashtable的元素数阈值

# Sorted Set
zset-max-listpack-entries 128  # listpack->skiplist的元素数阈值
zset-max-listpack-value 64     # listpack->skiplist的值大小阈值

内存效率优化实践

使用合适的数据结构

1
2
3
4
5

# 查看对象编码
redis-cli OBJECT ENCODING mykey

# 查看内存使用
redis-cli MEMORY USAGE mykey

1
2
3
4
5
6
7
8
9
10
11
12
13

# 小Hash比String更省内存（利用listpack编码）
# 不推荐: 100万个独立key
SET user:1:name "Alice"
SET user:1:age "25"
SET user:1:email "[email protected]"
# 每个key都有redisObject开销

# 推荐: Hash分桶
# 将 user:1 映射到 bucket = 1 / 100 = 0, field = 1
HSET user_bucket:0 1:name "Alice"
HSET user_bucket:0 1:age "25"
HSET user_bucket:0 1:email "[email protected]"
# 每个bucket内使用listpack，大幅减少内存开销

关键内存优化建议

1. 控制key的长度：key本身占用内存，尽量简洁（如u:1:n代替user:1:name）
2. 利用紧凑编码：保持Hash/Set/ZSet的元素数量和大小在阈值内
3. 使用整数ID：Sorted Set的member使用整数ID而非长字符串
4. 选择合适的数据类型：位图用于布尔标记，HyperLogLog用于基数统计
5. 设置过期时间：避免冗余数据长期占用内存

1
2
3
4
5

# 分析Redis内存分布
redis-cli --bigkeys           # 查找大key
redis-cli --memkeys           # 按内存排序
redis-cli INFO memory         # 内存总览
redis-cli MEMORY DOCTOR       # 内存诊断建议

总结

Redis底层数据结构的设计体现了对内存效率和访问性能的极致追求：

• SDS以少量额外空间换取O(1)长度获取、缓冲区安全和二进制安全
• ziplist/listpack通过连续内存和紧凑编码，在小数据量时节省大量内存
• quicklist将ziplist/listpack组织成双向链表，兼顾了内存效率和操作性能
• skiplist以简洁的概率数据结构实现了高效的有序集合操作
• 渐进式rehash避免了一次性rehash导致的服务卡顿
• 编码转换机制根据数据特征自动选择最优的底层实现

理解这些底层实现，能帮助我们在实际项目中做出更好的数据结构选择，充分发挥Redis的性能潜力。