Redis设计与实现-数据结构

如有侵权，请联系～
如有错误，也欢迎批评指正～
本篇文章大部分是来自学习《Redis设计与实现》的笔记

1、RedisObject对象

在介绍Redis各种类型的数据结构之前，先了解一下RedisObject数据结构。RedisObject翻译过来就是redis对象，它在redis服务端无时无刻都在，可以说redis服务端数据都是以redisObject形式存在。
例如，存储hash值，那么键是存储相应字符串的redisObject对象，值是存储相应hash表的redisObject对象。

先整体看下redis数据协议转换【redis之后在交互的时候是resp协议，在redis服务端都是redisObject】：

RedisObject的数据结构：

typedef struct redisObject {
    unsigned type:4;       // 数据类型（如字符串、列表、哈希等）
    unsigned encoding:4;   // 编码方式（如 raw、int、ziplist 等）
    unsigned lru:LRU_BITS; // LRU 时间戳或 LFU 数据（用于淘汰策略）
    int refcount;          // 引用计数（用于内存管理）
    void *ptr;             // 指向实际数据的指针
} robj;

字段说明：

• type：表示数据的类型，例如字符串（REDIS_STRING）、列表（REDIS_LIST）、哈希（REDIS_HASH）等。
• encoding：表示数据的编码方式，例如原始字符串（REDIS_ENCODING_RAW）、整数（REDIS_ENCODING_INT）、压缩列表（REDIS_ENCODING_ZIPLIST）等。
• lru：用于记录对象的访问时间，支持 LRU 或 LFU 淘汰策略。
• refcount：引用计数，用于内存管理和共享对象。当这个属性为0的时候，这个对象就会被回收。相同对象可以共享，减少内存使用。redis在初始化的时候会创建一万个字符串，值为0～9999的对象用于共享，类似于java的Integer包装类。
• ptr：指向实际数据的指针，数据的具体存储方式由 encoding 决定。

一个存储字符串的redisObject示意图：

具体编码方式有哪些以及存储结构可以参考：redis对象

redis中所有的键都是字符串对象，而值可以是下面的五种类型中的任意一个。所以说的列表键其实是指的值是列表类型。同样，命令TYPE返回的也是值的类型。

所有的编码方式encoding【可以通过OBJECT ENCODING可以查看键值对的值的编码方式】：

接下来直接讲各种数据结构，即Redis的ptr指针指向的那一部分。

2、简单动态字符串

2.1 SDS定义

redis中的字符串都是简单动态字符串（SDS）的形式存在的。不止是set key value的键和字符串值value，连其他数据结构中存储的字符串也是以SDS形式存储，如rpush fruits "apple " “banana”，队列保存的中的"apple " "banana"两个字符串元素也是SDS存储。

SDS除了保存字符串以外，还用在缓冲区：AOF缓冲区、客户端输入输出缓冲区。

SDS的数据结构：

struct sdshdr {
    int len;       // 字符串的长度（已使用的字节数）
    int free;      // 未使用的字节数（空闲空间）
    char buf[];    // 实际存储字符串内容的字符数组
};

字段说明：

• len：表示字符串的实际长度（不包括终止符 \0）。允许 O(1) 时间复杂度获取字符串长度。
• free：表示缓冲区中未使用的字节数。用于优化内存分配和减少频繁的内存重新分配。
• buf：存储实际的字符串内容，以 \0 结尾（兼容 C 字符串）。

针对于hello字符串对应的SDS：

len：等于5，因为hello字符串占用了5个字节，\0空字符并不单独算一个字符，即len、free都不会将其算入在内，\0是SDS函数自动添加的，对用户是透明的，为了能够使用c语言的一些函数。
free：等于3，表示buf申请的缓冲区中还有3个字节未使用。

2.2 SDS与C语言的区别

1. 获取字符串的长度时间复杂度
   因为SDS存储了字符串的长度，所以时间复杂度为O(1)；而C语言只存储了字符串本身，所以需要变量整个字符串才知道字符串的长度，时间复杂度为O(N)

2. 杜绝缓冲区溢出
   例如，字符串拼接函数strcat(s1, s2)将字符串s2拼接到s1后面，但是在拼接的时候没有检测s1的内存，s1没有足够的内存【s1后面存在其他有用的数据s3】，那么拼接就会导致s2会把s3的部分数据给修改了。而SDS空间分配策略就杜绝了这个问题出现。SDS API首先会检测空间是否满足，如果不满足自动的空间扩展。

