根据国人黄俊宏先生建议的阅读顺序 redis源码的设计与解析
这部分记录下redis的数据结构与对象

有些人觉得理论无用，不实现的思想等于扯淡。但试想，每一次开源组件的推出，都是先形成一种理念，后来才慢慢完善实现思路。

所以本文不急于立即着手redis的源码，首先介绍一下redis所属的分布式领域内的角色和定位

分布式应用系统知识

• 分布式存储系统

  • 分布式文件存储系统其作用主要有两个：其一存储海量的文档、图片、视频等blob类数据，其二作为分布式表格系统的持久化层，如 HDFS于HBase。流行的分布式文件存储系统有很多，如google的GFS、及其开源的实现版本HDFS和Facebook的Haystack等等。既然是分布式，肯定有多个机器甚至机房参与了，机器之间通过网络互连沟通；而又只要存在着沟通，由于昂贵的沟通成本(CAP理论)导致其实现原理会变得复杂。也就是说,分布式存储系统是将数据分散成多个数据存储到服务器上，并尽可能解决机器之间的沟通问题

  • (In-meomery) 内存型数据库

    • 随着业务的并发越来越高，存储系统对低延迟的要求也越来越高。 同时由于摩尔定律以及内存的价格不断下降，基于内存的存储系统也开始普及。比较有名的系统包括 memcahed ，以及 Redis。 这些基于 K-V 键值系统的主要目的是为基于磁盘的存储系统做 cache。还有一些偏向于内存计算的系统，比如可以追溯到普林斯顿 Kai Lee 教授早期的研究工作 distributed shared memory ( DSM )，斯坦福的 RamCloud， 以及最近比较火的基于 lineage 技术的 tachyon (Alluxio) 项目（Spark生态系统子项目）等等。

Redis的优势及实际应用场景

• Redis支持服务器端的数据操作：Redis相比Memcached来说，拥有更多的数据结构和并支持更丰富的数据操作，通常在Memcached里，你需要将数据拿到客户端来进行类似的修改再set回去。这大大增加了网络IO的次数和数据体积。在Redis中，这些复杂的操作通常和一般的GET/SET一样高效。所以，如果需要缓存能够支持更复杂的结构和操作，那么Redis会是不错的选择。
• 内存使用效率对比：使用简单的key-value存储的话，Memcached的内存利用率更高，而如果Redis采用hash结构来做key-value存储，由于其组合式的压缩，其内存利用率会高于Memcached。
• 性能对比：由于Redis只使用单核，而Memcached可以使用多核，所以平均每一个核上Redis在存储小数据时比Memcached性能更高。而在100k以上的数据中，Memcached性能要高于Redis，虽然Redis最近也在存储大数据的性能上进行优化，但是比起Memcached，还是稍有逊色。

Redis源码设计理念

• Redis数据存储的细节
  • 关于Redis数据存储的细节，涉及到内存分配器（如jemalloc）、简单动态字符串（SDS）、5种对象类型及内部编码、redisObject。在讲述具体内容之前，先说明一下这几个概念之间的关系。

下图是执行set hello world时，所涉及到的数据模型

RedisDataType.jpg

• dictEntry：Redis是Key-Value数据库，因此对每个键值对都会有一个dictEntry，里面存储了指向Key和Value的指针；next指向下一个dictEntry，与本Key-Value无关。

• Key：图中右上角可见，Key（”hello”）并不是直接以字符串存储，而是存储在SDS结构中。

• redisObject：Value(“world”)既不是直接以字符串存储，也不是像Key一样直接存储在SDS中，而是存储在redisObject中。实际上，不论Value是5种类型的哪一种，都是通过redisObject来存储的；而redisObject中的type字段指明了Value对象的类型，ptr字段则指向对象所在的地址。不过可以看出，字符串对象虽然经过了redisObject的包装，但仍然需要通过SDS存储。

实际上，redisObject除了type和ptr字段以外，还有其他字段图中没有给出，如用于指定对象内部编码的字段；后面会详细介绍。

• jemalloc：无论是DictEntry对象，还是redisObject、SDS对象，都需要内存分配器（如jemalloc）分配内存进行存储。以DictEntry对象为例，有3个指针组成，在64位机器下占24个字节，jemalloc会为它分配32字节大小的内存单元。

• Redis 3.2.6

• 编译redis源码，用GDB调试
  • 从 src程序入口开始编译后，根据PREV_FINAL_CFLAGS配置选项依次加载redis的各个模块,并编译该模块
    
    1.png

动态字符串SDS(以redis3.2.6为例)

• SDS is a string library for C designed to augment the limited libc string handling functionalities by adding heap allocated strings

sds.h

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
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 */
    char buf[];
};
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[];
};

