len / alloc / flags · 五档头部 · 预分配

SDS：Redis 的字符串

C 的字符串是一个 char* 加一个结尾的 \0。这个约定省掉了长度字段，代价落在三处：取长度要从头扫到 \0，是 $O(n)$ ；内容里不能出现 \0，否则字符串在那里就断了；追加要调用方自己算够不够放，算错就是缓冲区溢出。

Redis 存的是任意二进制数据，键与值都可能含 \0；它还要在热路径上频繁取长度。SDS（simple dynamic string）是它给出的替代品：在数据前面挂一个头部，把长度与容量显式记下来。

1 · 头部藏在指针之前

SDS 的类型定义是一个变长结构体，头部字段在前，buf 是柔性数组：

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;          /* 已用长度 */
    uint8_t alloc;        /* buf 容量, 不含头部与结尾的 NUL */
    unsigned char flags;  /* 低 3 位是档次编号, 高 5 位在 sdshdr5 里存长度 */
    char buf[];
};

关键在于 sds 这个类型就是 char *，而且它指向的是 buf 而非结构体开头。头部落在指针的负偏移上。sdslen 的做法是读 s[-1] 取出 flags，按低 3 位选档次，再回退相应字节数拿到 len。这一步是常数时间的字段读取，与字符串多长无关。

把指针对准 buf 换来一项兼容性：SDS 在数据末尾额外补一个 \0，且这个字节不计入 len。于是 printf("%s", s)、strcasecmp 这类只读的 C 函数可以直接吃一个 SDS，不必转换。写入类的 C 函数仍然不能用，它们不会去更新头部里的 len。

二进制安全同样是 len 带来的：定界靠长度字段，内容里的 \0 只是一个普通字节。末尾那个 \0 是给 C 函数看的兼容位，不是定界符。

2 · 五档头部与分档边界

一个头部要占多少字节，取决于 len 与 alloc 用几位表示。全用 64 位则任何短串都要背 17 字节头部，而 Redis 里的键大量是十几二十个字符。sds.h 的做法是按长度分档，sdsReqType 挑最小够用的一档：

档次	长度上限	`len` 与 `alloc`	头部字节
`sdshdr5`	31	挤在 `flags` 高 5 位，无 `alloc`	1
`sdshdr8`	255	`uint8_t`	3
`sdshdr16`	65535	`uint16_t`	5
`sdshdr32`	$2^{32}-1$	`uint32_t`	9
`sdshdr64`	$2^{64}-1$	`uint64_t`	17

图 2-1 · 给定长度时选中的头部档次、逐字段字节布局与总开销占比。可拖动长度扫过 31 / 255 / 65535 三处分档边界，观察开销的阶跃。

实测的总占用是头部加 alloc 加一个 NUL：31 字节的串占 33 字节，额外开销 2 字节，占 6.1%；再多一个字符落到 sdshdr8，占 36 字节，开销翻到 4 字节。开销的绝对值只在 2 到 18 之间跳，而它相对数据的占比在短串上很可观：16 字节的串开销占 11.1%，1000 字节的串只占 0.6%。

sdshdr5 有两处例外值得单记。其一，_sdsnewlen 里写着 if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;：空串一律升到 sdshdr8，因为空串多半是拿来接着追加的。其二，sdsavail 对 sdshdr5 直接返回 0，因为它没有 alloc 字段，记不住空余容量。任何一次追加都会走重新分配那条路，而那条路上有 if (type == SDS_TYPE_5) type = SDS_TYPE_8;。sdshdr5 省下的 2 字节只在「建好之后再不追加」的串上留得住。

顺带解释一个常被单独记忆的常数。Redis 的字符串对象在长度不超过 44 时用 embstr 编码，把 robj 与 SDS 一次分配在同一块内存里。44 这个数没有别的来历：16 字节的 robj，加 3 字节的 sdshdr8 头部，加 44 字节数据，加 1 字节 NUL，正好 64 字节，也就是一条 cache line。

注 · sds.h 里 sdshdr5 上方那行注释是 Note: sdshdr5 is never used, we just access the flags byte directly。初读会以为 Redis 根本不产生 sdshdr5 类型的串。它说的是这个 struct 定义在代码里没被引用过：长度直接从 flags 字节按位取，不必声明结构体变量。SDS_TYPE_5 本身在 _sdsnewlen 里照常产出，上表里那一行是真实存在的档次。

3 · 追加时的空间预分配

sdscatlen 先调 sdsMakeRoomFor 保证余量够，再 memcpy 并更新 len。余量够的时候整个调用不碰分配器；不够时按下面这段算新容量：

reqlen = newlen = (len+addlen);
if (greedy == 1) {
    if (newlen < SDS_MAX_PREALLOC) newlen *= 2;
    else newlen += SDS_MAX_PREALLOC;
}

SDS_MAX_PREALLOC 是 1 MB。小串按需求量翻倍，大串改为定量加 1 MB，避免一个 100 MB 的串一次要到 200 MB。

图 3-1 · 反复追加固定大小的块时，每一步的 len、alloc 与是否真的重新分配。可改块大小与追加次数，并关掉贪心预分配对照重分配次数。

实测逐字节追加一千次：贪心预分配下只重新分配 9 次，alloc 依次是 2, 6, 14, 30, 62, 126, 254, 510, 1022；关掉贪心（sdsMakeRoomForNonGreedy）则一千次全部重新分配。这是动态数组那套成倍扩容原封不动搬到字节串上，摊还结论也照搬。

有一处代价是动态数组没有的。头部换档时不能用 realloc：新头部更宽，数据必须整体后移，realloc 只会原地扩尾巴。sds.c 的对应分支是先 s_malloc_usable 一块新的，memcpy 过去，再 s_free 旧的。逐字节追加那一串里，第 255 次追加把 alloc 抬到 510，恰好跨过 255 的分档线，sdshdr8 换成 sdshdr16，这一次就是拷贝而非原地扩展。

4 · 惰性释放

sdsclear 的实现只有两行：sdssetlen(s, 0) 加 s[0] = '\0'。alloc 原样保留，那块内存一个字节也不还。

理由与动态数组不缩容一样，见扩容的摊还与增长因子 §4。被清空的串多半马上又要被写满，还回去再要一遍是白花两次分配。真要收，得显式调 sdsRemoveFreeSpace，Redis 只在少数几处这么做，例如把客户端查询缓冲区里的富余空间定期修掉。

代价同样是要使用方心里有数：STRLEN 报的是 len，而 MEMORY USAGE 算的是 alloc 加头部。一个反复 APPEND 到很大再被覆盖成短串的 key，两个数字可以差出一个数量级。

5 · 参考文献

Sanfilippo, S. SDS: Simple Dynamic Strings library for C. redis/src/sds.h 与 sds.c（Redis 7.4）。
Redis. Memory optimization. hash-max-listpack-value 与 embstr 一节。
Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd ed., §5.5 字符指针与数组). Prentice Hall.