《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 字符串的区别

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 链表实现特性

• 双端：链表节点带有 prev 和 next 指针获取某个节点的前置节点和后置节点的复杂度都是 O(1)。
• 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL 对链表的访问以 NULL 为终点。
• 带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O(1)。
• 带链表长度计数器：通过 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O(1)。
• 多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

3、字典

字典，是一种用于保存键值对 (key-valuepair) 的抽象数据结构，在字典中一个键 (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 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0 哈希表进行 rehash 时使用。

下图展示了一个普通状态下（没有进行 rehash）的字典：

3.2 哈希

当字典被用作数据库的底层实现，或者哈希键的底层实现，Redis 使用 MurmurHash2 算法来计算键的哈希值。

哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。

在对哈希表进行扩展或者收缩操作时，程序需要将现有的哈希表包含的所有键值对rehash到新的哈希表里面，并且这个 rehash 过程并不是一次性地完成的，而是渐进式地完成的。

4、跳跃表

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均 O(logN)，最坏 O(N) 的复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

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

跳跃表由 zskiplistNode 和 zskiplist 两个结构定义，其中 zskiplistNode 结构用于表示跳跃表节点，zskiplist 结构用于保存跳跃表节点的相关信息，跳跃表示例如下图所示：

zskiplist

header：指向跳跃表的表头节点。

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

level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层不计算在内）。

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

zskiplistNode

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

backward：后退指针，节点中用BW字样进行标记，在程序从表尾向表头遍历时使用。

score：分值，跳跃表中节点按各自保存的分值从小到大排列。

obj：成员对象。

5、整数集合

整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。它可以保存类型为int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素。

5.1 整数集合的结构

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

下图所示为一个包含五个int16_t类型整数值的整数集合：

5.2 升级

当我们要将一个新的元素添加到整数集合里面，并且新元素的类型比整数集合现有的所有元素的类型都要长，整数集合需要先进行升级(upgrade)，然后才能将新元素添加到整数集合里面。

步骤：

• 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
• 将底层数组现在的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位置上，并且在放置元素过程中，需要维持底层数组的有序性质不变。
• 将新元素添加到底层数组里面。

5.3 总结

• 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
• 升级操作为整数集合带来了操作上的灵活性，并尽可能的节约了内存。
• 整数集合只支持升级操作，不支持降级操作。

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 使用压缩列表作为列表对象的底层实现：

• 因为压缩列表比双端链表更节约内存，并且在元素数量较少的时候，在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中；
• 随着列表对象包含的元素越来越多，使用压缩列表来保存元素的优势逐渐消失时，对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表。

7.2 字符串对象

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

• 如果一个字符串对象保存的是整数值，并且这个整数值可以用 long 类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面(将 void* 转换成 long)，并将字符串的编码设置为 int。
• 如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于 32 字节，那么字符串对象将使用一个简单动态字符串 (SDS) 来保存这个字符串值，并将对象的编码设置为 raw。
• 如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于 32 字节，那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。
• Redis 中 longdouble 类型表示的浮点数也是作为字符串值来保存的。

7.3 列表对象

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

• Ziplist 编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点 (entry) 保存一个列表元素。
• Linkedlist 编码的列表对象使用双端链表作为底层实现，每个双端链表节点 (node) 都保存了一个字符串对象，每个字符串对象都保存一个列表元素。

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

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

7.4 哈希对象

哈希对象的编码可以是 ziplist 或者 hashtable。

• ziplist 编码的哈希对象使用压缩表作为底层实现。保存同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后；先添加的在表头方向，后添加的在表尾方向。
• hashtable 编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存：字典的每个键都是一个字符串对象，对象中保存了键值对的键；字典中每个值都是字符串对象，对象中保存了键值对的值

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

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

7.5 集合对象

集合对象的编码可以是 intset 或者 hashtable。

• inset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。
• hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含一个集合元素，而字典的值则全部被设置为NULL。

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

• 集合对象保存的所有元素都是整数值；
• 集合对象保存的元素数量不超过512个；不能满足这两个条件的集合对象需要使用hashtable编码。

7.6 有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist。

• ziplist 编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一个的压缩列表节点来保存，第一个节点保存元素的成员 (member)，第二个节点保存元素的分值 (score)。压缩列表内的元素按分值从小到大进行排序，分值较小的在表头方向，较大的在表尾方向。
• skiplist 编码的有序集合对象使用 zset 结构作为底层实现，一个 zset 结构同时包含一个字典和一个跳跃表。

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

• 有序集合保存的元素数量小于128个；
• 有序集合保存的所有元素成员的长度都小于64字节；不能满足以上两个条件的有序集合对象将使用skiplist编码。

7.7 检查类型

任何类型的键都可以执行的命令：DEL、EXPIRE、RENAME、TYPE、OBJECT

只能对特定类型的键执行：

DEL、EXPIRE 等命令和 LLEN 等命令的区别在于，前者是基于类型的多态，即一个命令可以同时处理多种不同类型的键；而后者是基于编码的多态，即一个命令可以同时处理多种不同编码。

7.8内存回收

Redis 构建了一个引用计数 (reference counting) 技术实现的内存回收机制。

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

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

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

7.9 对象共享

在Redis中，让多个键共享同一个值对象需要执行以下两个步骤为：

• 将数据库键的值指针指向一个现有的值对象；
• 将被共享的值对象的引用计数增一。

这些共享对象不单单只有字符串键可以使用，那些在数据结构中嵌套了字符串对象的对象(linklist编码的列表对象、hashtable编码的哈希对象、hashtable编码的集合对象，以及zset编码的有序集合对象)都可以使用这些共享对象。