简介

  Redis 没有直接使用C语言的字符串表示，而是构建了一种称为简单动态字符串（Simple Dynamic String，SDS）的抽象数据类型，并将SDS用作 Redis 的默认字符串表示。
  在Redis中，C字符串只会用作字符串字面量，用在一些无需对字符串进行修改的地方， 比如打印日志：
redisLog(REDIS_WARNING, "Redis is running...");

举例说明

如果客户端执行命令：

redis> SET msg "hello world"
OK

那么 Redis 将在数据库中创建了一个新的键值对，其中：
键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串"msg"的SDS；
键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串"hello world"的 SDS
又比如说，如果客户端执行命令：

redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3

那么 Redis 将在数据库中创建一个新的键值对，其中：
键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串"fruits"的SDS；
键值对的值是一个列表对象，列表对象包含了三个字符串对象，这三个字符串对象分别由三个SDS实现： 第一个SDS保存着字符串 "apple" ，第二个SDS保存着字符串"banana"， 第三个SDS保存着字符串"cherry"。

  除了用来保存数据库中的字符串值之外， SDS 还被用作缓冲区（buffer）： AOF 模块中的 AOF 缓冲区， 以及客户端状态中的输入缓冲区， 都是由 SDS 实现的， 在之后介绍 AOF 持久化和客户端状态的时候， 我们会看到 SDS 在这两个模块中的应用。

SDS 的定义

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

图 2-2 展示了一个SDS示例：
free属性的值为5，表示这个 SDS 有5字节的空闲空间；
len属性的值为5，表示这个SDS保存了一个5字节长的字符串；
buf 属性是一个 char 类型的数组， 数组的前五个字节分别保存了 'R' 、 'e' 、 'd' 、 'i' 、 's' 五个字符， 然后使用一个字节保存空字符 '\0'，最后有5个空闲字节 。

图 2-2

  遵循空字符结尾这一惯例的好处是，SDS可以直接重用一部分C字符串函数库中的函数。举个例子， 如果我们有一个指向SDS的指针s，那么我们可以直接使用 stdio.h/printf 函数，通过执行以下语句：

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

来打印出SDS保存的字符串值 "Redis"，而无须为SDS编写专门的打印函数。

SDS与C字符串的区别

  根据传统，C语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串， 并且字符数组的最后一个元素总是空字符 '\0' 。
比如， 图 2-3 就展示了一个值为 "Redis" 的 C 字符串：

图 2-3
  C语言使用的这种简单的字符串表示方式，并不能满足 Redis 对字符串在安全性、效率、以及功能方面的要求，本节接下来的内容将详细对比C字符串和SDS之间的区别，并说明 SDS 比C字符串更适用于Redis的原因。

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

  因为C字符串并不记录自身的长度信息，所以为了获取一个C字符串的长度，程序必须遍历整个字符串，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为 O(N) ；和C字符串不同，因为SDS在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度仅为 O(1) 。
  通过使用SDS而不是C字符串，Redis 将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1) ，这确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。
  比如说，因为字符串键在底层使用SDS来实现，所以即使我们对一个非常长的字符串键反复执行如下命令，也不会对系统性能造成任何影响 ：

jedis.strlen("a"); // 获取键为a的SDS的长度

杜绝缓冲区溢出

  除了获取字符串长度的复杂度高之外，C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出。举个例子， strcat 函数可以将 src 字符串中的内容拼接到 dest 字符串的末尾：

char *strcat(char *dest, const char *src);

  因为C字符串不记录自身的长度， 所以strcat假定用户在执行这个函数时， 已经为dest分配了足够多的内存，可以容纳src字符串中的所有内容，而一旦这个假定不成立时， 就会产生缓冲区溢出。
  例如，假设程序里有两个在内存中紧邻着的C字符串 s1 和 s2 ， 其中 s1 保存了字符串 "Redis" ， 而 s2 则保存了字符串 "MongoDB" ， 如图 2-7 所示：

图 2-7

如果一个程序员执行：

strcat(s1, "Cluster");

将 s1 的内容修改为 "Redis Cluster" ， 但粗心的他却忘了在执行 strcat 之前为 s1 分配足够的空间， 那么在 strcat 函数执行之后， s1 的数据将溢出到 s2 所在的空间中， 导致 s2 保存的内容被意外地修改。
  与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当 SDS API 需要对 SDS 进行修改时，API会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出问题。
  举个例子， SDS 的 API 里面也有一个用于执行拼接操作的函数， 它可以将一个C字符串拼接到给定SDS所保存的字符串的后面，但是在执行拼接操作之前，该函数会先检查给定 SDS 的空间是否足够， 如果不够的话，该函数就会先扩展 SDS 的空间， 然后才执行拼接操作。
