Redis设计与实现之简单动态字符串

川长思鸟来 2023-09-28 20:56 121阅读 0赞

### 简单动态字符串 ###

#### 什么是 SDS ####

`SDS` ，即 Simple Dynamic String，简单动态字符串。

Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组），而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型，并将 SDS 用作 Redis 的默认字符串表示。

在 Redis 里面，C 字符串只会作为字符串字面量（string literal）用在一些 `无须对字符串值进行修改的地方` ，比如打印日志。

当 Redis 需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis 就会使用 SDS 来表示字符串值，比如在 Redis 的数据库里面，包含字符串值的 `键值` 对在底层都是由 SDS 实现的。

#### SDS 的定义 ####

在 SDS 结构中包含：

buf
    len
    free

举例：

![e2cac2da41ba5a8d533c069853ef8113.jpeg][]

*  len 属性的值等于 5，表示在 SDS 中保存了一个五字节长度的字符串
 *  free 属性的值等于 0，表示在 SDS 中没有分配任何未使用的空间
 *  buf 属性是一个 char 数组，前五位保存了五个字符，在最后一个字节保存了一个空字符'\\0'

需要注意的是：SDS 遵循 C 字符串以空字符结尾的惯例，保存空字符的 1 字节空间并不计算在 SDS 的 len 属性中，并且分配这额外的 1 字节空间，以及添加空字符到字符串末尾等操作，都是由 SDS 函数自动完成的。

刚才展示了 free 为 0 的情况，而存在未使用空间的时候则如下图，我们还是使用“Redis”字符串。

![0bfea0176c807a5cd573848e495c303f.jpeg][]

#### SDS 与 C 字符串的区别 ####

刚才我们说过 C 语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串，并且字符数组的最后一个元素总是空字符'\\0'。

这种简单的字符串表示方式，并不能满足 Redis 对字符串的安全性、效率以及功能上的要求。我们接下来对比一下 SDS 和 C 字符串之间的区别。

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

首先 C 字符串并不记录自身的长度信息，要是想获取 C 字符串长度，则必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到结尾标识符'\\0'为止。复杂度为 O(N)。

而 SDS 不同，SDS 中的 len 属性记录了 SDS 本身的长度，所以获取 SDS 字符串长度的复杂度仅仅为 O(1)。

需要注意的是，设置和更新 SDS 长度的工作是由 SDS 的 API 在执行的时候自动完成的。

使用 SDS 将获取字符串长度从复杂度 O(N)降低到了 O(1)，确保了在 Redis 中获取字符串长度不会成为性能瓶颈。

杜绝缓冲区溢出

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

举个例子，在 string.h 中 strcat 函数可以将 src 字符串中的内容拼接到 dest 字符串的末尾。

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

由于 C 字符串不记录自身长度，如果没有为 dest 分配足够多的内存来容下 src 字符串的所有内容的话，则会发生缓冲区溢出。

:loudspeaker: 需要注意，如果内存中相邻 s1，s2 两个字符串，如果在修改 s1 字符串的时候没有分配足够的空间，可能会导致溢出到 s2 字符串所在的内存空间，导致 s2 字符串被篡改。

而 SDS 不同，SDS 的 `空间分配策略` 完全杜绝了发生缓冲区溢出的可能。在对 SDS 进行修改的时候，API 首先会检查是否满足所需的要求，如果不满足则会自动进行扩容，然后再进行修改。

举例：

![3e752282efb450829335e1cc0d4e03b9.jpeg][]

如上图，这时候我们执行

sdscat(s," Cluster");

首先在拼接之前会进行检测当前 s 的长度是否足够，发现不足以拼接" Cluster"后，进行扩容，随后进行拼接，如下图所示。

![09543c0f5e448029e2ed2997c9ecd74d.jpeg][]

:loudspeaker: 需要注意：SDS 不仅仅进行了拼接操作，还另外分配了 13 字节的未使用空间，下面我们会了解 SDS 的空间分配策略。

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

