Redis底层数据结构详解

上一篇说了Redis有五种数据类型，今天就来聊一下Redis底层的数据结构是什么样的。是这一周看了《redis设计与实现》一书，现来总结一下。（看书总是非常烦躁的！）

Redis是由C语言所写，所以以下会有c语言的片段，不过都是一些定义，很好理解。

Redis底层数据结构有六种：

1、简单动态字符串

2、链表

3、字典

4、跳跃表

5、整数集合

6、压缩列表

7、快速列表

接下来看一下每种数据结构到底是啥？

一、简单动态字符串

（1）Redis默认字符串底层存储结构，比如set k1 v1，键k1是一个字符串，底层实现是保存着字符串k1的SDS，值v1也是一个字符串，底层实现是保存着字符串v1的SDS

（2）每个sds.h/sdshdr表示一个SDS，结构如下

struct sdshdr {
    //记录buf数组中已使用字节的数量，相当于保存的字符串的长度
    int len;  
    //记录buf数组中未使用的字节数量
    int free;
    //字节数组，用于保存字符串
    char buf[]
};

结构图如下：

buf数组的最后一个空字符‘\0’是因为其遵循了C字符串以空字符结尾的惯例。

（3）优点：

1>获取字符串长度的复杂度为O(1)。

2>杜绝缓存区溢出。因为其API会进行空间扩展，扩展之后未使用字节数量free和已使用字节数量len一样

3>减少字符串修改时的内存重分配次数，因为有free（预分配），所有在最坏的情况下就是修改n次，重分配n次。

二、链表

（1）redis的list数据类型的底层实现之一，类似于java集合类LinkedArrayList。

（2）每个链表节点用一个adlist.h/listNode结构来表示

struct listNode{
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;     
}listNode;

多个listNode可以通过prev和next指针组层双端链表

（3）链表通过结构adlist.h/list来构建

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）字典又称为符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构，如果了解java7的HashMap的底层实现，那么这个自然就懂了。

（2）使用哈希表由dict.h/dictht结构定义

struct dictht{
    //哈希表数组 
    dictEntry **table;
    //哈希表大小 
    unsigned long size;
    //大小掩码，用于计算索引值，总是等于size-1
    unsigned long sizemask;
    //已有节点的数量  
    unsigned long used;
}dictht;

table是一个数组，类型是指向dict.h/dictEntry结构的指针。每个dictEntry保存着一个键对值，结构如下

struct dictEntry{
    //键
    void *key;
    //值，下面三个的其中一个
    union{
        //指针
        void *val;
        //uint64_t整数
        uint64_tu64;
        //int64_t整数
        int64_ts64;
    }v;
    //指向下一个节点的指针
    struct dictEntry *next;
}dictEntry;

如果此时表中有一个entry的键为k0，插入键为k1的entry的时候，k1、k0它俩的hash值都一样，这时候就发生了哈希冲突，那么此时k1就会放在table中对应的索引下，k1的next就会指向k0，这个就是解决hash冲突的实现。（简直跟java7的HashMap实现一毛一样）

四、跳跃表（划重点，要考的）

（1）跳跃表是一种有序的数据结构，通过每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。这种数据结构可以在小于等于O(n)的情况下找到相应的数据。

1>由很多层组成

2>每一层都是一个有序的链表

3>最底层的链表包含了所有的元素；

4>如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）；

5>链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个链表节点；

简单的理解就是当前层节点之间的间隔都比下一层更大，但是每一层都必须是有头结点和尾节点。

（2）redis中跳跃表定义由zskiplistNode和zskiplist两个结构定义zskiplistNode表示节点，zskiplist表示整个跳跃表信息。

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

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

redis中的结构如下图：

上图中用BW字样表示节点的后腿指针，指向当前节点的前一个节点，可用于从后往前遍历。

（3）增删改节点操作

①、搜索：从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。

②、插入：首先确定插入的层数，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定插入的层数k后，则需要将新元素插入到从底层到k层。

③、删除：在各个层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。

五、整数集合

（1）整数集合（intset）是Redis用于保存整数值的集合抽象数据类型，它可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。

（2）用intset结构实现：

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

整数集合的每个元素都是 contents 数组的一个数据项，它们按照从小到大的顺序排列，并且不包含任何重复项。

length 属性记录了 contents 数组的大小。

需要注意的是虽然 contents 数组声明为 int8_t 类型，但是实际上contents 数组并不保存任何 int8_t 类型的值，其真正类型有 encoding 来决定。

（3）升级

当我们新增的元素类型比原集合元素类型的长度要大时，需要对整数集合进行升级，才能将新元素放入整数集合中。具体步骤：

1、根据新元素类型，扩展整数集合底层数组的大小，并为新元素分配空间。

2、将底层数组现有的所有元素都转成与新元素相同类型的元素，并将转换后的元素放到正确的位置，放置过程中，维持整个元素顺序都是有序的。

3、将新元素添加到整数集合中（保证有序）。

升级能极大地节省内存，因为如果需要保存不同长度的值的话，需要将集合置为64位的。

（4）整数集合不支持降级操作

六、压缩列表

（1）压缩列表（ziplist）是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

（2）结构如下：

