《Redis设计与实现》注释 - 数据结构和对象

1。简单动态字符串

Redis 并没有直接使用 C 语言的传统字符串表示形式，而是自己构建了一个简单动态字符串（SDS），使用 SDS 作为 Redis 默认的字符串表示形式。

1.1 SDS 定义

struct sdshdr {
    
// 记录 buf 数组中已经使用字节的数量，等于 SDS 所保存字符串的长度
    int len;
    
    // 记录 buf 数组中未使用字节的数量
    int free;
    
    // 字节数组，用于保存字符串
    char buf[];
};
复制代码

1.2 SDS 与 C 字符串的区别

C 字符串	SDS
获取字符串长度的复杂度❙为 O(N)，即 O(1)
The API 不安全，可能导致缓冲区溢出	API 安全，不会导致缓冲区溢出
更改字符串长度 N 次，必然需要 N 次内存重新分配	更改字符串长度 N 次，最多需要内存重新分配N 次内存重新分配
只能存储文本数据	可以存储文本或二进制数据
可以使用 库中的所有函数 您可以使用 库

2 和链表

链表在 Redis 中广泛使用。例如，列表键的底层实现之一是链接列表。当列表键包含的元素数量比较多，或者列表的元素是比较长的字符串时，Redis会使用链表作为列表键的底层实现。

2.1 Redis 链表结构

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;
复制代码

由一个 list 结构和三个 listNode 结构组成的链表如下图所示：

2.2 Redis 链表实现函数 -do 链表节点有 prev 和next 通过指针获取节点的前一个节点和后一个节点的复杂度为 O(1)。

3。字典

字典是一种用于存储键值对的抽象数据结构。在字典中，一个键（key）可以链接到一个值（value）。这些关联的键和值称为键值对。

Redis的数据库使用字典作为底层实现，数据库的增删改查操作也是建立在字典的操作之上的。

字典也是哈希键的底层实现之一。当一个哈希键包含很多键值对，或者键值对的元素是比较长的字符串时，Redis会使用字典作为哈希键的底层实现。

3.1 字典实现

Redis 的字典使用哈希表作为底层实现。一个哈希表中可以有多个哈希表节点，每个哈希表节点在字典中存储一个键值。正确的。

Redis中的字典结构为：

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

