深度剖析Redis关键数据结构

动态字符串SDS

字符串是Redis中常用的数据结构之一。

C语言字符串的局限

Redis未直接采用C语言原生字符串，原因在于C语言字符串存在以下弊端：

• 长度获取：需线性时间复杂度(O(n))遍历数组来获取长度。
• 非二进制安全：以\0作为结束标识，致使字符串无法容纳含\0的二进制数据，像图片、音频等无法存储。
• 操作不便：不可直接修改，进行拼接等操作时需手动处理内存，存在风险。

SDS详解

Redis构建了简单动态字符串（SDS）来替代C语言字符串。

SDS结构

Redis用C语言实现，SDS是结构体，源码示例：

struct __attribute__ ((packed)) sdshdr8 {  
    uint8_t len; /* buf中已存字符串字节数，不包含结束标记 */  
    uint8_t alloc; /* buf申请的总字节数，不包含结束标记 */  
    unsigned char flags; /* 用于区分不同SDS头类型，控制头大小 */  
    char buf [];  
};

为适配不同存储需求，还有sdshdr16、sdshdr32、sdshdr64等，数字对应int的位长，sdshdr5已弃用。各成员变量作用如下：

例如，存储字符串“name”的SDS结构示意：

动态扩容

SDS具动态扩容能力。通过alloc-len计算剩余空间，判断缓冲区是否能满足操作。空间不足时，Redis会自动扩展。扩容规则：若所需长度小于1MB，按翻倍扩容；超过1MB则进行内存预分配，新增长度为原长度加1MB，减少频繁内存分配，优化性能。示例代码：

hisds hi_sdsMakeRoomFor(hisds s, size_t addlen) 
{ 
    ...
    // 若剩余空间足够，直接返回
    if (avail >= addlen) return s; 
    // 获取当前长度
    len = hi_sdslen(s); 
    sh = (char *)s - hi_sdsHdrSize(oldtype); 
    // 计算扩展后至少需的长度
    newlen = (len + addlen); 
    // 根据新长度分配空间
    if (newlen < HI_SDS_MAX_PREALLOC)
        newlen *= 2; 
    else
        newlen += HI_SDS_MAX_PREALLOC; 
        ... 
}

SDS解决了C字符串的问题：获取长度通过len实现(O(1))时间复杂度；二进制安全靠遍历len个字符；支持动态扩容，减少内存分配次数。

IntSet

IntSet是Redis中set集合的一种实现，基于整数数组，具长度可变、有序等特性。

结构

typedef struct intset {
    uint32_t encoding;/* 编码方式，支持16位、32位、64位整数 */
    uint32_t length;/* 元素个数 */
    int8_t contents[];/* 整数数组，存储集合数据 */
} intset;

其中encoding有三种模式，对应不同整数大小：

/* 编码有序，INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64 */
#define INTSET_ENC_INT16(sizeof(int16_t))/* 2字节整数，类似Java的short */
#define INTSET_ENC_INT32(sizeof(int32_t))/*4字节整数，类似Java的int */
#define INTSET_ENC_INT64(sizeof(int64_t))/* 8字节整数，类似Java的long */

元素按升序存储在contents数组，结构示例：

IntSet升级

以元素为[5,10,20]（编码为INTSET_ENC_INT16）为例，添加50000时会升级编码。流程：

1. 升级编码为INTSET_ENC_INT32，扩容数组，计算所需空间。
2. 倒序拷贝原数组元素到新位置，避免覆盖。
3. 插入新元素到数组末尾。
4. 更新编码和长度属性。

部分源码示例：

intset *intsetAdd(intset *is,int64_t value,uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value); // 获取值编码
    uint32_t pos; // 插入位置
    if(success) *success=1;
    // 若编码超出当前IntSet编码，升级
    if(valenc >intrev32ifbe(is->encoding)) {
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 查找元素位置
        if(intsetSearch(is,value,&pos)) {
            if(success) *success =0; // 找到则不插入
            return is;
        }
        // 扩容数组
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        // 移动元素腾出空间
        if(pos <intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }
    // 插入新元素
    intsetSet(is,pos,value);
    // 更新元素长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;
    // 更新编码
    is->encoding = intrev32ifbe(newenc);
    // 扩容数组
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* 倒序拷贝元素 */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* 插入新元素 */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    // 更新长度
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

IntSet特点：元素唯一有序、支持类型升级、底层用二分查找。

Dict

Redis键值映射靠Dict实现。

结构

Dict由哈希表（dictht）、哈希节点（dictEntry）、字典（dict）组成。

typedef struct dictht {
    dictEntry **table; // entry数组，元素是指向entry的指针
    unsigned long size; // 哈希表大小（2的幂）
    unsigned long sizemask; // size-1，用于计算索引
    unsigned long used; // entry个数
} dictht;

typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    struct dictEntry *next; // 下一个entry指针（解决哈希冲突）
} dictEntry;

