Skip to content

Redis的底层数据结构有什么

Redis对外暴露了五种基础数据类型：字符串(string)、列表(list)、哈希(hash)、集合(set)和有序集合(zset)。然而，这些只是Redis在逻辑层面的对象类型。为了在性能和空间效率之间取得最佳平衡，Redis会根据具体场景为同一个逻辑对象选择不同的内部编码，也就是底层数据结构来实现。

Redis的核心底层数据结构主要有以下六种：

1. 简单动态字符串 (SDS - Simple Dynamic String)

Redis并没有直接使用C语言传统的以空字符 \0 结尾的字符串，而是构建了名为SDS的抽象类型。这主要是为了解决C字符串的一些固有缺陷。

实现方式：

SDS的结构包含一个头部（header）和一个实际存储数据的字符数组。在Redis 6.0中，为了节省内存，头部设计有多种类型（sdshdr8, sdshdr16, sdshdr32, sdshdr64），根据字符串长度自动选择最小的头部。

一个典型的SDS结构如下：

struct sdshdr {
    // 记录字符串的实际长度
    unsigned int len;
    // 记录字符数组的总容量（不包括头和末尾的\0）
    unsigned int alloc;
    // 存储类型标志
    unsigned char flags;
    // 实际存储字符串的柔性数组
    char buf[];
};

核心优势与实现原理：

  • 常数复杂度获取长度：由于头部直接存储了长度 len，获取字符串长度的时间复杂度为 O(1)，避免了C语言 strlen 需要遍历整个字符串的 O(n) 操作。
  • 杜绝缓冲区溢出：在对SDS进行修改时，API会先检查 alloc 记录的容量是否足够。如果不足，会自动进行扩容，然后再执行修改，从而避免了C语言中 strcat 等函数可能导致的缓冲区溢出问题。
  • 减少内存重分配次数：SDS采用了两种优化策略：
    • 空间预分配：当对SDS进行扩容时，程序不仅会分配所必需的空间，还会分配额外的未使用空间。具体策略是：如果修改后SDS的长度小于1MB，则分配与len相同大小的额外空间；如果超过1MB，则额外分配1MB。这大大减少了连续增长字符串时内存重分配的次数。
    • 惰性空间释放：当缩短SDS字符串时，多出来的空间并不会立即被回收，而是通过更新 len 的值来记录，等待未来使用。
  • 二进制安全：SDS通过 len 属性来判断字符串是否结束，而不是 \0 字符。因此，buf 数组中可以包含任意二进制数据（包括 \0），不会出现数据被截断的问题。
  • 兼容部分C字符串函数：尽管是二进制安全的，SDS依然遵循惯例在字符串末尾追加一个 \0 字符，这使得它可以安全地重用一部分C语言 <string.h> 库中的函数。

2. 压缩列表 (ZipList)

ZipList是一种为了极致地节省内存而设计的特殊编码的双向链表。它可以存储字符串或整数。

实现方式：

ZipList是一块连续的内存空间，其内部结构紧凑。

  • zlbytes (4字节): 记录整个ZipList占用的总字节数。
  • zltail (4字节): 记录到最后一个节点的偏移量，用于快速定位表尾，实现O(1)复杂度的pop操作。
  • zllen (2字节): 记录节点（entry）的数量。当节点数超过65535时，需要遍历才能得到真实数量。
  • entry (不定长): 存储数据节点。
  • zlend (1字节): 特殊的结束标记，值为 0xFF。

Entry结构是ZipList节省内存的关键：

每个Entry由三部分构成：<prevlen><encoding><entry-data>

  • prevlen: 记录前一个节点的长度。为了节省空间，它的长度是可变的：如果前一个节点长度小于254字节，prevlen 就用1个字节表示；否则，它会用5个字节来表示。
  • encoding: 记录了 entry-data 的类型和长度。它的编码方式非常复杂，会根据存储的是整数还是字符串，以及数据的大小，采用不同长度和内容的编码，以求使用最少的空间来表示数据。
  • entry-data: 实际存储的数据，可以是整数或字符串。

核心优势与缺点：

  • 优点：通过可变长度编码，极大地减少了冗余的元数据空间，非常节省内存。
  • 缺点：
    • 每次写入操作（增删）都需要对整块内存进行重分配，性能开销与ziplist长度成正比。
    • 存在连锁更新的风险：如果一个节点的长度发生变化（例如从小于254字节变为大于等于254字节），其prevlen的编码需要从1字节变为5字节。这可能导致后续节点的起始位置改变，从而像多米诺骨牌一样，引发后续所有节点的prevlen都需要更新，这是一个O(N)级别的操作。

3. 快表 (QuickList)

