本文的内容主要参考《Redis设计与实现》一书。该书是基于Reids 2.9来编写的。

所以，本文的部分内容相对于新版本的Redis，可能会有差异。

1、概述

1.1 五种数据类型

Redis数据库里面的每个键值对（key-value pair）都是由对象（object）组成。

1. 数据库键（Key）总是一个字符串对象（String Object）
2. 数据库键对应的值（Value）可以是：

• 字符串对象
• 列表对象（List Object）
• 集合对象（Set Object）
• 有序集合对象（Sorted Set Object）
• 哈希对象（Hash Object）

各种数据类型的逻辑结构如下所示：

1.2 数据类型对应的底层数据结构

Redis底层提供了如下六种数据结构：

• 简单动态字符串
• 双向链表
• 字典
• 跳跃表
• 整数数组
• 压缩列表

上文介绍的五种数据类型，每种数据类型都可能会有一种或多种底层实现的数据结构，他们之前的对应关系如下：

# 查看某个key的数据类型
> type {key}
# 查看某个key的底层数据结构
> object encoding {key}
# 例如：
127.0.0.1:6379> set hello world
OK
127.0.0.1:6379> type hello
string
127.0.0.1:6379> object encoding hello
"embstr"
127.0.0.1:6379> sadd numbers 1 3 5 7 9
(integer) 5
127.0.0.1:6379> type numbers
set
127.0.0.1:6379> object encoding numbers
"intset"

2、Redis底层数据结构

2.1 简单动态字符串

Redis没有直接使用C语言传统的字符串表示（以空字符结尾的字符数组，以下简称C字符串），而是自己构建了一种名为简单动态字符串（Simple Dynamic String，SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。

举个例子，当我们在客户端执行如下命令：

redis> SET msg "hello world"
OK

那么Redi将在数据库中创建两个SDS，一个用于保存字符串"msg"，一个用于保存字符串"hello world"。

2.1.1 SDS定义

struct sdshdr {

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

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

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

没有任何未使用空间的 SDS 示例：

带有五字节未使用空间的 SDS 示例：

SDS遵循C字符串以空字符串结尾的惯例，'\0'占用1字节的存储空间，但是不计算在len属性里。

SDS遵循遵循这一惯例的好处时可以复用一部分C字符串函数库里面的函数。

例如：printf("%s", s->buf);

2.1.2 SDS与C字符串的比较

相对于C字符串，SDS具有如下优点：

1. 获取字符串长度的复杂度为O(1)； 直接基于len属性获取；
2. 杜绝缓冲区溢出；——误操作导致的缓冲区溢出 例如：如果在执行strcat(s1, "Cluster")之前，没有对s1进行扩容，则字符串拼接后，s1会发生溢出，使用s2的内存空间。

3. 减少修改字符串时带来的内存重分配次数；【字符串扩容策略】 C字符串在修改时，都会先重新申请一个修改后长度+1的字符数组。 空间预分配：优化字符串增长操作导致的多次内存重分配。 惰性空间释放：优化字符串缩短操作，即缩短时，不回收空间。但是SDS提供了相应的API，可释放多余的空间。
4. 二进制安全 可以保存空字符'\0'，因为SDS的len属性记录了字符串的长度，它不是基于'\0'来判断字符串结尾 SDS可以保存任意格式的二进制数据

因此，Redis作为数据库，从性能和存储方面考虑，使用SDS来存储字符串。

2.2 双向链表

双向链表是列表键的底层实现之一。

双向链表中每个节点的定义如下：

typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;
} listNode;

双向链表的结构定义如下：