typedef struct dict {
    dictType *type; // dict类型，含哈希函数
    void *privdata; // 私有数据，用于特殊哈希运算
    dictht ht[2]; // 两个哈希表，ht[0]存数据，ht[1]用于rehash
    long rehashidx; // rehash进度，-1表示未rehash
    int16_t pauserehash; // rehash暂停标志
} dict;

结构示例：

添加元素

添加键值对时，先计算key的hash值，通过h & sizemask确定存储索引，哈希冲突用头插法解决。

Dict扩容与收缩

Dict根据负载因子（LoadFactor=used/size）触发扩容或收缩。负载因子≥1且无后台进程时扩容；负载因子<0.1时收缩。扩容大小为第一个≥used+1的2的幂，收缩大小为第一个≥used的2的幂（不小于4）。

渐进式rehash

rehash分多次完成，每次操作时将ht[0]的entry链表rehash到ht[1]，最终切换哈希表，确保ht[0]只减不增。

ZipList

ZipList是特殊的连续内存块结构，可双端操作，时间复杂度(O(1))。

结构

ZipListEntry

节点含前一节点长度、编码、内容。前一节点长度占1或5字节（<254用1字节，≥254用5字节）；编码分字符串和整数，字符串以“00”“01”“10”开头，整数以“11”开头。

连锁更新问题

当连续节点长度在250 - 253字节间，插入长度为254字节的数据时，会引发后续节点的连续空间扩展，即连锁更新。

QuickList

为解决ZipList连续内存申请问题，Redis引入QuickList，是节点为ZipList的双端链表。

结构

typedef struct quicklist {
    quicklistNode *head; // 头节点指针
    quicklistNode *tail; // 尾节点指针
    unsigned long count; // 所有ziplist的entry总数
    unsigned long len; // ziplists总数
    int fill : QL_FILL_BITS; // ziplist的entry上限
    unsigned int compress : QL_COMP_BITS; // 首尾不压缩节点数
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistNode {
    quicklistNode *prev; // 前一节点指针
    quicklistNode *next; // 下一节点指针
    unsigned char *zl; // 当前节点的ZipList指针
    unsigned int sz; // 当前节点ZipList字节大小
    unsigned int count : 16; // 当前节点ZipList entry个数
    unsigned int encoding : 2; // 编码方式（ZipList或lzf压缩）
    unsigned int container : 2; // 数据容器类型
    unsigned int recompress : 1; // 是否解压缩
    unsigned int attempted_compress : 1; 
    unsigned int extra : 10; /* 预留字段 */
} quicklistNode;

配置

通过list-max-ziplist-size控制ZipList entry数量，通过list-compress-depth控制节点压缩，首尾不压缩。

SkipList

SkipList是有序链表，节点含分数和值，有多级指针提高查询效率。

结构

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头尾节点指针
    unsigned long length; // 节点数量
    int level; // 最大索引层级
} zskiplist;

typedef struct zskiplistNode {
    sds ele; // 节点值
    double score; // 节点分数，用于排序
    struct zskiplistNode *backward; // 前一节点指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 下一节点指针
        unsigned long span; // 索引跨度
    } level[]; // 多级索引数组
} zskiplistNode;

RedisObject

Redis数据类型的键值封装为RedisObject，含16字节头部。

编码方式

Redis有11种编码方式，常见：

五种数据类型的编码

• String：分INT、EMBSTR、RAW编码，根据长度和内容选择。
• List：3.2前用ZipList和LinkedList，3.2后用QuickList。
• Set：分INTSET和HT编码，元素为整数且数量少时用INTSET，否则用HT。
• Zset：分ZipList、HT、SkipList编码，元素少时用ZipList，多时用HT+SkipList。
• Hash：分ZipList和HT编码，元素少时用ZipList，多时用HT。