面试题：Redis 源码中有哪些巧妙的设计，举几个典型的例子？

4712

Redis 的源码设计中融入了许多巧妙的思路，旨在提升性能、降低复杂性并优化资源使用。以下是几个典型的例子，结合源码细节进行说明：

1. 简单动态字符串（SDS, Simple Dynamic String）

问题背景：
C 语言原生字符串存在以下缺陷：

  • 获取字符串长度需要遍历（O(N)）。
  • 拼接时容易发生缓冲区溢出。
  • 不支持存储二进制数据（如含空字符 \0 的内容）。

Redis 的解决方案：
Redis 引入 SDS 结构，通过预分配内存和记录长度字段，解决了上述问题。

源码示例（以 sdshdr8 为例）：

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;     // 当前已使用长度
    uint8_t alloc;   // 当前分配的总长度（不含头和终止符）
    unsigned char flags; // 类型标识
    char buf[];      // 实际存储的字符串数据
};

设计亮点：

  1. 长度字段：直接通过 len 获取字符串长度（O(1)），避免遍历。
  2. 内存预分配：扩展字符串时，Redis 会预分配额外内存（小于 1MB 时扩展为两倍，大于 1MB 时扩展 1MB）。
    • 优点：减少频繁的内存分配次数，提升性能。
  3. 二进制安全：SDS 通过 len 字段管理数据，支持存储任意二进制内容（如图片、音频）。
  4. 兼容性：SDS 末尾仍保留 \0，兼容 C 字符串函数（如 printf）。

实际应用：

  • 执行 SET key value 时，Redis 会创建两个 SDS：一个存储 key（”key”），一个存储 value（”value”）。
  • 拼接操作（如 APPEND key new_data）利用预分配机制高效扩展。

2. 跳跃表（Skip List）

问题背景：
有序集合需要支持高效排序和范围查询。传统红黑树实现复杂，而链表查询效率低。

Redis 的解决方案：
Redis 使用 跳跃表 实现有序集合（ZSet），通过多层索引实现 O(log N) 的查找效率，且实现简单。

源码示例（跳跃表节点 zskiplistNode）：

struct zskiplistNode {
    robj *obj;              // 存储的元素（Member）
    double score;           // 分数（Score）
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned int span;             // 跨度
    } level[];
};

设计亮点：

  1. 多层链表：每一层是一个升序链表，最高层为索引层，最低层为数据层。
  2. 随机层级：插入新节点时，通过概率算法（幂次定律）决定层级（最大 32 层）。
  3. 跨度计算：span 字段记录节点间的跨度，支持快速计算排名（Rank）。
  4. 双向指针：通过 backward 指针支持从后向前遍历（如 ZREVRANGE 命令）。

实际应用：

  • 执行 ZRANGE key 0 10 时，跳跃表通过索引层快速定位范围，再顺序遍历结果。
  • 支持高效插入（ZADD）、删除（ZREM）和范围查询（ZRANGEBYSCORE）。

3. 压缩列表（Ziplist）

问题背景：
对于小数据量的集合或列表，使用哈希表或链表会占用较多内存。

Redis 的解决方案：
Redis 使用 压缩列表 存储小数据量的 List、Hash 和 ZSet，通过连续内存块减少内存开销。

源码示例（压缩列表头部 ziplist）：

struct ziplist {
    unsigned int zlbytes;   // 总字节数
    unsigned int zltail;    // 尾节点偏移量
    unsigned int zllen;     // 节点数量
    unsigned char zlend;    // 结束标志（ZIP_END）
};

设计亮点：

  1. 紧凑存储：所有元素存储在连续内存块中，减少指针开销。
  2. 编码优化：根据数据类型（字符串或整数）和大小选择编码方式（如 int16_t、int32_t）。
  3. 双向遍历：通过 zltail 快速定位尾节点，支持从头或尾访问。
  4. 动态扩展：插入新元素时，直接修改内存块，避免频繁分配。

实际应用：

  • 当 List 中的元素数量 ≤ 512 且每个元素长度 ≤ 64 字节时，Redis 使用 Ziplist 存储。
  • 通过 ZIPLIST_INCR_LENGTH 宏动态扩展内存块。

4. 单线程模型与事件驱动

问题背景：
多线程模型可能导致上下文切换和锁竞争，增加复杂性。

Redis 的解决方案：
Redis 采用 单线程 + 事件驱动模型，通过 I/O 多路复用（epoll/kqueue）处理客户端请求。

源码示例（事件循环 aeMain）：

void aeMain(aeEventLoop *eventLoop) {
    eventLoop->stop = 0;
    while (!eventLoop->stop) {
        if (aeProcessEvents(eventLoop, AE_ALL_EVENTS) == AE_ERR) break;
    }
}

设计亮点：

  1. 非阻塞 I/O：通过 aeProcessEvents 监听多个文件描述符（如客户端连接），避免阻塞主线程。
  2. 单线程简化：无需处理线程同步问题，代码更简洁。
  3. 高性能：内存操作（如 GET/SET）耗时极低（<1 微秒），单核 CPU 可支撑高并发。

实际应用：

  • Redis 通过 ae.c 实现事件循环，处理网络请求、定时任务等。
  • 单线程模型适用于 I/O 密集型场景，但需配合持久化（RDB/AOF）异步执行。

5. 渐进式 Rehash

问题背景：
哈希表扩容时，一次性迁移所有数据会导致主线程阻塞。

Redis 的解决方案：
Redis 使用 渐进式 Rehash，将数据迁移分散到每次操作中。

源码示例（字典 dict 的渐进式 Rehash）：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];       // 两个哈希表
    long rehashidx;     // 当前正在迁移的桶索引
    ...
} dict;

设计亮点：

  1. 双哈希表：ht[0] 为旧表，ht[1] 为新表，逐步迁移数据。
  2. 分批迁移：每次操作（如 GET/SET）迁移少量桶，避免阻塞主线程。
  3. 线性探测：通过 rehashidx 记录迁移进度，确保最终一致性。

实际应用：

  • 执行 HSET 时，若触发扩容，Redis 会将当前桶的数据迁移到 ht[1]。
  • rehashidx 递增直到所有数据迁移完成，最终释放 ht[0]。

总结：Redis 设计的核心哲学

设计目标效果
SDS替代 C 字符串高效操作、内存优化
跳跃表实现有序集合高效排序与范围查询
压缩列表优化小数据存储节省内存，减少碎片
单线程模型简化并发控制高性能、低复杂度
渐进式 Rehash避免阻塞平滑扩容，不影响主线程

Redis 的这些设计体现了“为场景优化”的理念，通过针对性的结构选择和巧妙的实现，平衡了性能、内存和代码复杂性。

THE END
Redis 面试题
喜欢就支持一下吧
点赞12 分享
相关推荐