Redis数据结构

redis 共有5个数据类型:

字符串/整型/浮点数;
列表（List）；
哈希表(Hash)；
集合（Set）;
有序集合(sorted set);

注：本文Redis版本为5.0

Redis数据结构底层实现

Redis底层数据结构有以下几种：

简单动态字符串（simple dynamic string,SDS）；
链表；
字典；
跳跃表；
集合；
压缩列表。

数据结构与底层数据结构的关系

数据结构	底层数据结构
字符串/整型/浮点数	简单动态字符串
列表（List）	链表
哈希表	字典
集合	intset/哈希表
有序集合	跳跃表

简单动态字符串

Redis并没有使用c语言本身的字符串类型，而是自己构建了一种名为简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示。

源码在redis/src/sds.h

Redis3.0底层结构

typedef char *sds;
struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

Redis5.0底层结构

typedef char *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 */
    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[];
};

typedef char *sds不就是char*嘛？的确，Redis采用一整段连续的内存来存储sds结构，char*类型正好可以和传统的C语言字符串类型兼容。但是，sds和char*并不等同，sds是二进制安全的，它可以存储任意二进制数据，不能像C语言字符串那样以‘\0’来标识字符串结束。

5.0版本细分了数据长度，具体与之前版本区别都不大，sds中有以下几个属性：

len，表示字符串真正的长度，不包含空终止字符;
alloc，表示字符串的最大容量，不包含Header和最后的空终止字符

flags，表示header的类型

// 五种header类型，flags取值为0~4
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

buf[]，存储字符串

上面的定义相对于 C 语言对于字符串的定义，多出了 len 属性以及其他的属性。为什么不使用C语言字符串实现，而是使用 SDS呢？这样实现有什么好处？

常数复杂度获取字符串长度

　　由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。而对于 C 语言，获取字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。通过 strlen key 命令可以获取 key 的字符串长度。

杜绝缓冲区溢出

　　我们知道在 C 语言中使用 strcat 函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。而对于 SDS 数据类型，在进行字符修改的时候，会首先根据记录的 len 属性检查内存空间是否满足需求，如果不满足，会进行相应的空间扩展，然后在进行修改操作，所以不会出现缓冲区溢出。

减少修改字符串的内存重新分配次数

　　C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。

　　而对于SDS，由于len属性和alloc属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：

　　1、空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。

　　2、惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。）

二进制安全

　　因为C字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串，因此C字符串无法正确存取；而所有 SDS 的API 都是以处理二进制的方式来处理 buf 里面的元素，并且 SDS 不是以空字符串来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束。

兼容部分 C 字符串函数

　　虽然 SDS 是二进制安全的，但是一样遵从每个字符串都是以空字符串结尾的惯例，这样可以重用 C 语言库<string.h> 中的一部分函数。

链表

链表是一种比较基础的数据结构，主要在插入和删除时效率较高。Redis实现的是双向链表。

typedef struct list{
     //表头节点
     listNode *head;
     //表尾节点
     listNode *tail;
     //链表所包含的节点数量
     unsigned long len;
     //节点值复制函数
     void (*free) (void *ptr);
     //节点值释放函数
     void (*free) (void *ptr);
     //节点值对比函数
     int (*match) (void *ptr,void *key);
}list;

Redis链表特性：

双端：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。
无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结束。　　
带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。
多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

字典

字典又称为符号表或者关联数组、或映射（map），是一种用于保存键值对的抽象数据结构。字典中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。C 语言中没有内置这种数据结构的实现，所以字典依然是 Redis自己构建的。

源码在redis/src/dict.h

哈希对象

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;

哈希表

typedef struct dictht {
    dictEntry **table; /* dictEntry*数组,Hash表 */
    unsigned long size; /* Hash表总大小 */
    unsigned long sizemask; /* 计算在table中索引的掩码, 值是size-1 */
    unsigned long used; /* Hash表已使用的大小 */
} dictht;

哈希节点

typedef struct dictEntry {
    void *key;       // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;  // 链表的下一个节点
} dictEntry;

字典类型函数

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

redis中hash表是使用拉链法来解决哈希冲突，dictht代表一个哈希表，基本结构是一个dictEntry的数组，数组中的每一个元素（key, value）都是一个链表，哈希相同的数据在同一条链表上。

key的hash计算

在dict.h中可以找到

1	#define dictHashKey(d, key) (d)->type->hashFunction(key)

这是一个 C语言宏定义，其实幕后真正承担 Hash值计算的是上面介绍的 dictType结构体中的函数指针 hashFunction。

而该 hashFunction函数指针在初始化时会对应被赋值为一个个真实的计算 Hash值的实际函数。

默认实现算法在siphash.c中

/* The default hashing function uses SipHash implementation
 * in siphash.c. */

uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k);
uint64_t siphash_nocase(const uint8_t *in, const size_t inlen, const uint8_t *k);

uint64_t dictGenHashFunction(const void *key, int len) {
    return siphash(key,len,dict_hash_function_seed);
}

uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len) {
    return siphash_nocase(buf,len,dict_hash_function_seed);
}

跳跃表

跳跃表的定义在server.h中

zskiplistNode代表跳表中的各个节点，zskiplist代表跳表。

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

集合

如果能够转成int的对象（isObjectRepresentableAsLongLong），那么就用intset保存。
如果用intset保存的时候，如果长度超过512（REDIS_SET_MAX_INTSET_ENTRIES）就转为hashtable编码。
其他情况统一用hashtable进行存储

int setTypeAdd(robj *subject, sds value) {
    long long llval;
    // 字典
    if (subject->encoding == OBJ_ENCODING_HT) {
        dict *ht = subject->ptr;
        // value为字典的key,字典的value为null
        dictEntry *de = dictAddRaw(ht,value,NULL);
        if (de) {
            dictSetKey(ht,de,sdsdup(value));
            dictSetVal(ht,de,NULL);
            return 1;
        }
    } else if (subject->encoding == OBJ_ENCODING_INTSET) {
        // 可以作为整数保存
        if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {
            uint8_t success = 0;
            subject->ptr = intsetAdd(subject->ptr,llval,&success);
            if (success) {
                /* Convert to regular set when the intset contains
                 * too many entries. */
                if (intsetLen(subject->ptr) > server.set_max_intset_entries)
                    setTypeConvert(subject,OBJ_ENCODING_HT);
                return 1;
            }
        // 如果对象的值不能编码为整数，那么将集合从 intset 编码转换为 HT 编码
        // 然后再执行添加操作
        } else {
            /* Failed to get integer from object, convert to regular set. */
            setTypeConvert(subject,OBJ_ENCODING_HT);

            /* The set *was* an intset and this value is not integer
             * encodable, so dictAdd should always work. */
            serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);
            return 1;
        }
    } else {
        serverPanic("Unknown set encoding");
    }
    return 0;
}

intset 整型集合

有3个属性：

编码
数据长度

数据内容

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

压缩列表

Redis使用字节数组表示一个压缩列表，字节数组逻辑划分为多个字段。

zlbytes	zltail	zllen	entry1	entry2	…	zlend

Redis源码(1):数据结构及底层实现