Redis

Redis笔记之数据类型

Posted by Jesse' Notes on June 20, 2017

Redis的数据结构

Redis 命令参考：http://doc.redisfans.com/ try Redis(不用安装Redis即可体验Redis命令)：http://try.redis.io/

1 首先

1

"Redis is written in ANSI C"-->Redis由C语言编写

首先还是得声明一下，Redis的存储是以key-value的形式的。Redis中的key一定是字符串，value可以是string、list、hash、set、sortset这几种常用的。

Redis并没有直接使用这些数据结构来实现key-value数据库，而是基于这些数据结构创建了一个对象系统。

每次我们在Redis数据库中新创建一个键值对时，至少会创建出两个对象。一个是键对象，一个是值对象。

Redis中的每个对象都由一个redisObject结构来表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef struct redisObject{

    // 对象的类型
    unsigned type 4:;

    // 对象的编码格式
    unsigned encoding:4;

    // 指向底层实现数据结构的指针
    void * ptr;

    //.....


}robj;

redisEncode.png

redisObject  
type REDIS_STRING 表示其类型为String
encoding REDIS_ENCODING_INT 使用整数值实现的字符串对象
ptr 指针——> 指向底层的数据结构

下面我就来说一下我们Redis常见的数据类型：string、list、hash、set、sortset。它们的底层数据结构究竟是怎么样的！

2.1 SDS简单动态字符串

