简单动态字符串 SDS

@[toc] --- ## SDS 的定义 <img src="https://cs-wiki.oss-cn-shanghai.aliyuncs.com/img/20220608175330.png" style="zoom:55%;" /> - `int len`：buf 中已使用空间的长度 - `int free`：**buf 中剩余可用空间的长度**（这个字段可以说是 SDS 的灵魂所在） - `char buf[]`：数据空间（SDS 遵循 C 字符串以空字符结尾的惯例） ## Redis 为什么要使用 SDS 而不是 C 字符串？ 主要有 5 点： 1）**O(1) 时间复杂度获取字符串长度** - C 字符串：获取一个 C 字符串的长度的时间复杂度是 O(N) - SDS：SDS 在 len 属性中记录了 SDS 本身的长度，所以获取一个 SDS 长度的复杂度仅为O(1) 2）**杜绝缓冲区溢出（buffer flow）** - C 字符串：举个例子，C 语言中的 `strcat` 函数可以将 src 字符串中的内容拼接到 dest 字符串的末尾：strcat(dest, src)。 因为 C 字符串不记录自身的长度，**所以 strcat 假定用户在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立时，就会产生缓冲区溢出** 假设程序里有两个在内存中紧邻着的C字符串s1和s2，其中 s1 保存了字符串 "Redis"，而 s2 则保存了字符串 "MongoDB"  如果一个程序员执行：strcat(s1, " Cluster"); 却忘了在执行 strcat之前为 s1 分配足够的空间，那么在 strcat 函数执行之后，s1 的数据将溢出到 s2 所在的空间中，导致 s2 保存的内容被意外地修改  - SDS：SDS 的【**空间预分配策略**】完全杜绝了发生缓冲区溢出的可能性（详细解释见下文） 3）**减少修改字符串时带来的内存重分配次数** - C 字符串：因为 C 字符串并不记录自身的长度，所以对于一个包含了 N 个字符的 C 字符串来说，这个 C 字符串的底层实现总是一个 N+1 个字符长的数组（额外的一个字符空间用于保存空字符）。**所以每次增长或者缩短一个C字符串，程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作** - 【缓冲区溢出】：如果程序执行的是增长字符串的操作，比如拼接操作（append），那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小——如果忘了这一步就会产生缓冲区溢出 - 【内存泄漏】：如果程序执行的是缩短字符串的操作，比如截断操作（trim），那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间——如果忘了这一步就会产生内存泄漏 > 内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作 > > 在一般程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重分配是可以接受的 > > 但是 Redis 作为缓存，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的话，会对性能造成影响 - SDS：SDS 通过未使用空间（free）解除了字符串长度和底层数组长度之间的关联 - 【空间预分配】：用于优化 SDS 的字符串增长操作，防止缓冲区溢出，并减少字符串增长时的空间重分配的次数 <u>当 SDS 的 API 对一个 SDS 进行修改，并且需要对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间 free</u> 如果对 SDS 进行修改之后，SDS 的长度（也即是 len 的值）将 < 1MB，那么程序分配和 len 属性同样大小的未使用空间，这时 `SDS.len = free` 如果对 SDS 进行修改之后，SDS 的长度将 >= 1MB，那么程序会分配 1MB 的未使用空间 - 【惰性空间释放】防止内存泄漏：用于优化 SDS 的字符串缩短操作，防止内存泄露，并减少字符串缩短时的空间重分配的次数 <u>当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用</u> 4）**二进制安全** - C 字符串：C 字符串中的字符必须符合某种编码（比如 ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾；这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据 - SDS：SDS 的 API 都是二进制安全的（binary-safe），所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样 > 这也是我们将 SDS 的 `char buf` 属性称为**字节数组**的原因：Redis 不是用这个数组来保存字符，而是用它来保存一系列二进制数据 5）**兼容部分 C 字符串函数** SDS 遵循 C 字符串以空字符结尾的惯例，使得其可以重用一部分 C 语言中 <string.h> 库定义的函数，避免不必要的代码重复