《Redis设计与实现》七个底层数据结构

本文最后更新于 2025年8月27日凌晨

简单动态字符串 SDS（Simple Dynamic String）

基本结构

struct sdshdr{
    int len; // buf数组中已使用字节的数量 (SDS所保存字符串的长度)
    int free; // buf数组中未使用字节的数量
    char buf[]; // 字节数组，用于保存字符串
}

注意：

char buf[] 与C语言中用于描述字符串的方式相同，也会在末尾加一个\0来表示字符串结束，因此，buf[]的真正长度应是len + 1

动机

char buf[]的结构允许了该数据结构可以直接使用C字符串函数中的函数
将获取字符串长度的时间复杂度从 $O(n)$ 变为 $O(1)$
杜绝缓冲区溢出，原因与下一个点的内存分配方式有关
减少了修改字符串内容时带来的内存重分配次数
- 内存预分配：在修改字符串导致长度超出结构允许范围时（free < 0），会触发该机制。具体逻辑取决于字符串修改后的大小
  - 大小 < 1mb：额外分配与len属性相同大小的未使用空间
  - 大小 > 1mb：额外分配1mb未使用空间
- 缩短字符串则不会触发内存预分配，而是将预留的空间空出来，并且在free属性中表示剩余空间。这杯成为惰性空间释放策略。
  - SDS拥有相应的API，用于释放未使用空间。
保证了二进制安全：允许空字符存在于字符串中
- C语言中会用空字符来分割多个字符串，而SDS则仅通过len属性来决定字符串是否结束。
- SDS API会以处理二进制的方式处理buf中的数据，其写入时是什么样，读取时便就是什么样。

链表 LinkedList / ListNode

基本结构

