Redis 源码硬核解析系列专题 - 第二篇：核心数据结构之SDS（Simple Dynamic String）

第二篇：核心数据结构之SDS（Simple Dynamic String）

1. 引言

Redis没有直接使用C语言的标准字符串（以\0结尾的字符数组），而是自定义了SDS（Simple Dynamic String）。SDS是Redis的基础数据结构之一，广泛用于键值存储、命令参数等场景。本篇将深入剖析SDS的实现原理、优势以及源码细节。

2. 为什么不用C标准字符串？

C字符串存在以下问题：

缓冲区溢出：strcat等操作可能越界。
长度计算：需要遍历到\0，时间复杂度O(n)。
内存管理：频繁的拼接和释放效率低下。

SDS通过额外的元数据和优化策略，解决了这些问题，成为Redis高性能的基石。

3. SDS的结构体定义

SDS的定义在src/sds.h和src/sds.c中。Redis 3.2之后引入了多种SDS类型以节省内存，但核心思想一致。我们以最基本的SDS结构为例：

代码片段（sds.h）：

1
2
3
4
5
6
7
typedef char *sds;

struct sdshdr {
    unsigned int len;    // 已使用长度
    unsigned int free;   // 未使用长度
    char buf[];          // 实际存储数据的柔性数组
};

len：记录字符串的实际长度，避免遍历。
free：记录剩余可用空间，支持动态扩展。
buf：存储字符串内容，紧跟结构体。

硬核点：SDS的内存布局是连续的，sds指针直接指向buf，而通过指针偏移可以访问sdshdr。

Mermaid内存布局图：

classDiagram
    class SDS {
        -len: uint
        -free: uint
        -buf: char[]
    }
    note for SDS "sds指针指向buf起始地址"

4. SDS的核心操作解析

4.1 创建SDS（`sdsnew()`）

代码片段（sds.c）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;
    size_t alloc = initlen;
    sh = zmalloc(sizeof(struct sdshdr) + alloc + 1); // +1 为\0
    sh->len = initlen;
    sh->free = 0;
    if (init) memcpy(sh->buf, init, initlen);
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}

硬核解析：

zmalloc()：Redis自定义的内存分配器。
内存分配包括sdshdr头部和buf（加1字节存放\0以兼容C函数）。
返回值是buf的地址，隐藏了头部信息。

4.2 拼接SDS（`sdscat()`）

代码片段（sds.c）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *sh = (void*) (s - sizeof(struct sdshdr));
    size_t curlen = sh->len;
    sdsMakeRoomFor(s, len); // 确保空间足够
    memcpy(s + curlen, t, len);
    sh->len = curlen + len;
    sh->free -= len;
    s[curlen + len] = '\0';
    return s;
}

硬核解析：

通过指针偏移（s - sizeof(struct sdshdr)）获取sdshdr。
sdsMakeRoomFor()：检查并扩展空间（后文详解）。
更新len和free，保持\0结尾。

4.3 扩展空间（`sdsMakeRoomFor()`）

代码片段（sds.c）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh = (void*) (s - sizeof(struct sdshdr));
    size_t avail = sh->free;
    if (avail >= addlen) return s; // 空间足够，直接返回
    size_t newlen = sh->len + addlen;
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2; // 小于1MB时翻倍
    else
        newlen += SDS_MAX_PREALLOC; // 超过1MB加1MB
    sh = zrealloc(sh, sizeof(struct sdshdr) + newlen + 1);
    sh->free = newlen - sh->len;
    return sh->buf;
}

硬核解析：

空间预分配：若需扩展，小于1MB时容量翻倍，大于1MB时增加1MB（SDS_MAX_PREALLOC）。
zrealloc()：重新分配内存，保持数据连续性。

Mermaid扩展流程：

graph TD
    A["sdscat()"] --> B["sdsMakeRoomFor()"]
    B --> C{free >= addlen?}
    C -->|是| D[直接返回]
    C -->|否| E[计算newlen]
    E --> F{newlen < 1MB?}
    F -->|是| G[翻倍]
    F -->|否| H[加1MB]
    G --> I["zrealloc()"]
    H --> I
    I --> J[更新free]
    J --> K[返回新buf]

4.4 释放SDS（`sdsfree()`）

代码片段（sds.c）：

1
2
3
4
void sdsfree(sds s) {
    if (s == NULL) return;
    zfree(s - sizeof(struct sdshdr));
}

硬核点：释放时需偏移到sdshdr头部，回收整个内存块。

5. SDS的优势与优化

O(1)长度获取：len字段直接提供长度。
安全性：避免缓冲区溢出。
高效扩展：
- 预分配：减少频繁realloc。
- 惰性释放：sdsRemoveFreeSpace()可清理多余空间，但默认保留以复用。

6. 总结与调试建议

收获：掌握SDS的内存布局与动态扩展机制。
调试技巧：用gdb打印sdshdr（如p *(struct sdshdr *)(s - sizeof(struct sdshdr))）。
下一步：探索SDS如何在字典（Dict）中使用。

Redis 源码硬核解析系列专题 - 第二篇：核心数据结构之SDS（Simple Dynamic String）

相关文章：