①、previous_entry_ength：记录压缩列表前一个字节的长度。previous_entry_ength的长度可能是1个字节或者是5个字节，如果上一个节点的长度小于254，则该节点只需要一个字节就可以表示前一个节点的长度了，如果前一个节点的长度大于等于254，则previous length的第一个字节为254，后面用四个字节表示当前节点前一个节点的长度。利用此原理即当前节点位置减去上一个节点的长度即得到上一个节点的起始位置，压缩列表可以从尾部向头部遍历。这么做很有效地减少了内存的浪费。

②、encoding：节点的encoding保存的是节点的content的内容类型以及长度，encoding类型一共有两种，一种字节数组一种是整数，encoding区域长度为1字节、2字节或者5字节长。

③、content：content区域用于保存节点的内容，节点内容类型和长度由encoding决定。

七、快速列表

（1）由于使用链表的附加空间相对太高以及内存碎片化等缺点，Redis后续版本对列表数据结构进行改造，使用quicklist代替了ziplist和linkedlist。

（2）快速列表有quicklistNode和quicklist结构组成

// 快速列表节点
struct quicklistNode {
    quicklistNode *prev;
    quicklistNode *next;
    ziplist *zl;         // 指向压缩列表
    int32 size;          // ziplist字节总数
    int16 count;         // ziplist中元素数量
    int2 encoding;       // 存储形式，表示原生字节数组还是LZF压缩存储
    ...
} quicklistNode；

// 快速列表
struct quicklist {
    quicklistNode *head;
    quicklistNode *next;
    long count;           // 元素总数
    int nodes;            // ziplist节点个数
    int compressDepth;    // LZF算法压缩深度
}
quicklist;

从代码可以看出，quicklist实际上是ziplist和linkedlist的混合体，它将linkedlist按段进行切分，每一段使用ziplist进行紧凑存储，多个ziplist之间使用双向指针进行串接。

以上就是Redis七种数据结构的介绍。下面看一下Redis五种数据类型的底层数据结构分别是什么？

Redis中的每一个对象都是由redisObject结构表示，三个属性分别是type，encoding，ptr

struct redisObject{
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针 
    void *ptr;
}robj;

type记录里对象的类型，是如下几个，可以在redis中用“type key”获取类型

对象的ptr指针指向对象的底层实现数据结构，而数据结构是由encoding属性决定的。

Encoding属性记录了对象所使用的编码，也即是说使用了何种数据结构 。

使用object encoding key可以查看数据库的键的值对象所使用的编码。

一、字符串对象

字符串对象的编码可以是int，raw或者是embstr。

如果一个字符串对象保存的是整数值，此时使用的int编码

如果一个字符串对象保存的字符串长度大于32字节，使用的raw编码

如果一个字符串对象保存的字符串长度小于32字节，使用的是embstr编码，此编码与raw并无不同，只是底层结构不一样，如下图，其空间是连续的，而raw的redisObject和SDS是分开的。

二、列表对象

在redis的早期版本中，列表对象使用的编码是ziplist或linkedlist。

但是现在使用的是快速列表（quicklist）

三、哈希对象

哈希对象的底层编码是ziplist或者hashtable（字典）

当哈希对象保存的所有键对值的键和值的长度都是小于64字节并且键对值数量小于512个的时候，使用ziplist。

保存键对值的时候，现将键压至栈底，再将值压至栈底。

当不满足用ziplist的条件的时候，使用hashtable

上述两个条件的上限值是可以修改的，具体是配置文件中的hash-max-ziplist-value和hash-max-ziplist-entried属性。

四、集合对象

集合对象可使用的编码是intset或hashtable

当集合中所有元素都是整数并且元素数量小于512个，intset底层是使用整数集合实现的。

当不满足用intset的条件的时候，使用hashtable

//使用eval命令执行lua脚本，往集合set_k添加514个数据
eval "for i=4,516 do redis.call('sadd',KEYS[1],i) end" 1 set_k

上述intset的上限值是可以修改的，具体的配置项是set-max-intset-entries属性。

五、有序集合对象

有序结合对象使用的是ziplist或者是skiplist

当有序集合中元素小于128个并且所有元素的长度都小于64字节，使用ziplist，ziplist保存的方式也是先保存键，再保存值，键和值是挨着的，元素是按照值由小变大排序的。

当不满足ziplist的两个条件的时候，使用的是skiplist，skiplist底层是zset结构，包含一个字典和一个跳跃表。

struct zset{
    //跳跃表
    zskiplist *zkl;
    //字典
    dict *dict;
}zset;

zsl属性是一个跳跃表，按分值从小到大保存所有集合元素，每个节点保存一个元素，节点的object属相保存元素的成员，scope属性保存元素的分值，通过跳跃表，可以实现范围的操作，例如ZRANK，ZRANGE等。

dict是一个字典，字典的每一个键对值保存着一个集合元素，键是元素，值是对应的分值。可以支持复杂度为O(1)的元素分值查找。

从上述可以各种数据类型的底层实现数据结构可以看到，redis支持在不同的场景下使用不同的编码用来优化对象的使用效率。

服务器在执行某个命令的时候，会先根据redisObject里的type属性判断是否可以执行指定的命令。

Redis使用引用计数实现内存回收机制（在JVM垃圾回收的时候说过，此机制不能解决循环引用的问题，所以JVM不用此机制）。

这篇文章比较长，普通redis使用者其实没必要了解的那么详细，简单知道有这么一回事就行了，真正应该关注的是redis在何种场景的用法是什么，这一点需要使用者慢慢去摸索。