Redis的每种对象其实都由对象结构(redisObject)与对应编码的数据结构组合而成，而每种对象类型对应若干编码方式，不同的编码方式所对应的底层数据结构是不同的。

从一下两个角度来研究底层：

  • 对象设计机制: 对象结构(redisObject)
  • 编码类型和底层数据结构: 对应编码的数据结构

对象机制

为什么Redis会设计redisObject对象

  1. Redis 必须让每个键都带有类型信息, 使得程序可以检查键的类型, 并为它选择合适的处理方式。
  2. 操作数据类型的命令除了要对键的类型进行检查之外, 还需要根据数据类型的不同编码进行多态处理.

为了解决以上问题, Redis 构建了自己的类型系统, 这个系统的主要功能包括:

  • redisObject 对象.
  • 基于 redisObject 对象的类型检查.
  • 基于 redisObject 对象的显式多态函数.
  • 对 redisObject 进行分配、共享和销毁的机制.

redisObject数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * Redis 对象
 */
typedef struct redisObject {
    // 类型
    unsigned type:4;
    // 编码方式
    unsigned encoding:4;
    // LRU - 24位, 记录最末一次访问时间（相对于lru_clock）; 或者 LFU（最少使用的数据：8位频率，16位访问时间）
    unsigned lru:LRU_BITS; // LRU_BITS: 24
    // 引用计数
    int refcount;
    // 指向底层数据结构实例
    void *ptr;
} robj;
  • type记录了对象所保存的值的类型 
    1
    2
    3
    4
    5
    #define OBJ_STRING 0 // 字符串
    #define OBJ_LIST 1 // 列表
    #define OBJ_SET 2 // 集合
    #define OBJ_ZSET 3 // 有序集
    #define OBJ_HASH 4 // 哈希表
  • encoding记录了对象所保存的值的编码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /*
    * 对象编码
    */
    #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  /* 注意：版本2.6后不再使用. */
    #define OBJ_ENCODING_LINKEDLIST 4 /* 注意：不再使用了，旧版本2.x中String的底层之一. */
    #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 */
  • ptr是一个指针，指向实际保存值的数据结构。
    这个数据结构由type和encoding属性决定。
    举个例子，如果一个redisObject 的type 属性为OBJ_LIST ，encoding 属性为OBJ_ENCODING_QUICKLIST，那么这个对象就是一个Redis 列表（List），它的值保存在一个QuickList的数据结构内，而ptr 指针就指向quicklist的对象
  • lru属性: 记录了对象最后一次被命令程序访问的时间

命令的类型检查和多态

那么Redis是如何处理一条命令的呢？

当执行一个处理数据类型命令的时候，redis执行以下步骤

  • 根据给定的key，在数据库字典中查找和他相对应的redisObject，如果没找到，就返回NULL；
  • 检查redisObject的type属性和执行命令所需的类型是否相符，如果不相符，返回类型错误；
  • 根据redisObject的encoding属性所指定的编码，选择合适的操作函数来处理底层的数据结构；
  • 返回数据结构的操作结果作为命令的返回值。

底层数据结构

  • 简单动态字符串 - sds
  • 压缩列表 - ZipList
  • 快表 - QuickList
  • 字典/哈希表 - Dict
  • 整数集 - IntSet
  • 跳表 - ZSkipList

简单动态字符串 - sds

Redis 是用 C 语言写的，但是对于Redis的字符串，却不是 C 语言中的字符串（即以空字符’\0’结尾的字符数组），它是自己构建了一种名为简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示。
这是一种用于存储二进制数据的一种结构, 具有动态扩容的特点. 其实现位于src/sds.h与src/sds.c中。

SDS定义


其中sdshdr是头部, buf是真实存储用户数据的地方。
另外注意, 从命名上能看出来, 这个数据结构除了能存储二进制数据, 显然是用于设计作为字符串使用的, 所以在buf中, 用户数据后总跟着一个\0. 即图中 “数据” + “\0” 是为所谓的buf。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// sds.h
typedef char *sds;

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

SDS有五种不同的头部. 其中sdshdr5实际并未使用到. 所以实际上有四种不同的头部, 分别如下:

  • len 保存了SDS保存字符串的长度
  • buf[] 数组用来保存字符串的每个元素
  • alloc 分别以uint8, uint16, uint32, uint64表示整个SDS, 除过头部与末尾的\0, 剩余的字节数
  • flags 始终为一字节, 以低三位标示着头部的类型, 高5位未使用

