Redis(一):简单动态字符串(SDS)

朴灿烈づ我的快乐病毒、 2022-05-25 09:37 169阅读 0赞

#### 简单动态字符串(Simple Dynamic String) ####

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

在Redis里面，C字符串只会作为字符串字面量(String literal)用在一些无须对值进行修改的地方。当需要使用到需要修改的字符串的时候就会使用SDS来表示字符串的值。

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

每个sds.h/sdshdr结构表示一个SDS值:

struct sdshdr{
        //记录buf数组中已经使用字节的数量
        //等于SDS所保存字符串的长度
        int len;
        //记录buf数组中未使用字节的数量
        int free;
        //字节数组，用来保存字符串。真正的字符就保存在这个数组里面。
        char buf[];
    }

![20180511215749275][]

如图展示了一个SDS示例:

*  free属性值为0，表示这个SDS没有分配任何未使用的空间。buf数组里面没有剩余空间了。
 *  len属性为5，表示这个SDS保存了一个5字节长的字符串
 *  buf数组是一个char类型的数组，数组的前5个字节分别保存了'R','e','d','i','s' 五个字符串，最后一个字节则保存了空字符串'\\0'

SDS遵循了C字符串以空字符结尾的惯例，保存了空字符的1字节不计算在SDS的len属性里面。并且为空字符分配额外的一字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的。所以这个空字符对于SDS的使用者来说就是透明的。遵循空字符结尾这一个习惯的好处是，SDS可以直接重用一部分C字符串函数库里面的函数。

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

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

因为C字符串并不记录自身的长度信息，所以为了获取一个C字符串的长度。程序必须遍历整个字符串。对遇到的每个字符进行计算，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为O(N)。但是对于SDS来说，程序只需要访问SDS的len属性。就可以立即知道了SDS的长度了。而设置和更新SDS长度的工作是由SDS的API在执行时自动完成的，使用SDS无须进行任何手动修改长度的工作。

2、杜绝缓冲区溢出

除了获取字符串长度的复杂度高之外，C字符串不记录长度带来的另一个问题是容易造成缓冲区移除(buffer overflow).与C字符串不同，SDS空间的分配策略完全杜绝了发生缓冲区溢出的可能性。当SDS的API需要对字符串进行修改时。API会先检查SDS的空间是否满足修改所需的需求。如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际参数的操作。

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

因为C字符串并不记录自身的长度，所以对于一个包含了N个字符串的C字符串来说，这个C字符串的底层实现总是一个N+1个字符长的数组。因为C字符串的长度和底层数组的长度之前存在着这种关联性，所以每次增长或者缩短一个C字符串，程序都总要对这个C字符串数组进行一次内存重新分配。因为SDS有冗余的空间，所以每次在对字符串的动态修改的时候就可以节省内存重新分配操作。

3.1 空间预分配

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

3.1.1 如果对SDS进行修改之后，SDS的长度将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将会和free属性的值。

3.1.2 如果对SDS进行修改之后。SDS的长度将会大于1MB，那么程序会分配1MB的未使用空间。

3.2 惰性空间施放

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

4、二进制安全

C字符串中的字符必须符合某种编码(比如ASCII)，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被认为是字符串结尾，这些限制使得C字符串只能保持文本数据。而不能保存图片、音频、视频、压缩文件这样的二进制数据。因为SDS不以空字符作为字符串的结尾，所以空格以及其他等数据都是可以正常的保存的。

总结 C字符串和SDS之间的区别

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

本文参考了书籍：Redis设计与实现(第二版),推荐希望对Redis要频繁使用，希望对Redis有深入了解的朋友可以去买这本书看。写得简单通俗易懂。看完后会对Redis的实现与原理会有深入的了解。在平常的使用当中可以有很高的提升。

[20180511215749275]: /images/20220525/0654fb7bfd97482b838baceb4c41413a.png