redis数据结构分析

    本文是3年前做的redis源码研究的一些零散文章，到现在要复习以前的一些东西，整理成文。有些图参考了那时淘宝的技术博客的分析，一些是自己分析源码，并实践而画出来的图。

Redis 的保存的数据都是基于几种内存结构保存的，以下分析这几种主要的内存结构：

1.1 redis 基础数据内存结构

* redisDb 结构

    redis的数据库中的所有数据都是保存在该结构组织的数据中。

typedef struct redisDb {

    dict *dict;                 /* The keyspace for this DB */ // 保存key-value的主要数据结构

    dict *expires;              /* Timeout of keys with a timeout set */ //保存过期时间的结构

    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */

    dict *ready_keys;           /* Blocked keys that received a PUSH */

    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */

    int id;

    long long avg_ttl;          /* Average TTL, just for stats */

} redisDb;

* dict 结构

    该结构是数据库中数据保存的主要结构。包括两个dictht哈希表。

typedef struct dict {

    dictType *type;

    void *privdata;

    dictht ht[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    int iterators; /* number of iterators currently running */

} dict;

* dictht结构

/* 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 **table;     // hash表节点数组

    unsigned long size;

    unsigned long sizemask;

    unsigned long used;

} dictht;

* dictEntry 结构

该结构是hash表的节点，也是数据(key/value)保存的地方。

typedef struct dictEntry {

    void *key;

    union {

        void *val;    // 指向真正的数据的位置，其值可能是某个类型实体的指针。

        uint64_t u64;  //value是64位整数

        int64_t s64;    //value是整数

        double d;        //value是double型数据

    } v;

    struct dictEntry *next;  //指向下一个hash表的节点

} dictEntry;

* sdshdr结构

代码定义如下：

typedef char *sds;

struct sdshdr {

    unsigned int len;

    unsigned int free;

    char buf[];

};

* redisObject结构

    redis 会把每一个 key 和 value 都创建成一个 redis 的 object 对象结构，然后把该结构添加到 redisdb 结构中。例如保存一个字符串的结构：

* redis 的 Object 类型

/* Object types */

#define REDIS_STRING 0

#define REDIS_LIST 1

#define REDIS_SET 2

#define REDIS_ZSET 3

#define REDIS_HASH 4

* redis 编码方式

#define REDIS_ENCODING_RAW 0 /* Raw representation */

#define REDIS_ENCODING_INT 1 /* Encoded as integer */

#define REDIS_ENCODING_HT 2 /* Encoded as hash table */

#define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */

#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */

#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */

#define REDIS_ENCODING_INTSET 6 /* Encoded as intset */

#define REDIS_ENCODING_SKIPLIST 7 /* Encoded as skiplist */

说明：

（1）若 type 是 REDIS_STRING 类型的,则其值如果是数字,就可以编码成REDIS_ENCODING_INT,以节约内存。

（2）若 type 是 REDIS_HASH 类型的,如果其 entry 小于配置值:hash-max-zipmap-entries 或 value 字符串的长度小于

hash-max-zipmap-value, 则可以编码成 REDIS_ENCODING_ZIPMAP 类型存储,以节约内存. 否则采用 Dict 来存储。

（3）若 type 是 REDIS_LIST 类型的,如果其 entry 小于配置值:list-max-ziplist-entries 或 value 字符串的长度小于

list-max-ziplist-value, 则可以编码成 REDIS_ENCODING_ZIPLIST 类型存储,以节约内存; 否则采用 REDIS_ENCODING_LINKEDLIST 来存储.

（4）若 type 是 REDIS_SET 类型的,如果其值可以表示成数字类型且 entry小于配置值 set-max-intset-entries, 则可以编码成 REDIS_ENCODING_INTSET类型存储,以节约内存; 否则采用 Dict 类型来存储.

（5）lru: 是时间戳

（6）refcount: 引用次数

（7） void * ptr : 指向实际存储的 value 值内存块,其类型可以是 string,set, zset,list,hash ,编码方式可以是上述 encoding 表示的一种.

（8）至于一个 key 的 value 采用哪种类型来保存,完全是由客户端的指令来决定的,如 hset ,则值是采用 REDIS_HASH 类型表示的,至于那种编码(encoding),则由 redis 根据配置自动决定。

* redis 数据结构总览

注意：这是2年前淘宝技术博客上的一个图，画的非常不错。

说明：

    dict 是主要是由 struct dictht 的 哈唏表构成的, 之所以定义成长度为2 的( dictht ht[2] ) 哈唏表数组,是因为 redis 采用渐进的 rehash,即当需要 rehash 时,每次像 hset,hget 等操作前,先执行 N 步 rehash. 这样就把原来一次性的 rehash 过程拆散到进行, 防止一次性 rehash 期间 redis 服务能力大幅下降. 这种渐进的 rehash 需要一个额外的 struct dictht 结构来保存。

    struct dictht 主要是由一个 struct dictEntry 指针数组组成的, hash 表的冲突是通过链表法来解决的。

    struct dictEntry 中的 key 指针指向用 sds 类型表示的 key 字符串,由图中可以看出，数据最终是保存在以 dictEntry 为节点的链表中的。但由于key 和 val 的值都是 void *型，所以由此又衍生出多种内存结构。

* 命令和数据类型对应关系表


1.2 各种类型数据结构

* zipmap 结构

    如果 redisObject 的 type 成员值是 REDIS_HASH 类型的,则当该 hash 的entry 小于配置值: hash-max-zipmap-entries 或者 value 字符串的长度小于hash-max-zipmap-value, 则可以编码成 REDIS_ENCODING_ZIPMAP 类型存储,以节约内存. 否则采用 Dict 来存储.

    zipmap 其实质是：用一个字符串数组来依次保存 key 和 value，查询时是依次遍列每个 key-value 对,直到查到为止. 其结构示意图如下:

    初始化后的结构

以下是创建一个zipmap结构的函数。

/* Create a new empty zipmap. */

unsigned char *zipmapNew(void) {

    unsigned char *zm = zmalloc(2);    //创建了包含两个char的数组。

    zm[0] = 0; /* Length */

    zm[1] = ZIPMAP_END;

    return zm;

}

    初始化时只有 2 个字节,第 1 个字节表示 zipmap 保存的 key-value 对的个数(如果 key-value 对的个数超过 254,则一直用 254 来表示, zipmap 中实际保存的 key-value 对个数可以通过 zipmapLen() 函数计算得到).

执行 hset myhash name foo 后

(1)第 1 个字节保存 key-value 对(即 zipmap 的 entry 数量)的数量 1

(2)第 2 个字节保存 key_len 值 4

(3)第 3~6 保存 key “name”

(4)第 7 字节保存 value_len 值 3

(5)第 8 字节保存空闭的字节数 0 (当 该 key 的值被重置时,其新值的长度与旧值的长度不一定相等,如果新值长度比旧值的长度大,则 realloc 扩大内存;

    如果新值长度比旧值的长度小,且相差大于 4 bytes ,则 realloc 缩小内存,如果相差小于 4,则将值往前移,并用 empty_len 保存空闲的 byte 数)

(7)第 9~13 字节保存 value 值 “foo”

如果 key 或 value 的长度小于 ZIPMAP_BIGLEN(254),则用一个字节来表示,如果大于 ZIPMAP_BIGLEN(254),则用 5 个字节保存,第一个字节为保存ZIPMAP_BIGLEN(254),后面 4 个字节保存 key 或 value 的长度。

* ziplist 结构

    如果 redisObject 的 type 成员值是 REDIS_LIST 类型的,则当该 list 的elem 数小于配置值: hash-max-ziplist-entries 或者 elem_value 字符串的长度小于 hash-max-ziplist-value, 则可以编码成 REDIS_ENCODING_ZIPLIST 类型存储,以节约内存. 否则采用 Dict 来存储。

    ziplist 其实质是用一个字符串数组形式的双向链表。

    总体结构：

执行：unsigned char *zl = ziplistNew(); 后的内存情况

zl = {11, 0, 0, 0, 10, 0, 0, 0, 0, 0, 255}

1， ziplist header 由 3 个字段组成:

    a) ziplist_bytes: 用一个 uint32_t 来保存, 构成 ziplist 的字符串数组的总长度,包括 ziplist header,

    b) ziplist_tail_offset: 用一个 uint32_t 来保存,记录 ziplist 的尾部偏移位置.

    c) ziplist_length: 用一个 uint16_t 来保存,记录 ziplist 中 elem 的个数

