Redis 中的数据结构

Redis 内置了多种数据结构，这些数据结构用于构建我们使用的数据对象，同时它们也在 Redis 内部使用。本文介绍简要介绍这些数据结构的实现原理。

字符串

C 字符串是不可修改的，而且获取字符串长度需要遍历整个字符串，只能用于一些简单的场景，如打印日志。Redis 使用简单的动态字符串 (simple dynamic string，SDS) 作为默认字符串的数据结构。一个 SDS 的结构如下：

struct sdshdr {
    // buf 数组中已使用的字节数
    int len;
    // buf 数组中空闲的字节数
    int free;
    // 保存字符串值的数组
    char buf[];
}

buf 以字节进行存储，因此除了存储文本数据外，还可以用于存储图像等二进制数据。为了兼容 C 中的字符串 API，buf 遵循了以 \0 结尾。每次修改 buf 数组时都会记录最新的 len 属性，因此能以 O(1) 复杂度获取字符串长度，而不用遍历整个字符串。

SDS 的动态性体现在 buf 的动态伸缩上。在进行字符串增长操作时，预留的 free 字节数可能不够用，要重新进行内存分配，并且分配的空间不是刚好够用就行，而要比实际需要的大。在进行字符串缩短操作时，不会真正进行内存空间释放，而只更改 len 和 free 进行记录。buf 数组的这种伸缩策略，可以避免频繁内存分配造成的开销，提升修改字符串长度操作的性能。

用途：

保存数据库的字符串值，可能是键或者值
用作内部的缓冲区，如 AOF 持久化缓冲区，客户端输入缓冲区

链表

链表（list）是一种基本的数据结构，它的每个节点存储了相邻节点的链接，因此可以进行高效的节点增删操作。据不同的实现，链表可能是单向的、双向的或者环形的等。Redis 中链表节点、链表的结构如下：

typedef struct listNode {
    // 前置节点
    struct listNode * prev;
    // 后置节点
    struct listNode * next;
    // 节点的值
    void * value;
} listNode;

用途：

实现列表对象
用于发布与订阅、慢查询、监视器等功能
保存客户端状态信息，客户端输出缓冲区

字典

字典（dict）又称为映射，通常的实现方式是使用树或散列表（哈希表）。这两种实现方式也是数据库索引中常讨论的话题，如时间复杂度、范围查询等方面的比较。Redis 使用散列表来实现字典。

程序设计实现一书中认为，程序员经常重要的数据结构包括：数组、表（链表）、树和散列表，其中散列表是一项伟大的发明，它综合了数组、链表和一些数学方法。数组是指散列表数组，它在字典的结构中定义：

typedef struct dictht {
    // 散列表数组
    dictEntry **table;
    // 散列表大小
    unsigned long size;
    //散列表大小掩码，用于计算索引值
    //总是等于size-1
    unsigned long sizemask;
    // 散列表表已有节点的数量
    unsigned long used;
} dictht;

散列表节点的结构如下。节点中有键、值和 next 指针。

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

节点的位置由键的散裂值决定，散列值通过散列函数计算得到。当不同的键获得了同样的散列值，便发生了散列冲突。为了减少冲突，好的散列函数应尽可能满足随机的特点，而无视输入的规律。Redis 中采用的是 MurmurHash 算法。

然而想要完全避免散列冲突是不能的，在发生冲突时需要予以处理。常见的处理方法有链接法和开址法。链接法中，将同一位置的节点连接成一个链表；开址法中会不断探查散列表，直到找到空槽。两种处理方式的特点如下：

链接法

编写简单
负载因子可大于 1
需要空间存储指针
链表的查询性能不好，但好的散列算法可使每个链表的长度相对均匀

开址法

探查方法多，有线性探查、二次探查和双重散列等
负载因子不会大于 1
删除元素困难，会导致无法查询
探查会出现聚集问题
不用存储指针节约了空间，潜在地降低了冲突

Redis 中采用拉链法来处理散列冲突。链表中新加入的节点位于旧节点的前面，这样可以保证性能，也很容易编写。当负载因子足够大时触发扩展，即 rehash。一次完成 rehash 开销很大，所以这个操作是渐进式的。由于同时存在两个散列表，设计查询、删除和更新的操作在这两张表上进行，新增操作在新表上进行。

用途：

作为 k-v 数据库的底层
实现哈希对象和集合对象

跳跃表

跳跃表（skip list）对链表进行扩展，每个节点维护多个通往后面节点的指针，节点按编号大小有序排列。

跳跃表是一种概率性的数据结构。每一层的元素以一定的概率出现在上一层中，因此顶层的链表最稀疏，底层的链表包含每一个元素。容易理解，查询元素时从顶部开始，向下逐层缩短查询范围，到达底部时再进行少量的顺序查询。

跳跃表

用途：

实现有序集合对象
集群中的内部数据结构

整数集合

整数集合（intset）是用来保存整数的集合，支持多种宽度的整数类型，包括 int16_t, int32_t 和 int64_t。底层实现基于一个数组，在该数组中，整数有序排列且不重复。

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

注意到数组 contents 的类型为 int8_t，多个 int8_t 元素即可构成我们想要的 encoding 编码，如 int16_t 由两个相邻的 int8_t 构成。编码方式由在最大宽度的元素决定，当新插入的元素的宽度大于当前的编码方式时，整数集合会升级编码：将所有元素按照新的编码方式保存。数组的插入操作比较低效，只有在元素数量不太多时才会使用这种数据结构。

保存集合元素的数组具有如下特性：

动态扩展。
多种编码。根据元素大小，自动升级编码，支持多种整数类型。
有序。查找元素时使用二分法。

用途：

实现集合对象

压缩列表

压缩列表（ziplist）是一种连续内存的数据结构，包含任意数量的节点，每个节点存储一个整数或一个字节数组。在前文中，整数集合的每个元素有统一的编码，这使得设计十分简单，但元素数量很多时可能会造成内存的浪费。压缩列表可以节约内存，这也意味着该数据结构的设计会更加复杂。

每个压缩列表节点由三部分组成：

previous_entry_length 前一个节点的长度。视前一个节点长度的大小，该属性可能为 1 字节或多个字节。通过 previous_entry_length 可以反向遍历压缩列表。
encoding 数据类型与长度。标识位记录编码，其余位记录 content 字节长度。可能为 1 字节或多字节长。
content 节点值。类型与长度由 encoding 决定。

previous_entry_length 所占的字节数与前一个节点的长度有关。删除或新增节点可能造成下一个节点的 previous_entry_length 属性的长度发生变化，需要重新对其分配内存，继而可能形成多米诺骨牌效应，随后的多个节点都进行空间扩展，即发生连锁更新。连锁更新性能低下，但发生的条件苛刻：连续多个节点的长度处于即将引发 previous_entry_length 变化的范围内。

用途：

实现列表对象、有序集合地点对象和哈希对象

字符串

链表

字典

跳跃表

整数集合

压缩列表

参考