深入解析Redis的数据结构与对象系统

Redis 是一个高性能的开源键值存储系统，支持多种数据结构。本文将详细介绍 Redis 中的六种底层数据结构及其在对象系统中的应用，包括字符串对象、列表对象、哈希对象、集合对象和有序集合对象。通过12张图解，帮助读者全面理解 Redis 的数据结构和对象系统。

本文内容如下：

• 首先介绍六种基础数据结构：动态字符串、链表、字典、跳跃表、整数集合和压缩列表。
• 其次介绍 Redis 的对象系统中的字符串对象（String）、列表对象（List）、哈希对象（Hash）、集合对象（Set）和有序集合对象（ZSet）。
• 最后介绍 Redis 的键空间和过期键（expire）实现。

数据结构

简单动态字符串

Redis 使用动态字符串 SDS 来表示字符串值。下图展示了一个值为 Redis 的 SDS 结构：

• len: 表示字符串的实际长度（不包含 NULL 结束符）。
• alloc: 表示字符串的最大容量（不包含最后一个字节）。
• flags: 占用一个字节，其中最低3位表示 header 的类型。
• buf: 字符数组。

SDS 结构可以减少修改字符串时的内存重分配次数，主要依赖于内存预分配和惰性空间释放机制。当 SDS 需要扩展时，Redis 会分配额外的未使用空间：

• 如果修改后的 SDS 长度小于 1MB，预分配与 len 相同大小的未使用空间。
• 如果修改后的 SDS 长度大于 1MB，预分配 1MB 的未使用空间。

当 SDS 缩短其保存的字符串长度时，并不会立即释放多出来的字节，而是保留以供后续使用。

链表

链表在 Redis 中应用广泛，例如列表对象的底层实现之一就是链表。此外，发布和订阅、慢查询、监视器等功能也使用了链表。Redis 的链表是双向链表，如下图所示：

链表结构的 dup、free 和 match 成员属性用于实现多态链表所需的类型特定函数：

• dup 函数用于复制链表节点所保存的值，实现深度拷贝。
• free 函数用于释放链表节点所保存的值。
• match 函数用于对比链表节点所保存的值和另一个输入值是否相等。

字典

字典广泛用于实现 Redis 的各种功能，包括键空间和哈希对象。Redis 使用 MurmurHash2 算法计算键的哈希值，并使用链地址法解决键冲突。被分配到同一个索引的多个键值对会连接成一个单向链表，如下图所示：

跳跃表

Redis 使用跳跃表作为有序集合对象的底层实现之一。跳跃表以有序的方式在层次化的链表中保存元素，效率与平衡树相当，但实现更为简单直观。查找、删除、添加等操作都可以在对数期望时间内完成。如下图所示：

跳表的节点 zskiplistNode 包含元素值 ele 和分值 score，节点按 score 值有序排列。每个节点的 level 数组大小不同，level 数组中的值是指向下一个节点的指针和跨度值（span）。越高层的 level 数组值的跨度值越大，底层的 level 数组值的跨度值越小。level 数组类似于不同刻度的尺子，度量长度时先用大刻度估计范围，再用小刻度进行精确逼近。

整数集合

整数集合 intset 是集合对象的底层实现之一，当集合只包含整数值元素且元素数量不多时，Redis 使用整数集合作为集合对象的底层实现。整数集合的 encoding 表示其类型，可以是 int16_t、int32_t 或 int64_t。每个元素都是 contents 数组的一个数组项，按值的大小从小到大有序排列，数组中不包含重复项。length 属性表示整数集合包含的元素数量，如下图所示：

压缩列表

压缩列表 ziplist 是列表对象和哈希对象的底层实现之一。当满足一定条件时，列表对象和哈希对象会以压缩列表为底层实现。压缩列表是 Redis 为了节省内存而开发的顺序型数据结构，由一系列特殊编码的连续内存块组成。其属性值包括：

• zlbytes: 记录整个压缩数组的内存字节数。
• zltail: 记录压缩列表表尾节点距离压缩列表起始地址的字节数。
• zllen: 包含的节点数，当属性值小于 INT16_MAX 时，该值就是节点总数，否则需要遍历整个列表才能确定总数。
• zlend: 特殊值，用于标记压缩列表的末端。

每个节点 entry 由三部分组成：

• previous_entry_length: 前一个节点的长度，用于计算前一个节点的起始地址。
• encoding: 节点保存数据的类型和长度。
• content: 节点值，可以是一个字节数组或整数。

对象系统

Redis 并没有直接使用上述六种底层数据结构实现键值数据库，而是基于这些数据结构创建了一个对象系统，包括字符串对象、列表对象、哈希对象、集合对象和有序集合对象。每个对象都使用至少一种底层数据结构，根据不同的使用场景和内容大小选择合适的数据结构，以优化对象在不同场景下的使用效率和内存占用。

Redis 的 redisObject 结构定义如下：

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; 
    int refcount;
    void *ptr;
} robj;

其中 type 表示对象类型，包括 REDIS_STRING、REDIS_LIST、REDIS_HASH、REDIS_SET 和 REDIS_ZSET。encoding 表示对象使用的数据结构。

字符串对象

字符串对象的实现如下图所示。如果字符串对象保存的字符串长度大于 32 字节，使用 SDS 保存，编码设置为 raw。如果字符串长度小于 32 字节，使用 embstr 编码方式保存。embstr 编码通过一次内存分配创建两个结构，节省内存并提高缓存利用率，但不可修改。当 embstr 编码的字符串对象进行 append 操作时，Redis 会将其转换为 raw 编码。

列表对象

列表对象的编码可以是 ziplist 或 linkedlist。当列表对象满足以下条件时，使用 ziplist 编码：

• 所有字符串元素的长度都小于 64 字节。
• 元素数量小于 512 个。

否则使用 linkedlist 编码。

哈希对象

哈希对象的编码可以是 ziplist 或 dict。当哈希对象满足以下条件时，使用 ziplist 编码：

• 所有键值对的键和值的字符串长度都小于 64 字节。
• 键值对数量小于 512 个。

否则使用 dict 编码。

集合对象

集合对象的编码可以是 intset 或 dict。当集合对象满足以下条件时，使用 intset 编码：

• 所有元素都是整数值。
• 元素数量不超过 512 个。

否则使用 dict 编码。

有序集合对象

有序集合的编码可以是 ziplist 或 skiplist。当有序集合对象满足以下条件时，使用 ziplist 编码：

• 元素数量少于 128 个。
• 所有元素的长度都小于 64 字节。

否则使用 skiplist 编码。

数据库键空间

Redis 服务器有多个数据库，每个数据库有自己的键值空间。每个数据库使用 dict 保存所有键值对。键空间的键是字符串对象，值对象可以是字符串对象、列表对象、哈希表对象、集合对象或有序集合对象中的一种。Redis 也使用 dict 结构保存键的过期时间，键是键空间中的键值，值是过期时间。通过过期字典，Redis 可以直接判断一个键是否过期。