Redis 底层设计与源码设计 • 知之愈多，未知亦夥

Redis 是一个高性能的内存键值数据库,其底层设计和源码实现涵盖了高效的数据结构、事件驱动模型、持久化机制以及集群架构等多个方面。以下是 Redis 底层设计与源码设计的详细解读:

1. 底层数据结构

Redis 的核心是多种高效的数据结构,这些数据结构支撑了 Redis 的五种主要数据类型及其操作。

常用数据结构:

简单动态字符串 (SDS):

Redis 使用 SDS 代替传统的 C 字符串。
特点:
- 高效存储:支持动态扩展,减少频繁的内存分配。
- 长度记录:避免重复计算字符串长度。
- 二进制安全:支持存储任意二进制数据。
SDS 结构(sds.h):
```
struct sdshdr {
  int len;        // 当前字符串长度
  int alloc;      // 分配的总容量
  char buf[];     // 实际字符串
};
```

相关代码:

// 哈希函数
unsigned int dictHashFunction(const void *key) {
    return hash(key) & (ht->size - 1);
}

// 插入操作
int dictAdd(dict *d, void *key, void *val) {
    unsigned int idx = dictHashFunction(key);
    dictEntry *entry = malloc(sizeof(dictEntry));
    entry->key = key;
    entry->val = val;
    entry->next = d->ht[0].table[idx];
    d->ht[0].table[idx] = entry;
    d->ht[0].used++;
    return 1;
}

跳表(Skip List):

用于有序集合(zset)的实现。
特点:
- 高效范围查询。
- 插入、删除、查询的时间复杂度为 (O(\log N))。

跳表节点(zskiplist.h):

typedef struct zskiplistNode {
    double score;                // 分值
    sds ele;                     // 元素
    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;

相关代码:

// 插入元素
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
    zskiplistNode *x = zsl->header;
    for (int i = zsl->level - 1; i >= 0; i--) {
        while (x->level[i].forward && x->level[i].forward->score < score) {
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    int level = randomLevel();
    zskiplistNode *newNode = createNode(level, score, ele);
    for (int i = 0; i < level; i++) {
        newNode->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = newNode;
    }
    return newNode;
}

压缩列表(ZipList):

用于实现短小的列表和哈希表。
特点:
- 紧凑内存占用。
- 高效的顺序访问。

压缩列表结构(ziplist.h):

// 位于 src/ziplist.c
struct __attribute__ ((__packed__)) zlentry {
    unsigned int prevlen;   // 前一元素长度
    unsigned int encoding;  // 当前元素的编码方式
    unsigned char *p;       // 指向实际数据的指针
};

相关代码:

// 插入元素
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
    unsigned char *p;
    p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_TAIL(zl);
    return __ziplistInsert(zl, p, s, slen);
}
// 删除元素
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
    size_t offset = *p - zl;
    zl = __ziplistDelete(zl, p, 1);
    *p = zl + offset;
    return zl;
}

整数集合(IntSet):

用于存储小型整数集合。
特点:
- 根据元素类型动态调整存储大小。

整数集合结构(intset.h):

typedef struct intset {
    uint32_t encoding;      // 当前整数的编码类型(16、32、64 位)
    uint32_t length;        // 集合中的元素数量
    int8_t contents[];      // 实际存储数据的数组
} intset;

相关代码:

// 插入元素
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint32_t pos;
    if (intsetSearch(is, value, &pos)) {
        if (success) *success = 0;
        return is;
    }
    is = intsetResize(is, is->length + 1);
    if (pos < is->length) memmove(&is->contents[pos + 1], &is->contents[pos], (is->length - pos) * is->encoding);
    is->contents[pos] = value;
    is->length++;
    if (success) *success = 1;
    return is;
}
// 查找元素
uint8_t intsetFind(intset *is, int64_t value) {
    uint32_t pos;
    return intsetSearch(is, value, &pos);
}

快速列表(QuickList):

用于实现列表类型(list)。
特点:
- 双端链表和压缩列表的结合。

快速列表的结构(quicklist.h):

// 位于 src/quicklist.h
typedef struct quicklistNode {
    struct quicklistNode *prev;  // 前一个节点
    struct quicklistNode *next;  // 后一个节点
    unsigned char *zl;           // 指向压缩列表
    unsigned int sz;             // 压缩列表的大小
    unsigned int count : 16;     // 节点中元素的个数
    unsigned int encoding : 2;   // 编码方式
    unsigned int container : 2;  // 存储方式
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;         // 链表头节点
    quicklistNode *tail;         // 链表尾节点
    unsigned long count;         // 所有元素的总数
    unsigned int len;            // 链表节点的总数
} quicklist;

相关代码:

// 插入元素
void quicklistInsertAfter(quicklist *ql, quicklistNode *old_node, void *value, size_t sz) {
    quicklistNode *node = quicklistCreateNode();
    node->zl = ziplistPush(NULL, value, sz, ZIPLIST_TAIL);
    node->prev = old_node;
    node->next = old_node->next;
    if (old_node->next) old_node->next->prev = node;
    old_node->next = node;
    ql->count++;
}
// 删除元素
int quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {
    quicklistNode *node = iter->current;
    unsigned char *zl = node->zl;
    zl = ziplistDelete(zl, &entry->zi);
    node->zl = zl;
    node->count--;
    if (node->count == 0) quicklistDelNode(iter->quicklist, node);
    return 1;
}

2. 单线程事件驱动模型

Redis 通过单线程的事件驱动模型(基于 Reactor 模式)实现高性能。

特点:

多路复用:
- 使用操作系统的 I/O 多路复用机制(如 epoll、select、kqueue)。
事件处理器:
- 包括文件事件(如客户端连接)和时间事件(如定期任务)。
避免线程切换开销:
- 单线程避免了多线程上下文切换的开销,同时避免了锁竞争问题。

源码结构(ae.c):

typedef struct aeEventLoop {
    int maxfd;                  // 最大文件描述符
    aeFileEvent *events;        // 文件事件
    aeFiredEvent *fired;        // 已触发的事件
    aeTimeEvent *timeEventHead; // 时间事件
} aeEventLoop;

// 主事件循环
void aeMain(aeEventLoop *eventLoop) {
    while (!eventLoop->stop) {
        int numEvents = aeProcessEvents(eventLoop, AE_ALL_EVENTS);
        // 处理触发的事件
        processFiredEvents(eventLoop);
    }
}

3. 持久化机制

Redis 提供了两种主要的持久化机制,用于在内存数据丢失时恢复。

RDB(Redis DataBase)

定期将内存数据以快照形式保存到磁盘。
优点:
- 恢复速度快。
- 数据文件小,适合备份。
缺点:
- 数据可能丢失(快照间隔期间未保存的数据)。

相关代码(rdb.c):

int rdbSave(char *filename) {
    FILE *fp = fopen(filename, "wb");
    if (!fp) return -1;
    // 写入数据库元信息
    rdbSaveType(fp, RDB_OPCODE_DBSELECT);
    // 写入每个键值对
    dictIterator *di = dictGetIterator(server.db[0].dict);
    while ((de = dictNext(di)) != NULL) {
        rdbSaveKeyValuePair(fp, de->key, de->val);
    }
    fclose(fp);
    return 0;
}

AOF(Append Only File)

以日志的形式记录每个写操作。
优点:
- 数据持久化更安全。
缺点:
- 文件体积较大,恢复速度慢。

相关代码(aof.c):

void feedAppendOnlyFile(struct redisCommand *cmd, int argc, robj **argv) {
    sds buf = sdsempty();
    buf = sdscatlen(buf, "*", 1);
    buf = sdscatprintf(buf, "%d", argc);
    for (int j = 0; j < argc; j++) {
        buf = sdscatlen(buf, "$", 1);
        buf = sdscatprintf(buf, "%d", sdslen(argv[j]->ptr));
        buf = sdscatlen(buf, argv[j]->ptr, sdslen(argv[j]->ptr));
    }
    write(server.aof_fd, buf, sdslen(buf));
    sdsfree(buf);
}

混合持久化

Redis 4.0 引入了混合持久化,将 RDB 和 AOF 结合,利用 RDB 快照快速加载数据,同时用 AOF 补充增量数据。

4. 内存管理

Redis 的内存管理设计以高效为目标:

内存分配:
- 默认使用 jemalloc 作为内存分配器。
内存淘汰策略:
- 支持多种淘汰策略(如 LRU、LFU、TTL)。
内存压缩:
- 小型数据结构使用压缩列表等节省内存。

5. 集群与分布式

Redis 支持主从复制、哨兵模式和分布式集群。

主从复制:

主节点负责读写操作,从节点负责读取。
从节点复制主节点数据,用于负载均衡和高可用。

哨兵模式:

监控主从节点状态,自动故障转移。
保证服务的高可用性。

Redis 集群:

采用分片技术,将数据分布在多个节点上。
通过哈希槽(16384 个)分片。

槽分配(cluster.c):

unsigned int keyHashSlot(char *key, int keylen) {
    unsigned int hash = crc16(key, keylen);
    return hash % 16384;
}

6. 源码设计

Redis 的源码分模块清晰,主要包括以下部分:

数据结构实现:
- 位于 src/dict.c、src/sds.c 等文件。
事件处理:
- 由 src/ae.c 负责。
命令处理:
- 位于 src/command.c,所有 Redis 命令在此定义。
持久化机制:
- RDB 位于 src/rdb.c,AOF 位于 src/aof.c。
集群管理:
- 位于 src/cluster.c。

7. 性能优化

Pipeline:减少网络交互次数。
内存复用:减少频繁的内存分配。
Lazy Deletion:延迟删除大对象,避免阻塞。

总结

Redis 的底层设计以高效数据结构和单线程模型为核心,结合丰富的功能(持久化、集群、复制)和源码模块化设计,成为一款强大而高效的内存数据库。如果需要更深入的细节,可以结合具体源码文件进行分析和优化。