共读《redis设计与实现》-数据结构篇

每个月读一本厚书

准备将之前攒下的书先看一遍，主要是有个大概的了解，以后用的时候也知道在哪里找。所以准备开几篇共读的帖子，激励自己多看一些书。

Redis 基于 简单动态字符串（SDS）、双端链表、字典、压缩列表、整数集合等基础的数据结构，创建了一个对象系统，这个对象系统包含：字符串对象（String）、列表对象（List）、集合对象（Set）、有序集合对象（Zset）、哈希对象（Hash） 5种数据对象类型。但是这5种对象类型，其内部的基础的存储结构 并不是 一对一的一种，而是每一种包含了至少两种数据结构。

我们这篇主要用来说一下其基础的存储结构

前提条件

redis 底层是使用C语言编写的，所以很多函数直接使用的C库。

一、SDS（简单动态字符串）

我们知道C语言中字符串 是以字符数组char[]进行存储的，字符串的结束是以 空字符‘/0’ 来进行标识的，也就是字符串的实际长度比我们看见的字符串都会多1 byte(字节)。
如果我们想要查看一下字符串的长度，那么就需要遍历一下字符数组，时间复杂度为O(n)。

1.1 结构说明：

1. redis中使用结构体SDS用来存储字符串类型，同样的使用字符数组进行存储 也自带空字符‘/0’，从而可以使用C语言中字符串相关的特性/函数。
2. len：数组已用长度记录，就是说字符串的真实长度（不算‘/0’）
3. free：数组中剩余可用长度，也就是数组中还有多少长度使用的。

1.2 内存预分配

我们从SDS结构图可以知道SDS中字符数组的长度是和字符串长度不一样的，那么这个长度是如何分配的？

1. 首先如果是创建/扩展：
   1. 小于1M，分配的 未使用内存 是 使用内存的2倍
   2. 大于1M，那么 每次扩展未使用内存为 1M
2. 如果是收缩：

并不会立即真正释放，会留下未使用的内存，可以通过Api来进行释放，从而避免内存泄漏。

1.3 二进制

由于C语言中字符串以 ‘/0’标识结尾，所以C语言中字符串不能存储 图片、音视频的二进制数据，但是redis 中字符串以len来做为结尾的判断，所以可以使用字符串来存储二进制的数据。
当然对于 文本类型的 本身结束就是‘/0’结尾的，所以我们可以直接使用C的字符串特性。

1.4 特性(总结)：

1. 自带空格，从而可以使用C语言字符串相关特性
2. 存储 使用空间和未使用空间这样长度可以快速得出（时间复杂度O(1)），不用遍历数组(时间复杂度O(n))
3. 由2我们可以杜绝 C语言中缓存溢出的问题
4. 节省了避免缓存溢出而带来 内存重分配的系统开销
5. 空间预分配
   1. 扩展：小于1M 预分配未使用空间为 使用空间的2倍，大于1M，预分配未使用空间为1M；
   2. 收缩：惰性空间释放
6. 可以存储图片和音视频二进制数据。

关于 C语言缓存溢出：
我们知道数组是一块内存挨着的存储空间，C语言中，如果我们直接对字符串增加，会有如下这种情况的发生：

现在给hello 尾部添加 “-wi” 字符串

"字符串“hello”添加 "-wi" 字符串之后内存快照"

所以C语言中我们为了防止这种情况，每次扩展的时候都会进行 内存重分配，使得空余的字符数组可以容得下我们新加的字符串。但是 内存重分配会导致系统调用，对于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;

特性

1. 双向连表，这样查找前（或者后）一个节点，复杂度为O(1)
2. 有头尾指针，查找第一个节点、最后一个节点复杂度为O(1)
3. 带链表长度计数器，返回长度复杂度为O(1)
4. 无环（⚠️）
5. void* 存储节点的值,可以使用dup\free\match 等特定函数。

三、字典

C语言本身没有 字典类型，但是对于key-vale 这种映射的关系 在redis是常用的，所以redis 自己构建了一个结构体，本身使用的是 hash 结构

