Redis 入门-第一篇-数据结构与对象-简单动态字符串（SDS）

简单动态字符串（simple dynamic string）(之后简称 SDS ) 是 Redis 的默认字符串表示，在 Redis 里面，C 字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方。

struct sdshdr {
  int  len;   // 字节数组已使用的字节数，尾部的 '\0' 结束符不算在内，这个空字符对于用户来说是透明的，它的空间分配以及添加都是由 SDS 函数自动完成的，遵循尾部添加 '\0' 结束符的好处是，SDS 可以直接使用部分 C 字符串函数库里面的函数
  int  free;  // 字节数组未使用的字节数
  char buf[]; // 字节数组，用于保存 SDS 
}

SDS 可以在 O(1) 时间复杂度获取自身长度，同时在修改 SDS 内容时，SDS API 会自动检查 SDS 的字节数组是否足够存放本次修改后的内容，如果不够，API 会自动对其扩容，杜绝了缓冲区溢出的可能。

因为 C 字符串并不记录自身的长度，所以对于一个包含了 N 个字符的 C 字符串来说，这个字符串的底层实现总是一个 N + 1 个字符长的数组（额外的一个字符空间用于保存空字符 '\0' ）。因为 C 字符串的长度和底层数组长度之间存在着这种关联性，所以每增长或缩短一个 C 字符串，程序总是要对保存着这个 C 字符串的底层数组进行一次内存重分配操作，否则就会产生内存溢出或内存泄漏。

在一般的程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重分配是可以接受的，但是 Redis 作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串都要执行一次内存重分配的话，那么光是执行内存重分配的时间都会占去修改字符串所用时间的一大部分，如果这种修改操作频繁发生的话，可能还会对性能造成影响。为了避免 C 字符串这种缺陷，SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联，在 SDS 中，buf 数组长度不一定就是字符数量加一，数组里可以包含未使用的字节，而这些字节的数量就由 SDS 的 free 属性记录，通过字节数组未使用字节数 (free) 这个成员变量，SDS 实现了空间预分配和惰性空间释放两种优化策略。

空间预分配用于优化 SDS 的字节数组增长操作，当 SDS 的 API 对一个 SDS 进行修改，并且需要扩容时，程序不仅会为 SDS 分配必须的空间，还为 SDS 分配空闲空间。其中，额外分配的空闲空间由如下策略决定：

• 如果扩容后 len 将小于 1 MB ，那么分配的空闲空间将和 len 的大小一样，即 free 等于 len，这时候 buf 数组的实际字节大小为 free + len + 1。
• 如果扩容后 len 将大于 1 MB ，那么分配的空闲空间为 1MB 大小。

惰性空间释放用于优化 SDS 的字符串缩短操作，当 SDS 的 API 需要缩短保存的字符串时，程序并不立即试用版内存重分配来回收多余的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。与此同时，SDS 也提供了相应的 API ，让我们可以在有需要时，真正的释放 SDS 的空闲空间，所以不用担心惰性空间释放策略会造成内存浪费。

通过这种预分配策略，SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。此外，C 字符串中的字符必须符合某种编码，并且除了字符串末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串的结尾，这些限制使得 C 字符串只能保存文本数据，而不能保存图片、音频、视频、压缩文件等二进制数据。比如下面这样的字符串，用 C 字符串来保存的话后面的 ’Now‘ 就会被忽略掉。

因为 SDS 是靠 len 属性来判断是否读完 buf 数组中的所有字符的，所以不会存在 C 字符串这种问题，所以我们说 SDS 是二进制安全的，所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤或假设，数据在写入时是什么样，在读出的时候就是什么样。这也是我们将 SDS 的 buf 属性称为字节数组的原因，因为 Redis 不是用这个数组来保存字符，而是保存一系列二进制数据。

表1.1 C 字符串和 SDS 之间的区别

C 字符串 SDS 获取字符串长度的时间复杂度为 O(N) 获取字符串长度的时间复杂度为 O(1) API 是不安全的，可能会造成缓冲区溢出或内存泄漏 API 是安全的，不会造成缓冲区溢出或内存泄漏 修改字符串长度 N 次必然要执行 N 次内存重分配 修改字符串长度 N 次最多要执行 N 次内存重分配 只能保存文本数据 可以保存文本或二进制数据 可以使用所有 <string.h> 库中的函数 可以使用部分 <string.h> 库中的函数

表 1.1 C 字符串和 SDS 的区别

C 字符串	SDS
获取字符串长度的时间复杂度为 O(N)	获取字符串长度的时间复杂度为 O(1)
API 是不安全的，可能会造成缓冲区溢出或内存泄漏	API 是安全的，不会造成缓冲区溢出或内存泄漏
修改字符串长度 N 次必然要执行 N 次内存重分配	修改字符串长度 N 次最多要执行 N 次内存重分配
只能保存文本数据	可以保存文本或二进制数据
可以使用所有 <string.h> 库中的函数	可以使用部分 <string.h> 库中的函数