简单动态字符串 (SDS)【Redis 设计与实现】

发表于 | 分类于

内部实现

1
2
3
4
5
struct sdshdr {
  len int; // 所保存的字符串长度
  free int; // 未使用的字节长度
  char buf[]; // 字节数组，用于保存字符串
}

c 字符串通常是以空字符 ‘\0’ 结尾，所以一个 SDS 的长度为： len + free + 1

与 c 字符串的区别

类型 c 字符串 SDS
获取字符串长度 O(N) O(1)
是非 API 安全 存在缓冲区溢出风险 API 安全，无缓冲区溢出
是否二进制安全 非二进制安全 二进制安全
修改字符串导致内存分配 每次重新分配 N 次修改最多 N 次分配
是否兼容 <string.h> 标准库 完全兼容 部分兼容

获取字符串长度

  • c 字符串获取长度是逐个读取字符计算长度，时间复杂度为: O(N)
  • SDS 是通过 len 来获取字符串长度，时间复杂度为: O(1)

API 安全

  • c 字符串不会检查内存空间是否足够，当拼接字符串时，有可能会出现缓冲区溢出问题
  • SDS 则会根据 free 来判断空间是否足够，如果内存空间不足，则会申请内存空间，因此不会有缓冲区溢出问题

二进制安全

  • c 字符串是根据空字符 \0 来判断字符串是否结束，因此字符串中间不能有空字符， 只能用来保存文本内容，无法保存二进制数据
  • SDS 是通过 len 来判断字符串是否结束，因此既可以保存文本内容，又可以保存二进制数据

内存分配

  • c 字符串每次修改内容时都需要进行重新的内存分配
  • SDS 则是根据 free 判断空间是否足够，如果不足，重新内配， 并且当修改后的 len < 1M 时， 额外多分配 len 的长度， 此时 free = len ； 当缩短 SDS 字符串内容时， 并不会立即释放空间, 而是通过将 free 变大，记录剩余空间，以减少之后的再分配。（通过惰性释放避免内存浪费问题）