Redis五种基本数据类型底层详解

Redis五种基本数据类型底层详解

• 详细介绍Redis用到的数据结构
• • 简单动态字符串
  • • SDS和C字符串的区别
    • 总结
  • 链表
  • 字典
  • • 哈希表
    • 字典
    • 哈希算法
    • 解决键冲突
    • rehash(重点)
    • 渐进式rehash
  • 跳跃表
  • • Redis中跳跃表的实现
    • • 跳跃表节点结构
      • 跳跃表总体结构
  • 整数集合(intset)
  • • 整数集合具体实现
    • 数组升级
    • 数组降级？没有降级，一旦升级就不会降级
    • 数组升级的好处
  • 压缩列表

详细介绍Redis用到的数据结构

各位，稍安勿躁，讲解五种基本数据类型前，我们先来这些数据类型用到的数据结构，防止后面懵逼,本文所用源码来源：Redis源码链接，版本使用6.2

简单动态字符串

我们都知道Redis是用C写的，但Redis中并没有直接使用C语言传统的字符串(以空字符结尾的字符数组)，而是自己构建了一种名为简单动态字符串(simple dynamic string，简称SDS)的结构，并用作Redis的默认字符串。在Redis中，C字符串只会用作字符串字面量，一些不会对字符串发生修改的地方，比如说打印日志等等。

Redis中SDS的定义：

typedef char *sds;      

struct __attribute__ ((__packed__)) sdshdr5 {     // 对应的字符串长度小于 1<<5
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {     // 对应的字符串长度小于 1<<8
    uint8_t len; /* used */                       //目前字符串的长度
    uint8_t alloc;                                //已经分配的总长度
    unsigned char flags;                          //flag用3bit来标明类型
    char buf[];                                   //柔性数组，以'}'结尾
;struct
__attribute__ ( ()__packed__)sdshdr16 // 对应的字符串长度小于 1<<16 {    uint16_t
    ; len/* used */ uint16_t
    ; alloc/* excluding the header and null terminator */ unsigned
    char ; flags/* 3 lsb of type, 5 unused bits */ char
    [ buf];}
;struct
__attribute__ ( ()__packed__)sdshdr32 // 对应的字符串长度小于 1<<32 {    uint32_t
    ; len/* used */ uint32_t
    ; alloc/* excluding the header and null terminator */ unsigned
    char ; flags/* 3 lsb of type, 5 unused bits */ char
    [ buf];}
;struct
__attribute__ ( ()__packed__)sdshdr64 // 对应的字符串长度小于 1<<64 {    uint64_t
    ; len/* used */ uint64_t
    ; alloc/* excluding the header and null terminator */ unsigned
    char ; flags/* 3 lsb of type, 5 unused bits */ char
    [ buf];}
;
C字符串中使用n+1个字符数组表示n个长度的字符串，并且数组的最后一个总是‘时间复杂度为O(1)’，表示该字符串结尾了。

SDS和C字符串的区别

不会发生缓冲区溢出
• C字符串获取长度时，需要遍历一遍字符串，时间复杂度为O(N),而SDS获取字符串长度时，只需要从SDS结构中取出len字段便可以，减少字符串带来的内存重分配次数
• C字符串为其增加一段字符串时，如果没有为其分配足够的空间，则会造成缓冲区溢出；而使用我们的SDS时，则SDS会自动检查是否容量足够，不够的话就扩容，所以使用我们的SDS时不需要手动扩容，也就提前分配和惰性释放
• 提前分配,在C中，每次添加字符串都需要对数组扩容，删除字符串也需要内存重新分配。而SDS通过惰性释放可以很好的改善内存重分配次数
  二进制安全：当SDS剩余空间不足时，Redis不但会给它分配足够的空间，还会给它分配多余的空间，如果下次增加字符串时，则可以使用这部分空余的空间，减少内存重分配
  兼容部分C字符串函数:在删除一些字符时，Redis并不会立即释放空间，这样的话可以为将来的增加 *** 作减少内存重分配的次数；于此同时，在Redis真正需要空间时，Redis也会释放掉这部分空间，不会内存泄露
• typedef：C字符串中不能包含一些空字符，否则可能会被认为是字符串结尾导致字符串截断，所以不能保存一些图片视频的二进制数据。而SDS并不是通过空字符来判断结束的，不会对内容进行任何处理，可以保存二进制数据
• struct：Redis也会在结尾加上多余的一个‘\0’，使得某些情况可以使用C字符串的函数，减少自己实现重复功能

