3. Redis的底层数据结构及对象

前言

前面专题2中介绍了Redis的一些上层命令,包括一些基本的数据类型、订阅发布、消息队列、事物、Lua脚本等使用方式,都是比较上层应用的东西,这一节开始探究下Redis底层是如何支持这些上层实现的。笔记写于2018国庆节的最后一个假日,于杭州拱墅区图书馆阅读《Redis设计与实现》第一部分内容。

1. 简单动态字符串SDS（Simple Dynamic string）

Redis底层是C语言实现的。但是Redis并没有直接使用C语言中的字符串(C中的字符串是以\0结尾的字符数组)，而是直接自己构建了一种名为简单动态字符串(SDS)的抽象类型,并将SDS作为Redis的默认字符串表示。

因为C字符串的长度固定、修改消耗资源,毕竟是一个数组的实现。但是Redis需要的是一个可以被修改的字符串。在Redis数据库中,包含字符串值的键值都是使用SDS实现的。
比如我们操作一个SET命令:

redis> set name "Redis"
OK

这个操作对于Redis底层来说将在数据库中创建一个新的键值对,其中键值对的键值分别在底层创建了一个保存字符串"name"的SDS和保存着字符串"Redis"的SDS。

同时SDS除了用来保存数据库中的字符串之外,还可以用作缓冲区(buffer):AOF模块中的AOF缓存区、客户端状态中的输入缓冲区等后面会具体介绍。

1.1 SDS的结构

struct sdshdr{
    //记录buf[]数组中已经使用的也就是SDS所保存的字符串的长度
    int len;
    //记录buf[]数组中未使用字节的数量
    int free;
    // 字节数组,用来保存字符串转换成的二进制数据(也是SDS的特性,能保存任何东西)
    //在演示画图的时候我们不写01,直接写字符便于理解,只要记住它其实保存的是01即可
    char buf[];
};

image.png

如上述代码所示,free属性的值如果为0表示该SDS的空间都被使用了。len值如果为5表示这个redis保存了一个5字节长的字符串。buf属性是一个char类型的数组,分别保存了对应的字符,最后一个保存了空的字符\0。SDS遵循C字符串以空字符结尾的惯例,不计入len属性中,遵循这个的好处是我们可用复用<string.h>类库中对字符串的操作的一些方法,不用自己再写一套了。当然free属性可以有值的,比如下图中,free值为3表示buf还有3个字节没有被使用。

image.png

1.2 SDS与C字符串的区别

C语言的字符串不能满足Redis对字符串的安全性、效率性及功能等方面的要求。总结如下

1. 如果想要获得字符串的长度,C字符串需要遍历一遍,然后计数器的值就是长度,时间复杂度为O(N),而SDS保存了这个长度值,时间复杂度O(1)。
2. C字符串在扩容或者缩短的时候,需要检查容量是否足够。如果是增加操作,则程序需要通过内存重新分配来扩展底层数组空间大小，这一步如果忘了的话会产生缓冲区溢出。在缩短的时候需要通过内存重分配来释放字符串不用的那部分空间，如果忘了这一步会产生内存泄露。而频繁的内存重分配会比较耗时,效率比较低。Redis目的就是想要高效的操作的。
   而SDS拥有完善的空间分配策略,当SDS的API对SDS进行修改的时候,就会检查空间然后再执行修改操作。为了避免C字符串的缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。buf的长度>=字符数量+1。包含未使用的字节,它们使用free属性来记录。它拥有2套空间分配策略：
   2.1.空间预分配策略：当SDS的API对SDS进行增加操作,如果修改之后SDS的长度len<=1MB那么程序分配和len大小相等的未使用空间即 len == free,此时buf的实际长度为 len + free + 1byte。如果修改后的SDS长度 len > 1MB,那么则只分配1MB的free。此时buf的实际商都为 len + 1MB + 1byte。这样以来后续的操作可以不必再频繁的分配空间,如：增加N次,则内存最多重新分配N次。
   2.2.惰性空间回收策略：用来优化SDS的字符串的缩短操作,当SDS的API需要缩短SDS保存的字符串时,程序不立即内存重分配回收缩短后多出来的字节,而是记录在free里不回收,留待后面需要扩容的时候提供优化。当然SDS也提供了真正释放SDS的未使用空间,所以不用担心内存浪费。