2， ziplist node 也由 3 部分组成:

    a) prevrawlen: 保存上一个 ziplist node 的占用的字节数,包括: 保存prevarwlen,currawlen 的字节数和 elem value 的字节数.

    b) currawlen&encoding: 当

    c) (编码后的)value可以通过 prevrawlen 和 currawlen&encoding 来遍列 ziplist.

ziplist 还能到一些小技巧来节约内存.

    (1)len 的存储: 如果 len 小于 ZIP_BIGLEN(254),则用一个字节来保存;否则需要 5 个字节来保存,第 1 个字节存 ZIP_BIGLEN,作为标识符.

    (2)value 的存储: 如果 value 是数字类型的,则根据其值的范围转换成ZIP_INT_16B, ZIP_INT_32B 或 ZIP_INT_64B 来保存,否则用 raw 形式保存.

*  intset 结构

    intset 是用一个有序的整数数组来实现集合(set). struct intset 的定义，如下:

typedef struct intset

{

uint32_t encoding;

uint32_t length;

int8_t contents[];

} intset;

（1）encoding: 来标识数组是 int16_t 类型, int32_t 类型还是 int64_t 类型的数组. 至于怎么先择是那种类型的数组,是根据其保存的值的取值范围来决定的,初始化时是 int16_t, 根据 set 中的最大值在 [INT16_MIN, INT16_MAX] ,[INT32_MIN, INT32_MAX], [INT64_MIN, INT64_MAX]的那个取值范围来动态确定整个数组的类型. 例如 set 一开始是 int16_t 类型,当一个取值范围在[INT32_MIN, INT32_MAX]的值加入到 set 时,则将保存 set 的数组升级成int32_t 的数组.