为了平衡 linkedlist (双向链表) 和 ziplist 的优缺点，Redis 3.2 版本之后引入了QuickList作为列表对象的底层实现。

实现方式：

QuickList 本质上是一个双向链表，但它的每个节点（quicklistNode）不再是只存储一个数据，而是内嵌了一个 ziplist。

  • quicklist 结构: 宏观上是一个双向链表，包含头尾指针 (head, tail)、节点总数 (len) 和所有 ziplist 中元素总数 (count) 等信息。
  • quicklistNode 结构: 作为链表节点，它包含指向前后节点的指针 (prev, next)，以及一个指向 ziplist 的指针 (zl)。
  • 可配置的压缩: quicklist 还可以通过配置对 ziplist 进行LZF算法压缩，以进一步节省空间。可以设置链表两端有多少个节点不被压缩，以加快两端数据的访问速度。

核心优势：

QuickList是空间和时间的完美平衡。它将大的列表分割成小的 ziplist，避免了单个 ziplist 过大导致的性能问题，同时也比普通的链表（每个节点都有独立的指针）大大节省了内存。

4. 字典/哈希表 (Dict)

字典是Redis哈希（hash）类型和数据库本身（存储所有键值对）的底层实现。

实现方式：

Redis的字典本质上是一个哈希表，其实现涉及几个关键结构：

  • dictEntry: 存储单个键值对。包含一个指向键的指针 *key，一个存储值的联合体 v，以及一个指向下一个节点的指针 *next。
  • dictht: 这是哈希表的定义，包含一个 dictEntry 指针数组 table，以及 size、sizemask 和 used (已用节点数) 等信息。
  • dict: 顶层结构，包含两个 dictht 哈希表（ht[0] 和 ht[1]）和一个 rehashidx 变量。

核心机制：

  • 解决哈希冲突：采用链地址法。dictEntry 中的 *next 指针会将哈希值相同的多个键值对链接成一个单向链表。
  • 扩容与收缩 (rehash)：当哈希表需要扩容或缩容时，Redis不会一次性完成所有键的迁移。为了避免服务阻塞，它采用了渐进式rehash：
    1. 为字典的 ht[1] 分配一个新的、更大的（或更小的）哈希表空间。
    2. rehashidx 被设置为0，表示rehash开始。
    3. 在每次对字典进行增、删、查、改操作时，除了执行指定的操作外，还会“顺便”将 ht[0] 中 rehashidx 索引位置上的所有键值对迁移到 ht[1] 中，然后 rehashidx 加一。
    4. 这个过程会持续进行，直到 ht[0] 的所有数据都迁移完成，此时 ht[1] 会取代 ht[0]，成为新的主哈希表。

5. 整数集 (IntSet)

整数集是集合（set）类型在特定情况下的底层实现之一。当一个集合只包含整数值元素，并且元素数量不多时，Redis会采用IntSet。

实现方式：

IntSet是一块连续的内存区域，其结构定义如下：

typedef struct intset {
    // 编码方式，决定了contents数组中每个元素的整数类型
    uint32_t encoding;
    // 集合中元素的数量
    uint32_t length;
    // 存储元素的有序数组
    int8_t contents[];
} intset;
  • encoding: 可以是 INTSET_ENC_INT16, INTSET_ENC_INT32, 或 INTSET_ENC_INT64，表示 contents 数组中的每个元素是16位、32位还是64位的整数。
  • contents: 是一个有序的整数数组，不包含重复项。查找操作可以通过二分查找实现。

核心机制：升级（Upgrade）

当向一个IntSet中添加一个新元素，而这个新元素的类型比当前 encoding 所表示的类型要大时（例如，向一个INTSET_ENC_INT16的集合中添加一个32位整数），IntSet会进行升级： 1. 根据新类型扩展底层数组的空间。 2. 将数组中所有现有元素转换为新的、更大的类型。 3. 将新元素添加进去，并保持数组的有序性。 4. 更新 encoding 和 length 属性。

需要注意的是，IntSet只支持升级，不支持降级。即使移除了大类型的整数，encoding 也不会变回去。

6. 跳表 (ZSkipList)

跳表是有序集合（zset）的底层实现之一。它是一种通过增加多级索引来提高查询效率的链表结构。

实现方式：

Redis的跳表实现包含两个主要结构：

  • zskiplistNode: 跳表节点。
    • ele: 存储的成员对象（一个sds）。
    • score: 成员的分数，用于排序。
    • backward: 指向前一个节点的指针，使其成为双向链表。
    • level[]: 柔性数组，包含了该节点在不同层级的指针。每个 level 结构包含：
      • forward: 指向同一层级下一个节点的指针。
      • span: forward 指针跨越了多少个节点。
  • zskiplist: 跳表本身。包含头尾节点指针、长度和当前最大层数等信息。

