SDS 动态字符串：为什么不用 C string
第五章：SDS 动态字符串：为什么不用 C string
5.1 C 字符串的五大缺陷
在分析 SDS 的设计之前，必须先清楚 C 字符串为何不适合用于系统级软件。C 字符串是以 \0 终止的 char 数组，看似简单，实则埋下了五个根本性的问题。
5.1.1 O(n) 获取长度
C 标准库的 strlen() 需要遍历整个字符串直到找到 \0：
size_t strlen(const char *s) {
size_t len = 0;
while (*s++) len++; // 逐字节扫描
return len;
}
对于一个 10MB 的字符串，strlen() 需要扫描 1000 万个字节。如果在循环中反复调用 strlen()（如字符串比较、日志拼接），性能损耗不可忽视。
SDS 方案：在头部直接存储字符串长度（len 字段），sdslen() 是 O(1) 的直接内存读取：
static inline size_t sdslen(const sds s) {
unsigned char flags = s[-1]; // flags 字段在 buf 前一个字节
switch(flags & SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags); // 高 5 位存长度
case SDS_TYPE_8:
return SDS_HDR(8, s)->len;
case SDS_TYPE_16:
return SDS_HDR(16, s)->len;
case SDS_TYPE_32:
return SDS_HDR(32, s)->len;
case SDS_TYPE_64:
return SDS_HDR(64, s)->len;
}
return 0;
}
5.1.2 缓冲区溢出（Buffer Overflow）
C 字符串函数（strcat、strcpy、sprintf）不检查目标缓冲区大小：
char s1[5] = "Hello";
char s2[] = " World";
strcat(s1, s2); // ← 未定义行为！s1 只有 5 字节，但写入了 12 字节
// 覆盖相邻内存，可能导致安全漏洞（CVE 的主要来源之一）
SDS 方案：所有修改操作前先调用 sdsMakeRoomFor()，确保有足够的 alloc 空间：
/* 确保 SDS 至少有 addlen 字节的额外空间 */
sds sdsMakeRoomFor(sds s, size_t addlen) {
size_t avail = sdsavail(s); // 当前可用空间 = alloc - len
if (avail >= addlen) return s; // 足够则直接返回
size_t len = sdslen(s);
size_t newlen = len + addlen;
/* 空间预分配策略 */
if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC = 1MB
newlen *= 2; // 小于 1MB：翻倍分配
else
newlen += SDS_MAX_PREALLOC; // 大于等于 1MB：额外加 1MB
/* realloc 并更新 SDS 类型（可能从 sdshdr8 升级到 sdshdr16） */
return _sdsMakeRoomFor(s, addlen, 1);
}
5.1.3 频繁内存重分配
C 字符串修改（追加、截断）每次都需要 realloc：
char *s = strdup("hello");
s = realloc(s, strlen(s) + strlen(" world") + 1);
strcat(s, " world"); // 每次 APPEND 都调用 realloc
realloc 在最坏情况下需要：分配新内存、复制旧内容、释放旧内存——代价远高于原地写入。
SDS 方案：空间预分配（preallocation）+ 惰性空间释放（lazy free），大幅减少 realloc 频率。
5.1.4 不能存储二进制数据（内含 \0）
C 字符串以 \0 作为终止标志，因此字符串内部不能包含 \0 字节。这意味着无法存储：
- 图片的 EXIF 数据（二进制）
- 协议帧（可能含有 0x00 字节）
- 压缩后的数据（压缩算法输出的任意字节序列）
char s[] = "hello\0world";
strlen(s); // 返回 5，而非 11——\0 之后的内容被截断
SDS 方案：使用 len 字段记录内容长度，不依赖 \0 终止。Redis 的 SET 命令可以存储任意二进制数据：
# 存储包含 \0 的二进制数据
redis-cli SET binkey $'\x00\x01\x02\x03\x04'
redis-cli STRLEN binkey # → 5（正确）
5.1.5 不安全的标准库函数
C 标准库的字符串函数（gets、scanf %s、sprintf 无宽度限制）是历史上最大的安全漏洞来源之一。即使安全的替代版本（snprintf、strncat）也需要程序员手动计算缓冲区大小。
SDS 彻底避免使用这些函数，所有字符串操作都在内部处理边界检查。
5.2 SDS 五种头结构
SDS 根据字符串长度选择最小的头结构，节省内存：
/* src/sds.h */
/* sdshdr5：字符串长度存在 flags 高 5 位，最大 31 字节（实际 Redis 中很少用） */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 高 5 bits: 长度；低 3 bits: SDS_TYPE_5 (0x00) */
char buf[];
};
/* sdshdr8：最大 255 字节（uint8_t 上限） */
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 已使用长度 */
uint8_t alloc; /* 总分配容量（不含头部和 \0） */
unsigned char flags; /* 低 3 bits: SDS_TYPE_8 (0x01) */
char buf[]; /* 实际字符串内容 + \0 */
};
/* sdshdr16：最大 65535 字节（64KB） */
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags; /* 低 3 bits: SDS_TYPE_16 (0x02) */
char buf[];
};
/* sdshdr32：最大 4GB */
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags; /* 低 3 bits: SDS_TYPE_32 (0x03) */
char buf[];
};
/* sdshdr64：最大 18EB（理论值，内存不可能这么大） */
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags; /* 低 3 bits: SDS_TYPE_64 (0x04) */
char buf[];
};
5.2.1 __attribute__((packed)) 的作用
正常情况下，C 编译器会对结构体字段进行内存对齐（alignment）：
/* 没有 __packed__ 的 sdshdr8（假设）：
len (uint8_t) → 1 字节，但编译器对齐到 2 字节边界
alloc (uint8_t) → 1 字节，填充 1 字节到下一个 2 字节边界
flags (uint8_t) → 1 字节，填充 1 字节
buf[] → 从 4 字节边界开始
实际大小：6 字节（有 3 字节填充）
*/
/* 有 __packed__ 的 sdshdr8：
len (uint8_t) → 1 字节（紧邻）
alloc (uint8_t) → 1 字节（紧邻）
flags (uint8_t) → 1 字节（紧邻）
buf[] → 紧接着开始
实际大小：3 字节（零填充）
*/
__packed__ 禁止编译器插入填充字节，使结构体字段紧密排列。对于 sdshdr8，这节省了 3 字节（从 6 字节减到 3 字节）。在存储数亿个短字符串的场景下，节省非常可观。
代价：未对齐的内存访问在某些 CPU 架构上比对齐访问慢（x86 现代 CPU 通常无明显影响，但 ARM 严格对齐要求的旧版本会有性能损耗）。Redis 的目标平台以 x86/x86_64 为主，此代价可以接受。
5.2.2 SDS 类型选择逻辑
/* src/sds.c */
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5) /* < 32 字节 */
return SDS_TYPE_5;
if (string_size < 1<<8) /* < 256 字节 */
return SDS_TYPE_8;
if (string_size < 1<<16) /* < 65536 字节 (64KB) */
return SDS_TYPE_16;
if (string_size < 1ll<<32)/* < 4GB */
return SDS_TYPE_32;
return SDS_TYPE_64;
}
注意：sdshdr5 在 Redis 实践中几乎只用于存储 key 名（短字符串），不用于 value。因为 sdshdr5 没有 alloc 字段，无法进行空间预分配，任何追加操作都需要转换为其他类型。
5.2.3 flags 字段的双重含义
sdshdr5 的 flags 字段：
Bit 7 6 5 4 3 | Bit 2 1 0
─────────────────────────
字符串长度(5位) | SDS 类型(3位)
其他 sdshdr* 的 flags 字段：
Bit 7 6 5 4 3 2 | Bit 2 1 0
──────────────────────────
保留（未使用） | SDS 类型(3位)
类型值：
SDS_TYPE_5 = 0 (000)
SDS_TYPE_8 = 1 (001)
SDS_TYPE_16 = 2 (010)
SDS_TYPE_32 = 3 (011)
SDS_TYPE_64 = 4 (100)
从 buf[] 指针出发，向后偏移 -1 字节即可访问 flags，从而确定 SDS 类型，进而访问 len 和 alloc：
/* 通过 buf 指针获取 SDS 头部的宏 */
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_MASK 7 // 0b00000111
/* 使用示例 */
uint8_t len = SDS_HDR(8, sds_ptr)->len; // 访问 sdshdr8 的 len
5.3 内存布局完整示意图
以存储字符串 "Redis" 为例（sdshdr8 编码）：
内存地址 内容 说明
─────────────────────────────────────────────────────────────────
&buf[-3] 0x05 sdshdr8.len = 5（字符串长度）
&buf[-2] 0x05 sdshdr8.alloc = 5（当前分配容量）
&buf[-1] 0x01 sdshdr8.flags：低3位 = 001 = SDS_TYPE_8
&buf[0] 0x52 'R' buf[0]
&buf[1] 0x65 'e' buf[1]
&buf[2] 0x64 'd' buf[2]
&buf[3] 0x69 'i' buf[3]
&buf[4] 0x73 's' buf[4]
&buf[5] 0x00 '\0' C 字符串兼容终止符（不计入 len）
─────────────────────────────────────────────────────────────────
十六进制表示（从 sdshdr8 开始的连续内存）：
05 05 01 52 65 64 69 73 00
────── ─ ───────────── ──
len alloc flags "Redis" \0
sds 变量实际指向 buf[0]，而非 sdshdr8 的起始地址。这个设计使 SDS 与 C 字符串函数兼容（可以直接传给 printf、strcmp 等），同时通过负偏移访问 SDS 头部。
5.4 空间预分配策略
当 SDS 需要扩容时（如执行 APPEND 命令），Redis 不是精确分配刚好够用的空间，而是额外分配一些预留空间，避免频繁 realloc：
/* src/sds.c */
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s); // 当前剩余空间
size_t len, newlen, reqlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
if (avail >= addlen) return s; // 空间足够，直接返回
len = sdslen(s);
sh = (char*)s - sdsHdrSize(oldtype);
reqlen = newlen = (len + addlen);
assert(newlen > len); // 防止溢出
if (newlen < SDS_MAX_PREALLOC) { // SDS_MAX_PREALLOC = 1 << 20 = 1MB
newlen *= 2; // 小于 1MB：分配 2 倍
} else {
newlen += SDS_MAX_PREALLOC; // 大于等于 1MB：额外加 1MB
}
// ... realloc 并返回新 SDS
}
预分配策略的实际效果：
| 操作 | 修改前 len | 修改后 len | 预分配后 alloc | realloc 次数 |
|---|---|---|---|---|
| APPEND "hello" | 0 | 5 | 10 | 1 |
| APPEND "world" | 5 | 10 | 10（够用） | 0 |
| APPEND " foo" | 10 | 14 | 28 | 1 |
| APPEND "bar" | 14 | 17 | 28（够用） | 0 |
对比不预分配的情况（每次 APPEND 都 realloc）：4 次 APPEND 需要 4 次 realloc。使用预分配后：4 次 APPEND 只需要 2 次 realloc。字符串越长，节省的比例越高。
预分配上限（1MB 截断）的必要性：如果对一个 100MB 的字符串执行 APPEND，按 2 倍策略需要额外分配 100MB——总计 300MB。对于超大字符串，2 倍策略的内存浪费不可接受，因此超过 1MB 改为固定追加 1MB。
5.5 惰性空间释放
当字符串被截短时（如 SETRANGE 将字符串变短，或通过 Lua 脚本修改），SDS 不立即释放多余的内存：
/* 字符串截短：只减少 len，不减少 alloc */
void sdssetlen(sds s, size_t newlen) {
unsigned char flags = s[-1];
switch(flags & SDS_TYPE_MASK) {
case SDS_TYPE_8:
SDS_HDR(8,s)->len = newlen; // len 减小
// alloc 不变！多余空间保留
break;
// ...
}
s[newlen] = 0; // 更新 \0 位置
}
好处：如果后续操作再次扩展字符串，可以直接使用已有空间，无需 realloc。对于频繁在一个范围内增减的字符串，惰性释放避免了 realloc 的震荡。
坏处：短暂造成内存浪费。可以通过显式调用 sdsRemoveFreeSpace() 释放未使用的空间（Redis 内部在 RDB 保存等场景会调用此函数）。
/* 显式释放未使用空间 */
sds sdsRemoveFreeSpace(sds s, int would_regrow) {
// ... realloc 到 len + 头部大小 + 1(\0)
}
5.6 二进制安全性
SDS 的 len 字段使 Redis 可以安全地存储任意二进制数据：
# 存储包含 \0 字节的二进制数据
redis-cli SET binkey $'\x89\x50\x4e\x47\x0d\x0a\x1a\x0a' # PNG 文件头
redis-cli STRLEN binkey # → 8（正确，不会在第一个 \0 处截断）
# 追加二进制数据
redis-cli APPEND binkey $'\x00\x00\x00\x0d' # PNG IHDR chunk 长度字段
redis-cli STRLEN binkey # → 12
内部实现：
/* 比较两个 SDS（二进制安全） */
int sdscmp(const sds s1, const sds s2) {
size_t l1, l2, minlen;
int cmp;
l1 = sdslen(s1);
l2 = sdslen(s2);
minlen = (l1 < l2) ? l1 : l2;
cmp = memcmp(s1, s2, minlen); // 使用 memcmp 而非 strcmp（memcmp 不受 \0 影响）
if (cmp == 0) return l1 > l2 ? 1 : (l1 < l2 ? -1 : 0);
return cmp;
}
memcmp 而非 strcmp 是二进制安全比较的关键。
5.7 SDS 与 C string 互操作
SDS 的 buf[] 末尾始终维护一个 \0 字节（不计入 len），这使得 SDS 可以直接传给 C 标准库函数：
sds s = sdsnew("hello");
printf("%s\n", s); // 直接传给 printf（利用 \0 终止）
strlen(s); // 可以调用（但 Redis 内部用 sdslen()）
strcmp(s, "hello"); // 可以调用（但二进制数据可能截断）
注意：这种兼容性仅对不含 \0 的字符串安全。对于二进制数据，必须使用 sdslen() + memcmp()，而不是 strlen() + strcmp()。
5.8 embstr 与 raw 的切换机制深度分析
这是第四章中提到的知识点的底层实现细节：
5.8.1 embstr 的内存分配
/* src/object.c */
robj *createEmbeddedStringObject(const char *ptr, size_t len) {
/* 关键：robj 和 sdshdr8 在同一次 zmalloc 中分配 */
robj *o = zmalloc(sizeof(robj) + sizeof(struct sdshdr8) + len + 1);
struct sdshdr8 *sh = (void*)(o + 1); // sdshdr8 紧跟在 robj 之后
o->type = OBJ_STRING;
o->encoding = OBJ_ENCODING_EMBSTR;
o->ptr = sh + 1; // ptr 指向 sdshdr8 的 buf 字段（即实际字符串内容）
o->refcount = 1;
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
} else {
o->lru = LRU_CLOCK();
}
sh->len = len;
sh->alloc = len;
sh->flags = SDS_TYPE_8;
if (ptr == SDS_NOINIT)
sh->buf[len] = '\0';
else if (ptr) {
memcpy(sh->buf, ptr, len);
sh->buf[len] = '\0';
} else {
memset(sh->buf, 0, len+1);
}
return o;
}
关键行：zmalloc(sizeof(robj) + sizeof(struct sdshdr8) + len + 1)
计算：16 + 3 + len + 1 = len + 20 字节，向上取整到 jemalloc 的大小类：
- len = 5（"hello"）：25 字节 → 分配 32 字节
- len = 44（最大 embstr）：64 字节 → 分配 64 字节（刚好是一个 jemalloc 大小类）
5.8.2 embstr 修改时的转换
/* src/t_string.c：APPEND 命令实现 */
void appendCommand(client *c) {
// ...
o = lookupKeyWrite(c->db, c->argv[1]);
if (o == NULL) {
// key 不存在，创建新对象
o = createRawStringObject(c->argv[2]->ptr, sdslen(c->argv[2]->ptr));
} else {
// key 存在，必须确保是可修改的 raw 字符串
if (checkStringLength(c, curlen, append) != C_OK) return;
/* 关键：dbUnshareStringValue 将 embstr 转为 raw */
o = dbUnshareStringValue(c->db, c->argv[1], o);
// 现在 o 是 raw 编码，可以安全修改
o->ptr = sdscatlen(o->ptr, append, applen);
}
// ...
}
dbUnshareStringValue 的内部逻辑：
robj *dbUnshareStringValue(redisDb *db, robj *key, robj *o) {
if (o->refcount != 1 || o->encoding == OBJ_ENCODING_EMBSTR) {
robj *decoded = getDecodedObject(o);
// getDecodedObject 将 INT/EMBSTR → RAW
o = createRawStringObject(decoded->ptr, sdslen(decoded->ptr));
decrRefCount(decoded);
dbOverwrite(db, key, o);
}
return o;
}
5.8.3 44 字节边界的严格验证
/* src/object.c */
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
return createEmbeddedStringObject(ptr, len);
else
return createRawStringObject(ptr, len);
}
# 验证边界
redis-cli SET key44 "$(python3 -c "print('x'*44, end='')")"
redis-cli OBJECT ENCODING key44 # → embstr
redis-cli SET key45 "$(python3 -c "print('x'*45, end='')")"
redis-cli OBJECT ENCODING key45 # → raw
5.9 SDS 的操作函数速查
| 函数 | 功能 | 时间复杂度 |
|---|---|---|
sdsnew(s) |
从 C 字符串创建 SDS | O(n) |
sdsempty() |
创建空 SDS | O(1) |
sdslen(s) |
获取长度 | O(1) |
sdsavail(s) |
获取剩余空间 | O(1) |
sdscat(s, t) |
追加 C 字符串 | O(n) |
sdscatsds(s, t) |
追加 SDS | O(n) |
sdscpy(s, t) |
复制 C 字符串到 SDS | O(n) |
sdsrange(s, start, end) |
截取子串（就地） | O(n) |
sdstrim(s, cset) |
去除两端指定字符 | O(n) |
sdscmp(s1, s2) |
二进制安全比较 | O(n) |
sdsdup(s) |
复制 SDS | O(n) |
sdsfree(s) |
释放 SDS | O(1) |
sdsMakeRoomFor(s, n) |
确保 n 字节额外空间 | O(n)（可能 realloc） |
sdsRemoveFreeSpace(s) |
释放预分配空间 | O(n)（realloc） |
5.10 SDS 在 Redis 中的使用统计
SDS 不只用于存储用户的 String 类型值，Redis 内部大量使用 SDS：
- key 名称：每个 key 都是一个 SDS
- Hash 的 field 和 value（listpack 模式下是内嵌二进制，HT 模式下是 SDS）
- ZSet 的 member：SDS
- Set 的成员（非 intset 模式）：SDS
- AOF 缓冲区：
server.aof_buf是一个 SDS，用于批量写入 AOF 文件 - 查询响应缓冲区：
client.querybuf是 SDS，存储客户端发来的命令
由此可见，SDS 是 Redis 内存系统的基础砖块，优化 SDS 的内存使用（通过编码选择和预分配策略）直接影响 Redis 的整体内存效率。
5.11 常见的 SDS 相关性能问题
5.11.1 大 Value 的 APPEND
# 反模式：频繁 APPEND 到大字符串
APPEND log:2024-01 "line1\n" # 6 字节
APPEND log:2024-01 "line2\n" # 12 字节
# ... 持续 APPEND 直到字符串达到 100MB
问题：虽然有空间预分配，但当字符串超过 1MB 后，每次 APPEND 至少触发一次 realloc（额外分配 1MB）。100MB 的字符串执行 APPEND 需要复制整个 100MB 数据（realloc 的内存复制代价）。
解决方案：将大日志拆分为多个 key（如按小时分片）或使用 Redis Stream。
5.11.2 GETSET 触发 embstr → raw 不必要的转换
SET counter 0
INCR counter # 保持 INT 编码
GET counter # 返回 "1"（INT 编码，不转换）
APPEND counter "" # 即使追加空字符串，也会触发 INT → embstr → raw 转换！
避免对不需要修改的字符串执行任何写操作，保持编码不变。
5.12 小结
SDS 的设计是 Redis 高性能的重要基础：
- O(1) 长度查询：
len字段直接存储，无需扫描 - 安全的内存操作：
sdsMakeRoomFor在修改前确保容量 - 空间预分配：减少频繁操作下的 realloc 次数
- 惰性空间释放：避免截短操作后立即 realloc
- 二进制安全：
len字段而非\0定界，支持任意字节 - C 兼容性：
buf[]末尾的\0允许直接传给 C 函数 - 五种头结构：按字符串长度选择最小头，节省内存
结合第四章的 redisObject 编码机制，SDS 的 embstr/raw 选择与 robj 的编码层紧密协作：embstr 通过一次 malloc 将 robj 和 sdshdr8 合并，是 Redis 内存优化的典型范例。
理解 SDS 的内存行为，对于分析 Redis 的内存使用、优化数据设计、定位性能瓶颈都具有直接指导意义。后续章节将继续深入其他数据结构（listpack、skiplist、dict）的实现细节。