关于redis:深入理解redisredis经典五种数据类型及底层实现

1.Redis的根底类型dictEntry和redisObject

2.程序员应用redis时的底层思维

3.String底层数据结构

4.Hash数据结构介绍

5.List数据结构介绍

6.Set数据结构介绍

7.ZSet数据结构介绍

8.总结

1.Redis的根底类型dictEntry和redisObject

咱们能够先去redis的github上下载源码：https://github.com/redis/redis

就像咱们的JAVA对象，顶层全是Object一样，咱们的redis的顶层都是dictEntry，让咱们来看这样一段源码（dict.h中）：

typedef struct dictEntry {    void *key;  //示意字符串 就是redis KV构造中的KEY    union {        void *val;   //val指向的是redisObject中        uint64_t u64;        int64_t s64;        double d;    } v;    struct dictEntry *next;     /* Next entry in the same hash bucket. */    void *metadata[];           /* An arbitrary number of bytes (starting at a                                 * pointer-aligned address) of size as returned                                 * by dictType's dictEntryMetadataBytes(). */} dictEntry;

咱们以最简略的set k1 v1 为例，因为Redis是以KV为构造的数据库，每个键值对都会有一个dictEntry, 这外面指向了key和value的指针，next指向下一个dictEntry。
key是字符串，然而Redis没有间接应用C的char数组，而是存在了redis的自定义字符串中（等等上面会解释），value因为会有不同的类型，redis将这几种根本的类型形象成了redisObject中，实际上五种罕用的数据类型，都是通过redisObject来存储的。
咱们看看redisObject的源码（server.h）：

typedef struct redisObject {    unsigned type:4;       //以后对象的类型    unsigned encoding:4;   //以后对象的底层编码类型    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or  LRU或者LFU的拜访工夫数据                            * LFU data (least significant 8 bits frequency                            * and most significant 16 bits access time). */    int refcount;           //对象援用计数的次数    void *ptr;              //真正指向底层数据结构的指针} robj;

接下来咱们便能够取得这张图片，咱们对redis的存储构造就高深莫测了：

为了便于操作，Redis采纳redisObject构造来形象了不同的数据类型，这样所有的数据类型就能够用雷同的模式在函数之间传递，而不是应用特定的类型构造。同时，为了辨认不同的数据类型，
redisObject中定义了type和encoding字段对不同的数据类型加以辨别。简略地说，redisObject就是String,hash,list,set,zset的父类，能够在函数间传递的时候暗藏具体的根本类型信息，所以作者形象了redisObject。

2.程序员应用redis时的底层思维
咱们刚开始学习redis的时候，只会调用调用顶层的api，所以咱们看到的redis是这个样子的：

然而咱们学习了redis的的底层数据结构后，咱们将会看到这样子的redis：

3.String底层数据结构
Redis的String类型，其实底层是由三种数据结构组成的：
1）int： 整数且小于二十位整数以下的数字数据才会应用这个类型

2）embstr （embedded string，示意嵌入式的String）：代表embstr格局的SDS（Simple Dynamic String 简略动静字符串），保留长度小于44字节的字符串。
3）raw ：保留长度大于44的字符串

咱们先对下面这个案例做一个测试：

咱们发现保留的数据内容，会随着保留内容的变动而发生变化。

这就是redis中，String类型没有间接复用C语言的字符串，而是新建了属于本人的构造————SDS（简略动静字符串）。在Redis数据库里，蕴含字符串的键值对都是由SDS实现的，Redis中所有的值对象蕴含的字符串对象底层也是由SDS实现！

咱们点开sds.h，发现sds由多种类型形成：

struct __attribute__ ((__packed__)) sdshdr5 { //被废除    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */    char buf[];};struct __attribute__ ((__packed__)) sdshdr8 {    uint8_t len; /* used */                                       //已用长度    uint8_t alloc; /* excluding the header and null terminator */ //字符串最大字节长度    unsigned char flags; /* 3 lsb of type, 5 unused bits */       //用来展现的sds类型    char buf[];                                                   //真正无效的字符串数据，长度由alloc管制};struct __attribute__ ((__packed__)) sdshdr16 {    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 {    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 {    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[];};

它用
sdshdr5、(2^5=32byte)
sdshdr8、(2 ^ 8=256byte)
sdshdr16、(2 ^ 16=65536byte=64KB)
sdshdr32、 (2 ^ 32byte=4GB)
sdshdr64，2的64次方byte＝17179869184G

来存储不同长度的字符串，len示意长度，这样获取字符串长度就能够在O(1)的状况下，拿到字符串，而不是像C语言一样去遍历。
alloc能够计算字符串未被调配的空间，有了这个值就能够引入预调配空间的算法了，而不必去思考内存调配的问题。
buf 示意字符串数组，真存数据的。

为什么Redis要从新设计一个字符串SDS，而不间接应用char[]数组呢？

咱们能够从redis和sds的比照中能够发现：

	C语言	SDS
字符串长度解决	要从数组的头部开始遍历，直到遇到'\0'，工夫复杂度O（n）	间接读取长度，工夫复杂度O（1）
内存重新分配	内存超出调配的空间后，会导致下标越界或者溢出	预调配： SDS调配后，如果长度小于1M，那么会额定调配一个与len雷同长度的未应用的空间。惰性开释：SDS短时并不会发出多余的空间，而是将多余的空间记录下来，如果有变更操作，间接应用多余的空间，缩小调配频率。
二进制平安	数据内容可能蕴含'\0'，C语言遇上'\0'会提前结束，不会读取前面的内容	有了len作为长度，就不会有遍历这种问题了

论断：
只有整数才会应用int，如果是浮点数，就是用字符串保留。
embstr 与 raw 类型底层的数据结构其实都是 SDS (简略动静字符串，Redis 外部定义 sdshdr5， sdshdr8等等)。

存储构造：
1）int
当数据类型为整数的时候，RedisObject中的prt指针间接赋值为整数数据，不会额定指向整数了，节俭内存开销。redis在一万以内只会存一份，就像JAVA的Integer -128~127只存一份。

2) embstr
当保留的字符串数据小于等于44字节的时候，embstr类型将会调用内存调配函数，只调配一块间断的空间，空间中一次蕴含redisObject和sdshdr两个构造，让元数据，指针和sds是一块间断的区域，防止内存碎片。

3) raw
字符串大于44字节时，SDS的数据质变多变大了，SDS和RedisObject布局会离开，会给SDS调配多的空间并用指针指向SDS构造，raw 类型将会调用两次内存调配函数，调配两块内存空间，一块用于蕴含 redisObject构造，而另一块用于蕴含 sdshdr 构造。

调配流程图：

4.Hash数据结构介绍
在查看Hash的数据结构之前，咱们先来看这样的一个配置：

咱们可能看不太懂，我来给解释一下：

hash-max-ziplist-entries：应用压缩列表保留哈希汇合中的最大元素个数。

hash-max-ziplist-value：应用压缩列表保留时哈希汇合中单个元素的最大长度。

可能咱们这么说还是不太懂，上案例：

Hash数据类型也和String有相似之处，达到了肯定的阈值之后就会对数据结构进行降级。

数据结构：
1）hashtable 就是和java当中应用的hashtable一样，是一个数组+链表的构造。

2）ziplist 压缩链表

咱们先来看一下压缩链表的源码：

ziplist是一种比拟紧凑的编码格局，设计思路是用工夫换取空间，因而ziplist实用于字段个数少，且字段值也较小的场景。压缩列表内存利用率高的起因与其连续性内存个性是分不开的。

当一个hash对象，只蕴含大量的键，且每个键值对的值都是小数据，那么ziplist就适宜做为底层实现。

ziplist的构造：

它是一个通过非凡编码的双向链表，它尽管是双向链表，但它不存储指向上一个链表节点和指向下一个链表节点的指针，而是存储上一个节点的长度和以后节点的长度，通过就义局部读写性能，来换取高空间利用率。

zlbytes 4字节，记录整个压缩列表占用的内存字节数。
zltail 4字节，记录压缩列表表尾节点的地位。
zllen 2字节，记录压缩列表节点个数。
zlentry 列表节点，长度不定，由内容决定。
zlend 1字节，0xFF 标记压缩的完结。

节点的构造源码：

typedef struct zlentry {    unsigned int prevrawlensize; //上一个节点的长度     unsigned int prevrawlen;     //存储上一个链表节点长度所须要的的字节数                      unsigned int lensize;        //以后节点所须要的的字节数                                                                                                                                  unsigned int len;            //以后节点占用的长度                                                                                                                                                                unsigned int headersize;     //以后节点的头大小       unsigned char encoding;      //编码方式                                                                      unsigned char *p;            //指向以后节点起始地位

因为保留了这个构造，能够让ziplist从后往前遍历。

为什么有链表了，redis还要整出一个压缩链表？
1）一般的双向链表会有两个前后指针，在存储数据很小的状况下，咱们存储的理论数据大小可能还没有指针占用的内存大。而ziplist是一个非凡的双向链表，并没有保护前后指针这两个字段，而是存储上一个entry的长度和以后entry的长度，通过长度推算下一个元素在什么中央。就义读取的性能，获取高效的空间利用率，因为（简短KV键值对）存储指针比存储entry长度更费内存，这是典型的工夫换空间。

2）链表是不间断的，遍历比较慢，而ziplist却能够解决这个问题，ziplist将一些必要的偏移量信息都记录在了每一个节点里，使之能跳到上一个节点或者尾节点节点。

3）头节点里有头结点同时还有一个参数len，和SDS类型相似，这就是用来记录链表长度的。因而获取链表长度时不再遍历整个链表，间接拿到len值就能够了，获取长度的工夫复杂度是O（1）。

遍历过程：
通过指向表尾节点的地位指针zltail,减去节点的previous_entry_length，失去前一个节点的起始地址的指针。如此循环，从表尾节点遍历到表头节点。

5.List数据结构介绍

咱们先来看一下list的默认配置：

ziplist压缩配置：list-compress-depth 0
示意一个quicklist两端不被压缩的节点个数，这里的quicklist（下文会解释）是指quickList双向链表的节点，而不是指ziplist外面的数据项个数。

参数取值含意：
0：是个非凡值，示意都不压缩，这是redis的默认值。
1: 示意quicklist两端各有1个节点不压缩，两头的节点压缩。
2: 示意quicklist两端各有2个节点不压缩，两头的节点压缩。
3: 示意quicklist两端各有3个节点不压缩，两头的节点压缩。
依此类推…

(2) ziplist中entry配置：list-max-ziplist-size -2

当取正值的时候，示意依照数据项个数来限定每个quicklist节点上的ziplist长度。比方当这个配置为5的时候，ziplist里最多有5个数据项。

当取负值的时候，示意依照占用字节数来限定quicklist节点上的ziplist长度。这时，它只能取-1~-5这几个值。

-5: 每个quicklist节点上的ziplist大小不能超过64 Kb。（注：1kb => 1024 bytes）
-4: 每个quicklist节点上的ziplist大小不能超过32 Kb。
-3: 每个quicklist节点上的ziplist大小不能超过16 Kb。
-2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（-2是Redis给出的默认值）
-1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

quicklist构造介绍：
list用quicklist来存储，quicklist存储了一个双向链表，每一个节点都是一个ziplist。

](/img/bVcX7sS)

源码：

typedef struct quicklist {    quicklistNode *head;        //指向双向列表的表头    quicklistNode *tail;        //指向双向链表的表尾    unsigned long count;        //所有ziplist中共存储了多少个元素 /* total count of all entries in all listpacks */    unsigned long len;          //双向链表的长度，node的数量 /* number of quicklistNodes */    signed int fill : QL_FILL_BITS;       /* fill factor for individual nodes */    unsigned int compress : QL_COMP_BITS;  //压缩深度 /* depth of end nodes not to compress;0=off */    unsigned int bookmark_count: QL_BM_BITS;    quicklistBookmark bookmarks[];} quicklist;

typedef struct quicklistNode {    struct quicklistNode *prev; //前指针    struct quicklistNode *next; //后指针    unsigned char *entry; 指向理论的ziplist    size_t sz;             /* entry size in bytes */    unsigned int count : 16;     /* count of items in listpack */    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */    unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */    unsigned int recompress : 1; /* was this node previous compressed? */    unsigned int attempted_compress : 1; /* node can't compress; too small */    unsigned int extra : 10; /* more bits to steal for future usage */} quicklistNode;

6.Set数据结构介绍

咱们来看一下set的配置：

set-max-intset-entries
set数据类型汇合中，如果没有超出了这个数量，且数据元素都是整数的话，类型为intset,否则为hashtable。

intset类型：

typedef struct intset {    uint32_t encoding;    uint32_t length;    int8_t contents[];} intset;

看到源码后，咱们能够得出，论断，intset的数据结构实质是一个数组。而且**存储数据的时候是有序的，因为在查找数据的时候是通过二分查找来实现的。
**

咱们略微剖析一下set的单个元素的增加流程。
如果set曾经是hashtable的编码，那么走hashtable的增加流程。
如果原来是intset：
1）能转化为int对象，就用intset保留。
2）如果长度超过设置，就用hashtable保留
3）其它状况对立用hashtable保留。

7.ZSet数据结构介绍

咱们看一下ZSet的配置：

当有序汇合中蕴含的元素数量超过服务器属性 zset_max_ziplist_entries 的值（默认值为 128 ），
或者有序汇合中新增加元素的 member 的长度大于服务器属性zset_max_ziplist_value 的值（默认值为 64 ）时，redis会应用跳跃表（下文会解释）作为有序汇合的底层实现。

否则会应用ziplist作为有序汇合的底层实现

看一下源码：

当元素个数大于设置的个数或者元素的列表原本就是skiplist编码的时候，用skiplist存储，否则就用ziplist存储。

skiplist（跳表）是什么：
跳表是一种以空间换取工夫的构造。

因为链表是无奈进行二分查找的，因而借鉴了数据库索引的思维，提取出链表中要害节点（索引），当初要害节点上进行查找，再进入链表进行查找。

提取了很多要害节点，就造成了跳表。

因为跳表是以一种跳跃式的数据存在，当咱们查问‘14’这个数据的时候，能够跳过很多无用的数据，缩小遍历的次数。

跳表是一个典型的空间换工夫的解决方案，而且只有在数据量较大的状况下能力体现进去劣势。还是要读多写少的状况才适宜应用，所以它的适用范围还是比拟无限的，新增或者删除的时候要把所有数据都更新一遍。

8.总结