1.3 二进制安全的

C字符串必须符合某种编码比如ASCII,并且除了字符串末尾之外不能包含空字符,所以只能保存文本数据而不能保存图像等二进制数据。为了确保Redis可以适用各种不同的场景，SDS的API都是而今夕安全的,所有的SDS的API都会以二进制的方式来处理SDS存放在buf数组中的数据。这样的话数据在写入的样子和读取出来的样子一致,所以可以保存任意格式的二进制数据。并且可以重用一部分<string.h>中对字符串操作的方法避免了代码重复。

小结：

比起C字符串,SDS有以下优点
a. 常数复杂度获取字符串长度
b. 杜绝缓冲区溢出
c. 减少修改字符串长度时所需要的内存重分配次数
d. 二进制安全的
e. 兼容部分C字符串的方法

2. 链表

链表提供了高效的节点重排能力、顺序性的节点访问方式、可通过增删改节点来灵活地调整链表的长度
C中并没有链表的实现,所以Redis自己写了一套,常用在连标键、发布订阅、慢查询、监视器等功能。它的结构如下

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

多个listNode可以通过prev和next指针组成双端链表,虽然仅仅使用多个listNode就可以组成链表,但是使用list操作更加方便。

typedef struct list{
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(vlid *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr,void *key);
}list;

list结构为链表提供了表头指针head和表尾指针tail,以及链表长度的记录len。dup、free和match成员则是用于实现多态链表所需的类型特定函数。
dup函数用来赋值链表节点所保存的值
free函数用来释放链表节点所保存的值
match函数用来对比链表节点锁保存的值和另一个输入值是否相等

Redis的链表实现总结如下：

1. 双端:链表节点带有prev和next指针
2. 无环,头节点的prev为Null,尾节点的next为Null
3. 带有表头和表尾节点
4. 带有链表长度的计数器
5. 多态:链表节点使用void*指针保存节点的值,并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数,所以链表可保存不同类型的值(通过为链表设置不同类型特定函数)。

3. 字典

字典又称为符号表、关联数组或映射,是一种用于保存键值对的抽象数据结构。在字典中,一个键可以和一个值进行关联,并且每个键都是独一无二的,Redis的数据库就是使用字典作为底层实现的。对数据库的CRUD也是基于字典的操作完成的。

比如我们执行下面的命令,在数据库中会创建这个键值对,并且这个键值对就是保存在数据库的字典里面的。除了用来表示数据库之外,字典也是哈希键的底层实现之一,当一个哈希键包含的键值对比较多或者键值对的元素都是比较长的字符串时,Redis就会使用字典作为哈希键的底层实现。

redis> set name "xiaoxiao";
OK

3.1 字典的实现

Redis的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,每个哈希表节点保存了字典中的一个键值对。

3.1.1 哈希表

Redis字典使用的哈希表定义如下：

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

table是一个数组,数组中的每个元素都是指向dictEntry的指针,每个dictEntry结构保存着一个键值对。size属性记录了哈希表的大小。而used属性表示已经使用的空间数量。sizemask=size-1,这个值和哈希值决定了一个键应该被放到table数组的索引位置,如下图:

dictht结构.png

3.1.2 哈希表节点

哈希表节点使用dictEntry结构表示,每个dictEntry结构都保存着一个键值对:

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