typedef struct dict {
    dictType *type;     //dictType也是一种数据结构，dictType结构中包含了一些函数，这些函数用来计算key的哈希值，进而用这个哈希值计算key在dictEntry型table数组中的下标
    void *privdata;     //私有数据，保存着dictType结构中函数的参数
    dictht ht[2];       //两张哈希表：一张用来正常存储节点，一张用来在rehash时临时存储节点
    long rehashidx;     //rehash的标记：默认-1，当table数组中已有元素个数增加/减少到一定量时，整个字典结构将进行rehash给每个table元素重新分配位置，rehashidx代表rehash过程的进度，rehashidx==-1代表字典没有在进行rehash，rehashidx>-1代表该字典结构正在对进行rehash
} dict;

3.1 字典结构体

1. dictType：也是一种数据结构，dictType结构中包含了一些函数（dup\free等），这些函数用来计算key的哈希值，进而用这个哈希值计算key在dictEntry型table数组中的下标。

说白了，也就是redis 的字典为每种基础类型都创建了一个dictType，使得可以使用类型特定的函数

2. privdata：私有数据，存储dictType构造参数，不同的类型传不同 的参数
3. ht[]：哈希表，真正存储数据的地方。其中ht[0]是使用的表，ht[1]是没有分配内存空间，只有在rehash的时候会分配内存，用到。
4. rehashidx：在rehash的时候才会使用。

3.1.1 redis 哈希表结构体：

typedef struct dictht { //哈希表
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask; 
    unsigned long used;
} dictht;

说明：

1. table 是hash 存储的桶数组地址
2. size 是桶的大小，也就是数组的容量
3. sizemask，进行hash 运算的时候会使用到，一般为 size-1;(用于计算每个key在table中的下标位置=hash(key)&sizemask)
4. 记录哈希表的table中已有的节点数量（节点=dictEntry=键值对）。

3.1.2 redis的hash节点结构体

typedef struct dictEntry {
    void *key;//键
    union{     //值
        void *val;//值可以是指针
        uint64_tu64;//值可以是无符号整数
        int64_ts64;//值可以是带符号整数
    } v;
    struct dicEntry *next;//指向下个dictEntry节点：redis的字典结构采用链表法解决hash冲突,当table数组某个位置处已有元素时，该位置采用头插法形成链表解决hash冲突
} dictEntry;

3.2 结构图

3.3 hash 步骤

1. 算出key 的hash 值（通过key 自身的函数）
2. 使用 步骤1得到的 哈希值 和 sizemask进行运算 index = hash & dict->ht[x].sizemask;得到要存储的索引位置。

其实和java 的hashmap 运算过程一样
当然这种肯定会遇到hash 冲突，这时候就是用 链地址法解决冲突
也为了插入效率问题（插入的话还需要遍历在数组后面的链表），采用头插法

3.4 rehash 步骤

所谓的rehash 就是当前hash 结构（主要是 桶数组）已经低于某种效率了，需要进行优化，从而 再次进行hash运算

1. 给ht[1]分配内存，具体的分配规则：
   1. 如果是扩展(增加值)导致的rehash，分配的ht[1]内存为：h[0].user*2的2^n(2的n次幂)
   2. 如果是收缩导致的rehash，分配的ht[1]内存为：h[0].user的2^n(2的n次幂)
2. 将rehashidx赋值0
3. 将ht[0]的 值 重新hash 运算到ht[1]中去，运行一次 rehashidx值 +1
4. 将 ht[0]释放，将ht[1]改为ht[0]，新建一个ht[1]

3.5 rehash 触发条件

• 没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子 大于或等于1。
• 目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于或等于5。
• 当哈希表的负载因子``小于``0.1时，redis会自动开始对哈希表进行缩容操作。

说一下负载因子：节点数/桶大小

3.6 渐进rehash

对于数量小的hash表进行 reash 一次执行就ok ,但是数据量特别大的呢？那种成千上万几亿的数据，这种如果进行一次性的rehash的话占用资源是非常大的，此时redis 就要处于不可用的状态了，这种是绝对不允许的，所以这种是需要分批次来进行rehash,就是渐进rehash。

对于这种有个注意点：
如果在rehash 的时候写入数据，那么我们直接写到ht[1]上，
但是如果是读、更新、删除操作 则是两个ht[]都要用

3.7 特性

1. ht[0] 为一般存储，ht[1] 为rehash时使用的存储
2. rehashidx 开始为 -1 ，开始rehash的时候会变成0
3. hash 算法是MurMurHash
4. 通过链地址法解决冲突
5. 采用头插法
6. 使用渐进rehash
7. 触发条件