简单动态字符串(Simple dynamic string,SDS) Redis使用sdshdr结构来表示一个SDS值： ```c struct sdshdr{

1
2
3
4
5
6
7
8

// 字节数组，用于保存字符串
char buf[];

// 记录buf数组中已使用的字节数量，也是字符串的长度
int len;

// 记录buf数组未使用的字节数量
int free; } ``` [![sds.png](http://wx4.sinaimg.cn/mw690/66c46543gy1fylo0lu860j20e305p74m.jpg)](http://wx4.sinaimg.cn/mw690/66c46543gy1fylo0lu860j20e305p74m.jpg)
2.1.1为什么使用SDS

sdshdr数据结构中用len属性记录了字符串的长度。那么获取字符串的长度时，时间复杂度只需要O(1)。

SDS不会发生溢出的问题，如果修改SDS时，空间不足。先会扩展空间，再进行修改！(内部实现了动态扩展机制)。

SDS可以减少内存分配的次数(空间预分配机制)。在扩展空间时，除了分配修改时所必要的空间，还会分配额外的空闲空间(free 属性)。

SDS是二进制安全的，所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据。

2.2链表

listNode结构来表示每个节点：

1
2
3
4
5
6
7
8
9
10
11
12

typedef strcut listNode{

    //前置节点
    strcut listNode  *pre;

    //后置节点
    strcut listNode  *pre;

    //节点的值
    void  *value;

}listNode

使用listNode是可以组成链表了，Redis中使用list结构来持有链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

typedef struct list{

    //表头结点
    listNode  *head;

    //表尾节点
    listNode  *tail;

    //链表长度
    unsigned long len;

    //节点值复制函数
    void *(*dup) (viod *ptr);

    //节点值释放函数
    void  (*free) (viod *ptr);

    //节点值对比函数
    int (*match) (void *ptr,void *key);

}list

redisEncode.png

2.2.1Redis链表的特性

Redis的链表有以下特性：

无环双向链表

获取表头指针，表尾指针，链表节点长度的时间复杂度均为O(1)

链表使用void *指针来保存节点值，可以保存各种不同类型的值

2.3哈希表

在Redis里边，哈希表使用dictht结构来定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

typedef struct dictht{

        //哈希表数组
        dictEntry **table;  

        //哈希表大小
        unsigned long size;    

        //哈希表大小掩码，用于计算索引值
        //总是等于size-1
        unsigned long sizemark;     

        //哈希表已有节点数量
        unsigned long used;

    }dictht

redisEncode.png

哈希表的节点的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

typedef struct dictEntry {

        //键
        void *key;

        //值
        union {
            void *value;
            uint64_tu64;
            int64_ts64;
        }v;    

        //指向下个哈希节点，组成链表
        struct dictEntry *next;

    }dictEntry;

从结构上看：Redis实现的哈希表和Java中实现的是类似的。只不过Redis多了几个属性来记录常用的值：sizemark(掩码)、used(已有的节点数量)、size(大小)。 但是Redis为了更好的操作，对哈希表往上再封装了一层(参考上面的Redis实现链表)，使用dict结构来表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

typedef struct dict {

    //类型特定函数
    dictType *type;

    //私有数据
    void *privdata;

    //哈希表、有两个hash
    dictht ht[2];

    //rehash索引
    //当rehash不进行时，值为-1
    int rehashidx;  

}dict;


//-----------------------------------

typedef struct dictType{

    //计算哈希值的函数
    unsigned int (*hashFunction)(const void * key);

    //复制键的函数
    void *(*keyDup)(void *private, const void *key);

    //复制值得函数
    void *(*valDup)(void *private, const void *obj);  

    //对比键的函数
    int (*keyCompare)(void *privdata , const void *key1, const void *key2)

    //销毁键的函数
    void (*keyDestructor)(void *private, void *key);

    //销毁值的函数
    void (*valDestructor)(void *private, void *obj);  

}dictType

所以Redis所实现的哈希表最后的数据结构是这样子的： redisEncode.png

从代码实现和示例图上我们可以发现，Redis中有两个哈希表：

ht[0]：用于存放真实的key-vlaue数据 ht[1]：用于扩容(rehash)

Redis哈希冲突时：是将新节点添加在链表的表头。

2.3.1 rehash的过程

上面图中可以明显地看到，Redis是专门使用一个哈希表来做rehash的。这跟Java一次性直接rehash是有区别的。

在对哈希表进行扩展或者收缩操作时，reash过程并不是一次性地完成的，而是渐进式地完成的。 因为数据量如果过大的话，一次性rehash会有庞大的计算量，这很可能导致服务器一段时间内停止服务。

Redis具体是rehash时这么干的：

  1. 在字典中维持一个索引计数器变量rehashidx，并将设置为0，表示rehash开始。
  2. 在rehash期间每次对字典进行增加、查询、删除和更新操作时，除了执行指定命令外；还会将ht[0]中rehashidx索引上的值rehash到ht[1]，操作完成后rehashidx+1。 3.字典操作不断执行，最终在某个时间点，所有的键值对完成rehash，这时将rehashidx设置为-1，表示rehash完成 4.在渐进式rehash过程中，字典会同时使用两个哈希表ht[0]和ht[1]，所有的更新、删除、查找操作也会在两个哈希表进行。例如要查找一个键的话，服务器会优先查找ht[0]，如果不存在，再查找ht[1]，诸如此类。此外当执行新增操作时，新的键值对一律保存到ht[1]，不再对ht[0]进行任何操作，以保证ht[0]的键值对数量只减不增，直至变为空表。

redisEncode.png

2.4跳跃表(shiplist)

跳跃表(shiplist)是实现sortset(有序集合)的底层数据结构之一！

Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成。其中zskiplist保存跳跃表的信息(表头，表尾节点，长度)，zskiplistNode则表示跳跃表的节点。

zskiplistNode跳跃表节点的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

zskiplist的结构如下：

1
2
3
4
5
6
7
8
9

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

redisEncode.png

2.5整数集合(intset)

整数集合是set(集合)的底层数据结构之一。当一个set(集合)只包含整数值元素，并且元素的数量不多时，Redis就会采用整数集合(intset)作为set(集合)的底层实现。

整数集合(intset)保证了元素是不会出现重复的，并且是有序的(从小到大排序)，intset的结构是这样子的：

1
2
3
4
5
6
7
8

typeof struct intset {
        // 编码方式
        unit32_t encoding;
        // 集合包含的元素数量
        unit32_t lenght;
        // 保存元素的数组
        int8_t contents[];
} intset;

虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值：

INTSET_ENC_INT16

INTSET_ENC_INT32

INTSET_ENC_INT64

从编码格式的名字我们就可以知道，16,32,64编码对应能存放的数字范围是不一样的。16明显最少，64明显最大。

如果本来是INTSET_ENC_INT16的编码，想要存放大于INTSET_ENC_INT16编码能存放的整数值，此时就得编码升级(从16升级成32或者64)。步骤如下：

1）根据新元素类型拓展整数集合底层数组的空间并为新元素分配空间。 2）将底层数组现有的所以元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位上，需要维持底层数组的有序性质不变。 3）将新元素添加到底层数组。 只支持升级操作，并不支持降级操作。

2.6压缩列表(ziplist)

压缩列表(ziplist)是list和hash的底层实现之一。如果list的每个都是小整数值，或者是比较短的字符串，压缩列表(ziplist)作为list的底层实现。

压缩列表(ziplist)是Redis为了节约内存而开发的，是由一系列的特殊编码的连续内存块组成的顺序性数据结构。

压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。

压缩列表从表尾节点倒序遍历，首先指针通过zltail偏移量指向表尾节点，然后通过指向节点记录的前一个节点的长度依次向前遍历访问整个压缩列表。

添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高

zip.png 压缩表结构

zip.png 压缩表节点

三、Redis中数据结构的对象

3.1字符串对象

开头的图我们知道string类型有三种编码格式：

int：整数值，这个整数值可以使用long类型来表示

  • 如果是浮点数，那就用embstr或者raw编码。具体用哪个就看这个数的长度了
  • embstr：字符串值，这个字符串值的长度小于39字节
  • raw：字符串值，这个字符串值的长度大于39字节

embstr和raw的区别：

  • raw分配内存和释放内存的次数是两次，embstr是一次
  • embstr编码的数据保存在一块连续的内存里面

编码之间的转换：

  • int类型如果存的不再是一个整数值，则会从int转成raw
  • embstr是只读的，在修改的时候回从embstr转成raw

3.2 列表(list)对象

list类型有两种编码格式：

ziplist：字符串元素的长度都小于64个字节&&总数量少于512个 linkedlist：字符串元素的长度大于64个字节||总数量大于512个

ziplist编码的列表结构：

1
2

redis > RPUSH numbers 1 "three" 5
    (integer) 3

zip.png linkedlist编码的列表结构：

zip.png 编码之间的转换：

原本是ziplist编码的，如果保存的数据长度太大或者元素数量过多，会转换成linkedlist编码的。

3.3哈希(hash)对象

ziplist：key和value的字符串长度都小于64字节&&键值对总数量小于512 hashtable：key和value的字符串长度大于64字节||键值对总数量大于512

zip.png

zip.png

hashtable编码的哈希结构：

zip.png

原本是ziplist编码的，如果保存的数据长度太大或者元素数量过多，会转换成hashtable编码的。

3.4集合(set)对象

intset：保存的元素全都是整数&&总数量小于512 hashtable：保存的元素不是整数||总数量大于512

intset编码的集合结构: zip.png hashtable编码的集合结构： zip.png

原本是intset编码的，如果保存的数据不是整数值或者元素数量大于512，会转换成hashtable编码的。

3.5有序集合(sortset)对象

ziplist：元素长度小于64&&总数量小于128 skiplist：元素长度大于64||总数量大于128

ziplist编码的有序集合结构：

zip.png

zip.png

skiplist编码的有序集合结构：

zip.png

zip.png

有序集合同事被保存在字典和跳跃表中

有序集合(sortset)对象同时采用skiplist和哈希表来实现：

skiplist能够达到插入的时间复杂度为O(logn)，根据成员查分值的时间复杂度为O(1)

编码之间的转换：

原本是ziplist编码的，如果保存的数据长度大于64或者元素数量大于128，会转换成skiplist编码的。

3.6Redis对象一些细节

  1. 服务器在执行某些命令的时候，会先检查给定的键的类型能否执行指定的命令。 比如我们的数据结构是sortset，但你使用了list的命令。这是不对的，服务器会检查一下我们的数据结构是什么才会进一步执行命令
  2. Redis的对象系统带有引用计数实现的内存回收机制。对象不再被使用的时候，对象所占用的内存会释放掉
  3. Redis会共享值为0到9999的字符串对象
  4. 对象会记录自己的最后一次被访问时间，这个时间可以用于计算对象的空转时间。

五种数据结构

String

Redis-String.png

List

Redis-List.png

Hash

Redis-Hash.png

Set

Redis-Set.png

Zset

Redis-Zset.png

FEATURED TAGS
Design Pattern Redis MQ spring Java并发 InnoDB bigdata java redis
FRIENDS