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

Redis 是一个高性能的键值存储系统，其源码中有许多巧妙的设计，这些设计使得 Redis 在性能、内存效率和可扩展性方面表现出色。以下是几个典型的设计示例：

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

• 设计目的：Redis 需要频繁地处理字符串操作，如拼接、截取等，C 语言原生的字符串（以 \0 结尾的字符数组）在处理这些操作时效率较低。
• 巧妙之处：
  • SDS 结构体中包含了字符串的长度信息，使得获取字符串长度的时间复杂度为 O(1)。
  • SDS 采用了预分配策略，减少了内存重新分配的次数，提高了字符串操作的效率。
  • SDS 是二进制安全的，可以存储任意二进制数据，而不仅仅是文本数据。

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

2. 字典（Dict）

• 设计目的：Redis 使用字典来实现键值对的存储，字典需要高效地支持插入、删除和查找操作。
• 巧妙之处：
  • Redis 的字典使用了哈希表作为底层数据结构，并通过链地址法解决哈希冲突。
  • 字典支持渐进式 rehash，即在 rehash 过程中，字典可以同时处理新旧两个哈希表，避免了一次性 rehash 导致的性能抖动。
  • 字典的哈希表大小总是 2 的幂次方，这样可以通过位运算快速计算索引。

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2]; // 两个哈希表，用于渐进式 rehash
    long rehashidx; // rehash 的进度
} dict;

3. 跳跃表（Skip List）

• 设计目的：Redis 使用跳跃表来实现有序集合（Sorted Set），跳跃表需要高效地支持插入、删除和范围查询操作。
• 巧妙之处：
  • 跳跃表通过多级索引加速查找，使得查找、插入和删除操作的平均时间复杂度为 O(log n)。
  • 跳跃表的实现相对简单，且不需要复杂的平衡操作（如红黑树），因此在实现和维护上更加容易。
  • 跳跃表支持范围查询，可以高效地获取某个范围内的元素。

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

4. 内存分配器（jemalloc）

• 设计目的：Redis 需要高效地管理内存，避免内存碎片和提高内存分配的速度。
• 巧妙之处：
  • Redis 默认使用 jemalloc 作为内存分配器，jemalloc 是一个高效的内存分配库，特别适合多线程环境。
  • jemalloc 通过内存池和 slab 分配器减少内存碎片，提高内存利用率。
  • jemalloc 在多线程环境下表现出色，能够有效地减少锁竞争。

5. 事件驱动模型

• 设计目的：Redis 需要高效地处理大量的客户端连接和网络 I/O 操作。
• 巧妙之处：
  • Redis 使用了基于事件驱动的模型，通过单线程处理所有的网络 I/O 和命令执行。
  • Redis 使用了 I/O 多路复用技术（如 epoll、kqueue 等），使得单线程能够高效地处理成千上万的并发连接。
  • 事件驱动模型避免了多线程的上下文切换和锁竞争，提高了系统的吞吐量。

typedef struct aeEventLoop {
    int maxfd;
    int setsize;
    long long timeEventNextId;
    aeFileEvent *events;
    aeFiredEvent *fired;
    aeTimeEvent *timeEventHead;
    int stop;
    void *apidata;
    aeBeforeSleepProc *beforesleep;
} aeEventLoop;

6. 对象系统

• 设计目的：Redis 需要支持多种数据类型（如字符串、列表、哈希、集合、有序集合等），并且需要高效地管理这些数据。
• 巧妙之处：
  • Redis 使用了一个统一的对象系统来表示所有的数据类型，每个对象都包含类型、编码、引用计数等信息。
  • 对象系统通过引用计数实现内存管理，当对象的引用计数为 0 时，自动释放内存。
  • 对象系统支持多种编码方式，根据数据的特点选择最合适的编码方式，节省内存。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; // LRU 时间或 LFU 数据
    int refcount;
    void *ptr;
} robj;

总结

Redis 源码中的这些巧妙设计使得它在性能、内存效率和可扩展性方面表现出色。通过简单动态字符串、字典、跳跃表、内存分配器、事件驱动模型和对象系统等设计，Redis 能够高效地处理大量的数据和并发请求，成为一个高性能的键值存储系统。