核心优势与选择原因：

  • 高效的查找、插入和删除：跳表的增删改查操作的平均时间复杂度为 O(log N)，与平衡树相当。
  • 范围查询更简单：在执行范围查询（如ZRAANGE命令）时，跳表比平衡树的实现更简单。找到范围起点后，只需在底层链表上顺序遍历即可。
  • 实现简单：相对于红黑树等平衡树，跳表的代码实现和调试更为简单清晰。

各数据类型编码

Redis设计了一套“智能”的编码转换机制：

  • 初始阶段：当数据量较小时，优先使用紧凑、连续内存的结构（如 ziplist, intset），它们内存开销极小。

  • 成长阶段：当数据量增长，超过预设的阈值时，紧凑结构的性能会下降（例如，在ziplist中查找元素需要遍历），此时Redis会自动将其转换为更标准、更适合大规模数据的结构（如 hashtable, skiplist）。

1. String (字符串)

  • int: 这是最优化的编码。当您存入的字符串可以被解析为一个64位有符号整数时，Redis会直接将其存储为整数类型，而不是一个字符串对象。这极大地节省了内存。

    • 触发条件: SET mykey 12345

  • embstr (Embedded String): 用于存储短字符串。它的特点是将Redis对象头（redisObject）和SDS字符串体（sdshdr）分配在一块连续的内存中。这样做的好处是：1) 内存分配/释放只需要一次调用；2) 数据在内存中是连续的，能更好地利用CPU缓存（缓存局部性）。

    • 触发条件: 存储长度较短的字符串（例如，在Redis 6.x中长度小于等于44字节）。

  • raw: 用于存储长字符串。此时，Redis对象头和SDS字符串体是分开分配内存的。这是最通用的字符串编码。

    • 触发条件: 字符串长度超过 embstr 的阈值。

2. List (列表)

  • quicklist: 这是Redis 3.2版本后列表的唯一编码。它是一个双向链表，但每个链表节点（quicklistNode）本身又是一个ziplist。

    • 设计目的: 完美地结合了ziplist（省内存）和linkedlist（插入删除快）的优点。它将一个大列表切分成多个小的ziplist，避免了单个ziplist过大时插入/删除操作可能导致的“连锁更新”性能问题，同时也比为每个元素都创建独立节点的linkedlist节省了大量的指针内存开销。

3. Hash (哈希)

  • ziplist: 当哈希结构中存储的键值对数量很少，并且每个键和值的长度都很短时，Redis会使用ziplist来存储。它会将键和值交错地存放在一个连续的内存块中（例如：[key1, value1, key2, value2, ...]），内存利用率极高。

    • 转换条件: 当键值对数量超过 hash-max-ziplist-entries 或任一键/值的长度超过 hash-max-ziplist-value（这两个值可在redis.conf中配置）时，会触发转换。

  • hashtable (Dict): 当哈希结构超过上述阈值后，Redis会将其自动转换为标准的哈希表（字典）结构。虽然内存开销变大，但它能提供平均O(1)复杂度的读写性能，更适合处理大量键值对。

4. Set (集合)

  • intset (整数集合): 当集合中存储的所有元素都是整数，并且元素数量不多时，Redis会使用intset。它是一个有序的、不重复的整数数组，内存非常紧凑，并且可以通过二分查找快速定位元素。

    • 转换条件: 当1) 集合中被加入了一个非整数元素，或2) 元素数量超过了 set-max-intset-entries 配置的阈值时，会触发转换。

  • hashtable (Dict): 转换后的集合会使用哈希表来存储。集合中的每个元素作为哈希表的键（key），而值（value）则统一为一个NULL或一个占位符。

5. ZSet (有序集合)

  • ziplist: 与Hash类似，当有序集合的元素数量很少，并且每个成员和分数（score）的长度都很短时，会使用ziplist。成员和分数会成对地存储在连续内存中，并按分数排序。

    • 转换条件: 当元素数量或成员/分数长度超过 zset-max-ziplist-entries 和 zset-max-ziplist-value 配置的阈值时，触发转换。

  • skiplist + hashtable (Dict): 这是ZSet最经典、最强大的编码方式，它同时使用了两种数据结构：

    • skiplist (跳表): 成员和分数被存储在跳表中。跳表是一种“带有多级索引的链表”，它能以O(log N)的平均时间复杂度实现成员的排序、范围查找（如ZRANGE）和排名（如ZRANK）。

    • hashtable (字典): 字典则建立了从成员（member）到分数（score）的映射。这使得可以通过成员名以O(1)的复杂度直接获取其分数（如ZSCORE命令），弥补了跳表只能按分数查找的不足。