前言

我们都知道，redis最基本的数据结构有5种，分别是字符串、列表、哈希表、集合和有序集合。其实准确来说，这种表述容易造成误会，给人误解。从redis的源码来看，这5种其实是redis封装的对象，而底层对象的实现才应该成为数据结构。redis最基础的数据结构包括以下几种：简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表。而redis对象(也就是一开始提到的5种)其实底层都是基于这些数据结构的，这样的好处是，同一种对象根据实际场景的不同底层可以使用不同的数据机构来优化使用效率。redis的对象还基于引用计数实现了内存回收机制和对象共享机制，这里就不展开了。本文参考《Redis 设计与实现》主要介绍一下redis的6种底层数据结构。

简单动态字符串

定义

Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串）， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示。
如果 Redis 需要一个可以改变的字符串对象的时候，底层就会使用 SDS 来实现，SDS 结构的源码实现如下：

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

buf作为字节数组，底层保留了C语言以空字符('\0')结尾的特性以便重用部分C的函数，空字符不计算长度。

与C语言字符串的区别

Redis 不直接使用 C 的字符串肯定是因为有自己的考虑，就是因为 SDS 这种实现相比原生的 C 字符串有很多优点。

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

由 SDS 的源码可以看到，获取长度直接返回len即可，而 C 的字符串需要遍历，时间复杂度为O(N)。

• 杜绝缓冲区溢出

C 语言进行字符串拼接时需要人工考虑内存的分配，否则可能导致内存溢出从而覆盖已有的数据。而 SDS 在拼接时直接查询 free 字段即可知道空间是否足够，不够会自动进行扩展。

• 减少修改字符串时带来的内存重分配次数

C 字符串以空字符结尾，长度固定为 (有效字符数 + 1)，每次进行字符串拼接或者截断操作都需要进行内存重分配，否则会造成内存溢出和内存泄露。SDS 通过空间预分配和惰性空间释放来解决这个问题，free 字段记录了有效字符空间与实际数组空间的差值，SDS 扩展时会分配额外空间，这称为空间预分配；SDS 缩短时不会立即进行空间释放(除非手动调用API进行空间释放)，会用free字段记录释放的空间，这称为惰性空间释放。

• 二进制安全

C 的字符串不能保存含有空字符的数据，因为空字符是用来判断字符串结尾的，所以不能用于保存二进制数据。SDS 用len判断字符串长度可以保存任意二进制数据。

• SDS 可以兼容部分 C 字符串函数

因为buf作为字符数组也是用空字符结尾的，所以部分 C 语言的函数是可以直接使用的

链表

实现

Redis 实现的链表是一个双向链表，每个节点有特定实现的数据结构，而整个链表的表示则使用了另一个代表整体的结构，源码如下：

/*
 * 双端链表节点
 */
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} 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;

链表的特性：

1. 双端
2. 无环
3. 带表头指针和表尾指针
4. 带链表长度计数器
5. 多态，可以保存不同的值

Redis 用链表来实现列表建、发布与订阅、慢查询、监视器等功能。

字典

Redis 数据库以及哈希键的底层实现用的都是字典。

实现

哈希表

/*
 * 哈希表
 *
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
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;

next指针用于解决哈希冲突，跟Java中的HashMap实现是相同的。

字典

/*
 * 字典
 */
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

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

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;

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

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

image

哈希算法

当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。

解决键冲突

链地址法解决哈希冲突，类似于java中的HashMap。dictEntry组成的链表是一个单向链表，没有指向表尾的指针，多以后加入的节点如果产生了哈希冲突则会放到链表的表头。

rehash

所有的哈希表随着键值对的增多和减少都需要进行扩展或者收缩操作，不然就会造成哈希冲突过多或者内存浪费。Redis 的哈希表重新散列的步骤如下：

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 做准备。

rehash的触发条件：

1. 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1 ；
2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5 ；
3. 当哈希表的负载因子小于 0.1 时， 程序自动开始对哈希表执行收缩操作。

# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

渐进式rehash

主要防止哈希表过大导致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期间，查询会先插ht[0]再查ht[1]，增加则只会增加到ht[1]。

跳跃表

Redis在有序集合的实现以及集群节点内部数据机构用到了跳跃表。

实现

image

/*
 * 跳跃表节点
 */
typedef struct zskiplistNode {

    // 成员对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

/*
 * 跳跃表
 */
typedef struct zskiplist {

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

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

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

} zskiplist;

• 每个跳跃表节点的层高都是 1 至 32 之间的随机数。
• 在同一个跳跃表中， 多个节点可以包含相同的分值， 但每个节点的成员对象必须是唯一的。
• 跳跃表中的节点按照分值大小进行排序， 当分值相同时， 节点按照成员对象的大小进行排序。

整数集合

整数集合是 Redis 集合键的底层实现之一。

实现

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

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

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

} intset;

虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组， 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值：

1. 如果 encoding 属性的值为 INTSET_ENC_INT16 ， 那么 contents 就是一个 int16_t 类型的数组， 数组里的每个项都是一个 int16_t 类型的整数值 （最小值为 -32,768 ，最大值为 32,767 ）。
2. 如果 encoding 属性的值为 INTSET_ENC_INT32 ， 那么 contents 就是一个 int32_t 类型的数组， 数组里的每个项都是一个 int32_t 类型的整数值 （最小值为 -2,147,483,648 ，最大值为 2,147,483,647 ）。
3. 如果 encoding 属性的值为 INTSET_ENC_INT64 ， 那么 contents 就是一个 int64_t 类型的数组， 数组里的每个项都是一个 int64_t 类型的整数值 （最小值为 -9,223,372,036,854,775,808 ，最大值为 9,223,372,036,854,775,807 ）。

升级

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

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

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

整数集合的升级操作提升了灵活性，节约了内存，并且整数集合不支持降级操作。

压缩列表

压缩列表是列表键和哈希键的底层实现之一，主要目的就是为了节约内存。

构成

压缩列表是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。具体组成部分和说明如下：

压缩列表节点构成

每个压缩列表节点可以保存一个字节数组或者一个整数值， 其中， 字节数组可以是以下三种长度的其中一种：

• 长度小于等于 63 （2^{6}-1）字节的字节数组；
• 长度小于等于 16383 （2^{14}-1） 字节的字节数组；
• 长度小于等于 4294967295 （2^{32}-1）字节的字节数组；

而整数值则可以是以下六种长度的其中一种：

• 4 位长，介于 0 至 12 之间的无符号整数；
• 1 字节长的有符号整数；
• 3 字节长的有符号整数；
• int16_t 类型整数；
• int32_t 类型整数；
• int64_t 类型整数。

previous_entry_length

以字节为单位， 压缩列表中前一个节点的长度。

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

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

previous_entry_length可以用于压缩列表从尾部到头部的遍历。

encoding

值的最高位为 00 、 01 或者 10 的是字节数组编码，值的最高位以 11 开头的是整数编码。

content

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

连锁更新

previous_entry_length占用的空间是1字节或者5字节，取决于上一节点的长度，如果压缩列表中连续多个节点处于临界值，而此时改变某个节点的长度，就有可能触发连锁更新，最坏的时间复杂度到达O(N)。
因为出现条件比较苛刻，出现几率比较小，所以Redis没有避免这种情况，我们也可以大胆使用。