3. 减少修改字符串导致的重分配次数
   C语言针对于一个长度为N的字符串底层是一个N+1的字符数组，每次修改字符串都需要进行内存重分配。增加字符需要扩展内存【否则，出现内存溢出问题】，减少字符需要释放内存【否则，出现内存泄漏问题】。执行内存重分配就需要系统调用，比较耗时，而Redis作为存储设备，字符串变更更是家常便饭。
   Redis通过未使用空间解耦了字符串长度和底层数据之间的绑定关系，通过未使用空间就实现了空间预分配和惰性空间释放。

4. 二进制安全
   C语言字符串必须符合某种编码，而且除了字符串的末尾为空字符之外，其他地方不允许有空字符，否则字符串就会提前结束。这就导致C语言只能存储文本数据，不能保存像图片、视频、音频等二进制数据。而SDS是根据len属性的长度确定结束，所以没有上述问题。

5. 兼容部分C语言函数
   虽然SDS是二进制安全的，但是在内存分配和数据存储的时候都会自动的多分配一个字节用来存储空字符，这就是为了能直接兼容C语言的部分<string.h>库上的字符串函数。当然针对于中间有空字符的就不能使用C语言函数。

2.3 SDS的空间分配策略

2.3.1 空间预分配

字符串在增加的时候，SDS API就检测未使用空间是否满足，即free >= 待插入字符串的长度，如果满足，则直接插入；否则出现如下空间预分配策略：

• 如果对字符串修改之后¹ ，SDS的长度【len属性】小于1M，则程序也会分配同样大小的未使用内存；
• 如果对字符串修改之后 ，SDS的长度【len属性】大于1M，则程序针对未使用的内存也只会申请1M的大小

上述分配策略衡量了占用内存和性能，因为字符串都大于1M，再申请一倍的未使用内存，就会占用太多内存。

2.3.2 惰性空间释放

针对于字符串缩减的时候，SDS并不会将缩减完空余的空间立刻释放掉，而是会增加free属性，防止为了以后再增加还需要进行内存重分配。当然，SDS 也提供了能够释放未使用空间的API，不会出现内存泄漏问题。

2.4 SDS的API

以下是常见的 SDS API 函数及其功能说明。【插入：一下内容通过AI生成。本人先去百度搜索没有找到相关内容，并且找到的也不太方便截图。于是直接使用AI生成，按照符合的语法生成直接负责即可。点赞AI】
1. 创建与销毁

2. 修改与扩展

3. 查询与统计

4. 截取与分割

5. 其他操作

3、链表

由于C语言没有链表数据结构，所以Redis进行自己构建了链表。链表在Redis中的使用还是很广的，例如列表的底层就是链表【排出压缩列表的情况】、Redis服务端存储的客户端状态、客户端的输出缓冲区、发布订阅等都用到了链表。

3.1 链表的定义

链表是由一个个链表节点串联组合而成的双向链表，先看下链表节点的数据结构：