为什么使用SDS

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

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

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

  • 减少修改字符串的内存重新分配次数
    C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。
    而对于SDS，由于len属性和alloc属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：

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

      当执行追加操作时，比如现在给key=‘Hello World’的字符串后追加 ‘ again!’ 则这时的len=18，free由0变成了18，此时的**buf=’Hello World again!\0………………..’(.表示空格)**，也就是buf的内存空间是18+18+1=37个字节，其中‘\0’占1个字节。redis给字符串多分配了18个字节的预分配空间，所以下次还有append追加的时候，如果预分配空间足够，就无须在进行空间分配了。
      在Redis 6.0版本中，当新字符串的长度小于1M时，redis会分配他们所需大小一倍的空间，当大于1M的时候，就为他们额外多分配1M的空间。

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

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

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

压缩列表 - ZipList

ziplist是为了提高存储效率而设计的一种特殊编码的双向链表。
它可以存储字符串或者整数，存储整数时是采用整数的二进制而不是字符串形式存储。
它能在O(1)的时间复杂度下完成list两端的push和pop操作。
但是因为每次操作都需要重新分配ziplist的内存，所以实际复杂度和ziplist的内存使用量相关。

ziplist结构

整个ziplist在内存中的存储格式如下：

  • zlbytes字段的类型是uint32_t, 这个字段中存储的是整个ziplist所占用的内存的字节数。
  • zltail字段的类型是uint32_t, 它指的是ziplist中最后一个entry的偏移量。
    用于快速定位最后一个entry, 以快速完成pop等操作。
  • zllen字段的类型是uint16_t, 它指的是整个ziplit中entry的数量。
    这个值只占2bytes（16位）。
    如果ziplist中entry的数目小于65535(2的16次方), 那么该字段中存储的就是实际entry的值。
    若等于或超过65535, 那么该字段的值固定为65535, 但实际数量需要一个个entry的去遍历所有entry才能得到。
  • zlend是一个终止字节, 其值为全F, 即0xff。
    ziplist保证任何情况下, 一个entry的首字节都不会是255。

ziplist-entry结构

  • 第一种情况：一般结构<prevlen> <encoding> <entry-data>
    • prevlen：前一个entry的大小；
    • encoding：不同的情况下值不同，用于表示当前entry的类型和长度；
    • entry-data：真是用于存储entry表示的数据；
  • 第二种情况：<prevlen> <encoding>
    在entry中存储的是int类型时，encoding和entry-data会合并在encoding中表示，此时没有entry-data字段。
    redis中，在存储数据时，会先尝试将string转换成int存储，节省空间。

为什么ZipList特别省内存

只有理解上面的Entry结构，我们才会真正理解ZipList为什么是特别节省内存的数据结构。

ziplist节省内存是相对于普通的list来说的，如果是普通的数组，那么它每个元素占用的内存是一样的且取决于最大的那个元素（很明显它是需要预留空间的）；所以ziplist在设计时就很容易想到要尽量让每个元素按照实际的内容大小存储，所以增加encoding字段，针对不同的encoding来细化存储大小。
这时候还需要解决的一个问题是遍历元素时如何定位下一个元素呢？在普通数组中每个元素定长，所以不需要考虑这个问题；但是ziplist中每个data占据的内存不一样，所以为了解决遍历，需要增加记录上一个元素的length，所以增加了prelen字段。

快表 - QuickList

quicklist这个结构是Redis在3.2版本后新加的, 之前的版本是list(即linkedlist)， 用于String数据类型中。
它是一种以ziplist为结点的双端链表结构。
宏观上, quicklist是一个链表；微观上, 链表中的每个结点都是一个ziplist。

字典/哈希表 - Dict

本质上就是哈希表

哈希表结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
typedef struct dictht{
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    //总是等于 size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
 
}dictht

//哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，
// dictEntry 结构定义如下：
typedef struct dictEntry{
     //键
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
 
     //指向下一个哈希表节点，形成链表
     struct dictEntry *next;
}dictEntry

整数集 - IntSet

整数集合（intset）是集合类型的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。

跳表 - ZSkipList

跳跃表结构在 Redis 中的运用场景只有一个，那就是作为有序列表 (Zset) 的使用。
跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来相比较的，而且在实现方面比平衡树要优雅，这就是跳跃表的长处。
跳跃表的缺点就是需要的存储空间比较大，属于利用空间来换取时间的数据结构。

思考：为什么用跳跃表实现，而不是平衡树或者哈希表？

什么是跳跃表

跳表其实就是一种可以进行二分查找的有序链表。
跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找，将查找的时间复杂度从O(N)降到O(logN)。

Redis zskiplist的设计

redis跳跃表并没有在单独的类（比如skplist.c）中定义，而是其定义在server.h中, 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

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


