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[];//柔性数组，以'\0'结尾};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[];};

SDS和C字符串的区别

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

总结

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

链表

Redis定义的结构

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

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

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

typedef struct list {//表头结点    listNode *head;    //表尾结点    listNode *tail;    //结点复制函数    void *(*dup)(void *ptr);    //结点释放函数    void (*free)(void *ptr);    //结点对比函数，通过这三个函数可以为结点值设置不同的函数，从而包含各种不同类型的值，实现多态    int (*match)(void *ptr, void *key);    //结点的数量    unsigned long len;} list;

总体结构如下：

字典

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

Redis的字典底层使用哈希表来实现，一个哈希表中有多个哈希表结点，一个哈希表结点保存了字典中的一个键值对

哈希表

Redis中源码表示：

/* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. */typedef struct dictht {//哈希表数组，里面是一个dictEntry结构    dictEntry **table;    //哈希表大小    unsigned long size;    //哈希表大小掩码，用于计算索引值，总是等于size-1    unsigned long sizemask;    //已经存在结点的数量    unsigned long used;} dictht;//哈希表结点typedef struct dictEntry {//键    void *key;    //值    union { void *val; uint64_t u64; int64_t s64; double d;    } v;    //下一个节点，使其形成链表    struct dictEntry *next;} dictEntry;

以上两个结构总体为：

字典

Redis中字典结构源码表示：

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

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

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

哈希算法

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

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

#使用字典设置的哈希函数，计算键key 的哈希值 hash = dict->type->hashFunction(key); #使用哈希表的sizemask 属性和哈希值，计算出索引值 #根据情况不同，ht[x] 可以是ht[0] 或者ht[1] index = hash & dict->ht[x].sizemask;

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

解决键冲突

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

rehash(重点)

随着操作的进行，哈希表的键值对会逐渐增多或者减少，为了让哈希表的负载因子保持在一个合理的范围区间，就必须对哈希表进行扩展或者收缩。而扩展或者收缩，我们需要执行rehash(重新散列)来完成一次操作
rehash执行步骤如下：

• 为字典的ht[1]分配空间，大小取决于ht[0]和所执行的扩展或者收缩操作。
• 将ht[0]的所有键值对rehash到ht[1]上(rehash指的是重新计算哈希值和索引，重新散列到ht[1]这个哈希表中)
• 移动完成后，释放ht[0]的空间，将ht[1]改为ht[0]，并为ht[1]重新创建一个空的哈希表，为下一次rehash准备

渐进式rehash

如果数据量比较多时，一次性移动我们的hash表，那么时间会比较久，就有可能造成redis服务停止。所以执行rehash时，并不是一次完成的，而是渐进式完成的
渐进式rehash步骤如下：

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
2. 在字典中维持一个rehashidx，也就是上面的字典结构的属性，将其值设置为0，表示rehash工作开始
3. 在rehash期间，程序除了执行指定的操作外，还会将索引为rehashidx的数据移动到ht[1]相当于将ht[0]里的数据删除，在ht[1]里面增加，当rehashidx这个索引的数据全部移动完成时，则将rehashidx值加1，直到全部完成
4. 完成后，将rehashidx的值表示为-1，并将ht[1]设置为ht[0].

在渐进式rehash期间，字典进行的删除，更新，查找会在两张哈希表上进行。比如查找，redis会先在ht[0]查找，找不到才会到ht[1]上面查找

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

跳跃表

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

Redis中跳跃表的实现

跳跃表节点结构

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

/* ZSETs use a specialized version of Skiplists */typedef struct zskiplistNode {//成员对象    sds ele;    //分值    double score;    //回退指针    struct zskiplistNode *backward;    //跳表层    struct zskiplistLevel {    //前进指针 struct zskiplistNode *forward; //跨度 unsigned long span;    } level[];} zskiplistNode;

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

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

跳跃表总体结构

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

typedef struct zskiplist {//表示表头结点和表尾节点    struct zskiplistNode *header, *tail;    //节点数量    unsigned long length;    //最大层数    int level;} zskiplist;

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

整数集合(intset)

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

整数集合具体实现

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

encoding编码方式表示数组用什么类型来保存
length集合数量保存了集合中的数量
contents[]集合数组虽然是类型是int8_t，但是实际取决于encoding编码方式。数组内是大小有序的，从小到大，不含重复值

数组升级

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

• 按新的类型扩展原有数组大小，并为新元素分配空间
• 将原来的数组元素转换为新的元素类型，并且保存有序
• 将新添加的元素加入数组
  大致流程如下：
  
  
  
  

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

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

数组升级的好处

1. 更加方便
C语言中要保存两种不同类型的元素就必须使用两个类型数组来保存
而Redis则使用数组升级来避免了使用两个数组，更加方便，且不用担心类型错误
2. 节约内存
要让一个数组保存不同的类型，最简单就是直接定义一个最大的数组类型，但是这样会占用不必要的空间
而Redis则只是在必要的时候才升级数组，尽量节约了内存

压缩列表

压缩列表是Redis为了节约内存而开发的，是一种由连续内存块组成的顺序结构。一个压缩列表包含多个节点，每个节点可以是一个字节数组或者整数。
下图是压缩列表的各个组成部分：

各个字段含义如下：

下面是压缩列表的节点构成：

previous_entry_length：表示前一个节点的长度，用于从尾向前遍历；如果前一个节点长度小于254个字节，那么就用1字节来保存，如果大于等于254字节，就用5字节来保存。
encoding：记录了content保存的数据类型和长度
content：保存节点的值，类型和长度由encoding类型决定

连锁更新

那我们考虑一种情况，如果每一个节点的长度都在靠近254字节。那么新插入了一个大于等于254字节的节点，那么下一个节点的头部就必须是5个字节了(本来previous_entry_length只用一个字节)，所以程序将对压缩列表执行空间重分配操作，将该节点扩容至5字节。但是该节点现在扩容后又大于254字节了，所以后面的节点又要接着扩容。当然，删除一个节点也可能造成这种情况：比如说第一个节点长度大于等于254，第二个节点长度小于254，那么后面一个节点previous_entry_length保存的就是1字节，那我们把第二个节点删除，现在不就又变成刚才的情况了嘛！！！Redis把这种特殊情况造成的连续更新叫做连锁更新

五种数据类型

Redis使用对象来表示数据库中的键和值。当创建一个对象时，最少会包含两个对象，一个用作键值对的键(固定是字符串类型)，一个用作键值对的值(可以是五种数据类型)。我们可以使用type命令显示键对应值的数据类型

Redis的每个对象都用一个redisObject结构来表示（src/server.h）：

typedef struct redisObject {//类型    unsigned type:4;    //编码方式    unsigned encoding:4;    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or* LFU data (least significant 8 bits frequency* and most significant 16 bits access time). */    //用来实现引用计数的，内存管理计数    int refcount;    //指向底层实现数据结构的指针    void *ptr;} robj;

type类型：就是上面的五种类型
ptr指针指向底层实现的数据结构
ending编码方式:

/* Objects encoding. Some kind of objects like Strings and Hashes can be * internally represented in multiple ways. The 'encoding' field of the object * is set to one of this fields for this object. */#define OBJ_ENCODING_INT 1     /* Encoded as integer */#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */#define OBJ_ENCODING_RAW 0     /* Raw representation */#define OBJ_ENCODING_HT 2      /* Encoded as hash table */#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */

通过object encoding可查看对应的编码

下面我们来讲讲这五种基本数据类型的对象，对象底层可以使用的编码方式等等

字符串对象

字符串对象的编码可以是以下这三种：

#define OBJ_ENCODING_INT 1     /* Encoded as integer */#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */#define OBJ_ENCODING_RAW 0     /* Raw representation */

int：存储8个字节的长整型(long,2的63次方-1)，那么字符串对象会将整数值保存在字符串里的ptr属性里面，将void*转换为long，并将字符串编码设置为int
embstr：代表embstr格式的SDS，用来存储小于等于44字节的字符串；embstr只会调用一次内存分配函数来分配空间，因为redisObject结构和sdshdr结构是连在一起的
raw：存储大于44字节的字符串，需要调用两次内存分配函数
Redis浮点数也是用字符串值来表示的，需要用时先把它转为浮点数，计算完后又转为字符串值保存

列表对象

#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */

在Redis早期的时候，当列表数量较少时使用ziplist压缩列表，数量较多时使用linkedlist来实现 (好多书上也是这样讲的)

后面版本列表对象都是由quicklist快速列表实现的。

哈希对象

当键值对的长度都小于64字节，且键值对数量小于512个时，使用ziplist，否则使用hashtable

明天写