key属性保存着键值对中的键,而v属性保存着值，其中键值对的值可以是一个指针,或者是unit64_t/int64_t的整数。next属性是指向另一个哈希表节点的指针,这个指针可以将多个哈希值相同的键值对连接在一起，以此解决哈希冲突(也叫哈希碰撞,是因为计算的哈希值是一样的了,所以此处使用链地址法解决哈希碰撞)。如下图

dicthtNode哈希碰撞.png

# 3.1.3字典

Redis中的字典由<dict.h>中的dict结构表示,源码如下:

typedef struct dict{
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表,为啥是2个后面会介绍
    dictht ht[2];
    //rehash的进度,不在rehash时值为-1
    int trehashinx;
}dict;

type属性和Privdate属性是针对不同类型的键值对,为创建多态字典而设置的。type指向dictType结构的指针,这个而机构保存了一簇用于操作特定类型键值对的函数,redis会为用途不同的字典设置不用的类型特定函数。而privdata属性则保存了需要传给哪些特定函数的可选参数。ht[2]这是一个长度为2的哈希数组,h[0]被用来存放实际的元素,ht[1]只有在rehash的时候才会用到,当rehash开始的时候treashidx为0,不在rehash的时候ht[1]是空的。如下图所示,是一个没有在进行rehash的字典结构。

dict字典.png

3.1.4 哈希算法

当需要将一个新的键值对添加到字典里面的时候,程序需要先根据键值对的键计算出哈希值和索引值,然后根据索引值决定放在ht[0]哈希表的指定索引上面。计算过程如下：

1. 使用字典设置的哈希函数,计算key的哈希值。hash = dict->type->hashFunction(key);
2. 使用哈希表的sizemask属性和哈希值,计算出索引值。
   根据情况不同,ht[x]可以是0或者1,取决于是不是在进行rehash操作。index = hash & dict->ht[x].sizemask;

3.2哈希碰撞的解决方法

类似Java中的Hash碰撞,尽管我们采用了一些计算索引的手段尽量避免落入同一个桶内。当两个或者两个以上的键被分配到了哈希表的同一个索引处就发生了哈希碰撞。Redis使用链地址法解决哈希冲突,每个哈希表节点都有一个next指针，连接成一个单向链表。因为没有保存链表的尾节点，为了效率考虑，采用的是头插法。之前的3.1.3节的图里有相关的介绍，并且k1的节点是在k2存在之后插入的数据。

3.3 Rehash

我们前面介绍了它的结构中有一个哈希表,实际情况下,当哈希表保存的键值对数量太多或者太少时,哈希表也需要不断的扩容/收缩来满足业务需要。这个过程通过rehash(重新散列、就是扩容完了重新计算下索引位置)。Redis中执行rehash的步骤如下：

1. 为字典的哈希表ht[1]分配空间，这个空间取决于实际要执行的操作,以及ht[0]本身包含的键值对数量。如果是扩容,ht[1]的大小为 第一个大于等于ht[0].used * 2 (2的n次方幂)。如果执行的是收缩操作，则为第一个大于等于 ht[0].used 的2的n次方幂。
2. 将保存在ht[0]中的所有键值对rehash到ht[1]上也就是重新计算哈希值放到ht[1]。上
   3.释放ht[0]然后把ht[1]设置为ht[0],修改trehashidx为-1.并使ht[1]为空。
   整个过程中如果数量庞大的话，就需要渐进式的去rehash，此时就使用到了trehashidx这个字段，从0开始，每次rehash一个位置上的。移动到末尾的时候就代表rehash完成了，并且在rehash的过程所有新增的值都直接计算完成放到ht[1]中,这个措施保证了ht[0]包含的键值对数量只减不增。

总结

这个专题里,学习了底层的字符串实现SDS,并且介绍了它和C语言的字符串相比好在了哪里。接着都是数据结构的一些实现,比如链表。然后学习了一个非常重要的底层实现---字典,分别介绍了字典底层的数据结构及rehash的一些重要过程。其实在jdk中有很多类似的思想,比如HashMap等等。