总结 Redis 封装 C 字符串为 SDS 的实现。
SDS 结构
结构定义
SDS 全称 Simple Dynamic String(简单动态字符串),是 Redis 对 C 原生字符串的封装,结构定义如下:
1 | // sds 是 char * 的类型别名,用于指向 sdshdr 头部的 buf 字符串 |
len:有符号
int
类型,占 4 字节,最大能表示2^31 B
=2^21 KB
=2^11 MB
=2 GB
大的数据。但 Redis 把单 key 字符串值最长限制在了512MB
。参考:maximum-value-size-in-redisbuf:声明时无长度的柔性数组,是 C99 标准中的不完整类型,虽然结构体中的各字段在内存上是连续的,但柔性数组空间并不计入结构体总内存:
1
printf("%zu\n", sizeof(struct sdshdr)); // 8
内存布局
假设存入字符串 “Redis”,其内存布局如下:
64 位 Linux 上各内存段长度验证:
1 | int main() { |
SDS API 实现
源码:sds.c,几个重要的 API 实现:
sdslen
O(1) 复杂度返回字符串长度。直接让 SDS 左移 2 个 int 长度寻址,读取字符串的长度后返回:
1 | static inline size_t sdslen(const sds s) { |
sdsnew
注意 zmalloc
没有为 buf 柔性数组分配内存,其值是用 memcpy
高效复制字符串的值进行初始化的:
1 | // 新建 sds |
sdsclear
惰性删除,将 SDS 清空为空字符串,未释放的空间会保留给下次分配使用:
1 | void sdsclear(sds s) { |
sdsMakeRoomFor
Redis 的内存预分配策略根据新内存字节数决定:
[0, 1 MB)
:翻倍增长[1, ∞)
:每次仅增长 1 MB
1 | // 扩展 sds 空间增加 addlen 长度,进行内存预分配 |
sdscat
用 memcpy
高效地拷贝内存,将字符串连接到 SDS 尾部,其使用 sdsMakeRoomFor
进行空间预分配:
1 | // 将长度为 len 的字符串 t 追加到 sds |
注意相近的 sdscpy
函数会将字符串覆盖式地拷贝到 SDS 中。
sdsfree
释放 SDS 整块内存:
1 | void sdsfree(sds s) { |
SDS 优点
结合如上的 API 实现,总结下 SDS 相比 C 原生字符串的 4 个优点:
O(1) 复杂度获取字符串长度
C 字符串是最后一个元素为 \0
的字符数组,获取长度需从头到尾 O(N) 遍历。
SDS 结构中用 len 字段记录了字符串长度,并在各种增删操作中动态维护其长度,使用 strlen
直接读取字段值即可。
避免缓冲区溢出
C 字符串的 strcpy
操作,若 dst
未分配足够内存,应用有 crash 或被缓冲区溢出攻击的风险。
SDS 在操作字符串前会检查其空间,若不够则预分配,从根源上杜绝溢出。
二进制安全
C 以 '\0'
作为字符串分隔符,故不能保存如图片等穿插大量空字符的数据。
SDS API 用 len 长度来界定字符串边界,存入什么就取出什么,故操作二进制数据是安全的。但 SDS 同样以 '\0'
作为字符串的分隔符,方便直接重用 string.h
中的丰富库函数。
内存预分配与惰性释放
C 的字符串每次增长或缩减,都要 realloc 重分配内存。
SDS 每次以成倍或加 1MB 的方式扩展空间,且清空时不释放内存预留下次使用。从而将 N 次字符串操作,内存重分配次数从必定 N 次减少为最多 N 次。
总结
Redis 封装 C 原生字符串为 SDS,并实现了取长度、复制、比较、内存预分配等 API 供上层使用,可以看到 API 实现中对 buf
直接进行内存拷贝等操作,十分高效。
因为封装,SDS 相比原生字符串中间隔了一层取地址等操作,但其 API 耗时并未成为 Redis 的性能瓶颈,设计上十分精巧。