typedef struct listNode {
    struct listNode *prev;  // 指向前一个节点，如果当前节点是链表的头节点，则 prev 为 NULL。
    struct listNode *next;  // 指向下一个节点，如果当前节点是链表的尾节点，则 next 为 NULL。
    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;

针对于列表中的三个函数指针进行详细介绍，可以自定义下面的函数：

• dup：用于复制链表节点的值。
  当需要复制链表时（例如深拷贝），Redis 会调用 dup 函数来复制每个节点的值。
  默认行为：如果未设置 dup 函数，则 Redis 不会对节点值进行复制，直接将指针赋值给新节点
• free：用于释放链表节点值占用的内存。
  当删除链表节点或释放整个链表时，Redis 会调用 free 函数来释放节点值。
  默认行为：如果未设置 free 函数，则 Redis 不会释放节点值，可能导致内存泄漏。
• 用于比较两个节点值是否相等。
  当需要查找链表中的某个节点时，Redis 会调用 match 函数来比较节点值与目标值。
  默认行为：如果未设置 match 函数，则 Redis 使用指针比较（即比较两个指针是否相同）。

redis删除策略【区别于过期策略（惰性策略和定期策略）和淘汰策略（内存不足的时候）】：

• 如果一个key开始指向一个字符串，然后更新一个字符串，会怎么办？因为字符串底层数据结构是SDS，所以会复用前一个字符串的SDS。
• 如果一个key开始指向一个复杂的数据结构，如列表、哈希，然后更新一个新的，会怎么办？redis会先递归删除原来的数据，然后讲新的赋值给这个key。

以链表存储字符串为例的结构图：

链表的特点：

• 链表获取长度的时间复杂度为O(1)
• 链表获取链表头和尾的时间复杂度为O(1)
• 链表获取前一个节点和后一个节点的时间复杂度为O(1)
• 链表不存在环的问题，因为头节点的head为null，后节点的next也为null
• 多态：链表提供了复制dup、删除free、比较match函数，可以自定义这些函数，所以再复杂的数据结构也OK

3.2 链表的API

1. 创建与销毁

2. 添加节点

3. 删除节点

4. 查找节点

5. 遍历链表

6. 自定义函数

4、字典

4.1 字典的定义

字典和链表一样C语言没有内置相关数据结构，都是redis自己构建实现的。字典是redis的全局哈希和哈希类型的底层实现。

哈希表的结构定义：

typedef struct dict {
    dictType *type;          // 类型特定函数，例如键、值等的复制、删除、对比函数或者是计算哈希值的函数
    void *privdata;          // 私有数据。保存类型特定函数的可选参数
    dictht ht[2];            // 两个哈希表（用于渐进式 rehash）。平时一直都是使用ht[0]，只有在哈希表进行扩缩容的时候才会使用ht[1]
    long rehashidx;          // 当前 rehash 的索引（-1 表示未进行 rehash）
    unsigned long iterators; // 正在运行的迭代器数量
} dict;

typedef struct dictht {
    dictEntry **table;       // 哈希表数组
    unsigned long size;      // 哈希表大小
    unsigned long sizemask;  // 掩码，用于计算索引。始终是sizemask=size-1，主要是用于计算一个键的hash索引
    unsigned long used;      // 已使用的、存在的键值对数量
} dictht;

typedef struct dictEntry {
    void *key;               // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;                      // 值，这个值可以是对象或者是uint64_t整数或者是int64_t整数
    struct dictEntry *next;   // 指向下一个节点（解决冲突），形成链表
} dictEntry;

• dict：哈希表的顶层结构，包含两个哈希表（ht[0] 和 ht[1]），用于支持渐进式 rehash。
• dictht：单个哈希表的结构，包含数组、大小、掩码和已使用节点数。
• dictEntry：哈希表中的单个节点，包含键、值和指向下一个节点的指针。

字典整体的数据结构：

4.2 哈希算法

插入数据的大致流程：

• 通过字典中设置的哈希函数，计算键key的哈希值：hash = dict.type.hashFunction(key);
• 计算该键值对需要插入的数组索引：index = hash & sizemask;
• 如果table数组的该索引处存在键值对，则插入到链表的头部，即头插法。

redis默认使用的哈希函数是Murmurhash2算法，并且出现冲突、哈希碰撞则使用链地址法解决冲突问题。

4.3 哈希表的扩缩

虽然程序的不断运行，哈希表中的数据会实时的变化，不断的增加或者减少。为了能过依然保持哈希表的性能和空间优化，会对哈希表进行扩缩，使得负载因子【load factor = used/size】保持在合理返回。

4.3.1 哈希表扩缩的判断依据

哈希表扩展的情况：

• 当redis正在执行bgsave【rdb持久化】或者bgwriteaof【aof重写】命令的时候，负载因子大于等于5
• 当redis没有执行bgsave【rdb持久化】或者bgwriteaof【aof重写】命令的时候，负载因子大于等于1

哈希表收缩的情况：

• 当负载因子小于0.1

4.3.2 哈希表rehash

• 根据当前ht[0]中键值对数量为字典的ht[1]分配空间：

  • 当哈希表进行扩容的时候， ht[1]分配的空间大小为：第一个大于等于的ht[0].used*2的2ⁿ;
  • 当哈希表进行扩容的时候， ht[1]分配的空间大小为：第一个大于等于的ht[0].used的2ⁿ;

• 将ht[0]上的值渐近式的rehash到ht[1]上

• 等ht[0]上的所有键值对都迁移到ht[1]上之后，释放ht[0]，将ht[1]上的哈希表赋值给ht[0]，然后ht[1]创建一个新的哈希表

4.3.2 渐进式rehash

当哈希表需要扩缩容的时候，不可能等到完全将ht[0]中的数据全部迁移到ht[1]之后再对外提供服务，尤其是哈希表中存储了大量的数据。因为这会导致服务一段时间的不可用，所以使用的是渐进式的、分批次的rehash。

当创建完ht[1]哈希表之后，rehashidx就设置为0。每当redis执行增删改查的时候，就会将ht[0]哈希表对应的rehashidx索引处的所有键值对都迁移rehash到ht[1]上，然后rehashidx加一。直到ht[0]哈希表所有的键值对都rehash完成，则rehashidx=-1。

当前在进行rehash期间，redis所有的增删改查操作会在ht[0]和ht[1]两个表上进行。例如：查询是否存在某个键的时候，会首先在ht[0]上进行查找，如果ht[0]没有，还会在ht[1]哈希表上查询；插入操作则是直接插入到ht[1]上，不会在再ht[0]上进行任何的插入操作。

4.4 字典的API

1. 创建与销毁

2. 插入与更新

3. 删除

4. 查找

5. 遍历

6. 其他操作

5、跳跃表

跳跃表是一个有序的数据结构，大部分情况下可以与平衡树相媲美，却比平衡数简单。那么为什么mysql不使用跳跃表呢？【跳跃表一般层级比较深相比于平衡树，对于磁盘读取影响比较大，而内存无关紧要】。跳跃表是有序集合的底层实现。

5.1 跳跃表的实现

跳跃表节点的数据结构：

typedef struct zskiplistNode {
    sds o;                      // 元素值（字符串）
    double score;                 // 分值，用于排序
    struct zskiplistNode *backward; // 指向前一个节点（仅在第一层有效）
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 指向同一层的下一个节点
        unsigned long span;           // 到下一个节点的跨度（跨越的节点数），这样在便利得到某个元素的时候就可以通过span之后得到排名。例如o2的排名等于1+1
    } level[];                     // 多层索引
} zskiplistNode;