总结

由于Redis数据库的特性，会频繁的增删查改，保存一些二进制数据，而原来的C字符串并不能高性能的完成这些事，所以Redis才自己封装了SDS

链表

Redis定义的结构

listNode struct listNode {
    * ; structprevlistNode
    * ; voidnext*
    ; }value;
typedef listNodestruct

这是双端链表最基础的定义，下图是示意图：

虽然使用多个listnode便可以组成链表的话，但Redis使用list结构来持有链表， *** 作更加方便

list //表头结点 * {
	;
    listNode //表尾结点head*
    ;
    listNode //结点复制函数tailvoid
    *
    ( *)(dupvoid*) ;ptr//结点释放函数void
    (
    * )(freevoid*) ;ptr//结点对比函数，通过这三个函数可以为结点值设置不同的函数，从而包含各种不同类型的值，实现多态int
    (
    * )(matchvoid*, voidptr* ) ;key//结点的数量unsigned
    long
    ; } len;
Redis的字典底层使用哈希表来实现 list/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */

总体结构如下：

字典

在字典中，一个键（key）可以和一个值（value）进行关联（或者 说将键映射为值），这些关联的键和值就称为键值对；

typedef，一个哈希表中有多个哈希表结点，一个哈希表结点保存了字典中的一个键值对

哈希表

Redis中源码表示：

struct
dictht //哈希表数组，里面是一个dictEntry结构 * {
	*
    dictEntry ;//哈希表大小tableunsigned
    long
    ; //哈希表大小掩码，用于计算索引值，总是等于size-1 sizeunsigned
    long
    ; //已经存在结点的数量 sizemaskunsigned
    long
    ; } used;
//哈希表结点 dicthttypedef

struct
dictEntry //键 void {
	*
    ; //值keyunion
    void
    * {
        ; uint64_tval;
        int64_t u64;
        double s64;
        } d;
    //下一个节点，使其形成链表 vstruct
    dictEntry
    * ; }next;
typedef dictEntrystruct

以上两个结构总体为：

字典

Redis中字典结构源码表示：

dict //类型特定函数 * {
	;
    dictType //私有数据typevoid
    *
    ; //两个哈希表，作用后面说privdata[
    2
    dictht ht];//当rehash不进行时，值为-1long
    ;
    /* rehashing not in progress if rehashidx == -1 */ rehashidxint16_t ;
    } pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
type和privdata dictht[2]

rehashidx是针对不同类型的键值对，为多态而创建的
=两个哈希表是为了rehash而设计的，一般只使用ht[0]这个哈希表，ht[1]只会在对ht[0]进行rehash的时候使用
hashFunction它记录了目前rehash的进度，为-1时则说明不进行rehash

不进行rehash下的字典示意图：

哈希算法

当插入一个键值对时，需要用哈希算法算出对应的索引值，并把它插入其中(具体就不再多说什么，不了解的可以去查看数据结构这门课程)

Redis计算哈希值和索引的方法：

#使用字典设置的哈希函数，计算键key 的哈希值 
hash ( dict->type->);key[] 
#使用哈希表的sizemask 属性和哈希值，计算出索引值 
#根据情况不同，
ht[x0 可以是ht][1 或者ht]=& index [ hash ] dict->ht.x;而扩展或者收缩，我们需要执行rehash(重新散列)来完成一次 *** 作sizemask
为字典的ht[1]分配空间，大小取决于ht[0]和所执行的扩展或者收缩 *** 作。

Redis使用MurmurHash2算法来计算键的哈希值，这种算法最大的优点就是当输入有规律的数时，也能平均散列到数组中

解决键冲突

Redis使用链地址法解决键冲突

rehash(重点)

随着 *** 作的进行，哈希表的键值对会逐渐增多或者减少，为了让哈希表的负载因子保持在一个合理的范围区间，就必须对哈希表进行扩展或者收缩。

将ht[0]的所有键值对rehash到ht[1]上(rehash指的是重新计算哈希值和索引，重新散列到ht[1]这个哈希表中)

rehash执行步骤如下：

• 移动完成后，释放ht[0]的空间，将ht[1]改为ht[0]，并为ht[1]重新创建一个空的哈希表，为下一次rehash准备
所以执行rehash时，并不是一次完成的，而是渐进式完成的
• 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表

渐进式rehash

如果数据量比较多时，一次性移动我们的hash表，那么时间会比较久，就有可能造成redis服务停止。

在字典中维持一个rehashidx，也就是上面的字典结构的属性，将其值设置为0，表示rehash工作开始