ht属性是一个包含两个元素的数组。数组的每个元素都是一个 dicttht 哈希表。一般情况下字典只使用 ht[0] ha 哈希表，只有重新哈希 ht[0 哈希表时才会使用 ht[1] 哈希表。

下图是正常状态下的字典（没有rehash）：

3.2 Hash

当字典作为数据库的底层实现，或者说是hash key的底层实现时，Redis使用MurmurHash2算法计算密钥的哈希值。

哈希表使用链地址方法来解决键冲突。分配给同一索引的多个键值对将链接成一个单向链表。

在扩展或收缩哈希表时，程序必须将现有哈希表中的所有键值对重新哈希到新哈希表中，并且这个重新哈希过程不是一次完成的。 ，但逐步完成。

4。跳转列表

跳转列表是一种有序的数据结构，在每个节点中维护多个指向其他节点的指针，以达到快速访问节点的目的。

跳跃表支持平均复杂度为O(logN)、最坏情况复杂度为O(N)的节点搜索，还可以通过顺序操作批量处理节点。

Redis 使用跳跃列表作为有序集键的底层实现之一。

跳过列表由两个结构体定义：zskiplistNode 和 zskiplist。 zskiplistNode结构体用于表示跳表节点，zskiplist结构体用于存储跳表节点的相关信息。跳转表示如下图所示：

zskiplist

header：指向跳转表的顶节点。

tail：指向跳转表的尾节点。

level：记录当前跳表中层数最多的节点的层数（不包括最上面节点的层数）。

length：记录跳转表的长度（顶层节点的层数不计算在内）。

zskiplistNode

level：层，每层有两个属性：前向指针和跨度。

backward：向后指针，该节点用BW标记，当程序从表尾到表头时使用。

score：分数，跳转表中的节点按照各自存储的分数从小到大排序。

obj：成员对象。

5。整数集

整数集是 set key 的底层实现之一。当一个集合只包含整数值元素，并且这个集合中的元素数量并不多时，Redis会使用整数集合作为集合键的底层实现。达到。它可以存储int16_t、int32_t、int64_t类型的整数值并确保集合中不会有重复的元素。 ？此外，新元素的类型比整数集合中所有现有元素的类型长。必须先升级整数集合，然后才能将新元素添加到整数集合。

步骤：

• 根据新元素的类型，扩展整型集合底层数组的空间大小，为新元素分配空间。
• 将底层数组中的所有当前元素转换为与新元素相同的类型，并将类型转换后的元素放置在正确的位置。在放置元素的过程中，必须保持底层矩阵的有序性。改变。
• 向底层矩阵添加新元素。 ？
• 升级操作为整数集合提供了操作灵活性，并尽可能节省内存。
• 整数集合仅支持升级操作，不支持降级操作。

6。压缩列表

压缩列表（ziplist）是一种旨在节省内存的顺序数据结构。它是列表键和散列键的底层实现之一。它可以包含多个节点，每个节点可以包含一个字节数组或整数值。在压缩列表中添加新的节点，或者从压缩列表中删除节点，都可能会触发链更新操作，但这种操作的概率并不高。

当列表键只包含少量列表元素，并且每个列表元素要么是一个小整数值，要么是一个相对较短的字符串时，Redis将使用压缩列表作为列表构建的底层实现。

当哈希键仅包含少量键值对，并且每个键值对的键和值要么是小整数值，要么是短字符串时，Redis 会使用压缩列表进行哈希处理。希腊键的底层实现。

下图是一个包含三个节点的压缩列表：

• zlbytes：记录整个压缩列表占用的内存字节数；
• zltail：记录压缩列表从起始地址到结束节点的节点数。部分;
• zllen：记录压缩列表包含的节点数量；
• entryx：压缩列表中包含的各个节点，节点长度由存储的内容决定；
• zlend：用于标记压缩列表的结尾。

7。对象

Redis 的对象类型：字符串对象、列表对象、哈希对象、集合对象、有序集合对象。

7.1 对象类型和编码

Redis 使用对象来表示数据库中的键和值。每个对象都由一个redisObject结构来表示：

type struct redisObject {
    // 类型
    unsigned type:4;
    
    // 编码
    unsigned encoding:4;
    
    // 指向底层实现数据结构的指针
    void *ptr;
    
    //...
} robj;
复制代码

通过encoding属性指定对象使用的编码。您可以Redis允许Redis根据不同的使用场景为对象设置不同的编码，从而优化对象在特定场景下的效率。

例如，当列表对象包含的元素较少时，Redis 使用压缩列表作为列表对象的底层实现：

• 因为压缩列表比双端链表存储更多的内存，并且当元素数量较多时是小。此时，存储在内存中连续块中的压缩列表可以比双端链表更快地加载到缓存中；
• 由于列表对象包含的元素越来越多，因此使用压缩列表来存储元素。随着优势消失，对象会将其底层实现从压缩列表切换到双向链表，后者更强大并且更适合保存大量元素。

7.2 字符串对象

字符串对象的编码可以是 int、raw 或 embstr。

• 如果字符串对象存储的是整数值，并且整数值可以用 long 类型表示，则字符串对象会将整数值存储在字符串对象结构体的 ptr 属性中（将 void* 转换为 long ）并设置将字符串编码为 int。
• 如果字符串对象存储字符串值，并且字符串值的长度大于32字节，则字符串对象将使用简单动态字符串（SDS）来存储字符串值，并且对象的编码设置为生的。
• 如果字符串对象存储字符串值，并且字符串值的长度小于或等于32字节，则字符串对象将使用embstr编码来存储字符串值。
• Redis 中 longdouble 类型表示的浮点数也以字符串值的形式存储。

7.3 列表对象

列表对象的编码可以是ziplist或linkedlist。

• Ziplist 编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点（条目）存储一个列表元素。
• Linkedlist 编码列表对象使用双向链表作为底层实现。每个双端链表节点（node）存储一个字符串对象，每个字符串对象存储一个列表元素。

当列表对象能够同时满足以下两个条件时，列表对象使用ziplist编码：

• 列表对象存储的所有字符串元素的长度小于64字节；
• 列表对象存储的元素数量小于512；不能满足这两个条件的列表对象必须使用链表编码。

7.4 哈希对象

哈希对象的编码可以是ziplist或hash bar。

• ziplist 编码的哈希对象使用压缩表作为底层实现。存储相同键值对的两个节点总是彼此靠近。存储key的节点在前面，存储value的节点在后面。先添加的节点位于表的顶部，后添加的节点位于表的末尾。
• hashtable 编码的哈希对象使用字典作为底层实现。哈希对象中的每个键值对都使用字典键值对来存储：字典中的每个键都是一个字符串对象，存储在对象中。键值对的key；字典中的每个值都是一个字符串对象，键值对的值存储在对象中

当哈希对象能够同时满足以下两个条件时，哈希对象使用 ziplist 编码：

• key的字符串长度和hash对象存储的所有键值对的值都小于64字节；
• 哈希对象存储的键值对数量小于512；不能满足这两个条件的哈希对象必须使用可哈希编码。

7.5 集合对象

集合对象的编码可以是插入的或可散列的。

• 插入编码的集合对象使用整数集合作为底层实现，集合对象的所有元素都存储在整数集合中。
• 可哈希编码的集合对象使用字典作为底层实现。字典中的每个键都是一个字符串对象。每个字符串对象都包含一个集合元素，字典的值设置为NULL。

当集合对象能够同时满足以下两个条件时，该对象使用intset编码：

• 集合对象存储的所有元素都是整数值；
• 集合对象存储的元素数量不超过512个；它不能被满足。这两个条件的集合对象必须使用 hashable 进行编码。

7.6 有序集对象

有序集的编码可以是ziplist或jumplist。

• ziplist 编码的压缩列表对象使用压缩列表作为底层实现。每个集合元素都使用两个相邻的压缩列表节点来存储。第一个节点存储项目，第二个节点存储项目的分数。压缩列表中的项目按分数从小到大排序，分数较小的位于表格顶部，分数较大的位于表格底部。
• shiplist编码的有序集对象使用zset结构作为底层实现。 zset 结构包含字典和跳转列表。

当有序集合对象能够同时满足以下两个条件时，该对象使用ziplist编码：

• 有序集合中存储的项数小于128；
• 有序集合中存储的所有元素成员的长度小于64字节；不能满足上述两个条件的有序集合对象将使用shiplist编码。

7.7 检查类型

可以在所有类型的按键上执行的命令：DEL、EXPIRE、RENAME、TYPE、OBJECT

只能在特定的按键类型上执行，是 EXPIRE 等。命令与LLEN等命令的区别在于前者是基于类型的多态性，即一个命令可以同时处理几种不同类型的按键；而后者是基于编码的多态性，即一个命令可以同时处理几种不同的编码。

7.8 内存回收

Redis 构建了一种通过引用计数技术实现的内存回收机制。

typedef struct redisObject{
    
    //...
    //引用计数
    Int refcount;
    //...
}robj;
复制代码

对象的引用计数信息会随着对象的使用状态而不断变化：

• 当新对象创建时，引用计数值会初始化为1；
• 当一个对象被新程序使用时
• 当该对象不再被程序使用时，其引用计数值将减一；
• 当对象的引用计数值变为0时，对象占用的内存被释放。

7.9 对象共享

在 Redis 中，要允许多个键共享同一个值对象，必须执行以下两个步骤：

• 将数据库键的值指针指向已有的值对象；
• 将共享值对象的引用计数加一。

这些共享对象不仅仅是可以使用的字符串键，而是那些在数据结构中嵌套了字符串对象的对象（链表编码的列表对象、哈希表编码的哈希对象、哈希表编码的集合对象和zset编码的排序集合）对象）可以使用这些共享对象。

作者：Rabbit_Judy
链接：https://juejin.im/post/5ca16472f265da30d9486388
来源：掘金归作者所有。商业转载请联系作者获取授权。非商业转载请注明来源。