Redis源码分析（sds）
源码版本：redis-4.0.1
源码位置：https://github.com/antirez/sds
一、SDS 简介
SDS（Simple Dynamic String）是 Redis 自行封装的字符串类型。其中 Simple 意为简单，Dynamic 意为动态，表明其具备动态扩容能力，使用者无需关心空间分配细节；String 即字符串。该项目由 Redis 作者 antirez 创建，作为 Redis 的核心数据结构之一，现已独立为一个单独的项目，地址见 这里。
SDS 经历过版本迭代。在 Redis 3.2 之前使用的是第一版，其数据结构如下：
typedef char *sds; // 注意：sds 并非结构体类型，而是被 typedef 为 char*，优势见下文
struct sdshdr {
unsigned int len; // buf 中已使用的长度
unsigned int free; // buf 中未使用的长度
char buf[]; // 柔性数组成员 (flexible array member)
};在 Redis 3.2 版本中，数据结构进行了优化。针对不同的长度范围定义了不同的结构体，以节省内存开销。目前的结构如下：
typedef char *sds;
// 对应的字符串长度小于 1<<5 (32)
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 bit 类型标识，5 bit 字符串长度 */
char buf[];
};
// 对应的字符串长度小于 1<<8 (256)
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; // 当前字符串长度
uint8_t alloc; // 已分配的总长度
unsigned char flags; // 3 bit 类型标识，其余 5 bit 未使用
char buf[]; // 柔性数组，以 '\0' 结尾
};
// 对应的字符串长度小于 1<<16
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};
// 对应的字符串长度小于 1<<32
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
// 对应的字符串长度小于 1<<64
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];
};新版结构的好处在于针对不同长度的字符串选择了合适的数据类型（如 uint8_t、uint16_t 等）来表示长度和分配大小，从而节省内存。结构体中的 __attribute__ ((__packed__)) 指令告诉编译器取消字节对齐，使得结构体大小等于成员实际大小之和，进一步优化空间。
二、SDS 的优势和不足
与一般的自定义 String 结构相比，SDS 有其独特的优势和不足。假设我们用 C 语言定义一个普通的 String 结构体，通常如下：
struct mysds {
char *buf; // 存储实际字符
size_t len; // 字符串长度
// ... 其他成员
};若要打印 buf 的内容，使用方式如下：
struct mysds *sds = mysdsnew("Hello World"); // 假设 mysdsnew 分配空间并初始化
printf("%s", sds->buf);
/* 输出 */
// Hello World此时打印的是 struct mysds 的成员 buf，需要通过指针操作。而 Redis SDS 的定义是 typedef char *sds;，实现同样功能的代码如下：
sds s = sdsnew("Hello World");
printf("%s", s);
/* 输出 */
// Hello World这里直接输出 s 即可。之所以能这样操作，是因为其内存布局如下所示：
+--------+-------------------------------+-----------+
| Header | Binary safe C alike string... | Null term |
+--------+-------------------------------+-----------+
|
`-> 返回给用户的指针 (char *)sdsnew 返回的是一个 char * 类型的指针，指向字符串的开始位置，而头部信息（Header）分配在字符串前面。这种设计带来了以下优势：
- 兼容 C 标准库函数：可以将 SDS 直接传递给任何接受
char *参数的函数（如strcmp,strcat等），无需通过结构体获取地址。 - 访问便捷：可以直接访问单个字符，例如
printf("%c %c\n", sds[0], sds[1]);。若使用mysds则需每次访问mysds->buf[1]。 内存连续，缓存友好：一次连续分配
Header + String + Null，内存地址连续，有利于提高高速缓存命中率。相比之下，mysds通常需要两次malloc，无法保证连续性：struct mysds *sds = (struct mysds *) malloc(sizeof(struct mysds)); sds->buf = (char *) malloc(SIZE); // 这两次 malloc 不能保证 sds 和 buf 内存地址是连续的
除了优点，SDS 也存在一些缺点：
API 返回后需重新赋值：无法确定内部是否重新分配了空间。
s = sdscat(s, "Some more data");s既是参数也是返回值。因为在调用sdscat前不确定剩余空间是否足够，若不足，内部会重新malloc并将原有数据拷贝过去。若未将返回地址重新赋值给s，原指针将失效。- 共享修改风险：如果 SDS 在程序的不同位置共享，修改字符串时必须注意所有引用。因为它本质是
char *地址，一旦在某处重新分配，其他地方的引用将失效。
三、创建、扩容和销毁
本节通过示例跟踪源码，展示 SDS 的 创建 、 扩容 和 销毁 过程。
1. 示例代码
int main(int argc, char *argv[]) {
sds s = sdsnew("Hello World,");
printf("Length:%d, Type:%d\n", sdslen(s), sdsReqType(sdslen(s)));
s = sdscat(s, "The length of this sentence is greater than 32 bytes");
printf("Length:%d, Type:%d\n", sdslen(s), sdsReqType(sdslen(s)));
sdsfree(s);
return 0;
}
/* 输出 */
// Length:12, Type:0
// Length:64, Type:1首先创建名为 s 的 SDS，初始化为 "Hello World,"，打印其 length 和 type 分别为 12 和 0。接着追加字符串使长度变为 64，此时 type 变为 1。最后释放 s。type 的定义位于 sds.h，随长度变化：
#define SDS_TYPE_5 0 // 长度小于 1<<5 (32)
#define SDS_TYPE_8 1 // 长度小于 1<<8 (256)
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 42. 创建过程 (sdsnew)
从 sdsnew 入手分析实现：
/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}sdsnew 计算字符串长度后调用 sdsnewlen：
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
char type = sdsReqType(initlen);
/* 空字符串通常用于追加，使用 type 8 因为 type 5 不适合此场景 */
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
sh = s_malloc(hdrlen + initlen + 1);
if (!init)
memset(sh, 0, hdrlen + initlen + 1);
if (sh == NULL) return NULL;
s = (char*)sh + hdrlen;
fp = ((unsigned char*)s) - 1;
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8, s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
// SDS_TYPE_16/32/64 逻辑类似，省略...
}
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
return s;
}基本流程如下：
确定类型：
char type = sdsReqType(initlen);根据长度获取类型。static inline char sdsReqType(size_t string_size) { if (string_size < 1<<5) return SDS_TYPE_5; if (string_size < 1<<8) return SDS_TYPE_8; if (string_size < 1<<16) return SDS_TYPE_16; #if (LONG_MAX == LLONG_MAX) if (string_size < 1ll<<32) return SDS_TYPE_32; #endif return SDS_TYPE_64; }计算头大小：
int hdrlen = sdsHdrSize(type);获取 Header 长度。static inline int sdsHdrSize(char type) { switch(type & SDS_TYPE_MASK) { case SDS_TYPE_5: return sizeof(struct sdshdr5); case SDS_TYPE_8: return sizeof(struct sdshdr8); // ... 其他类型 } return 0; }- 分配内存：
malloc申请hdrlen + initlen + 1空间（头部 + 字符串 + Null）。s指向字符串首地址，fp指向头部最后一个字节（flag）。 - 初始化头部：根据类型进入
switch。对于SDS_TYPE_5，长度信息存在flag中（5 bit 长度，3 bit 类型）。 - 拷贝字符串：完成拷贝并置结尾
\0。
此时 SDS 结构如下图所示：
flag 占 1 字节，中间 String 占 11 字节，后跟 \0。
3. 扩容过程 (sdscat)
代码执行追加操作：
s = sdscat(s, "The length of this sentence is greater than 32 bytes");追加超过 32 字符的内容，目的是使其转变为 SDS_TYPE_8 类型。sdscat 调用 sdscatlen：
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s);
s = sdsMakeRoomFor(s, len);
if (s == NULL) return NULL;
memcpy(s + curlen, t, len);
sdssetlen(s, curlen + len);
s[curlen + len] = '\0';
return s;
}关键函数 sdsMakeRoomFor 保证空间足够，不足则动态分配：
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
/* 空间足够则直接返回 */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s - sdsHdrSize(oldtype);
newlen = (len + addlen);
/* 预分配策略：小于 1MB 则翻倍，否则增加 1MB */
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);
/* 追加操作不使用 type 5，因为它无法记录空闲空间 */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype == type) {
/* 类型未变，使用 realloc */
newsh = s_realloc(sh, hdrlen + newlen + 1);
if (newsh == NULL) return NULL;
s = (char*)newsh + hdrlen;
} else {
/* 类型变化，Header 大小改变，需重新分配并拷贝 */
newsh = s_malloc(hdrlen + newlen + 1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh + hdrlen, s, len + 1);
s_free(sh);
s = (char*)newsh + hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
sdssetalloc(s, newlen);
return s;
}检查可用空间：
sdsavail(s)获取当前可用空间。static inline size_t sdsavail(const sds s) { unsigned char flags = s[-1]; switch(flags & SDS_TYPE_MASK) { case SDS_TYPE_5: return 0; case SDS_TYPE_8: { SDS_HDR_VAR(8, s); return sh->alloc - sh->len; } // ... 其他类型类似 } return 0; }SDS_TYPE_5无空闲空间记录，返回 0；其他类型通过alloc - len计算。- 判断是否扩容：若
avail >= addlen直接返回。 - 计算新长度：新长度 = 当前长度 + 追加长度。若小于
SDS_MAX_PREALLOC(1MB) 则翻倍，否则增加 1MB，避免频繁malloc。 - 重新分配：若类型变化（如本例从 Type 5 变 Type 8），Header 大小改变，无法使用
realloc，需malloc新空间并拷贝数据，释放旧空间。
sdscatlen 继续执行拷贝、设置长度和 \0。此时 s 结构如下：
注意：打印长度 64 指 len，图中 128 是 alloc，可用空间剩余 64 字节。下次追加小于 64 字节的内容无需重新分配。
4. 销毁过程 (sdsfree)
void sdsfree(sds s) {
if (s == NULL) return;
s_free((char*)s - sdsHdrSize(s[-1]));
}若不为 NULL，根据 flag 类型获取 Header 长度，指针前移得到 Header 首地址后释放。
四、其他接口和特性
SDS 还提供了丰富的辅助接口：
sdssplitargs：分割字符串。默认按\n、空格、\t、\r、\0以及双引号和单引号分割。// 示例 1 sds *arr = sdssplitargs("H\ne\tl\rlo Wor\ald", &args); // 输出：H e l lo Wor ld (args: 5) // 示例 2 (处理引号) sds *arr = sdssplitargs("\"Hello\" World", &args); // 输出：Hello World (args: 2) // 示例 3 (十六进制) sds *arr = sdssplitargs("\x41 \x42 \x43", &args); // 输出：A B C (args: 3)注意：结果数组需使用
sdsfreesplitres(arr, args)释放。sdssplitlen：指定分隔符分割，分隔符可以是字符串。sds s = sdsnew("Hello_-_World"); sds *arr = sdssplitlen(s, sdslen(s), "_-_", 3, &args); // 输出：Hello World (args: 2)sdscatprintf：格式化字符串，类似sprintf。s = sdscatprintf(s, "%d+%d = %d", a, b, a+b); // 输出：Sum is: 1+1 = 2sdscatfmt：类似sdscatprintf但更快（不依赖libc sprintf），仅支持部分格式符。// 支持：%s, %S, %i, %I, %u, %U, %% s = sdscatfmt(s, "%s", " World"); // 输出：Hello Worldsdstrim：剔除指定字符集。sds s = sdsnew("AA...AA.a.aa.aHelloWorldiii :::"); s = sdstrim(s, "A. a:i"); // 输出：HelloWorldsdsrange：截取子串（类似 substring）。sds s = sdsnew("Hello World"); sdsrange(s, 1, -1); // 1 表示第二个字符，-1 表示倒数第一个 // 输出：ello Worldsdsmapchars：替换指定字符。sds s = sdsnew("Hello World"); s = sdsmapchars(s, "o", "u", 1); // 将 o 替换成 u // 输出：Hellu Wurld
说明：本文基于Redis 4.0.1源码进行分析。SDS 数据结构自Redis 3.2定型后保持稳定，后续版本（如 6.x/7.x）核心结构未发生显著变化，本文结论仍具参考价值。
版权声明：本文为原创文章，版权归 戴老师的博客 所有，转载请联系博主获得授权。
本文地址：https://1diff.fun/archives/redis-yuan-ma-fen-xi-sds.html
如果对本文有什么问题或疑问都可以在评论区留言，我看到后会尽量解答。