渐进式rehash步骤如下：

相当于将ht[0]里的数据删除，在ht[1]里面增加
1. 完成后，将rehashidx的值表示为-1，并将ht[1]设置为ht[0].
2. 在rehash期间，程序除了执行指定的 *** 作外，还会将索引为rehashidx的数据移动到ht[1]删除，更新，查找，当rehashidx这个索引的数据全部移动完成时，则将rehashidx值加1，直到全部完成
插入

在渐进式rehash期间，字典进行的/* ZSETs use a specialized version of Skiplists */会在两张哈希表上进行。比如查找，redis会先在ht[0]查找，找不到才会到ht[1]上面查找

而字典进行的typedef *** 作，则只会在ht[1]表里执行。这样的话，ht[0]表里的数量只减 不增，也减少了重复插入的 *** 作

跳跃表

在Redis中，有两个地方用到了跳跃表，一个是实现有序集合类型，一个是在集群节点中作内部数据结构

Redis中跳跃表的实现 跳跃表节点结构

跳跃表节点在/src/server.h/中zskiplistNode结构定义：

struct
zskiplistNode //成员对象 ; {
	//分值
    sds eledouble
    ;
    //回退指针 scorestruct
    zskiplistNode
    * ; //跳表层backwardstruct
    zskiplistLevel
    //前进指针 struct {
    	zskiplistNode
        * ; //跨度forwardunsigned
        long
        ; } span[
    ] level;};
zskiplistLevel跳表层： zskiplistNodeforward

span
上图的L1,L2就表示的是跳表层，每个层有两个属性。 backward回退指针：表示前进指针，用它来遍历后面的元素。score分值：表示跨度：上图连线上的数字就是这个跨度，两个元素离的越远，跨度就越大；而这个跨度的作用就是计算我们的rank(排位) ，在遍历一个元素时，就他路径上的跨度全部加起来就是它的rank。比如查找下面的o3这个节点时，rank就为3

ele成员对象：
每个节点只有一个回退指针，所以每次只能回退到前一个节点，而不能跳来跳去；回退指针用于从后向前遍历
typedef是一个double类型的浮点数，跳表中所有元素都是按分值来排序的。
struct是一个sds的字符串对象。成员对象必须是唯一的，而分值可以是相同的。分值相同时，按成员变量的字典序排序

跳跃表总体结构

一个跳跃表有多个跳跃表节点。通过zskiplist来持有这些节点。
Redsi中zskiplist结构的定义如下：

zskiplist //表示表头结点和表尾节点 struct {
	zskiplistNode
    * , *header; //节点数量tailunsigned
    long
    ; //最大层数 lengthint
    ;
    } level;
typedef zskipliststruct

看到上面这张图应该就可以明白每个字段表示的含义了吧！表头那个节点并不计算在内。准确的来说，表头节点虽然都有对应的属性，但是我们是不会用到的，只是后面插入，删除时更加方便

整数集合(intset)

整数集合是Redis用来保存整数值的集合，保证集合中不会出现重复的元素

整数集合具体实现

intset //编码方式 uint32_t {
	;
    //集合数量 encodinguint32_t
    ;
    //保存元素的数组 lengthint8_t
    [
    ] contents;};
encoding编码方式 intsetlength集合数量

contents[]集合数组表示数组用什么类型来保存
数组内是大小有序的，从小到大，不含重复值保存了集合中的数量

按新的类型扩展原有数组大小，并为新元素分配空间

虽然是类型是int8_t，但是实际取决于encoding编码方式。

将原来的数组元素转换为新的元素类型，并且保存有序

数组升级

当对数组中添加新元素时，如果新添加的元素类型大于原来的数组的类型，则需要对数组进行升级。
升级步骤如下：

1. 更加方便2. 节约内存
• 将新添加的元素加入数组
  大致流程如下：
  
  
  
  

因为新添加的类型是大于原有数组类型的，所以新添加的元素一定大于或者小于原有数组里的元素，每次插入也一定是插到头或者尾

数组降级？没有降级，一旦升级就不会降级 数组升级的好处

C语言中要保存两种不同类型的元素就必须使用两个类型数组来保存
而Redis则使用数组升级来避免了使用两个数组，更加方便，且不用担心类型错误

要让一个数组保存不同的类型，最简单就是直接定义一个最大的数组类型，但是这样会占用不必要的空间
而Redis则只是在必要的时候才升级数组，尽量节约了内存

压缩列表

明天写