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

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

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

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

前提条件

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

一、SDS(简单动态字符串)

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

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语言中,如果我们直接对字符串增加,会有如下这种情况的发生:
《共读《redis设计与实现》-数据结构篇》
现在给hello 尾部添加 “-wi” 字符串
《共读《redis设计与实现》-数据结构篇》
“字符串“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;

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

特性

  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,使得可以使用类型特定的函数

  1. privdata:私有数据,存储dictType构造参数,不同的类型传不同 的参数
  2. ht[]:哈希表,真正存储数据的地方。其中ht[0]是使用的表,ht[1]没有分配内存空间,只有在rehash的时候会分配内存,用到。
  3. 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 结构图

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

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*22^n(2的n次幂)
    2. 如果是收缩导致的rehash,分配的ht[1]内存为:h[0].user2^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 内部结构中使用到了。
本意是减少复杂度,替代平衡树,并且因为跳跃表的实现比平衡树要来得更为简单,所以有不少程序都使用跳跃表来代替平衡树。
结构图:
《共读《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)),我们有没有办法去提高链表的查找效率呢?
我们可以每隔一个节点在上面建立一个节点,也就是新的链表之前链表一半的数量,查找的时候以新链表起点,遇到比当前节点大(小)比后一节点小(大)的就移动到之前节点去查找,这样查找的效率可以得到很大的提升,当然,我们可以在新链表上在建立一层,查找速度比之前的在提高一些,然后在新建一层……这样最终就是一个建立索引的过程。
《共读《redis设计与实现》-数据结构篇》
对于 二分规则(每隔一个节点建立上一层索引) 是否要完美``执行
当最后我们建立好之后是不是发现,每隔一个建立这种索引的过程是不是和平衡二叉树有点像啊?而且有个最重要的是,当我们插入新数据的时候,为了维持每隔一个建立上一层索引的概念,我们不得不更新索引。。这样当索引数量大的时候不又产生效率问题么,似乎也没办法解决了??
既然有这种问题,我们就没必要严格执行二分不就行了么。关注一下我们的 目的 只在于让查找的效率提升,那么我们按照这种方法 提升查找效率,既然不能达到百分百完美,那我们就尽量的靠近实现二分就行。
用数学统计学中 的概率问题去解决,也就是实现平均的二分其实查找效率就能够得到提升,所以并不是严格执行每隔一个进行一次建立索引。

特性:

  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. encodingintset结构体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 那么我在升级 整个集合的类型。从而避免了资源的浪费。
升级首先要做的就是空间重分配
只有升级操作,没有``降级操作。
《共读《redis设计与实现》-数据结构篇》

5.3 优点

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

六、压缩列表

它是我们常用的 zset ,list 和 hash 结构的底层实现之一
《共读《redis设计与实现》-数据结构篇》
《共读《redis设计与实现》-数据结构篇》
和其他类型一样,压缩列表也是由一个结构体来持有存储的数据数据,然后存储了数组中节点的数量,节点的偏移量,节点的存储大小。
其中,entry[] 存储的是有序的数组序列。

entry[]

我们重点看一下entry[]的结构体
《共读《redis设计与实现》-数据结构篇》
《共读《redis设计与实现》-数据结构篇》

为什么小数据量使用

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

encoding

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

一字节、两字节或者五字节长, 值的最高位为 00 、 01 或者 10 的是字节数组编码: 这种编码表示节点的 content 属性保存着字节数组, 数组的长度由编码除去最高两位之后的其他位记录;
一字节长, 值的最高位以 11 开头的是整数编码: 这种编码表示节点的 content 属性保存着整数值, 整数值的类型和长度由编码除去最高两位之后的其他位记录;
《共读《redis设计与实现》-数据结构篇》

《共读《redis设计与实现》-数据结构篇》
如此。我们在遍历节点的之后就知道每个节点的长度(占用内存的大小),就可以很容易计算出下一个节点再内存中的位置。这种结构就像一个简单的压缩列表了。

previous_entry_length

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

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

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

连锁更新

由上述我们知道,下一个节点存储上一个节点的大小,如果我们添加节点 或者 删除节点的时候,节点的大小发生了变化:
《共读《redis设计与实现》-数据结构篇》
考虑下这种情况:
比如多个连续节点长度都是小于254 字节的,都处于 250 和253 字节之间,现在我们在前面插入一个大于254 字节长度的节点,那么后一节点 之前的 1字节 显然不能满足,只能更改为 5 字节来尽心存储 大于254 字节的长度,我们在看后面,麻烦的事情来了:我们将previous_entry_length 改成5字节的长度,那么我们当前节点就超过了254节点,显然下一节点的previous_entry_length也不满足了,然后我们就又要改,这样一系列的问题就出现了。这样的问题称为 连锁更新。
尽管连锁更新的复杂度较高,但是它真正造成性能问题的几率是很低的:

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

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

对象系统

到这里我们已经将redis 的存储结构讲完了,但是对象系统和 存储结构之间具体的关系,或者说联系是什么呢?
首先我们明白,在对象系统中,redis 有大对象:STRINGLISTSETZSETHASH
然后每个对象 的底层存储是 我们上面说的哪几种类型,
说白了就是说的 java中的基本类型对象之间的关系。
《共读《redis设计与实现》-数据结构篇》
《共读《redis设计与实现》-数据结构篇》
从上面我们知道每种对象都至少 有两种 基本类型,那么他们之间的划分 或者说界限是什么呢?

1. 界限

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

2. 各种对象API

STRING API

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

LIST API

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

SET API

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

ZSET API

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

HASH API

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

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设计与实现》-黄健宏
部分图片来与百度搜索

    原文作者:张小吉
    原文地址: https://www.cnblogs.com/zhangxiaoji/p/16146311.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