四、跳跃表

对于一个有序数组，我们想要快速访问，并且频繁的更新数据，那么我们会使用什么样的存储操作呢？对于 有序这两个字 我们快速访问肯定想到的是二分表，树形结构，尤其是 二叉平衡树 最为可靠，但是二叉平衡树 以及它的简易替代 红黑树在数据库这种 更新比较频繁的应用中，维持他们的平衡是很耗费性能的。所以redis 采用了相似的 跳跃表 这种结构。

不同于前面几种结构，跳跃表 只是在存储大量的有序数组中 或者 redis 内部结构中使用到了。
本意是减少复杂度，替代平衡树，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。
结构图：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;    //header指向跳跃表的表头节点，tail指向跳跃表的表尾节点
    unsigned long length;   //记录跳跃表的长度，也即是，跳跃表目前包含节点的数量(表头节点不计算在内)
    int level;  //记录目前跳跃表内，层数最大的那个节点的层数(表头节点的层数不计算在内)
} zskiplist;

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

说明：

这里说一下跳跃表的思想：
我们在有序列表中查找一个数，

对于**数组**那么我们就可以使用二分法去查找，以此来提高查找效率，但是如果我们要频繁的插入新数据，那就要不断的去移动这个数组的数据，这样来说数据如果特别大性能并没有得到很大的提升（移动数据数据相比查找来说是更耗时的）

对于**链表**来说，我们的插入和删除就比较方便了，毕竟只有指针之间引用的修改，这不提高效率了么？但是链表是不可以用二分法的（中间元素需要遍历才能找到O(n)，数据可以直接访问O(1)），我们有没有办法去提高链表的查找效率呢？
我们可以每隔一个节点在上面建立一个节点，也就是新的链表是之前链表的一半的数量，查找的时候以新链表为起点，遇到比当前节点大（小）比后一节点小（大）的就移动到之前节点去查找，这样查找的效率可以得到很大的提升，当然，我们可以在新链表上在建立一层，查找速度比之前的在提高一些，然后在新建一层……这样最终就是一个建立索引的过程。

对于 二分规则（每隔一个节点建立上一层索引） 是否要完美``执行？
当最后我们建立好之后是不是发现，每隔一个建立这种索引的过程是不是和平衡二叉树有点像啊？而且有个最重要的是，当我们插入新数据的时候，为了维持每隔一个建立上一层索引的概念，我们不得不更新索引。。这样当索引数量大的时候不又产生效率问题么，似乎也没办法解决了？？
既然有这种问题，我们就没必要严格执行二分不就行了么。关注一下我们的 目的 只在于让查找的效率提升，那么我们按照这种方法 提升查找效率，既然不能达到百分百完美，那我们就尽量的靠近实现二分就行。
用数学统计学中 的概率问题去解决，也就是实现平均的二分其实查找效率就能够得到提升，所以并不是严格执行每隔一个进行一次建立索引。

特性：

1. 同样的，跳跃表也是redis 建立了一个结构体来持有节点对象，这样我们使用的时候可以使用 length来获取长度，level 获取最大层数、以及头节点、尾节点，这些获取的时候复杂度都是O(1)
2. 然后 每个 listnode 节点都有 多个``前进指针 和 一个``后退指针
3. 前进指针 指向 比节点大（或者小）的下个节点；（也就是指向尾部元素 的方向）
4. 后退指针 指向 当前节点的 上一层级（只有一个，并且指向上一层级，不能跨级）
5. 我们访问或者查找元素时 通过 前进指针就可以查找到。
6. 随机层数：对于每一个新插入的节点，都需要调用一个随机算法给它分配一个合理的层数，Redis 跳跃表默认允许最大的层数是 32

五、整数集合 5.1 结构体

//每个intset结构表示一个整数集合
typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合中包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

整数集合也是一样的持有一个整数数组的 结构体，结构体中存储 数组长度、数组类型