我们刚才说过，C 字符串是不记录字符串长度的，所以在增加或缩短一个字符串时，都要进行内存重分配操作。

*  如果执行的是增长字符串操作，比如 append，那么在操作前需要通过内存重分配策略来扩展底层数组的大小，如果忘记这一步，则会发生缓冲区溢出
 *  如果执行的是缩短字符串操作，比如 trim，那么在执行这个操作后需要进行内存重分配来释放不再使用的空间，如果忘记这一步，则会发生内存泄漏

为了避免 C 字符串的这种缺陷，SDS 通过未使用空间 free 解除了字符串长度与底层数组长度之间的关联，在 SDS 中，buf 数组的长度并不一定是字符数量加一，还可能包含未使用字节。

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

`1.空间预分配`

顾名思义，SDS 在进行扩展的时候，不仅仅会为 SDS 分配修改所必要的空间，还会为 SDS 分配额外的未使用空间。

空闲空间分配策略：

len = free

通过这种预分配策略，SDS 将连续增长 N 次的字符串所需内存操作次数从必定 N 次减少到了最多 N 次。

`2.惰性空间释放`

在进行缩短字符串操作时，SDS 并不会立即使用内存重分配来进行回收多余的空间，而是使用 free 进行记录，在后续如果进行增长操作的时候，就可能不需要再进行扩容。SDS 也提供了 API，来进行释放 SDS 未使用的空间。

二进制安全

我们知道 C 字符串末尾是空字符表示，在中间是不能包含空字符，否则会被认为是字符结尾。并且需要符合某种编码（比如 ASCII），导致 C 字符串只能保存文本数据，无法保存图片、视频等二进制数据。

SDS 的 API 都是二进制安全的，程序并不会对数据进行任何处理，写入时是什么样子，读取时候就是什么样子，而且在 SDS 中是可以包含空字符，因为 SDS 中是使用 len 来判断字符串是否结束。

但是为什么 SDS 末尾还是会有一个空字符？这是为了可以重用 `<string.h>` 中的部分函数，避免不必要的代码重复。

#### 总结 ####

<table> 
 <thead> 
  <tr> 
   <th>C 字符串</th> 
   <th>SDS</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>获取字符串长度为 O(N)</td> 
   <td>获取字符串长度为 O(1)</td> 
  </tr> 
  <tr> 
   <td>API 不是安全的，可能造成缓冲区溢出</td> 
   <td>API 是安全的，不会造成缓冲区溢出</td> 
  </tr> 
  <tr> 
   <td>修改字符串 N 次则必须要 N 次内存重分配</td> 
   <td>修改字符串 N 次则最多进行 N 次内存重分配</td> 
  </tr> 
  <tr> 
   <td>只能保存文本数据</td> 
   <td>不仅可以保存文本数据也可以保存二进制数据</td> 
  </tr> 
  <tr> 
   <td>可以使用所有&lt;string.h&gt;库中的函数</td> 
   <td>可以使用部分&lt;string.h&gt;库中的函数</td> 
  </tr> 
 </tbody> 
</table>

[e2cac2da41ba5a8d533c069853ef8113.jpeg]: https://img-blog.csdnimg.cn/img_convert/e2cac2da41ba5a8d533c069853ef8113.jpeg
[0bfea0176c807a5cd573848e495c303f.jpeg]: https://img-blog.csdnimg.cn/img_convert/0bfea0176c807a5cd573848e495c303f.jpeg
[3e752282efb450829335e1cc0d4e03b9.jpeg]: https://img-blog.csdnimg.cn/img_convert/3e752282efb450829335e1cc0d4e03b9.jpeg
[09543c0f5e448029e2ed2997c9ecd74d.jpeg]: https://img-blog.csdnimg.cn/img_convert/09543c0f5e448029e2ed2997c9ecd74d.jpeg