比如说， 如果我们执行：

jedis.append("a", "cd"); // 在键为a的SDS后面拼接上字符串cd

那么append将在执行拼接操作之前检查 a 的长度是否足够，在发现 a 目前的空间不足以拼接 "cd" 之后，append就会先扩展 a 的空间， 然后才执行拼接 "cd" 的操作。

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

  正如前两个小节所说， 因为C字符串并不记录自身的长度，所以对于一个包含了 N 个字符的C字符串来说， 这个C字符串的底层实现总是一个 N+1 个字符长的数组（额外的一个字符空间用于保存空字符）。
  因为 C 字符串的长度和底层数组的长度之间存在着这种关联性， 所以每次增长或者缩短一个C字符串，程序都总要对保存这个C字符串的数组进行一次内存重分配操作：

• 如果程序执行的是增长字符串的操作， 比如拼接操作（append）， 那么在执行这个操作之前， 程序需要先通过内存重分配来扩展底层数组的空间大小 —— 如果忘了这一步就有可能产生内存溢出；
• 如果程序执行的是缩短字符串的操作， 比如截断操作（trim）， 那么在执行这个操作之后， 程序需要通过内存重分配来释放字符串不再使用的那部分空间 —— 如果忘了这一步就有可能产生内存泄漏；
    因为内存重分配涉及复杂的算法， 并且可能需要执行系统调用， 所以它通常是一个比较耗时的操作：
• 在一般程序中， 如果修改字符串长度的情况不太常出现， 那么每次修改都执行一次内存重分配是可以接受的。
• 但是 Redis 作为内存数据库， 经常被用于速度要求严苛、数据被频繁修改的场合， 如果每次修改字符串的长度都需要执行一次内存重分配的话， 那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分， 如果这种修改频繁地发生的话， 可能还会对性能造成影响。
  为了避免C字符串的这种缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联： 在 SDS 中， buf 数组的长度不一定就是字符数量加一， 数组里面可以包含未使用的字节， 而这些字节的数量就由SDS的 free 属性记录。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

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

• 如果对SDS进行修改之后，SDS的长度（也即是 len 属性的值）将小于1MB ， 那么程序分配和len属性同样大小的未使用空间， 这时 SDS len 属性的值将和 free 属性的值相同。 举个例子， 如果进行修改之后， SDS 的 len 将变成13字节， 那么程序也会分配 13 字节的未使用空间， SDS 的buf数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。
• 如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ， 那么程序会分配 1 MB 的未使用空间。 举个例子， 如果进行修改之后， SDS 的 len 将变成 30 MB ， 那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。
  通过空间预分配策略， Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。
  举个例子， 对于图 2-11 所示的 SDS 值 s 来说， 如果我们执行：

jedis.append("s", " Cluster");

那么将执行一次内存重分配操作， 将 SDS 的长度修改为 13 字节， 并将 SDS 的未使用空间同样修改为 13 字节， 如图 2-12 所示。

图 2-11
图 2-12

如果这时， 我们再次对 s 执行：

jedis.append("s", " Tutorial");

那么这次将不需要执行内存重分配： 因为未使用空间里面的 13 字节足以保存 9 字节的 " Tutorial" ， 执行 sdscat 之后的 SDS 如图 2-13 所示。

图 2-13

在扩展 SDS 空间之前， SDS API 会先检查未使用空间是否足够， 如果足够的话， API 就会直接使用未使用空间， 而无须执行内存重分配。

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

惰性空间释放

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

二进制安全

  C字符串中的字符必须符合某种编码（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、视频这样的二进制数据。
  举个例子， 如果有一种使用空字符来分割多个单词的特殊数据格式， 如图 2-17 所示， 那么这种格式就不能使用 C 字符串来保存， 因为 C 字符串所用的函数只会识别出其中的 "Redis" ， 而忽略之后的 "Cluster" 。

图 2-17

  虽然数据库一般用于保存文本数据， 但使用数据库来保存二进制数据的场景也不少见， 因此， 为了确保 Redis 可以适用于各种不同的使用场景， SDS 的 API 都是二进制安全的（binary-safe）： 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据， 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的， 它被读取时就是什么样。
  这也是我们将 SDS 的 buf 属性称为字节数组的原因 —— Redis 不是用这个数组来保存字符， 而是用它来保存一系列二进制数据。
  比如说， 使用 SDS 来保存之前提到的特殊数据格式就没有任何问题， 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束。
  通过使用二进制安全的 SDS ， 而不是 C 字符串， 使得 Redis 不仅可以保存文本数据， 还可以保存任意格式的二进制数据。