typedef struct list {

    // 表头节点
    listNode *head;

    // 表尾节点
    listNode *tail;

    // 链表所包含的节点数量
    unsigned long len;

    // 节点值复制函数
    void *(*dup)(void *ptr);

    // 节点值释放函数
    void (*free)(void *ptr);

    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

图 3-2 是由一个 list 结构和三个 listNode 结构组成的链表：

Redis 的双向链表实现的特性可以总结如下：

• 双端： 链表节点带有 prev 和 next 指针， 获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。

• 无环： 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ， 对链表的访问以 NULL 为终点。

• 带表头指针和表尾指针： 通过 list 结构的 head 指针和 tail 指针， 程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。

• 带链表长度计数器： 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 O(1) 。

• 多态： 链表节点使用 void* 指针来保存节点值， 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值。

2.3 字典

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。

在字典中，一个键（key）可以和一个值（value）进行关联（或者说将键映射为值），这些关联的键和值就称为键值对。

字典是哈希键的底层实现之一。

2.3.1 字典的结构定义

字典是基于哈希表实现的，下面先看下哈希表的结构定义：

// 哈希表的结构
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

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

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

// 哈希表节点的结构
typedef struct dictEntry {
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

• key属性保存着键值对中的键，而v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。
• next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision） 的问题。【即链地址法解决hash冲突】

下图为一个存放了2对键值对的哈希表。

Redis并没有直接使用哈希表来表示哈希键的值，而是基于哈希表定义了一个字典的数据结构。

接下来，我们来看下字典的结构定义：

typedef struct dict {
    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的：

• type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。

• 而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。

typedef struct dictType {

    // 计算哈希值的函数
    unsigned int (*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;

ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表， 一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ：它记录了 rehash 目前的进度，如果目前没有在进行 rehash ，那么它的值为 -1 。

图 4-3 展示了一个普通状态下（没有进行 rehash）的字典：

2.3.2 rehash

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展和收缩哈希表的工作可以通过执行 rehash（重新散列）操作来完成，Redis 对字典的哈希表执行rehash 的步骤如下：

1. 为字典的 ht[1] 哈希表分配空间， 这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量（也即是 ht[0].used 属性的值）：

• 如果执行的是扩展操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n （2 的 n 次方幂）；

• 如果执行的是收缩操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n 。

2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上。
3. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表），释放 ht[0] ，将 ht[1] 设置为 ht[0] ，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。

举个例子，假设程序要对图 4-8 所示字典的 ht[0] 进行扩展操作，那么程序将执行以下步骤：

1. ht[0].used 当前的值为 4 ， 4 * 2 = 8 ，而 8（2^3）恰好是第一个大于等于 4 的 2 的 n 次方， 所以程序会将 ht[1] 哈希表的大小设置为 8 。 图 4-9 展示了 ht[1] 在分配空间之后，字典的样子。
2. 将 ht[0] 包含的四个键值对都 rehash 到 ht[1] ，如图 4-10 所示。
3. 释放 ht[0] ，并将 ht[1] 设置为 ht[0] ，然后为 ht[1] 分配一个空白哈希表，如图 4-11 所示。

至此，对哈希表的扩展操作执行完毕，程序成功将哈希表的大小从原来的 4 改为了现在的 8 。

2.3.3 渐进式rehash

rehash 动作并不是一次性、集中式地完成的， 而是分多次、渐进式地完成的。

这样做的原因在于，如果 ht[0] 里只保存着四个键值对，那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht[1] ； 但是，如果哈希表里保存的键值对数量不是四个，而是四百万、四千万甚至四亿个键值对，那么要一次性将这些键值对全部 rehash 到 ht[1] 的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

因此，为了避免 rehash 对服务器性能造成影响，服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1] ，而是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到 ht[1] 。

以下是哈希表渐进式 rehash 的详细步骤：

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

渐进式 rehash 的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。

这里需要说明一下，对于渐进式rehash，redis在实现上，可能会有差异，比如：rehashidx不一定每次增1，可能每次会处理多个桶。

图 4-12 至图 4-17 展示了一次完整的渐进式 rehash 过程，注意观察在整个 rehash 过程中，字典的rehashidx 属性是如何变化的。

渐进式 rehash 执行期间的哈希表操作：

• 字段的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。比如说：查找操作，程序会先在 ht[0] 里面进行查找，如果没找到的话，就会继续到 ht[1] 里面进行查找，诸如此类。
• 添加（add）操作：新添加到字典的键值对一律会被保存到 ht[1] 里面。

2.4 跳跃表

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

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

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

Redis 使用跳跃表作为有序集合键的底层实现之一：如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis 就会使用跳跃表来作为有序集合键的底层实现。

2.4.1 跳跃表的实现

Redis 的跳跃表由 zskiplistNode 和 zskiplist 两个结构定义。

• zskiplistNode 结构用于表示跳跃表节点，
• zskiplist 结构则用于保存跳跃表节点的相关信息， 比如节点的数量， 以及指向表头节点和表尾节点的指针，等等。

图 5-1 展示了一个跳跃表示例，位于图片最左边的是 zskiplist 结构，该结构包含以下属性：

• header ：指向跳跃表的表头节点。

• tail ：指向跳跃表的表尾节点。

• level ：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。

• length ：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

位于 zskiplist 结构右方的是四个 zskiplistNode 结构，该结构包含以下属性：

• 层（level）：节点中用 L1 、 L2 、 L3 等字样标记节点的各个层，L1 代表第一层，L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。

• 后退（backward）指针：节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。

• 分值（score）：各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。

• 成员对象（obj）：各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象。

注意表头节点和其他节点的构造是一样的： 表头节点也有后退指针、分值和成员对象， 不过表头节点的这些属性都不会被用到，所以图中省略了这些部分，只显示了表头节点的各个层。

zskiplistNode的结构定义如下：

typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];
} zskiplistNode;

zskiplist的结构定义如下：

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;
} zskiplist;

根据上面的数据结构，如何查找某个member的score？

答：其实对于有序集合键，它的值还会使用字典数据结构存放member->score的映射关系。

2.5 整数数组

整数数组，也叫整数集合（intset）。是集合键的底层实现之一。

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

redis> SADD numbers 1 3 5 7 9
(integer) 5
redis> OBJECT ENCODING numbers
"intset"

2.5.1 整数集合的实现

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

typedef struct intset {
    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];
} intset;