zskiplist的核心设计要点

  • 头节点不持有任何数据, 且其level[]的长度为32
  • 每个结点
    • ele字段，持有数据，是sds类型。
    • score字段，其标示着结点的得分, 结点之间凭借得分来判断先后顺序, 跳跃表中的结点按结点的得分升序排列。
    • backward指针，这是原版跳跃表中所没有的. 该指针指向结点的前一个紧邻结点。
    • level字段, 用以记录所有结点(除过头节点外)；每个结点中最多持有32个zskiplistLevel结构，实际数量在结点创建时，按幂次定律随机生成(不超过32)。
      每个zskiplistLevel中有两个字段：
      • forward字段指向比自己得分高的某个结点(不一定是紧邻的)，并且，若当前zskiplistLevel实例在level[]中的索引为X，则其forward字段指向的结点, 其level[]字段的容量至少是X+1。这也是上图中, 为什么forward指针总是画的水平的原因。
      • span字段代表forward字段指向的结点，距离当前结点的距离。紧邻的两个结点之间的距离定义为1。

Redis对象和底层结构对应关系

字符串对象 string

字符串是Redis最基本的数据类型，不仅所有key都是字符串类型，其它几种数据类型构成的元素也是字符串。
注意字符串的长度不能超过512M。

编码
字符串对象的编码可以是int，raw或者embstr。

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

内存布局
字符串对象支持三种编码方式: RAW, INT, EMBSTR, 三种方式的内存布局分别如下:

raw 和 embstr 的区别

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

对于 embstr 编码，由于 Redis 没有对其编写任何的修改程序（embstr 是只读的），在对embstr对象进行修改时，都会先转化为raw再进行修改，因此，只要是修改embstr对象，修改后的对象一定是raw的，无论是否达到了44个字节。

列表对象 list

list 列表，它是简单的字符串列表，按照插入顺序排序，你可以添加一个元素到列表的头部（左边）或者尾部（右边），它的底层实际上是个链表结构。

编码
列表对象的编码是quicklist。 (之前版本中有linked和ziplist这两种编码。进一步的, 目前Redis定义的10个对象编码方式宏名中, 有两个被完全闲置了, 分别是: OBJ_ENCODING_ZIPMAP与OBJ_ENCODING_LINKEDLIST。 从Redis的演进历史上来看, 前者是后续可能会得到支持的编码值（代码还在）, 后者则应该是被彻底淘汰了)
内存布局

哈希对象 hash

哈希对象的键是一个字符串类型，值是一个键值对集合。
编码
哈希对象的编码可以是 ziplist 或者 hashtable；对应的底层实现有两种，一种是ziplist，一种是dict。
编码的转换
当同时满足下面两个条件时，使用ziplist（压缩列表）编码：

  1. 列表保存元素个数小于512个
  2. 每个元素长度小于64字节

不能满足这两个条件的时候使用 hashtable 编码。

集合对象 set

集合对象 set 是 string 类型（整数也会转换成string类型进行存储）的无序集合。
注意集合和列表的区别：集合中的元素是无序的，因此不能通过索引来操作元素；集合中的元素不能有重复。
编码
集合对象的编码可以是 intset 或者 hashtable; 底层实现有两种, 分别是intset和dict。

显然当使用intset作为底层实现的数据结构时, 集合中存储的只能是数值数据, 且必须是整数;
而当使用dict作为集合对象的底层实现时, 是将数据全部存储于dict的键中, 值字段闲置不用.
编码的转换
当集合同时满足以下两个条件时，使用 intset 编码：

  1. 集合对象中所有元素都是整数
  2. 集合对象所有元素数量不超过512

不能满足这两个条件的就使用 hashtable 编码。
第二个条件可以通过配置文件的 set-max-intset-entries 进行配置。

有序集合对象 zset

和集合对象相比，有序集合对象是有序的。
与列表使用索引下标作为排序依据不同，有序集合为每个元素设置一个分数（score）作为排序依据。
编码
有序集合的底层实现有两种：
一种是使用ziplist作为底层实现, 对应的编码值宏为ZIPLIST；
另外一种比较特殊, 底层使用了两种数据结构: dict与skiplist, 对应的编码值宏为SKIPLIST。

使用ziplist来实现有序集合很容易理解, 只需要在ziplist这个数据结构的基础上做好排序与去重就可以了。
使用zskiplist来实现有序集合也很容易理解, Redis中实现的这个跳跃表似乎天然就是为了实现有序集合对象而实现的, 那么为什么还要辅助一个dict实例呢?
我们先看来有序集合对象在这两种编码方式下的内存布局, 然后再做解释。

  • ZIPLIST
  • SKIPLIST

编码的转换
当有序集合对象同时满足以下两个条件时，对象使用 ziplist 编码：

  1. 保存的元素数量小于128；
  2. 保存的所有元素长度都小于64字节。

不能满足上面两个条件的使用 skiplist 编码。
以上两个条件也可以通过Redis配置文件zset-max-ziplist-entries 选项和 zset-max-ziplist-value 进行修改。