Redis - 底层数据结构

2023-04-12 08:35 由程序员翔仔发表于 #数据库

简介

Redis 的底层数据结构主要以下几种：

SDS(Simple Dynamic String, 简单动态字符串)
ZipList(压缩列表)
QuickList(快表)
Dict(字典)
IntSet(整数集合)
ZSkipList(跳跃表)

简单动态字符串

在 Redis 中，并不会直接使用 C 语言自带的字符串结构作为实际的存储结构，而只是将字符串作为字面量使用，大多数情况使用自定义的 SDS 来表示字符串。

SDS 主要用于储存 Redis 的默认字符串表示、AOF 模块中的 AOF 缓冲区、客户端状态输入缓冲区。它的定义如下：

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

优点

相对于 C 语言的字符串实现，Redis 实现的 SDS 有以下优点：

通过记录 len 属性，实现常数级时间复杂度获取字符串长度
通过检查 len 属性，避免字符串在修改时出现缓冲区溢出的情况
通过记录 len 属性和 alloc 属性，对于修改字符串实现了空间预分配和惰性空间释放
实际存储的 buf 是一个字节数组，可以实现 SDS 安全操作二进制数据
SDS 仍然以 \0 作为字符串结尾的标识，这样可以重用 C 语言字符串的部分函数

空间预分配

当 SDS 修改时需要扩展空间大小，程序不仅会为 SDS 扩展修改所需的空间，还会为 SDS 分配额外的未使用空间。这额外空间一般是 len 的大小，最大不超过 1MB。

这样可以减少连续执行字符串增长操作所需的内存重分配次数。

惰性空间释放

当 SDS 修改时需要缩短空间大小，程序并不会立即将多出来的空间进行空间重分配，而是使用 alloc 属性将这些空间大小记录下来，以待后续使用。

而且 SDS 也提供手动释放未使用空间的方法，这样可以避免浪费内存。

压缩列表

ZipList 实际是由一系列特殊编码的连续内存块组成的顺序型数据结构，是 Hash 类型底层实现的一种方式。

结构

一个 ZipList 结构由 zlbytes、zltail、zllen、entries、zlend 这些属性组成，这些属性顺序连接在一起组成了 ZipList：

zlbytes 用于记录 ZipList 占用的内存字节数，在对 ZipList 进行内存重分配或者计算 zlend 的位置时使用。

zltail 记录了 ZipList 表尾结点距离 ZipList 的起始地址有多少个字节，Redis 可以通过这个属性快速确定表尾结点的地址。

zllen 记录了 ZipList 包含的结点数量，当这个属性小于 UINT16_MAX(65535) 时，这个值就是 ZipList 包含的结点数量；这个属性大于 UINT16_MAX 时，则需要遍历整个 ZipList 才能计算得出结点数量。一个 ZipList 可以包含任意多个结点，每个结点可以保存一个字节数组或者一个整数值。

zlend 定义了特殊值 OxFF 用于标记 ZipList 的末端。

优点

ZipList 是一种节省内存的列表结构，对于普通的数组来说，其中每个元素占用的空间大小取决于最大的元素，而 ZipList 解决了这个问题。

因此，ZipList 在设计的时候，尽量让每个元素按照实际的内容大小存储，所以增加了 encoding 属性，使得程序可以根据不同的 encoding 属性来细化存储大小。

由于数组每个元素都占用相同的内存空间，在遍历数组时非常方便。

而 ZipList 每个元素存储的内存空间不一样，为了解决倒序遍历的问题，增加了 prevlen 属性来定位上一个元素的起始位置。

缺点

ZipList 内部的数据存储是一段连续的空间，并且没有预留内存空间，在移除结点时也是立即缩容，这表示每次写操作都会进行内存分配操作。

第二个缺点就是，在某种情况下，ZipList 会出现连锁更新的问题。

连锁更新

ZipList 存储了 prevlen 属性表示前一个元素的长度，如果前一个元素长度小于 254 个字节，则 prevlen 使用 1 个字节保存这个长度值，如果前一个结点大于 254 个字节，则 prevlen 使用 5 个字节保存这个长度值。

如果 ZipList 中正好存在连续多个长度介于 250~253 个字节的结点，这时需要在 ZipList 前面插入一个大于等于 254 个字节的新结点，后一个结点的 prevlen 需要从 1 个字节转换成 5 个字节，则后一个结点也会大于等于 254 个字节，后续的结点以此类推，将会造成这部分结点出现连续更新。

快表