在redis3.2.6中
len 表示已经使用的长度,alloc表示字符串的最大容量（不包含最后多余的那个字节）。flags在redis一开始设计的时候,sds是有五种数据类型的，换算成字节数刚好占3位。buf数组这里指真正有效的字符串数据，其长度是最大容量+1。

sds的redis4.0版本

struct sdshdr {

    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;

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

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

};

在redis4.0中，buf表示字节数组，用来存储字符串；len表示buf已使用的长度，free表示buf未使用的长度。下面是两个例子。

我们发现一件事情.原先header中的alloc以及 flags都消失了
替换成了 free未使用的字节数.根据c语言中无符号数据类型的划分，之所以设计alloc和flags，只是需要保存对应的无符号数据类型,因为不同平台都有会有不同的字长，本质还是用来区别数据类型所占用的字节数。

• 不妨这样想，既然alloc和flags也是用来指定字节数的。那么为什么一开始不维护一个int变量，记录buf数组未使用的长度呢？。
  • 猜测: 无需关心该字符串究竟使用了哪种字长，sds只是为了更直观的操作字符串。
    当前buf数组的长度 = 已使用的字节数+未使用的字节数。那么我们在进行增长字符串的操作时，只需要修改free的值即可。如果修改后字符串的buf数组小于当前字符串的buf数组长度，则无需修改已经使用的len值。

为了证明猜测，让我们看下sds的具体操作 sds.c(redis3.2.6)

/* Create a new sds string with the content specified by the 'init' pointer
 * and 'initlen'.
 * If NULL is used for 'init' the string is initialized with zero bytes.
 * If SDS_NOINIT is used, the buffer is left uninitialized;
 *
 * The string is always null-termined (all the sds strings are, always) so
 * even if you create an sds string with:
 *
 * mystring = sdsnewlen("abc",3);
 *
 * You can print the string with printf() as there is an implicit \0 at the
 * end of the string. However the string is binary safe and can contain
 * \0 characters in the middle, as the length is stored in the sds header. */
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

在初始化字符串操作中，面对类型检查的情况,sh->len = initlen; sh->alloc = initlen;，真正作为确定无符号数据类型的变量只是一个指针，至于字符串真正长度则记录在len当中

在往下阅读sds.c的过程中，我们发现这样一段代码

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

这里的意思是扩大sds字符串末尾的空闲空间，以便在调用此函数之后，可以覆盖到字符串末尾的addlen字节。
Notes：这并不改变sdslen()返回的sds字符串的长度，而是只改变我们有的空闲缓冲空间

什么是空闲缓冲空间？不着急，再往下看具体的函数调用

/* Grow the sds to have the specified length. Bytes that were not part of
 * the original length of the sds will be set to zero.
 *
 * if the specified length is smaller than the current length, no operation
 * is performed. */
sds sdsgrowzero(sds s, size_t len) {
    size_t curlen = sdslen(s);

    if (len <= curlen) return s;
    s = sdsMakeRoomFor(s,len-curlen);
    if (s == NULL) return NULL;

    /* Make sure added region doesn't contain garbage */
    memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
    sdssetlen(s, len);
    return s;
}

这个函数的作用是在进行增长字符串之前，先维护之前sds申请的从原来字符串末尾到新增长后字符串末尾的空闲缓冲空间len-curlen，这里就是sds的一个作用，杜绝缓冲区溢出。然后再把这段字符串的每个字节全部置为0，为之后的增长字符串做准备

链表

• /* Node, List, and Iterator are the only data structures used currently. */
  adlist.h

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

这里的链表结构与普通的链表结构一致，每个链表节点保存前驱和后继。并交由一个list持有这些链表节点,以及一个节点迭代器结构记录当前遍历到的节点位置。但令人眼前一亮的，还是关于节点值的动态内存分配。

在下面的文件中，我们可以看到zmalloc用来指定每次需要释放和分配的节点值，像linux中也有tcmalloc，他的设计思路来源于linux的内核空间与用户空间。
adlist.c

list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

回顾一下 redis的内存划分

• user meomry
  • Redis分配器分配的内存总量
• used_memory_rss
  • 包括redis进程本身的虚拟内存和内存碎片

ps: 内存碎片的介绍以及虚拟内存

比对一下 linux的用户空间和内核空间中的内存划分

• 内核空间
  • 操作系统和驱动程序所占的内存
• 用户空间
  • 一般应用程序所占的内存

猜测：前者充当的角色相当于 内核空间,后者充当的角色相当于用户空间

为了证明这个猜测，我们看一下 zmalloc.h的分配函数

