【Redi设计与实现】第二章：简单动态字符串

2.1 SDS的定义

每一个 sdshdr 结构表示一个 SDS 值：

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

实例：

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

SDS遵循C字符串以空字符串结尾 的惯例，保留空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节空间。

我们看一下另一个实例：

与之前SDS最大的区别是：这里的 free 属性的值为5，图中使用五个空格来表示五字节的未使用空间

这个 free 属性在 SDS 中的作用是什么呢？

2.2 SDS和C字符串的区别

C语言使用长度为 N+1 的字符数组来代表长度为 N 的字符串，并且数组的最后一个值为 \0。

例如：

C语言这种简单的字符串表示方式，并不能满足 Redis 对字符串在安全性、效率以及功能方面的要求。

我们接下来来看一下，C语言字符串和SDS的区别，并说明SDS比C语言字符串更适合Redis的原因。

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

我们都知道，对于C字符串来说，我们要想获取它的长度，必须从头遍历一遍，直到遇见代表字符串结尾的空字符为止，这个操作的时间复杂度为：O(N)

实例如下：

和C字符串是不同的，我们的SDS的len属性代表了SDS本身的长度，所以获取一个SDS长度为5字节。

设置和更新SDS长度的工作是由SDS的API在执行时自动完成的，使用SDS无须进行任何手动更改长度的操作。

通过使用SDS而不是字符串，Redis将获取字符串长度所需要的时间复杂度从O(N)降低到了O(1)，这确保了获取字符串长度不会成为Redis的性能瓶颈。

比如，我们对一个很长的字符串使用 STRLEN 命令，也不会对性能有所影响，因为 STRLEN 的时间复杂度为：O(1)。

2.2.2 杜绝缓冲区溢出

除了获取字符串长度的复杂度高以外，C字符串不记录自身长度带来的另一个问题就是：容易造成缓冲区溢出（Buffer overflow）

举个例子：我们现在要拼接 dest和 src 两个字符串，使用 char *strcat(char *dest, const char *src)

因为C字符串不记录自身的长度，所以strcat假定用户在执行这个函数的时候，已经为dest分配了足够多的内存，可以容纳src字符串的所有内容，而这个假设不成立时，就会产生缓冲区溢出。

从另一个例子来看，假设程序里有两个在内存中紧邻的C字符串s1和s2，其中s1保存了字符串"Redis"，而s2则保存了字符串"MongoDB"，如图所示：

如果一个程序员执行：strcat(s1，"Cluster");

将s1的内容修改为"Redis Cluster"，但是他忘记了在执行strcat之前，要为s1分配足够的空间，否则，s1的数据就会溢出到s2所在的空间中，导致s2保存的内容被意外的修改。如图：

与C字符串不同，SDS的空间分配策略完全杜绝了缓冲区溢出的发生。

当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需要的要求，

如果不满足的话，API会自动将SDS的空间扩展至修改所需要的大小，然后执行实际的修改操作。所以使用SDS不需要自己手动修改SDS的空间大小，也不会产生缓冲区溢出。

举个例子：在我们的SDS的API里面，也有一个执行拼接的 sdscat 函数，它可以将一个C字符串拼接到给定SDS的字符串后面，但是在执行拼接的操作之前，sdscat会先检查给定SDS的空间是否足够，如果不够的话，sdscat就会先扩展SDS的空间，然后执行拼接操作。

例如，我们执行：sdscat(s，"Cluster")

其中SDS值如图所示：

在执行sdscat之前，会先检查操作之前的s的长度是否足够，如果发现s的长度不够的话，sdscat就会先进行扩容，然后在执行拼接的操作，如图：

注意，图2-10所示的SDS，sdscat不仅对这个SDS进行了拼接的操作，还会SDS分配了13字节的未使用空间，并且拼接完后的字符串也正好是13字节长，这不是巧合，它和SDS的空间分配策略有关。

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

因为我们的C字符串并不记录自身的长度，所以对于一个包含N个字符的C字符串来说，这个C字符串的底层实现总是一个N+1个字符长的数组（额外的一个用于保存空字符）。如果我们要对这个C字符串进行操作的话，不论是增长还是缩短，程序都要对这个C字符串进行一次内存重分配操作：

• 如果程序执行的是增长字符串的操作，比如拼接（append），那么在执行这个操作之前，程序需要通过内存重分配来扩展底层数组的空间大小-----如果忘了，就会产生缓冲区的溢出。
• 如果程序执行的是缩短字符串的操作，比如截断（trim），那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间-----如果忘了，就会产生内存泄漏。

因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以，他通常是一个比较耗时的操作：

• 在一般程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重分配是可以接受的。
• 但是Redis作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串长度都需要执行一次内存重分配的话，会造成时间复杂度的增高，带来大量的性能损失。

为了避免C字符串的这种缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联：

在SDS中，buf数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量由SDS的free属性记录。

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

2.2.3.1 空间预分配

空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须的空间，还会为SDS分配额外的未使用空间。

额外分配的空间数量的公式如下：

• 如果对SDS进行修改之后，SDS的长度（也就是len的值）将小于1MB，那么程序分配和len属性相同大小的未使用空间，这个时候SDS的len属性值将和free属性的值相等。
  
• 如果对于SDS修改以后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。举个例子，如果进行修改之后，SDS的len将变成30MB，那么程序会分配1MB未使用空间，SDS的buf数组的实际长度为：10MB + 1MB + 1byte。

通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

SDS将原来必定N次的内存重分配，现在变成了最多N次的内存重分配。

2.2.3.2 惰性空间释放

惰性空间释放用于优化SDS的字符串缩短的操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短多出来的字节，而是使用free属性将这些字节的数量给记录起来，等待着以后使用。

例如：我们移除SDS中所有在C字符串出现过的字符

sdstrim(s, "XY"); // 移除SDS字符串中的所有‘x’和‘y’

会将我们的SDS修改为图2-15的样子：

我们可以看到，SDS的free属性已经变为8，代表当前buf中有8个空闲的字符空间。

我们可以想一下，为什么不直接删除掉这些空闲的内存而是将它用一个free属性来进行标记？

我们知道，SDS字符串增长的时候，会先去检查该SDS字符串是否有空余的空间，防止缓冲区溢出。如果有空间的话，则会直接进行拼接，无空间，则会开辟新的空间放置新的字符串。

我们使用free属性来标记的原因：假如我们在截断之后，又进行了拼接的操作。如果我们在截断之后删除了空闲的空间，就会导致我们拼接的时候，要重新进行内存的分配，造成时间和性能的浪费。不删除空闲空间的话，只需要减小我们的free属性就可以了。

2.2.4 二进制安全

C字符串中的字符必须符合ASCII码的规范，并且除了字符串末尾以外，字符串里面不能包含空字符，否则会被程序认为这是字符串的结束符。

这些限制使我们的C字符串只能保存文本数据，而不能保存图片、音频、视频等二进制数据。

例如：

这种的话，我们的程序只能识别“Redis”，识别不到“Cluster”

但对于SDS来说，无论保存什么数据都没有问题，因为我们SDS在读取的时候，使用的是len的值判断字符串是否结束。

通过使用二进制安全的SDS，而不是C字符串，使得我们的Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。

2.2.5 兼容部分C字符串函数

对于SDS来说，一定程度上也兼容了C的一些函数，比如：

2.2.6 总结

C字符串和SDS字符串的区别：