Redis中的数据结构

Redis

Word count: 2.6kReading time: 9 min

 2019/01/14 

Redis 命令参考
 try Redis(不用安装Redis即可体验Redis命令

Redis支持丰富的数据结构，常用的有string、list、hash、set、sortset。

“Redis is written in ANSI C” – Redis由C语言编写

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

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

简单来说：Redis使用对象来表示数据库中的键和值。每次我们在Redis数据库中新创建一个键值对时，至少会创建出两个对象。一个是键对象，一个是值对象。

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

typedef struct redisObject{

    // 对象的类型
    unsigned type;

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

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

    //.....
}robj;

不同类型和编码的对象

简单来说就是Redis对key-value封装成对象，key是一个对象，value也是一个对象。每个对象都有type(类型)、encoding(编码)、ptr(指向底层数据结构的指针)来表示。

值为1006的字符串对象

SDS简单动态字符串

Redis中的Simple dynamic string使用sdshdr结构来表示一个SDS值：

struct sdshdr{

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

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

    // 记录buf数组未使用的字节数量
    int free;
}

SDS例子

使用SDS的好处

sdshdr数据结构中用len属性记录了字符串的长度。那么获取字符串的长度时，时间复杂度只需要O(1)。
SDS不会发生溢出的问题，如果修改SDS时，空间不足。先会扩展空间，再进行修改！(内部实现了动态扩展机制)。
SDS可以减少内存分配的次数(空间预分配机制)。在扩展空间时，除了分配修改时所必要的空间，还会分配额外的空闲空间(free 属性)。
SDS是二进制安全的，所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据。

链表

对于链表而言，我们不会陌生的了。在Java中Linkedxxx容器底层数据结构也是有链表存在的。

Redis使用listNode结构来表示每个节点：

typedef strcut listNode{

    //前置节点
    strcut listNode  *pre;

    //后置节点
    strcut listNode  *pre;

    //节点的值
    void  *value;

}listNode

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

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

链表结构

Redis链表的特性

Redis的链表有以下特性：

无环双向链表
获取表头指针，表尾指针，链表节点长度的时间复杂度均为O(1)
链表使用void *指针来保存节点值，可以保存各种不同类型的值

哈希表

又有书中称作“字典”

在Redis中，key-value的数据结构底层就是哈希表来实现的。对于哈希表来说，我们也并不陌生。在Java中，哈希表实际上就是数组+链表的形式来构建的。下面我们来看看Redis的哈希表是怎么构建的吧。

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

typedef struct dictht{

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

    //哈希表大小
    unsigned long size;

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

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

}dictht

哈希表的数据结构

我们下面继续写看看哈希表的节点是怎么实现的吧：

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结构来表示：

typedef struct dict {

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

    //私有数据
    void *privdata;

    //哈希表
    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所实现的哈希表最后的数据结构是这样子的：

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

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

Redis中哈希算法和哈希冲突跟Java实现的差不多，它俩差异就是：

Redis哈希冲突时：是将新节点添加在链表的表头。
JDK1.8后，Java在哈希冲突时：是将新的节点添加到链表的表尾。

rehash的过程

下面来具体讲讲Redis是怎么rehash的，因为我们从上面可以明显地看到，Redis是专门使用一个哈希表来做rehash的。这跟Java一次性直接rehash是有区别的。

在对哈希表进行扩展或者收缩操作时，rehash过程并不是一次性地完成的，而是渐进式地完成的。

Redis在rehash时采取渐进式的原因：数据量如果过大的话，一次性rehash会有庞大的计算量，这很可能导致服务器一段时间内停止服务。

Redis具体是rehash时这么干的：

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

跳跃表(shiplist)

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

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

按照惯例，我们来看看zskiplistNode跳跃表节点的结构是怎么样的：

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

zskiplistNode的对象示例图(带有不同层高的节点)：

一个完整的跳跃表如下：
跳跃表节点的示例图

zskiplist的结构如下：

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

整数集合(intset)

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

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

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