Redis底层数据结构设计

Redis是一个分布式缓存中间件，基于C语言写的key-value内存数据库，可以用于做数据缓存、分布式锁、海量数据统计、会话缓存、计数器、分布式队列、延迟队列、分布式ID生成等。Redis是一个键值对数据库，所以介绍Redis得从它的键值对说起，Redis的键只能为字符串对象，Redis的值有五种数据结构，分别是：string（字符串）、list（列表）、hash（字典）、set（集合）和zset（有序集合）。

SDS

Redis的key和value都可以是字符串，并且上面也提到Redis是基于C语言开发，下面就来探究下Redis字符串是如何存储的。Redis没有直接使用C语言传统的字符串表示，而是自定义了一个字符串对象SDS（Simple Dynamic String），就是简单的动态字符串，作为Redis中字符串的默认存储。

Redis3.2之前SDS数据结构如下：

struct sdshdr {
    unsigned int len; //表示 buf（缓冲区）中已经使用的空间长度  
    unsigned int free;//表示 buf中未使用的长度  
    char buf[];//buf[] 表示缓冲区数组，存储字符         
};

使用SDS作为Redis默认字符串存储的好处：

C语言字符串	SDS
获取字符串长度的复杂度为O(N)	获取字符串长度的复杂度为O(1)
API是不安全的，可能会造成缓冲区溢出	API是安全的，不会造成缓冲区溢出
修改字符串长度N次必然需要执行N次内存重分配	修改字符串长度N次最多需要执行N次内存重分配
只能保存文本数据	可以保存文本数据或者二进制数据二进制安全
可以使用所有C字符串函数库	兼容部分C字符串函数库

但是在Redis 3.2 版本中，对数据结构做出了修改，针对不同的长度范围定义了不同的结构的header，这样短字符串就能使用较小的存储结构，从而节省内存：

typedef char *sds;      