（2）length: 表示 set 中值的个数

（3）contents: 指向整数数组的指针

创建一个空的intset的函数：

/* Create an empty intset. */

intset *intsetNew(void) {

    intset *is = zmalloc(sizeof(intset));

    is->encoding = intrev32ifbe(INTSET_ENC_INT16);

    is->length = 0;

    return is;

}

* zset 结构(跳转表)

a) 跳转表定义

    是一种数据结构，该结构按照已排序的方式来维护一堆 key 值。

b) 跳转表的特征

 1) 由 n 个层次组成

 2) 所有的 key 值都会出现在第一层

 3) 每层都是一个已排序的链表

 4) 若 key 出现在第 i 层，那么该 key 值也出现在低于 i 的各层

 5) 一个在第 i 层的元素，也同时指向第 i-1 层的同样的元素

 6) top 指针指向最高层的最小 key 值元素

c) 向跳转表中插入数据 x

 1）决定 x 要插入的层数 k 值

 2）在表中查询 x 的值，并且插入 x 值到低于 k 的所有层

 3）若计算出来的层数大于目前的最大层数，那么增加一个新的层，并更新 top 指针，例如，在第 4 层添加元素 119，下图所示：

d) 从跳转表中删除元素 x

（1）在 x 参与的所有层查找 x，并且在每一次删除元素 x

（2）若更高层已经为空了，那么删除该层，并更新 top 指针

结构实现：

/* ZSETs use a specialized version of Skiplists */

typedef struct zskiplistNode {

    robj *obj;

    double score;

    struct zskiplistNode *backward;

    struct zskiplistLevel {

        struct zskiplistNode *forward;

        unsigned int span;

    } level[];

} zskiplistNode;

typedef struct zskiplist {

    struct zskiplistNode *header, *tail;

    unsigned long length;

    int level;

} zskiplist;

typedef struct zset {

    dict *dict;

    zskiplist *zsl;

} zset;

    zset 的实现用到了 2 个数据结构: hash_table 和 skip list (跳跃表),其中 hash table 是使用 redis 的 dict 来实现的,主要是为了保证查询效率为O(1),而 skip list (跳跃表) 是用来保证元素有序并能够保证 INSERT 和REMOVE 操作是 O(logn)的复杂度。

* zset 初始化状态

zslCreate()函数用来创建并初如化一个 skiplist。 其中，skiplist 的 level 最大值为ZSKIPLIST_MAXLEVEL=32 层。

* ZADD myzset 1 “one”的实现

ZADD 命令格式：

ZADD key score member

（1） 根据 key 从 redisDb 进行查询，返回 zset 对象。

（2） 以 member 作为 key, score 作为 value，向 zset 的 dict 进行中插入;

（3） 如果返回成功，表明 member 没有在 dict 中出现过，直接向kiplist 进行插入。

（4） 如果步骤返回失败，表明以 member 已经在 dict 中出现过，则需要先从 skiplist 中删除，然后以现在的 score 值重新插入。

插入三个元素后的结构