void *zmalloc(size_t size) {
    void *ptr = malloc(size+PREFIX_SIZE);

    if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_alloc(zmalloc_size(ptr));
    return ptr;
#else
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)ptr+PREFIX_SIZE;
#endif
}


#define update_zmalloc_stat_alloc(__n) do { \
    size_t _n = (__n); \
    if (_n&(sizeof(long)-1)) _n += sizeof(long)-(_n&(sizeof(long)-1)); \
    atomicIncr(used_memory,__n); \
} while(0)

• 阅读 atomicvar.h文件可知该文件作为一个传递系统宏定义指令的文件，我们可以看到在内核空间中经常被引用的信号量互斥锁
  atomicvar.h

  *To test Redis with Helgrind (a Valgrind tool) it is useful to define
 * the following macro, so that __sync macros are used: those can be detected
 * by Helgrind (even if they are less efficient) so that no false positive
 * is reported.
# define atomicIncr(var,count) do { \
    pthread_mutex_lock(&var ## _mutex); \
    var += (count); \
    pthread_mutex_unlock(&var ## _mutex); \
} while(0)

那么为什么list类型不像sds动态字符串一样动态分配内存呢?
我们发现,list结构并不像sds一样，存在可以记录当前字符串未使用字节的数量free数组，所以会产生内存碎片,而在没有记录当前未使用空间的情况下，内存的内部碎片(分配器分给节点的内存大于节点本身需要的内存)就会产生。
而 zmalloc的作用正如源文件中描述的那样

• Explicitly override malloc/free etc when using tcmalloc.

  • 关于 zmalloc分配器的讲解,在之后的章节中会描述

字典

• 在介绍本类型之前，请先看一段伪码，这里仅给出了 hash表未扩容情况下，hash表的转移方式

redis 字典hash算法

long useds[] ; 当前转移到的hash桶

dict root =  dict() // 定义字典

Hashtable  hash1 = dictht() // 第一个hash表

HashTable hash2 = dictht() // 第二个hash表

dict[0] = hash1
dict[1] = hash2


//hash桶未rehash,所有元素此时位于hash1
for(int i=0;i<4;i++){
 root.dict[0].used = 4,root.dict[0].size = 4;
 root.dict[1].used = 0,root.dict[1].size = 0;
}


//场景
1.当元素位于hash1时，先分配hash2的内存容量
rehashindex相当于一个全局变量，
面向过程监视hash1到hash2是否转移

假设hash1拥有1..n个element元素需要转移,则
for(int i=1;i<n;i++){
 //当hash2还没扩容，先根据hash1中的元素扩容，然后转移
 if(root.rehashindex!=-1){
     //判断是否转移
     if(root.dict[0].used!=0)
         hash2.size = hash1.size*2-1
     //释放hash1的内存
         hash1.size = 0;
     else{
         //已转移到hash2，但当前因为hash2还没有扩容
         //为了避免hash2扩容后地址映射出错
         //所以先恢复hash1,扩容后再转移到hash2

         root.dict[0] = root.dict[1]

     }

 }
}

redis中 dict.h

typedef struct dictht {

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

    // 哈希表大小
    unsigned long size;

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

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

} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

• 字典的hash算法,根据dict结构中定义的dictht结构，对应上面伪码的hash表类型,dict本身就如上面一样，维护两个hash表，一dictht个负责存放桶数组，也就是字典序最先放入的hash表，另一个负责进行扩容和保存hash1转移到hash2的桶数组

跳跃表

typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

我们知道链表查询一个元素的复杂度为O(n) ，如何让链表的元素查询接近O(logn)呢？

1.png

header 和 tail 指针分别指向跳跃表的表头和表尾节点， 通过这两个指针， 程序定位表头节点和表尾节点的复杂度为 O(1) 。
通过使用 length 属性来记录节点的数量， 程序可以在 O(1) 复杂度内返回跳跃表的长度。
level 属性则用于在 O(1) 复杂度内获取跳跃表中层高最大的那个节点的层数量， 注意表头节点的层高并不计算在内。

• 插入

要插入一个节点，不难想象首先需要查询插入的位置，因此首先其实是类似的执行一次查询。然后视情况定是做替换操作还是新增节点。插入的时候要利用一个随机算法来获取该元素要插入的层高，并根据“如果某个元素位于第 i 层，那该层一下的所有层也会包含此元素”这一特性，在要插入层和以下层中都要插入这个新元素。最后还要注意维护层高。以下是插入过程的一个示例：

222.png

• 删除

删除的第一步和插入很类似，首先要执行查找过程。如果查找到，则将该元素删除。这里也必须注意“如果某个元素位于第 i 层，那该层一下的所有层也会包含此元素”这一特性。最后还要注意维护层高。

• 查找

性能上，跳跃表支持平均 O(log N)、最坏 O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点。