typedef struct listNode{
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct list{
    listNode *head; //头结点
    listNode *tail; //尾节点
    usgined long len; //链表长度
    void *(*dup) (void *ptr); //复制节点函数
    void *(*free) (void *ptr); //节点释放函数
    int (*match) (void *ptr, void *key) //节点值对比函数
} list;

特性

双端：链表节点带有prev和next指针
无环：双端尽头都是NULL节点，链表访问以NULL为终点
带表头与表尾：可以轻松访问头结点和尾节点
带链表长度计数器：访问链表长度的时间复杂度为 $O(1)$
多态：用void*来保存节点值，并且dup, free, match三个属性节课对节点值设置类型特定函数。这让链表可以同时保存各种不同类型的值

字典

基本结构

// 哈希表
typedef struct dictht{
    // 哈希表数组
    dictEntry **table;
    
    // 哈希表的大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    
    // 该哈希表已有节点数量
    unsigned long used;
} dictht;

// 哈希表节点
typedef struct dictEntry{
    // 键
    void *key;
    
    // 值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    
    // 指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

// Redis中的字典
typedef struct dict{
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash索引
    // 当rehash不在进行时，值为-1
    int trehashidx;
} dict;

// dictType
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;

注意：

*next用于解决键冲突问题，当有多个值的索引（哈希值）相等，便会在哈希表数组中的索引位置上形成链表
ht属性为一个包含两个项的数组，一般只会用ht[0]哈希表，当需要对ht[0]进行rehash的时候才会使用ht[1]，在rehash结束后，ht[0] = ht[1]; ht[1] = 空的哈希表

哈希算法

// 将 k0, v0添加到字典中
// 第一步： 计算hash值
hash = dict->type->hashFunction(k0);

// 第二部： 计算索引值
// 此处的x取决于当时的情况，x in [0,1]
index = hash & dict->ht[x].sizemask;

当字典被用作数据库的底层实现，或哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值
- 注意：目前来说，对于某些场景来说，Redis依然使用MurmurHash2算法。但是现在默认算法为SipHash。该算法主要是为了方式Hash Flooding/ Hash DoS攻击。该类攻击会构造大量哈希冲突的键，使哈希表退化成链表，导致性能急剧下降。而SipHash是一种加密强度更高的哈希函数，能有效抵御此类攻击。
- 用户可以在编译时定义USE_MURMUR宏，或是运行时配置server.should_use_murmur变量，将哈希算法换为性能更高的MurmurHash2。
- 在一些特殊环境下，比如集群和哨兵环境下，或者在哈希键中，哈希算法也会有所不同。

键冲突

Redis的键冲突的解决方法与Java的HashMap类似，也是使用链地址法将冲突键元素构造成链表（Redis不会在一定长度后变成红黑树）。只是要注意，由于dictEntry节点组成的链表没有执行链表尾部的指针，所以在添加新元素进链表时，会将元素放在表头。dict->table[x]一开始指向的是一个NULL节点，因此最终会形成一个尾部指向NULL节点的链表。

重哈希 Rehash & 扩容与缩容

Redis同样拥有自己的容量控制机制。该机制通过执行rehash操作来完成。操作流程大致如下：

graph TD

1[rehash开始] --扩展操作--> 2["ht[1].size = ht[0].used*2"]
1 --收缩操作--> 3["ht[1].size = ht[0].used"]
2 --> 4["h[1] = rehashed(ht[0])"]
3 --> 4
4 --"ht[0]为空时"--> 5["free(ht[0]); ht[0] = ht[1]; ht[1] = 空dictht"]

ht[0].size和ht[1].size都维持在 $2^n, n\in \mathbb{Z}$ 。修改后的值为大于其值的最小 $2^n$ 。比如修改后ht[1].size = 6，大于6且最小的 $2^n$ 为8，因此最终ht[1].size = 8

Redis中哈希表的扩展与收缩原则与Java的有所不同。当一下任意条件满足时，程序会自动对哈希表执行扩展操作：

服务器目前没有在执行BGSAVE命令或BGREWRITEAOF命令，且哈希表负载因子大于等于1。
服务器目前正在执行BGSAVE或BGREWRITEAOF命令，且哈希表负载因子大于等于5。

1 2	`// 负载因子为 load_factor = ht[0].used / ht.size`

负载因子在两种情况不同的原因为，BGSAVE和BGREWRITEAOF命令的过程会产生子进程。大多数操作系统都会采用**COW（copy-on-write)**技术来优化子进程的执行效率，因此在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，以尽可能避免子进程存在期间进行哈希表扩展操作，以避免不必要的内存写入操作。

BGSAVE 和 BGREWRITEAOF

这本书往后看应该也会有该内容的解释，但现在我没看到，因此先写在这里

BGSAVE：

目的是为当前Redis数据库生成一个快照，并将其持久化进磁盘。以避免在服务器宕机等可能问题时丢失信息。
生成的是RDB文件，里面只包含了Redis的数据信息。
每次执行都会将Redis中所有数据写入文件。
由于每次执行都要写入全量信息，I/O压力较大。然而，这个机制会在子进程中执行，所以不会对主进程造成多少阻塞

BGREWRITEAOF：

目的是为已经的AOF文件优化内部内容（重写AOF文件），以整理和清理不必要的命令序列。
后台异步执行。
背景： AOF文件（日志）会记录每一个写操作，因此会不断变大。然而随着日志变大可能会使某些命令变得冗余（比如一个数据被set了几十次，但只有最后一次是有用的），需要某种机制来清除这类问题。这样既可以节省空间，也会简化命令执行，优化恢复效率。

因为不论是BGSAVE还是BGREWRITEAOF命令都会创建子进程，因此在其流程中，主进程的任何写操作都会触发COW技术。而哈希表的扩容过程中会出现大量的写操作，因此该操作在与这两个命令同时执行的时候会导致程序性能大大降低。因此，Redis将在执行这两个命令时，哈希表的扩容负载因子阈值增大到了5，以尽可能避免两个操作同时运行。

渐进式rehash

当redis字典中存在过多键值对，比如千万级别的数据量时，寻常的rehash方法可能会因为过于庞大的数据量的写入导致服务器出现明显卡顿。Redis提出了一个简单的方法来解决这个问题：将rehash流程拆分成多个离散的流程，使ht[0]中的数据逐步被rehash到ht[1]中，并且同时允许其他操作进行。

具体流程如下：

Redis中的字典维护了一个rehashidx属性。该属性在一般情况下都为-1，代表目前并未有rehash命令正在进行。当rehash命令开始时，该属性值将被设为0。
rehash过程中，只会从ht[0]中rehash索引位置为rehashidx上的数据。当该索引下所有数据都被rehash到ht[1]后，rehashidx += 1。
当ht[0]中的数据全部被rehash到ht[1]后，rehashidx = -1，表示rehash操作已完成。

该方法避免了集中式rehash带来的庞大计算开销，同时也可以保证对哈希表的操作不受到阻碍：

在渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]。具体来说，当要对某个数据进行读取或更新时，会先从ht[0]中找，找不到则会去ht[1]中找。
- 由于Redis是一个单线程的命令模型，因此不会出现并发状态下数据冲突的问题。比如某个键正在rehash的时候，来了个访问该数据的请求。此时该请求会在这个键rehash结束之后，正常访问到对应的数据。