Redis 在 3.2 版本之后新增了快表数据结构，它是一种以 ZipList 为结点的双端链表结构，可以理解成分段的 ZipList 链接在一起。

在 3.2 版本之前，Redis 使用 ZipList 或 LinkedList 来实现 List 类型，并且有一个选择的标准：

保存的所有字符串元素的长度都小于 64 字节，且保存的元素数量小于 512 个，选择使用 ZipList
否则使用 LinkedList 数据结构替代 ZipList

ZipList 要求有一段连续的内存空间，而使用 LinkedList 分配内存又会出现大量的内存碎片，因此 QuickList 对此做了优化，既避免出现大量的内存碎片，又避免一次性占用内存过大。

字典

字典在 Redis 中的应用非常广泛，比如 Redis 的数据库就是使用字典来作为底层实现的，对数据库的增、删、改、查操作都是构建在对字典的操作之上的。

哈希表结点

字典存储数据的最小结构就是哈希表结点，Redis 中的哈希表结点使用 dictEntry 结构表示，每个 dictEntry 都保存着一个键值对：

typedef struct dictEntry {
    void *key;                  // 键值对的键
    union {                     // 键值对的值
        void *val;              // 可以是一个指针
        uint64_t u64;           // 可以是一个 uint64_t 整数
        int64_t s64;            // 可以是一个 int64_t 整数
    } v;

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

这里值得注意的就是，next 指针会指向下一个哈希表结点，而它的功能就是用于解决哈希冲突，由此可见 Redis 的哈希表解决哈希冲突的方法是链地址法。

哈希表

哈希表是由多个哈希表结点组成的，Redis 中自定义的哈希表结构如下：

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

一般的，哈希表的物理存储结构都是数组，Redis 的哈希表结构也是如此，而这个结点数组中的每个元素都是一个指向 dictEntry 结构的指针。

字典结构

Redis 为了使哈希表结构更加具有通用性，最后是在自定义的 dictht 哈希表结构外层再包一层字典结构，即是 dict 结构：

typedef struct dict {
    dictType *type;     // 类型特定函数
    void *privdata;     // 私有数据
    dictht ht[2];       // 哈希表
    int rehashidx;      // rehash 索引，当 rehash 不在进行时，值为 -1
} dict;

这里展示了另一个 dictType 的结构，其实这个结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。以下是 dictType 的结构定义：

typedof 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, const void *key);                // 销毁键的函数
    void *(*keyDestructor)(void *privData, const void *obj);                // 销毁值的函数
} dictType;

其实 dict 结构的 type 属性和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。其中 privData 属性保存了需要传给那些类型特定函数的可选参数。

需要注意一下，字典结构的 ht 属性是一个长度为 2 的数组，也就是说，这个字典结构存储了两个 dictType 结构，其中一个用于存储实际使用的哈希表，另一个用于存储重新哈希的临时哈希表。

这个重新哈希还涉及到了 rehashidx 属性，表示的是重新哈希当前的进度。

哈希算法

当要将一个新的键值对添加到字典里面时，程序会先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表结点放到哈希表数组的指定索引上。

Redis 计算哈希值和索引值的流程是：通过 dict 中的 type 属性找到计算哈希值的函数，然后通过函数计算出对应的哈希值；确定对应的 dictht 结构之后，再根据 sizemask 和哈希值计算出索引值。

Redis 使用 MurmurHash2 算法计算键的哈希值，其优点就是对于有规律的输入值也能给出很好的随机分布性，并且算法的计算速度也非常快。

哈希冲突

相同的哈希值会计算出相同的索引值，这就会导致哈希冲突。

Redis 使用了链地址法解决哈希冲突，每一个哈希表结点都有一个 next 指针，多个冲突的哈希表结点就会使用这个 next 指针构成一个单向链表，这就解决了键冲突的问题。

这里需要注意一点，由于哈希表结点不存储链表的尾结点，为了速度考虑，哈希冲突时构建的单向链表使用头插法插入一个链表结点。

重新哈希

随着操作不断执行，哈希表保存的数据会逐渐增多或减少，为了让哈希表的负载因子维持在一个合理的范围内，Redis 会在必要的时候进行重新哈希的操作。

重新哈希指的是重新计算哈希表结点的哈希值和索引值，然后将键值对放到 ht 数组的另一个哈希表中。

Redis 对哈希表进行扩展操作的两个条件如下：

服务器目前没有正在执行 BGSAVE 命令或 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1。
服务器目前正在执行 BGSAVE 命令或 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5。

其中负载因子 = 哈希表已保存结点数量 / 哈希表大小。

