Redis 数据结构之SDS

Redis 是用 C 语言写的，但是为了解决C语言字符数组的存储问题，它构建了一种名为简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示。

用于存储二进制数据的一种结构, 具有动态扩容的特点。其实现位于src/sds.h与src/sds.c中，其中sdshdr是头部, buf是真实存储用户数据的地方

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    
    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];
};

• free 属性的值为0，表示这个 SDS 没有分配任何未使用空间。
• len 属性的值为5，表示这个 SDS 保存了一个五字节长的字符串。
• buf 属性是一个 char 类型的数组， 数组的前五个字节分别保存了 ‘R’ 、 ‘e’ 、 ‘d’ 、 ‘i’ 、 ‘s’ 五个字符， 而最后一个字节则保存了空字符 ‘’

SDS 遵循 C 字符串以空字符结尾的惯例， 保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面， 并且为空字符分配额外的 1 字节空间， 以及添加空字符到字符串末尾等操作都是由 SDS 函数自动完成的， 所以这个空字符对于 SDS 的使用者来说是完全透明的

C语言用字符数组存储的问题：

1. 获取长度需要遍历整个数组，O(n)复杂度
2. 字符串append需要扩容
3. 无法存储二进制数据（例如图片），因为会对字符解释成字符串的结尾符

• 常数复杂度获取字符串长度
  由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。而对于 C 语言，获取字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。通过 strlen key 命令可以获取 key 的字符串长度。

• 杜绝缓冲区溢出
  在 C 语言中使用strcat函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。而对于 SDS 数据类型，在进行字符修改的时候，会首先根据记录的 len 属性检查内存空间是否满足需求，如果不满足，会进行相应的空间扩展，然后在进行修改操作，避免出现缓冲区溢出

• 减少修改字符串的内存重新分配次数
  C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。
  对于SDS，由于len属性和alloc属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：

  1. 空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数
  2. 惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节的数量记录下来，等待后续使用

• 二进制安全
  因为C字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串，因此C字符串无法正确存取；而所有 SDS 的API 都是以处理二进制的方式来处理buf里面的元素，并且 SDS 不是以空字符串来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束。

• 兼容部分 C 字符串函数
  虽然 SDS 是二进制安全的，但是一样遵从每个字符串都是以空字符串结尾的惯例，这样可以重用 C 语言库中的一部分函数

空间预分配策略：

• 如果对SDS进行修改之后，SDS的长度未超过1MB，分配len属性大小的未使用空间（此时free属性的值=len属性）
• 如果对SDS进行修改之后，SDS的长度超过1MB，分配 1 MB 的未使用空间

Redis的字符串表示为SDS，而不是C字符串（以结尾的char*）， 它是Redis 底层所使用的字符串表示，它被用在几乎所有的Redis 模块中

一般来说，SDS 除了保存数据库中的字符串值以外，SDS 还可以作为缓冲区（buffer）：包括 AOF 模块中的AOF缓冲区以及客户端状态中的输入缓冲区

参考资料：

1. Redis 设计与实现
2. SDS定义
3. SDS简单动态字符串