跳到主要内容

Redis 内部数据结构

介绍​

Redis（Remote Dictionary Server）是一个高性能的键值存储系统，广泛用于缓存、消息队列和实时数据处理等场景。Redis之所以如此高效，很大程度上得益于其精心设计的内部数据结构。这些数据结构不仅支持丰富的数据类型，还通过优化存储和访问方式，确保了Redis的高性能。

在本节中，我们将深入探讨Redis的内部数据结构，包括简单动态字符串（SDS）、字典、跳跃表、压缩列表等。我们将通过代码示例和实际案例，帮助你理解这些数据结构的工作原理及其在Redis中的应用。

简单动态字符串（SDS）​

Redis中的字符串并不是直接使用C语言的原生字符串，而是使用了一种称为**简单动态字符串（Simple Dynamic String, SDS）**的数据结构。SDS具有以下优点：

  1. O(1)时间复杂度获取字符串长度：SDS在结构体中存储了字符串的长度，因此获取字符串长度的时间复杂度为O(1)。
  2. 二进制安全：SDS可以存储任意二进制数据，而不仅仅是文本数据。
  3. 自动扩容：SDS会根据需要自动扩容，避免了频繁的内存分配操作。

SDS结构​

c
struct sdshdr {
    int len;    // 字符串长度
    int free;   // 未使用的空间
    char buf[]; // 字符串数据
};

示例​

假设我们有一个SDS字符串 sds，其内容为 "hello"，那么它的结构可能如下：

字典（Dict）​

字典是Redis中用于存储键值对的核心数据结构。Redis的字典实现基于哈希表，支持O(1)时间复杂度的查找、插入和删除操作。

字典结构​

c
typedef struct dict {
    dictType *type;  // 类型特定函数
    void *privdata;  // 私有数据
    dictht ht[2];    // 哈希表数组
    int rehashidx;   // rehash索引
} dict;

哈希冲突解决​

Redis使用链地址法来解决哈希冲突。当多个键映射到同一个哈希槽时，这些键值对会以链表的形式存储。

示例​

假设我们有一个字典 dict，其中包含以下键值对：

  • "name" -> "Alice"
  • "age" -> "30"

其结构可能如下：

跳跃表（Skip List）​

跳跃表是一种有序数据结构，Redis使用跳跃表来实现有序集合（Sorted Set）。跳跃表通过多层链表来加速查找操作，平均时间复杂度为O(log n)。

跳跃表结构​

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

示例​

假设我们有一个跳跃表 zsl，其中包含以下元素：

  • "Alice" -> 30
  • "Bob" -> 25
  • "Charlie" -> 35

其结构可能如下：

压缩列表（Ziplist）​

压缩列表是Redis为了节省内存而设计的一种紧凑型数据结构。它用于存储小型的列表或哈希表，通过连续的内存块来存储数据，减少了内存碎片。

压缩列表结构​

c
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
  • zlbytes：整个压缩列表占用的内存字节数。
  • zltail：最后一个节点的偏移量。
  • zllen：节点数量。
  • entry：每个节点的数据。
  • zlend：压缩列表的结束标志。

示例​

假设我们有一个压缩列表 zl，其中包含以下元素：

  • "Alice"
  • "Bob"
  • "Charlie"

其结构可能如下：

实际应用场景​

缓存​

Redis的字典和SDS结构使其非常适合作为缓存系统。例如，我们可以使用Redis缓存用户信息：

bash
SET user:1:name "Alice"
SET user:1:age "30"

排行榜​

Redis的有序集合（基于跳跃表）非常适合实现排行榜功能。例如，我们可以存储用户的分数并快速获取排名：

bash
ZADD leaderboard 1000 "Alice"
ZADD leaderboard 800 "Bob"
ZADD leaderboard 1200 "Charlie"
ZRANGE leaderboard 0 -1 WITHSCORES

总结​

Redis的内部数据结构是其高性能的关键。通过简单动态字符串、字典、跳跃表和压缩列表等数据结构，Redis能够高效地处理各种数据类型和操作。理解这些数据结构的工作原理，不仅有助于我们更好地使用Redis，还能为我们在设计高性能系统时提供灵感。

附加资源​

练习​

  1. 使用Redis的SDS结构存储一个字符串，并尝试获取其长度。
  2. 实现一个简单的哈希表，并使用链地址法解决哈希冲突。
  3. 使用Redis的有序集合实现一个简单的排行榜功能。