Redis底层数据结构

RedisObject

默认有16个数据库，每一个db 有两个dict， 一个存储数据内容，一个记录失效时间。存储数据的dict：key是String，value是RedisObject。

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    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;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4

#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
/*
 * Redis 对象
 */
typedef struct redisObject {

    //type表示了该对象的对象类型，即五种数据类型的一个。
    unsigned type:4;        
    // 编码方式 同一个类型的 type 会有不同的编码方式，
    unsigned encoding:4;
    // LRU 时间,用于记录缓存对象最后被访问的时间
    unsigned lru:22;
    // 引用计数,每个对象都有个引用计数 refcount，当引用计数为零时，对象就会被销毁，内存被回收。
    int refcount;
    // 指向底层数据结构的指针
    void *ptr;
} robj;

SDS

SDS(Simple Dynamic String) 类似于 Java 中的 ArrayList，可以通过预分配冗余空间的方式来减少内存频繁分配。SDS 还可以作为缓冲区：包括 AOF 模块中的AOF缓冲区以及客户端状态中的输入缓冲区。

struct sdshdr{
 int len;//记录buf数组中已使用字节的数量=等于 SDS 保存字符串的长度
 int free;//记录 buf 数组中未使用字节的数量
 char buf[];//字节数组，用于保存字符串
}

encoding可能是int、raw、embstr。

如果一个字符串的内容可以转换为long，那么该字符串就会被转换成为long类型，对象的ptr就会指向该long，并且对象类型也用int类型表示。

embstr应该是Redis 3.0新增的数据结构,在2.8中是没有的。如果字符串对象的长度小于39字节，就用embstr对象。否则用传统的raw对象。

raw：长度大于44字节的字符串，使用SDS(简单动态字符串)保存

embstr：长度小于等于44字节的字符串，效率比较高，且数据都保存在一块内存区域

为什么不使用C语言字符串实现，而是使用 SDS呢？

复杂度获取字符串长度

C语言对字符串长度的统计是从头遍历到末尾，直到发现空字符‘\0’停止以此统计出字符串长度，这样获取长度的时间复杂度来说是O(n)；SDS 字符串的长度只需要读取 len 属性。

杜绝缓冲区溢出

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

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

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

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

空间预分配：当我们对SDS进行扩展操作的时候，Redis会为SDS分配好内存，并且根据特定的公式，分配多余的free空间，还有多余的1byte空间（这1byte也是为了存空字符），这样就可以避免我们连续执行字符串添加所带来的内存分配消耗。

惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，因为可以预防你继续添加的操作，这样可以减少分配空间带来的消耗，但是当你再次操作还是没用到多余空间的时候，Redis也还是会收回对于的空间，防止内存的浪费的。

二进制安全

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

链表

链表是一种常用的数据结构，C 语言内部是没有内置这种数据结构的实现，所以Redis自己构建了链表的实现。

//链表定义
typedef struct listNode {
    struct listNode *prev;//前置节点
    struct listNode *next; //后置节点
    void *value;//节点的值
} listNode;
//多个 listNode 结构就可以组成链表，这是一个双向链表
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;

encoding早期使用ziplist或linkedlist，Redis 3.2版本后list使用quicklist

ziplist：压缩列表，

linkedlist：双向链表，节点中存放pre和next两个指针，还有节点相关信息。每增加一个node时需要重新malloc一块内存。修改效率高，但是由于需要保存前后指针，占内存比较多。

quicklist：3.2之后引入，可以理解成是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。这样既满足了快速插入删除性能，又不会出现太大的空间冗余。

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

字典

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

typedef struct dict {
    dictType *type;//类型特定函数，包括一些自定义函数，这些函数使得key和value能够存储
    void *privdata;//私有数据
    dictht ht[2]; //两张hash表 
    long rehashidx; //rehash索引，字典没有进行rehash时，此值为-1
    unsigned long iterators;  //正在迭代的迭代器数量
} dict;
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;
typedef struct dictht {
    dictEntry **table;//哈希表数组
    unsigned long size; //哈希表大小
    unsigned long sizemask;//哈希表大小掩码，用于计算索引值等于 size-1
    unsigned long used;//该哈希表已有节点的数量
} dictht;
typedef struct dictEntry {
    void *key;//键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;//值
    struct dictEntry *next;//指向下一个哈希表节点，形成链表
} dictEntry;

哈希算法：Redis计算哈希值和索引值方法如下：

//1、使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
//2、使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值
index = hash & dict->ht[x].sizemask;

