第 2 章 简单动态字符串

Redis 没有直接使用 C 语言的字符串来表示（即以空字符结尾的字符数组），构建一张简单动态字符串 SDS 的抽象类型，作为默认字符串

在 Redis 中，C 字符串作为字符串字面量，使用在没有对字符串修改的地方，如打印日志：

但是需要的不仅仅是字符串字面量时，而是可以被修改的字符串值时，就会使用 SDS 来表示，如包含字符串值的键值对底层都是 SDS 实现

• 键是字符串对象，也是 SDS
• 值是字符串对象，也是 SDS

SDS 还被用作缓冲区

• AOF 模块的 AOF 缓存区
• 客户端状态的输入缓存区

2.1 SDS 的定义

每个 sds.h/sdshdr 结构表示一个 SDS 值

• free 为 0 ，表示 SDS 没有分配任何未使用的空间

• len 为 5，表示 SDS 存储了 5 字节的字符串

• buf 为 char 类型数组，表示存储的字符，最后一个字符是空字符 '\0'

  • 空字符不在 SDS len 计算内，自动分配 1 字节空间，添加到 字符串末尾等操作为 SDS 函数自动完成

  • 好处：直接重用 C 字符串函数库里面的函数

  • 例子，s 指针指向所示 SDS，于是可以直接使用<stdio.h>/printf函数进行打印

    • printf("%s", s->buf);

  

  与图 1 类似，区别的是 SDS 为 buf 数组分配了 5 字节未使用空间， free 值为 5

2.2 SDS 与 C 字符串的区别

传统 C 语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串，且字符数组最后一个元素是空字符 '\0'

不能满足 Redis对字符串在安全性、效率性以及功能方面的要求

2.2.1 常数复杂度获取字符串长度

C 字符串没有记录自身的长度信息，所以为了得到 C 字符串长度，需要遍历整个字符串，直到代表末尾的空字符串 '\0'，时间复杂度 O(N)

SDS 则在 len 属性中记录了 SDS 本身的长度，时间复杂度 O(1),设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成

2.2.2 杜绝缓存区溢出

C 字符串容易造成缓冲区溢出

<string.h>/strcat函数可以将 src 字符串的内容拼接到 dest 字符串末尾，但 dest 字符串没有足够内存时则会溢出

SDS 空间分配策略杜绝了发送缓冲区溢出的可能性：

当 SDS API 对 SDS 进行修改时，会先检查 SDS 的空间是否满足修改所需的要求，不满足则会将 SDS 的空间扩展只执行修改所需的大小，再执行实际的修改，因此不会缓冲区溢出

SDS API 中 sdscat函数可以将 C 字符串拼接到 SDS 保存的字符串后，但会按照上述的方法山西实现

已存在的字符串长度 len 与未分配的长度一致

2.2.3 减少修改字符串时带来的内存重分配次数

内存重分配涉及复杂的算法，且可能需要执行系统调用，比较耗时

• 在一般程序中修改在字符串长度的情况不太常出现，每次修改执行内存重分配是可接受的
• Redis 作为数据库，速度要求严苛，数据被频繁修改，每次修改都进行内存重分配，则看内存重分配的时间会占去所用时间的一大部分，甚至对性能造成影响

通过未分配空间，SDS 实现了空间预分配与惰性空间释放两种优化策略

1.空间预分配

用于优化 SDS 的字符串增长操作：

​ 当 SDS 的 API 对 SDS 修改并需要扩展时，不仅会分配修改所必须要的空间，还会分配额外的未使用空间

额外分配的空间数量决定：

• 对 SDS 修改之后的 len 小于 1 MB，则程序分配和 len 相同的大小的 free 空间，假如修改后 len 为 13 字节，则 free 也为 13 字节，buf 数组的实际长度为 13 + 13 + 1 = 27 字节

• 大于 1 MB，则会分配 1 MB 未使用空间

在扩展 SDS 空间之前，SDS API 会检查未使用空间是否足够，足够则直接使用未使用空间，无须执行内存分配

通过预分配策略，SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次

2.惰性空间释放

用于优化 SDS 的字符串缩短操作：

​ 当需要缩短时，不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性来记录这些字节的数量记录

同时 SDS 也提供了相应的 API，在有需要时，真正释放 SDS 的未使用空间，不会因为惰性空间释放造成内存浪费

2.2.4 二进制安全

C 字符串字符需要符合某种编码 （如 ASCII ），除了字符串末尾之外，不能包含空字符串，否则会被误认为是字符串结尾

SDS API 都是二进制安全的，会以处理二进制的方式来处理 SDS 存放在 buff 数组里的数据，不会对其中的数据做任何限制、过滤或者假设，即 buff 属性被称字节数组的原因

2.2.5 兼容部分 C 字符串函数

SDS 一样遵循 C 字符串以空字符串结尾的惯例，为了让那些保存文本数据的 SDS 可以重用一部分 <string.h>库定义的函数

2.2.3 总结

2.3 SDS API

2.4 重点回顾

• Redis 只会使用 C 字符串作为字面量，大多数情况使用 SDS 作为字符串表示
• SDS 优点
  • 常数复杂度获取字符串长度
  • 杜绝缓冲区溢出
  • 减少修改字符串长度时所需的内存重分配次数
  • 二进制安全
  • 兼容部分 C 字符串函数