另一方面，当哈希表的负载因子小于 0.1 时，Redis 会自动开始对哈希表进行收缩操作。

Redis 做自动扩展的条件包含两种情况的原因是，执行 BGSAVE 和 BGREWRITEAOF 命令的是服务器的子进程，而大多数操作系统都采用写时复制技术以优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子。

渐进式重新哈希

为了避免因为重新哈希导致停止服务的情况，Redis 做重新哈希不是一次性完成的，而是分多次、渐进式地完成的。这也是 dict 结构中存在 ht 数组的原因。

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

整数集合

整数集合被 Redis 用于保存整数值的不重复集合，以下是整数集合的实现：

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

其中 contents 数组中存储的是整数集合中的元素，各个项按照从小到大进行排列，且数组中不包含任何重复值。

length 属性记录了整数集合包含的元素个数，也相当于 contents 的数组长度。

encoding 记录着整数集合的编码方式，虽然 contents 的定义是 int8_t 类型，但实际上 contents 数组存储元素的真正类型取决于 encoding 的值。

升级

整数集合的 contents 属性可以存储 int16、int32 或 int64 三种类型之一的数值，如果原本只存储了 int16 类型的 contents 数组插入一个 int32 类型的数值，这时就涉及到整数集合的升级操作。

每当要将一个整数插入到整机集合中时，Redis 都会先判断新元素的类型是否会比已存在的元素类型长，如果存在这种情况，整数集合需要先进行升级，才能将新元素添加到整数集合里面。具体的步骤如下：

根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间；
将现有元素都转换成与新元素的类型相同，并将转换类型后的数值放置到正确的位上，并保持原数组的顺序不变；
最后改变 encoding 的值，并将 length 加 1。

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

升级的好处

整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约内存。

因为 C 语言是静态类型语言，不同类型的整数值需要用不同的数组存储，而整数集合通过升级策略将有原本不同类型的整数添加到同一个数组中，减少了类型错误的情况。

同样的，整数集合通过使用一个数组存储了三种不同类型的整数，又确保升级操作只会在有需要的时候进行，这可以尽量节省内存。

跳表

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

Redis 的跳表包括了两个结构，一个是跳表结点的结构，另一个是存储跳表结点的外部结构。

跳表结点

以下是跳表结点的结构定义：

typedef struct zskiplistNode {
    struct zskiplistLevel {             // 索引层
        struct zskiplistNode *forward;  // 前进指针
        unsigned int span;              // 跨度
    } level[];
    robj *obj;                          // 成员对象
    double score;                       // 分值
    struct zskiplistNode *backward;     // 后退指针
} zskiplistNode;

这里只是一个跳表结点的结构，概念比较多。

跳表的 zskiplistLevel 是一个数组，数组的长度表示结点有多少层索引，其中每个元素都包含一个指向其他结点的指针，程序可以通过这些指针加快访问其他结点的速度。每次创建一个新的跳表结点的时候，程序都会根据幂次定律随机生成一个介于 1 和 32 之间的值作为数组的大小。

forward 是指每个索引层都包含指向下一个具有相同高度索引层的结点。也可以将前进指针理解成链表的 next 指针，从相同层级的角度上看，每一个相同层级的结点都组成了类似于链表的结构。

span 记录了两个结点之间的距离，实际上是用来计算排位的：在查找某个结点的过程中，将沿途访问过的所有层的跨度累积起来，得到的结果就是目标结点在跳跃表的排位。

backward 用于从表尾向表头访问结点，对于最底层的链表来说，前进指针和后退指针使得这个链表成为一个双向链表。

结点的 score 即是 Redis 的有序集合中的分值。结点的成员是一个指向 SDS 对象的指针，这个 SDS 对象存储当前结点的值。对于相同分值的成员，Redis 会按照成员对象在字典序中的大小来进行排序，成员对象较小的结点会排在前面，而成员对象较大的结点会排在后面。

跳表

仅使用多个跳表结点就可以实现跳表，但是新增外部跳表结构可以使得程序更方便处理跳表。Redis 的跳表结构如下：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;    // 头节点，尾节点
    unsigned long length;                   // 节点数量
    int level;                              // 目前表内节点的最大层数
} zskiplist;

其中 head 指针和 tail 指针分别指向跳表的表头和表尾，通过这两个指针，Redis 定位跳表表头结点和表尾结点的时间复杂度为 \(O(1)\)。

通过记录 length 属性，Redis 可以在 \(O(1)\) 的时间复杂度内返回跳表的长度。

跳表使用 level 属性记录了表内结点的最大层数，但这个是不包含表头结点的层高的。