各字段的详细说明：

下面列出了两个整数集合的示例：

contents数组的长度（按字节）：length * 2 = 5 * 2 = 10

contents数组的长度（按位）：length * 16 = 5 * 16 = 80

contents数组的长度（按字节）：length * 8 = 4 * 8 = 32

contents数组的长度（按位）：length * 64 = 4 * 64 = 256

2.5.2 升级

每当我们要将一个新元素添加到整数集合里面， 并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。

升级整数集合并添加新元素共分为三步进行：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
3. 将新元素添加到底层数组里面。

升级之后新元素的摆放位置

因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大，所以这个新元素的值要么就大于所有现有元素，要么就小于所有现有元素（负数）：

• 新元素小于所有现有元素的情况，新元素会被放置在底层数组的开头（索引 0 ）

• 新元素大于所有现有元素的情况，新元素会被放置在底层数组的末尾（索引 length-1 ）

升级的好处：

• 提升灵活性； 使得整数集合可以同时存储int16_t、int32_t、int64_t类型，而使用者不用关注这个细节；【C语言是静态类型语言（变量都需要指定类型）】
• 节约内存； 只有在需要的时候才升级；

2.6 压缩列表

压缩列表（ziplist）是列表键、有序集合键和哈希键的底层实现之一。

当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串， 那么 Redis 就会使用压缩列表来做列表键的底层实现。

redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6
redis> OBJECT ENCODING lst
"ziplist"

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

redis> HMSET profile "name" "Jack" "age" 28 "job" "Programmer"
OK
redis> OBJECT ENCODING profile
"ziplist"

2.6.1 压缩列表的构成

压缩列表是 Redis 为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型数据结构。

一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

下表列出了各个组成部分的详细说明：

图 7-2 展示了一个压缩列表示例：

• 列表 zlbytes 属性的值为 0x50（十进制 80），表示压缩列表的总长为 80 字节。

• 列表 zltail 属性的值为 0x3c（十进制 60），这表示如果我们有一个指向压缩列表起始地址的指针 p ，那么只要用指针 p 加上偏移量 60 ，就可以计算出表尾节点 entry3 的地址。

• 列表 zllen 属性的值为 0x3（十进制 3），表示压缩列表包含三个节点。

2.6.2 Entry节点的构成

每个压缩列表节点都由previous_entry_length、encoding、content三个部分组成。

2.6.2.1 previous_entry_length

节点的 previous_entry_length 属性以字节为单位，记录了压缩列表中前一个节点的长度。

previous_entry_length 属性的长度可以是 1 字节或者 5 字节：

• 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性的长度为 1 字节： 前一节点的长度就保存在这一个字节里面。

• 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性的长度为 5 字节：其中属性的第一字节会被设置为 0xFE （十进制值 254），而之后的四个字节则用于保存前一节点的长度。

下面列出了两种长度的示例：

因为节点的 previous_entry_length 属性记录了前一个节点的长度，所以程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。

压缩列表的从表尾向表头遍历操作就是使用这一原理实现的。

2.6.2.2 encoding

节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度。

encoding占用的字节长度可能为1字节、2字节、5字节。

如果content存放的是字节数组，则encoding的取值规则如下：

除去最高两位，剩余的位数记录了字节数组的长度。

如果content存放的是整数，则encoding的取值规则如下：

2.6.2.3 content

节点的 content 属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。

下面列出了两个示例：