Redis 底层数据结构深度解析（上）：SDS、链表、字典与 Rehash 机制

概述

Redis 不直接使用 C 语言原生字符串，而是构建了 **SDS（Simple Dynamic String）**、**双向链表**、**字典（哈希表）** 等基础数据结构，支撑上层 String、List、Hash、Set、ZSet 五大对象类型。本文深入剖析前三大底层结构的设计精妙。

一、简单动态字符串（SDS）

结构定义

struct sdshdr {
    int len;   // 已用长度
    int free;  // 剩余可用空间
    char buf[]; // 字节数组（柔性数组）
};

vs C 字符串的五大优势

核心策略详解

• 空间预分配：扩容时按 2 倍或固定增量分配 free，减少 realloc 调用。
• 惰性空间释放：缩容不立即 realloc，仅更新 free，供下次增长复用。
• 二进制安全：API 基于 len 而非 \0，完美支持任意二进制数据。

二、双向链表

节点与容器结构

// 节点
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

// 容器
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;

五大特性

1. 双向：prev/next 指针，前驱后继访问 O(1)。
2. 无环：头 prev=NULL，尾 next=NULL。
3. 头尾指针：head/tail，首尾操作 O(1)。
4. 长度计数器：len，获取长度 O(1)。
5. 多态：void* value + 三个函数指针，支持任意类型值的深拷贝、释放、比较。

三、字典 —— 哈希表的 Redis 实现

层级结构

// 1. 哈希表节点
typedef struct dictEntry {
    void *key;
    union { void *val; uint64_t u64; int64_t s64; } v;
    struct dictEntry *next; // 链地址法解决冲突
} dictEntry;

// 2. 哈希表
typedef struct dictht {
    dictEntry **table;      // 数组指针
    unsigned long size;     // 大小
    unsigned long sizemask; // 掩码 (size-1)，用于计算索引
    unsigned long used;     // 已用节点数
} dictht;

// 3. 字典
typedef struct dict {
    dictType *type;         // 类型特定函数（哈希、键值复制/释放/比较）
    void *privdata;         // 私有数据
    dictht ht[2];           // 两个哈希表：正常用 ht[0]，rehash 时用 ht[1]
    int rehashidx;          // rehash 进度索引，-1 表示未进行
} dict;

哈希冲突解决：链地址法

数组索引冲突时，新节点插入链表头部（next 指向旧节点）。

Rehash：渐进式扩容/缩容

负载因子 used/size 超阈值触发扩容，过小触发缩容。

1. 分配 ht[1]：扩容为第一个 ≥ ht[0].used * 2 的 2^n；缩容为第一个 ≥ ht[0].used 的 2^n。
2. 渐进式迁移：rehashidx=0，每次 CRUD 操作顺带迁移 ht[0][rehashidx] 链表至 ht[1]，rehashidx++。
3. 完成：ht[0] 全部迁移完，释放 ht[0]，ht[1] 变 ht[0]，新建空 ht[1]，rehashidx=-1。

渐进式 Rehash 优势

将 O(N) 的集中式迁移分摊到每次操作中，避免单次操作延迟飙升，保证 Redis 高性能特性。

总结

SDS 解决字符串操作的安全与效率；链表提供有序、灵活的序列存储；字典以渐进式 Rehash 的哈希表实现高性能键值映射。这三大基石支撑了 Redis 丰富的上层数据类型与极致性能。