struct __attribute__ ((__packed__)) sdshdr5 {     // 对应的字符串长度小于 1<<5
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {     // 对应的字符串长度小于 1<<8
    uint8_t len; /* used */                       //目前字符创的长度
    uint8_t alloc;                                //已经分配的总长度
    unsigned char flags;                          //flag用3bit来标明类型，类型后续解释，其余5bit目前没有使用
    char buf[];                                   //柔性数组，以'\0'结尾
};
struct __attribute__ ((__packed__)) sdshdr16 {    // 对应的字符串长度小于 1<<16
    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 {    // 对应的字符串长度小于 1<<32
    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 {    // 对应的字符串长度小于 1<<64
    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[];
};

其中：

len: 表示字符串的真正长度（不包含NULL结束符在内）。
alloc: 表示字符串的最大容量（不包含最后多余的那个字节）。
flags: 总是占用一个字节。其中的最低3个bit用来表示header的类型。header的类型共有5种，在sds.h中有常量定义。
由sds字符指针先向低地址方向偏移1个字节的位置，得到flags字段，这样就可以得到具体header类型，获取了header类型，就能很快定位到它的len和alloc字段，如下图。
sdshdr5与其它几个header结构不同，它不包含alloc字段，而长度使用flags的高5位来存储。因此，它不能为字符串分配空余空间。如果字符串需要动态增长，那么它就必然要重新分配内存才行。所以说，这种类型的sds字符串更适合存储静态的短字符串（长度小于32），如下图。

Redis对象

Redis使用对象来表示数据库中的键和值，每次我们在Redis数据库中创建一个键值对的时候，至少会创建两个对象，即键对象和值对象，对象的结构如下：

#define REDIS_LRU_BITS 24
typedef struct redisObject {
    unsigned type:4;// 类型
    unsigned encoding:4;// 编码
    unsigned lru:REDIS_LRU_BITS; // 对象最后一次被访问的时间，当前时间减去该值就是对象的空转时长
    int refcount;// 引用计数
    void *ptr;// 指向值对象的指针
} robj;

其中，type对应五种基本数据类型，encoding属性记录了对象所使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现，以下一个对象的类型以及对应的多种编码：

对象类型	对象编码	数据结构
REDIS_STRING	REDIS_ENCODING_INT、REDIS_ENCODING_EMBSTR、REDIS_ENCODING_RAW	整数（int）、embstr编码格式sds（embstr）、raw编码格式sds（raw）
REDIS_LIST	REDIS_ENCODING_ZIPLIST、REDIS_ENCODING_LINKEDLIST	压缩列表（ziplist）、双端链表（linkedlist）
REDIS_SET	REDIS_ENCODING_INTSET、REDIS_ENCODING_HT	整数集合（intset）、字典（hashtable）
REDIS_ZSET	REDIS_ENCODING_ZIPLIST、REDIS_ENCODING_SKIPLIST	压缩列表（ziplist）、跳跃表（skiplist）
REDIS_HASH	REDIS_ENCODING_ZIPLIST、REDIS_ENCODING_HT	压缩列表（ziplist）、字典（hashtable）

字符串

首先说下REDIS_STRING，字符串对象保存的数据是整型与字符串。字符串对象的底层有着三种实现结构：整数、embstr编码的sds字符串、raw编码的sds字符串。

当字符串对象保存的是一个整型值，那么字符串对象会将整数值保存在字符串对象的ptr属性中。当存入的是一个不大于44字节的字符串时，就采用embstr编码的sds字符串保存数据，而大于44字节的字符串就采用raw编码的字符串来保存。raw编码的ads与embstr编码的sds主要的区别在于embstr编码的sds内存与redisObj内存是在一块的(因为一起分配的内存)，所以保存的字符串是在其整体里，字符数据与对象共存亡。如下图所示：

编码的转换，int编码的字符串对象和emstr编码的字符串对象满足的情况下，会被转换为raw编码的字符串对象。对于int编码的字符串对象来说，执行命令让其不再是字符串对象时，字符串编码将从int变为raw。Redis对于embstr编码的对象没有修改程序，所以embstr字符串其实是只读的。当我们对于embstr编码的字符串对象进行修改命令时，程序先将对象编码从embstr转换为raw然后执行修改操作。所以，当对于一个embstr编码的字符串对象执行修改命令后，总会变成一个raw编码的字符串对象。

字符串扩容，需要注意的是当字符长度小于1MB时，扩容都是加倍现有的空间。如果字符串长度超过1MB，扩容时一次只会多扩1MB的空间，字符串最大长度为512MB。

列表

linkedlist，类似于java当中的LinkedList，普通的双向链表结构。

ziplist，Redis为了节约内存空间使用，很多数据结构都使用到了压缩列表来存储。压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。entry随容纳的元素类型不同，也会有不同的结构。prevlen表示前一个entry的长度，当压缩列表倒着遍历的时候，需要通过这个字段来快速定位到下一个元素位置。Redis为了节约存储空间，根据len前缀来识别具体存储的数据形式。如下图所示：

Redis早期存储少量元素时使用ziplist，当元素多的时候用linkedlist。考虑到链表的附加空间相对太高，prev和next指针就要占据16个字节（64位操作系统为8个字节），每个链表节点的内存都单独分配，会加剧内存碎片化，影响内存管理效率。Redis的新的版本对列表数据结构进行了改造，使用quicklist代替了ziplist和linkedlist。quicklist是ziplist和linkedlist的混合体，它将linkedlist按段切分，每一段使用ziplist让存储紧凑，多个ziplist之间使用双向指针串连起来，如下图：

quicklist内部默认单个ziplist长度为8KB，超出了这个字节数，会另起一个ziplist，可以通过list-max-ziplist-size配置。

字典

字典在Redis中应用比较广泛，哈希键以及Redis数据库都是基于字典实现。Redis中的字典相当于Java中的HashMap，采用的是数组加链表的哈希表结构来存储。当需要新增一个键值对时，首先根据键值计算出哈希值和索引值，然后根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上。当发生哈希冲突时，Redis使用头插法将碰撞的元素使用链表串起来。

哈希表代码如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

其中，table属性是一个数组，数组中每个元素指向dictEntry结构的指针，即哈希表节点，每个哈希表节点保存着一个键值对。size属性记录了哈希表的大小，即table的大小，而used则记录了哈希表已有键值对的数量。sizemask属性的值总是等于size-1，这个属性和哈希值一起决定一个键放到table的哪个索引上。

哈希表节点代码如下：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

其中key保存着键值对的键，v保存着键值对的值，其中值可以为一个指针，或者uint64_t整数，或者int64_t的整数，double浮点数。next指针指向另一个哈希表节点，用来解决哈希冲突。

字典的代码如下：

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;

其中type和privdate属性是针对不同类型的键值对，为创建字典多态设置的。ht属性是一个包含两个项的数组，数组中每一项都是一个dictht的哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表rehash用。rehashidx则记录了rehash的进度，没有rehash是为-1。

Redis的字段和Java的hashMap的不同，Redis的字典的值只能是字符串，并且他们rehash的方式不一样。Java中的rehash是一次性完成的，所以当字典很大的时候，耗时比较久。Redis为了追求高性能，不饿能阻塞服务，采用的是渐进式rehash策略。

Redis渐进式rehash的步骤如下：

为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash正式开始。
在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，完成rehashidx加一。
随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1]，这时程序将rehashidx属性设置为-1，表示rehash操作完成。

另外当一个哈希键只包含少量键对，并且每个键值对的键和值要么是小整数值，要么是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现，如图两个键值对，通过压缩列表作为底层存储：

编码的转换，当哈希对象满足以下两个条件时，哈希对象以ziplist编码，否则以hashtable编码：

哈希对象保存的所有键值对的字符串长度都小于64字节。
哈希对象保存的键值对数量小于512个。

集合

Redis的集合相当于Java中的HashSet，它内部的键值对是无序的、唯一的。集合对象的编码可以是intset和hashtable。

intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，并代表了一个集合元素，字典的值全部置为NULL。

编码转换，当集合对象满足以下两个条件时，对象使用intset编码，否则使用hashtable编码：

集合对象保存的所有元素都是整数值。
集合对象保存的元素数量不超过512个。

有序集合

有序集合顾名思义，就是有顺序的集合，主要通过给每个集合元素设置一个score来实现有序，有序集合的编码可以是ziplist和skiplist。

使用压缩列表作为底层实现时，每个集合元素使用两个紧挨在一起的压缩列表节点来保存。第一个节点保存元素的值（member），第二个元素保存元素的分数（score），如图，有序集合元素在压缩列表中按分值从小到大排列：

跳跃表实现的有序集合代码如下：

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

跳跃表节点，其中ele为数据值，score为数据对应的分数，backward指向前一个节点的指针（前向指针），level[]，数组的大小为层数，存放的是各层链表后一个节点的指针，其中每层forward表示单层的后向指针，span表示当前指针到后面元素跨越了多少个节点。

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

跳跃表，header和tail分别指向跳跃表的表头和表尾节点，通过该指针，程序定位表头节点和表尾节点的时间复杂度为o(1),length属性来记录节点的数量，level属性用来记录跳跃表中层高最大的那个几点的层数。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

以skiplist编码的有序集合对象zset，一个zset包含了一个字典和一个跳跃表，zsl跳跃表按分值从小到大保存了所有集合对象。dict字典为有序集合创建了一个从成员到分值的映射。字典的键保存了一个集合元素，值则是相应的分值。

使用跳跃列表作为底层实现有序列表结构示意图如下：

其中有三个元素，a为一层，b三层，c两层。

上面的图还不够直观，下面就举个直观的例子，来讲解跳跃列表，

有一个有序表如下，从该有序表中搜索元素 < 23, 43, 59 > ，需要比较的次数分别为 < 2, 4, 6 >，总共比较的次数为 2 + 4 + 6 = 12 次。

有没有优化的算法吗? 链表是有序的，但不能使用二分查找。类似二叉搜索树，我们把一些节点提取出来，作为索引。这里我们把 < 14, 34, 50, 72 > 提取出来作为一级索引，这样搜索的时候就可以减少比较次数了得到如下结构：

还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构：

总结了跳跃列表的一些特性：

新插入一个元素不会影响其它元素的层数
每一层都是一个有序的链表
最底层(Level 1)的链表包含所有元素
如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现
每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素
跳跃列表共有64层，能容纳2的64次方个与元素
跳跃列表对于每一个新插入的节点，都需要调用一个随机算法给它分配一个合理的层数。其中期望是50%分配到level1，25%的概率被分配到leve2，12.5%的概率分配到level3，以此类推，2的负63次方的概率分配到最顶层
插入元素时，搜索合适插入点的过程中将搜索路径找出来，然后为这个新节点随机分配一个层数，再将搜索路径上的节点和这个新节点通过前向后向指针串起来。如果分配的新节点的高度高于当前跳跃列表的最大高度，就需要更新一下跳跃列表的最大高度
删除过程和插入过程类似，需要先把这个搜索路径找出来，然后对于每个层的相关节点更新一下前向后向指针，同时还要注意更新下最高层数
更新，如果value不存在则为新增，如果存在只是改动score的值，则为更新。Redis的策略是先删除该元素，然后新增
score一样时，redis还会根据比较value的值
元素的排名rank值是根据搜索路径上所有span值的叠加计算出来的，Redis在插入、删除操作时都需要更新span的值

Redis主体对象结构

最后来总结下RedisDB主体数据结构：

Redis的整体结构图如上图所示，首先RedisDb中包含了Redis整体的信息，redisDb.id 存储着 redis 数据库以整数表示的号码。redisDb.expires 保存着每一个键的过期时间，redisDb.dict 存储着该库所有的键值对数据。当redis 服务器初始化时，会预先分配 16 个数据库。有时候当程序需要知道自己是在哪个数据库时，直接读取 redisDb.id 即可。

由上述的结构可以看出，redis 的字典使用哈希表作为其底层实现。dict 类型使用的两个指向哈希表的指针，其中 0 号哈希表（ht[0]）主要用于存储数据库的所有键值，而1号哈希表主要用于程序对 0 号哈希表进行 rehash 时使用，rehash 一般是在添加新值时会触发，这里不做过多的赘述。所以redis 中查找一个key，其实就是对进行该dict 结构中的 ht[0] 进行查找操作。最终哈希表节点上保存了key和val，val指向了实际的redis对象，redis对象则根据实际的type和encoding保存具体数据结构的值。

既然是哈希，那么我们知道就会有哈希碰撞，那么当多个键哈希之后为同一个值怎么办呢？redis采取链表的方式来存储多个哈希碰撞的键。也就是说，当根据key的哈希值找到该列表后，如果列表的长度大于1，那么我们需要遍历该链表来找到我们所查找的key。

了解了上述知识之后，我们就可以来分析redis如果在内存找到一个key了：

当拿到一个key后， redis 先判断当前库的0号哈希表是否为空，即：if (dict->ht[0].size == 0)。如果为true直接返回NULL。
判断该0号哈希表是否需要rehash，因为如果在进行rehash，那么两个表中者有可能存储该key。如果正在进行rehash，将调用一次_dictRehashStep方法，_dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash。
计算哈希表，根据当前字典与key进行哈希值的计算。
根据哈希值与当前字典计算哈希表的索引值。
根据索引值在哈希表中取出链表，遍历该链表找到key的位置。一般情况，该链表长度为1。
当 ht[0] 查找完了之后，再进行了次rehash判断，如果未在rehashing，则直接结束，否则对ht[1]重复345步骤。
到此我们就找到了key在内存中的位置了。