跳跃表（跳表）SkipList

基本结构

// 跳表节点
typedef struct zskiplistNode{
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        
        // 跨度
        unsigned int span;
    } level[];
    
    // 后退指针
    struct zskiplistNode *backward;
    
    //分值
    double score;
    
    // 成员对象
    robj *obj;
} zskiplistNode;

// 跳表
typedef struct zskiplist{
    // 头节点与尾节点
    struct zskiplistNode *header, *tail;
    
    // 表中节点数量
    unsigned long length;
    
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

注意：

跳表中，分值小的节点永远在分值大的节点前面。
跳表是一个有序链表
每个跳表节点的层高都是1至32的随机值，随机函数基于末次定律（越大的数出现的概率越小）
同一个跳表中可以有多个节点包含相同的分值，但节点的成员对象必须是唯一的
分值相同时，节点按照成员对象的大小进行排序

特性

跳表可以很快地（ $O(1)$ 复杂度）用于判断一个范围内是否存在值。
插入，删除，读取某个元素的平均时间复杂度均为 $O(\log N)$ ，最差为 $O(N)$ 。
支持范围删除和范围搜索。且时间复杂度都可以保证在 $O(N)$ 以下

总的来说，跳表在利用了稍微偏大的空间的情况下，换来了很低的时间复杂度。

整数集合（集合）IntSet

基本结构

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

注意：

contents[]中元素的类型并不是int8_t，其中类型只取决于encoding的属性值
- encoding属性值：INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64。代表16,32,64为整数。
contents[]中的元素按从小到大有序排列，切不包含重复项
encoding的属性值取决于集合中最大的数所需的元素类型，具体实现与升级规则有关

升级机制

当需要将一个新元素添加进集合中，且该元素类型比集合中所有元素类型都要长时，便会先触发升级机制，然后再将元素放进集合中。步骤如下：

根据新元素的类型，重新计算底层数组所需空间，并重新分配空间
将底层数组中的所有原元素类型转为新的元素类型，并将每一个元素放在正确的位上，并保持顺序不变
- 在步骤1后，底层数组将会被重新分配空间。原数组中的每一个元素将会以他们的下标来计算他们的空间（位）其实位置，并将其占用空间设为新的元素类型所需空间。
将新元素加入底层数组

注意：整数集合不具有降级机制，这意味着即便当前集合中没有与元素类型所需的足够大的元素，也依然会保持原本的元素类型。

由于在最差情况下，每一次插入新元素都需要触发升级机制，所以插入的时间复杂度为 $O(N)$ 。不过由于intset最大支持64位整型，从8位开始升级，总共最多需要升3次，所以平均复杂度应 $小于O(N)$ （由于插入的算法用的是二分法，所以平均复杂度应为 $O(\log N)$ ）。

压缩列表 ZipList

压缩列表中大部分内容都是使用十六进制编码表示，这样表达可以大大节省内存。

基本结构

压缩列表 ZipList

ziplist结构图

介绍一下各个组成部分（摘自《Redis设计与实现》）：

属性	类型	长度	用途
`zlbytes`	`uint32_t`	`4` 字节	记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 `zlend` 的位置时使用。
`zltail`	`uint32_t`	`4` 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
`zllen`	`uint16_t`	`2` 字节	记录了压缩列表包含的节点数量：当这个属性的值小于 `UINT16_MAX` （`65535`）时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 `UINT16_MAX` 时，节点的真实数量需要遍历整个压缩列表才能计算得出。
`entryX`	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
`zlend`	`uint8_t`	`1` 字节	特殊值 `0xFF` （十进制 `255` ），用于标记压缩列表的末端。

压缩列表节点 Entry

压缩列表节点

每个节点可以保存一个字节数组或者一个整数值
- 字节数组：仅会是以下三种其一
  - 长度小于等于63字节( $2^6 - 1$ )的字节数组
  - 长度小于等于16383字节( $2^{14} - 1$ )的字节数组
  - 长度小于等于4294967295字节( $2^{32} - 1$ )的字节数组
- 整数值：仅会是以下六中其一
  - 4位长，介于0-12之间的无符号整数
  - 1字节长的有符号整数
  - 3字节长的有符号整数
  - int16_t类型整数
  - int32_t类型整数
  - int64_t类型整数
previous_entry_length：前一个节点的长度。该属性的长度只会是1或者5。属性值用16进制表示。
- 前一节点长度小于254( $2^8-2$ )字节，则长度为1：前一节点的长度就在这一个字节里面。比如0x05代表前一节点长度为5字节（十进制）
- 前一节点长度大于等于254字节，则长度为5：第一字节会设为0xFE（十进制就是254），后面四个字节用于保存前一节点的长度。比如0xFE002766代表前一节点长度为10086字节（十进制）
- 使用该属性值，便可以轻松定位到前一个节点的起始位置
- 通过这个方式，可以对压缩列表进行从表尾到表头的遍历操作：从表尾开始，使用previous_entry_length来逐一遍历到表头
encoding：用于记录content属性所保存的数据类型及长度
这里解释一下1111xxxx为什么保存了一个介于0-12之间的值:
- 11110000和11111110已经被其他特定编码占用（24位和8位带符号的整数），因此，实际上仅剩下14个有效的xxxx二进制。
- 另一方面，书中虽然没有说，但是实际上encoding中还有一个11111111编码用作压缩列表结束的标记，因此仅剩下13个有效的xxxx二进制。
- 由于计数从0开始，所以说保存的是一个介于0-12之间的值。
content：用于保存节点的值，这个值可以是一个字节数组或一个整数，长度与类型由encoding属性解决。这里给出两个书中写的节点示例来让大家有一个更直观的理解

第一个图中，由于content = "hellow world"是一个11字节长度的字节数组，因此encoding遵循00bbbbbb编码规律，为00001011，表示一个长度为11（转为十进制）的字节数组。

第二个图中，由于content = 10086是一个int16_t的整型，因此encoding遵循11000000的编码，表示为一个int16_t的整型。

连锁更新

所谓连锁更新，指的是在对压缩列表进行插入或删除操作时，由于插入的或删除的元素对其他元素的previous_entry_length属性所需的字节空间带来变化为产生的一系列连锁更新反应。

比方说，原本存在一个压缩列表：

graph LR

e1 --- e2 --- e3 --- ...

其中每一个列表元素的大小都在250到253之间。由于每一个的前一个节点的长度都小于254，所以他们的previous_entry_length长度都是1字节。

想象一下，现在有一个长度大于等于254的新节点new放到列表的首位

graph LR

new --- e1 --- e2 --- e3 --- ....

那么，由于插入的new节点长度大于254，所以对于e1来说，它的previous_entry_length的长度将会从1变为5，同时其节点自身的长度也会增加4，这导致e1的节点长度变得大于等于254，从而影响e2的previous_entry_length。这种影响会形成连锁反应，直到遇到一个不会由于自身长度改变而导致下一个节点长度产生改变的节点。

Redis对于这类情况的解决方式也就和直觉上认为的一样，遇到需要更新的就更新，然后连锁就连锁。因此，在极端情况下，一次插入或删除操作都需要对压缩列表执行N次空间重分配操作，由于每次空间重分配的时间复杂度为 $O(N)$ ，因此最终的时间复杂度为 $O(N^2)$ 。

然而，由于这种情况（贯穿整个列表的进行更新）发生的概率极低，所以一般而言，我们会将其插入和删除的时间复杂度视为 $O(N)$ 。

压缩列表的优势

在我刚开始看这一个数据结构时，我就在想，为什么Redis需要特意去设计这样的一个数据结构，来完成用现有结构就能完成的任务（比如双向链表等）。看完之后，我的总结如下：

压缩列表中严谨地管理和维护了每一个列表元素的空间大小，并且用连续的内存空间来存储这些元素，让内存空间的使用覆盖率大大提升，不会出现浪费内存空间（内存碎片）的情况。这能够最大化利用内存空间，也能够在释放空间时效率变高。
对比其他数据结构，压缩列表更加节省空间。比如说对比链表和双向链表。由于在链表中，每一个元素都需要维护一个指向下一个节点的指针，一个指针是8字节，在双向链表中则是两个指针16字节。而在压缩列表中并不会使用指针来得到另一个节点的位置，而是通过将节点自己的地址与previous_entry_length进行计算来得到上一个节点的位置。而一个previous_entry_length所需的长度最多为5，因此比寻常结构节省了不少空间。
encoding的存在将存储的数据进行了智能编码，实现了在编码长度小于等于5字节的情况下依然能够编码大部分常用的数据（整型，字节数组）

Redis学习

#Redis

《Redis设计与实现》七个底层数据结构

http://example.com/2025/08/25/Redis学习/《Redis设计与实现》七个底层数据结构/

作者

Clain Chen

发布于

2025年8月25日

许可协议

《Redis设计与实现》对象上一篇

认知状态-行为集合以限制本地模拟时其他代理的可能动作下一篇