扩容和收缩：当哈希表保存的键值对太多或者太少时，就要通过 rerehash(重新散列）来对哈希表进行相应的扩展或者收缩。具体步骤：

1、如果执行扩展操作，会基于原哈希表创建一个大小等于 ht[0].used*2n 的哈希表（也就是每次扩展都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表）。相反如果执行的是收缩操作，每次收缩是根据已使用空间缩小一倍创建一个新的哈希表。

2、重新利用上面的哈希算法，计算索引值，然后将键值对放到新的哈希表位置上。

3、所有键值对都迁徙完毕后，释放原哈希表的内存空间。

触发扩容的条件：

1、服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。

2、服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。

渐近式 rehash

什么叫渐进式 rehash？也就是说扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。如果保存在Redis中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成Redis一段时间内不能进行别的操作。所以Redis采用渐进式 rehash,这样在进行渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行 增加操作，一定是在新的哈希表上进行的。

• 
  
• ```c typedef struct zskiplistNode { sds ele;//成员对象 double score;//分值 struct zskiplistNode *backward;//后退指针 struct zskiplistLevel {

  struct zskiplistNode *forward;//前进指针
  unsigned long span;//跨度 用来计算排位(rank)的
  

  } level[]; } zskiplistNode;

typedef struct zskiplist { struct zskiplistNode header, tail;//表头节点,表尾节点 unsigned long length;//跳跃表的长度 int level;//层数最大的那个节点的层数 } zskiplist;

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

<a name="859cee25"></a>
## 跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。具有如下性质：

1、由很多层结构组成；

2、每一层都是一个有序的链表，排列顺序为由高层到底层，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点；

3、最底层的链表包含了所有的元素；

4、如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）；

5、链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个链表节点；

```c
typedef struct zskiplistNode {
     //层
     struct zskiplistLevel{
           //前进指针
           struct zskiplistNode *forward;
           //跨度
           unsigned int span;
     }level[];

     //后退指针
     struct zskiplistNode *backward;
     //分值
     double score;
     //成员对象
     robj *obj;

} zskiplistNode

typedef struct zskiplist{
     //表头节点和表尾节点
     struct zskiplistNode *header, *tail;
     //表中节点的数量
     unsigned long length;
     //表中层数最大的节点的层数
     int level;

}zskiplist

①、搜索：从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。

②、插入：首先确定插入的层数，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定插入的层数k后，则需要将新元素插入到从底层到k层。

③、删除：在各个层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。

整数集合

整数集合（intset）是Redis用于保存整数值的集合抽象数据类型，它可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。

typedef struct intset{
     //编码方式
     uint32_t encoding;
     //集合包含的元素数量
     uint32_t length;
     //保存元素的数组
     int8_t contents[];

}intset;

升级

当我们新增的元素类型比原集合元素类型的长度要大时，需要对整数集合进行升级，才能将新元素放入整数集合中。具体步骤：

1、根据新元素类型，扩展整数集合底层数组的大小，并为新元素分配空间。

2、将底层数组现有的所有元素都转成与新元素相同类型的元素，并将转换后的元素放到正确的位置，放置过程中，维持整个元素顺序都是有序的。

3、将新元素添加到整数集合中（保证有序）。

升级能极大地节省内存。

②、降级

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

压缩列表

压缩列表（ziplist）是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。适用于长度较小的值，插入复杂度是O(N)，即每次插入都会重新进行realloc。

压缩列表的原理：压缩列表并不是对数据利用某种算法进行压缩，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。

redis五种数据类型的底层应用

String

编码可以是int，raw或者embstr。int 编码是用来保存整数值，raw编码是用来保存长字符串，而embstr是用来保存短字符串。

• int 编码：保存可以用 long 类型表示的整数值。
• raw 编码：保存长度大于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）。
• embstr 编码：保存长度小于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）。

当 int 编码保存的值不再是整数或大小超过了long的范围时，自动转化为raw。

embstr与raw都使用redisObject和sds保存数据。区别在embstr的使用只分配一次内存空间（redisObject和sds是连续的），而raw需要分配两次内存空间（分别为redisObject和sds分配空间）。与raw相比，embstr的优点在于创建时少分配一次空间，删除时少释放一次空间，以及对象的所有数据连在一起，寻找方便。而embstr的缺点是如果字符串长度增加需要重新分配内存时，整个redisObject和sds都需要重新分配空间。

hash

编码可以是 ziplist 或者 hashtable。

当哈希对象保存的键值对数量小于 512，并且所有键值对的长度都小于 64 字节时，使用ziplist存储；否则使用 hashtable 存储。

hset profile name "Tom"
hset profile age 25
hset profile career "Programmer"

使用ziplist编码也就是压缩列表作为底层实现，profile 存储如下：

当使用 hashtable 编码，底层使用字典数据结构时，上面命令存储如下：

list

编码可以是 ziplist和 linkedlist。

键值对数量小于 512，并且所有键值对的长度都小于 64 字节时，使用ziplist存储；否则使用使用 linkedlist。

rpush numbers 1 "three" 5

ziplist 编码表示如下：

linkedlist表示如下：

set

编码可以是 intset 或者 hashtable。

所有元素都是整数，元素数量不超过512，使用 intset 编码，否则采用 hashtable 编码。

intset 编码使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合中。

hashtable 编码使用字典作为底层实现，字典的每个键都是一个字符串对象，这里的每个字符串对象就是一个集合中的元素，而字典的值则全部设置为 null。（类比Java集合中HashSet 集合的实现，HashSet 集合是由 HashMap 来实现的，集合中的元素就是 HashMap 的key，而 HashMap 的值都设为 null。）

SADD numbers 1 3 5

SADD Dfruits "apple" "banana" "cherry"

zset

encoding使用ziplist或者skiplist。

元素数量小于128，所有元素长度都小于64字节，使用ziplist，否则使用 skiplist。

ziplist 使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个节点保存元素的分值。并且压缩列表内的集合元素按分值从小到大的顺序进行排列，小的放置在靠近表头的位置，大的放置在靠近表尾的位置。

skiplist 编码使用 zset 结构作为底层实现，一个 zset 结构同时包含一个字典和一个跳跃表：

typedef struct zset{
   zskiplist *zsl;//跳跃表 跳跃表节点的 object 属性保存元素的成员，跳跃表节点的 score 属性保存元素的分值。
   dict *dict;//字典 字典的键保存元素的值，字典的值则保存元素的分值
} zset;

ZADD price 8.5 apple 5.0 banana 6.0 cherry

参考

Redis五种基本数据类型底层实现
Redis详解
Redis 源码学习笔记