1. contents[]：是整数集合的底层实现，整数集合的每个元素都是 contents数组的个数组项(item),各个项在数组中按值的大小从小到大有序地排列,并且数组中不包含任何重复项。
2. length：属性记录了数组的长度。
3. encoding：intset结构体将contents属性声明为int8_t类型的数组,但实际上 contents数组并不保存任何int8t类型的值, contents数组的真正类型取决于encoding属性的值。encoding属性的值为INTSET_ENC_INT16则数组就是uint16_t类型，数组中的每一个元素都是int16_t类型的整数值(-32768——32767)，encoding属性的值为INTSET_ENC_INT32则数组就是uint32_t类型，数组中的每一个元素都是int16_t类型的整数值(-2147483648——2147483647)。

5.2 升级

C语言中，内存是需要我们自己行进管理的。其实我们可以知道我们储存的时候并不是一次性存储的，可能之前储存的是 int8 类型的，后来数据发生变化，我们储存int16甚至int32\int64类型的，为了防止这种情况发生，我们一般一开始就进行 int64的定义存储，这样我们就不用担心后面使用的时候发生内存溢出问题。但是有个问题是：我们这样做的话，假如前面的都是int8的，后面int64 最后很晚才入库 或者直接不入库了，这样我们用int64存储的int8数据，这不是内存浪费么？所以，redis 为了这种情况，对没有超过当前存储的情况使用当前结构进行存储，也就是开始就是 int8，等到进来一个数发现存储不够，需要int16\int32 那么我在升级 整个集合的类型。从而避免了资源的浪费。
升级首先要做的就是空间重分配。
只有升级操作，没有``降级操作。

5.3 优点

灵活性：就是我的存储可以更加的灵活，不必担心类型转换的问题。
节约内存：不必一开始就建立大容量的数据。

六、压缩列表

它是我们常用的 zset ，list 和 hash 结构的底层实现之一


和其他类型一样，压缩列表也是由一个结构体来持有存储的数据数据，然后存储了数组中节点的数量，节点的偏移量，节点的存储大小。
其中，entry[] 存储的是有序的数组序列。

entry[]

我们重点看一下entry[]的结构体

为什么小数据量使用

我们知道，对于内存的读取来说 顺序读取 是比 随机读取 效率要高很多的所以对于读取的操作，我们常常会将其设置为数组，提高其读取效率。但是如果是更新来说，大数据量的数组往往是效率不可靠的。所以，我们也就明白为什么 对于压缩列表来说，只有小数据量的才会使用。

encoding

——解决空间浪费问题
对于数据存储也有一个问题：就是我们在整数集合中说的，如果前面的数据是int8 的后面的是int64的，这样我们的存储空间就要设置成64的，前面不就浪费了很多内存么，如何解决这个问题？
我们可以存储成不同结构类型的 啊，比如entry 结构体，我的content 就是不同数据类型的，这样存储的时候小的存储成int8 大的存储成int64,但是这样会有个问题：我们在遍历它的时候由于不知道每个元素的大小是多少，因此也就无法计算出下一个节点的具体位置，如果前面读取的是in8 后面读取的int64 我怎么分开呢？
这个时候我们可以给每个节点增加一个encoding的属性，我们就可以知道这个**content**中记录数据的格式，也就是内存的大小了。

一字节、两字节或者五字节长， 值的最高位为 00 、 01 或者 10 的是字节数组编码： 这种编码表示节点的 content 属性保存着字节数组， 数组的长度由编码除去最高两位之后的其他位记录；
一字节长， 值的最高位以 11 开头的是整数编码： 这种编码表示节点的 content 属性保存着整数值， 整数值的类型和长度由编码除去最高两位之后的其他位记录；

如此。我们在遍历节点的之后就知道每个节点的长度(占用内存的大小)，就可以很容易计算出下一个节点再内存中的位置。这种结构就像一个简单的压缩列表了。

previous_entry_length

我们知道如何顺序读取了，但是如果我想后退读取数据呢？我们不知道前面数据的类型 大小，怎么取截取内存读取呢？
和encoding 一样，我们记录一下上一个entry的大小，然后用当前内存地址-**previous_entry_length** 如此就能计算出上一个内存地址，然后按照相应规则读取了。

