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

待我称王封你为后i 2023-01-18 14:22 9阅读 0赞

### 文章目录 ###

*   *  2.1 SDS的定义
     *  2.2 SDS和C字符串的区别
     *   *  2.2.1 常数复杂度获取字符串长度
         *  2.2.2 杜绝缓冲区溢出
         *  2.2.3 减少修改字符串时带来的内存重分配次数
         *   *  2.2.3.1 空间预分配
             *  2.2.3.2 惰性空间释放
         *  2.2.4 二进制安全
         *  2.2.5 兼容部分C字符串函数
         *  2.2.6 总结

## 2.1 SDS的定义 ##

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

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

实例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

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

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

我们看一下另一个实例：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]  
与之前SDS最大的区别是：这里的 `free` 属性的值为5，图中使用五个空格来表示五字节的未使用空间

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

## 2.2 SDS和C字符串的区别 ##

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

例如：  
![在这里插入图片描述][20210506201319380.png]  
C语言这种简单的字符串表示方式，并不能满足 Redis 对字符串在安全性、效率以及功能方面的要求。

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

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

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

实例如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 2]  
和C字符串是不同的，我们的SDS的len属性代表了SDS本身的长度，所以获取一个SDS长度为5字节。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 3]  
设置和更新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"，如图所示：  
![在这里插入图片描述][20210506223728436.png]  
如果一个程序员执行：`strcat(s1，"Cluster");`

将s1的内容修改为"Redis Cluster"，但是他忘记了在执行strcat之前，要为s1分配足够的空间，否则，s1的数据就会溢出到s2所在的空间中，导致s2保存的内容被意外的修改。如图：  
![在这里插入图片描述][20210506224134880.png]  
与C字符串不同，SDS的空间分配策略完全杜绝了缓冲区溢出的发生。

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

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

例如，我们执行：`sdscat(s，"Cluster")`  
其中SDS值如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 4]  
在执行sdscat之前，会先检查操作之前的s的长度是否足够，如果发现s的长度不够的话，sdscat就会先进行扩容，然后在执行拼接的操作，如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 5]  
注意，图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`属性的值相等。  
    ![在这里插入图片描述][20210507004511607.png]
 *  如果对于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字符串出现过的字符  
![在这里插入图片描述][20210507111015972.png]

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

会将我们的SDS修改为图2-15的样子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 6]  
我们可以看到，SDS的free属性已经变为8，代表当前buf中有8个空闲的字符空间。

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

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

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

### 2.2.4 二进制安全 ###

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

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

例如：  
![在这里插入图片描述][20210507112319564.png]  
这种的话，我们的程序只能识别“Redis”，识别不到“Cluster”

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

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

### 2.2.5 兼容部分C字符串函数 ###

对于SDS来说，一定程度上也兼容了C的一些函数，比如：`<string.h>`

### 2.2.6 总结 ###

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

<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>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221021/5f5f89a5b01e43f686b3fbc334e9558f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]: /images/20221021/de53c0c4900f48dd916ce581431954a7.png
[20210506201319380.png]: /images/20221021/43690d061ea14e09a90a0edbad7d64ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 2]: /images/20221021/f669ca8882014eb7a5e9469da91e5a24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 3]: /images/20221021/b6fc478f5e2846ddb278a98464a24e9c.png
[20210506223728436.png]: /images/20221021/66ec973f6e264857b6949324f9cc9340.png
[20210506224134880.png]: /images/20221021/c7c38efc82af47c7994a7ba34b8f3294.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 4]: /images/20221021/f160b55d52c64a068b117a97162dc358.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 5]: /images/20221021/28ec7744b6f6495db93a39c65bb278ec.png
[20210507004511607.png]: /images/20221021/4c49bec0a32940b3bc4d71337b2d7dcb.png
[20210507111015972.png]: /images/20221021/72a5fae8530f4b85b78f7ab93ef10bf5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 6]: /images/20221021/1282c35604a14a698519cd20530d7520.png
[20210507112319564.png]: /images/20221021/ab778b3f41e14acdb9f7c05296ebf46d.png