跳跃表的数据结构：

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

图形化：

5.2 跳跃表的API

1. 创建与销毁

2. 插入

3. 删除

4. 查找

5. 遍历

6. 辅助函数

6、整数集合

整数集合是集合的底层实现之一。当集合中元素都为整数并且数量不多的时候就会使用整数集合。

6.1 整数集合定义

数据结构定义：

typedef struct intset {
    uint32_t encoding;  // 编码方式，决定存储的整数类型
    uint32_t length;    // 集合中元素的数量
    int8_t contents[]; // 动态数组，用于存储整数
} intset;

• encoding 字段：表示当前整数集合使用的编码方式，决定了每个元素占用的字节数：
  • INTSET_ENC_INT16：每个元素占用 2 字节（int16_t）。
  • INTSET_ENC_INT32：每个元素占用 4 字节（int32_t）。
  • INTSET_ENC_INT64：每个元素占用 8 字节（int64_t）。
    当插入一个超出当前编码范围的整数时，Redis 会升级编码方式（例如从 INTSET_ENC_INT16 升级到 INTSET_ENC_INT32），并重新分配内存。
• length 字段：表示当前集合中元素的数量。
• contents 数组：存储集合中的所有整数，按从小到大的顺序排列。
  由于整数集合是有序的，查找操作可以通过二分查找实现，时间复杂度为 O(log N)。
  

每次插入数据或者删除数据都会根据二分法进行查找，找到合适位置插入或者找到值进行删除，后续元素向前填充。

数组扩容情况：

• 申请的数组也是动态的，即开始有个初始容量，当数组不足以继续插入的时候就会扩容，以二倍速度进行扩容。
• 编码升级，例如当前编码为INTSET_ENC_INT16类型，但是插入了一个超过这个容量的数据，则会升级为合适的类型，重新分配内存进行迁移。这个扩容是不可逆的

整数数组只能进行升级不能进行降级。例如整数数组开始都是INTSET_ENC_INT16，增加了一个INTSET_ENC_INT32类型的整数，这个时候整个数组都会升级为INTSET_ENC_INT32类型，即已经存在的原本为INTSET_ENC_INT16类型的整数也转换为INTSET_ENC_INT32类型。当新增的INTSET_ENC_INT32的那个整数删除，其余原本为INTSET_ENC_INT16类型的整数升级之后也不能降级。

6.2 整数集合API

7、压缩列表

压缩列表是列表、有序集合、哈希的底层实现，前提是满足数量不太多并且单个元素不大的情况下。

7.1 压缩列表定义

Ziplist 是一个连续的字节数组，其结构如下：

<zlbytes> <zltail> <zllen> <entry1> <entry2> ... <entryN> <zlend>

每个Entry的数据结构：

<prevlen> <encoding> <data>

连锁更新：
压缩列表是连续的内存，所以每次插入元素都会重新分配内存，然后数据迁移。通过上面prevlen字段的说明，根据前一个长度的大小决定这个字段的长度。例如目前所有元素大小都是253，当新增一个元素插入在第一个位置，大小大于254。那么第二个元素大小就会超过254【因为第二个元素的prevlen字段从占用1个字节变成占用5个字节】，同样也会导致第三个元素超过254，以此类推下去。

哈希类型满足一定条件也可以存储为压缩列表，可是哈希是键值对的形式存在的，是怎么存储到压缩列表中的呢？哈希键值对按照k1 v1 k2 v2顺序存储到压缩列表，每个key、每个value都是一个独立的entry，当进行读取数据的时候，每次会读取两个压缩节点。

7.2 压缩列表的API

以下是 Redis 中压缩列表（Ziplist）相关的 API，以 Markdown 表格形式排版。