这个属性记录了压缩列表前一个节点的长度，该属性根据前一个节点的大小不同可以是1个字节或者5个字节。
如果前一个节点的长度小于254个字节，那么previous_entry_length的大小为1个字节，即前一个节点的长度可以使用1个字节表示
如果前一个节点的长度大于等于254个字节，那么previous_entry_length的大小为5个字节，第一个字节会被设置为0xFE(十进制的254），之后的四个字节则用于保存前一个节点的长度。

连锁更新

由上述我们知道，下一个节点存储上一个节点的大小，如果我们添加节点 或者 删除节点的时候，节点的大小发生了变化：

考虑下这种情况：
比如多个连续节点长度都是小于254 字节的，都处于 250 和253 字节之间，现在我们在前面插入一个大于254 字节长度的节点，那么后一节点 之前的 1字节 显然不能满足，只能更改为 5 字节来尽心存储 大于254 字节的长度，我们在看后面，麻烦的事情来了：我们将previous_entry_length 改成5字节的长度，那么我们当前节点就超过了254节点，显然下一节点的previous_entry_length也不满足了，然后我们就又要改，这样一系列的问题就出现了。这样的问题称为 连锁更新。
尽管连锁更新的复杂度较高，但是它真正造成性能问题的几率是很低的：

1. 要很多连续的，长度介于 250和253 之间的节点
2. 即使出现连锁更新，但是如果只是小范围，节点数量不多，就不会造成性能影响。

所以在实际中我们可以放心的使用这个函数。

---

对象系统

到这里我们已经将redis 的存储结构讲完了，但是对象系统和 存储结构之间具体的关系，或者说联系是什么呢？
首先我们明白，在对象系统中，redis 有五大对象：STRING、LIST、SET、ZSET、HASH
然后每个对象 的底层存储是 我们上面说的哪几种类型，
说白了就是说的 java中的基本类型 和对象之间的关系。


从上面我们知道每种对象都至少 有两种 基本类型，那么他们之间的划分 或者说界限是什么呢？

1. 界限

2. 各种对象API STRING API

LIST API

SET API

ZSET API

HASH API

3. 公共Api 4. 类型检查

我们知道对于redis 来说，每个对象都使用了至少两种基本类型，但是C 语言中，如果类型不一样，常常会出现类型错误的问题。我们怎么解决呢？
这里我们看一下对象的储存结构：

struct redisObject {

    unsigned type:4; // 类型

    unsigned encoding:4; // 编码 

    void *ptr; //执行底层实现数据结构的指针

    int refcount; //引用计数，用于内存回收

    unsigned lru:22; // 记录最近一次访问这个对象的时间

}

通过这个我们可以看到，其实redis 对象存储了使用的基本结构，这样我们使用api的时候，都会进行一个类型检查然后再去进行使用，对于非本类型的 api 返回错误信息。

其实每个对象内部基本类型的转换也是需要注意一下的，就是边界。

5. 多态性

我们可以从 公共api 中可以看到 redis 对象的多态性，就是不同的类型执行的 方法结果是一样的，只不过对于不同的类型都有自己特殊的处理
其实这里的多态性在我们同一个类型中不同基础结构的 API 中也是有体现的。

6. 内存回收/引用计数器

C语言中，内存是交给我们自己来进行管理的，所以当我们不使用这块内存的时候就要就行内存释放。我们怎么知道内存是否还在使用呢？从之前我们对象结构中可以看到，redis 维护了一个 引用计数器，这样我们每次引用的时候都会 使得 refcount+1。其实引用计数器在很多 语言中都有使用java中也使用过，这里面有个比较难受的点：如果两个对象之间相互引用，但是两个都是没有用的，这种永远不会是0，也就就释放不了拉。在redis 中还维护了一个lru就是说设置一个时间，超过这个时间的，那么就强制释放它，这样就避免了相互引用导致的 内存释放问题。

7. 对象共享

redis 大量用到了sds 这种结构，而且可以在其他基本结构中 嵌套使用。例如链表的节点的值可以使用 sds 。我们如果有很多一样的数据，如果在内存中分配一个空间，少量的还行如果数量多了岂不会“浪费”？
所以redis 采用了对象共享，也就是这个类型的数据如果在内存中已经有了，那么我们再次创建的时候不会开辟新的空间，直接使用对象的引用，此时引用计数器+1，那么数据量大的时候就会节省很多内存。
redis 服务器启动的时候会创建一万个字符串对象，这些对象包含0-9999字符串对象，以后使用的时候不在创建新的而是使用这个对象。

参考资料

《Redis设计与实现》-黄健宏
部分图片来与百度搜索