Redis之SDS底层原理解读

逃离我推掉我的手 2023-10-15 16:53 8阅读 0赞

**目录**

SDS是什么？

SDS结构示例

概述

空间预分配

惰性空间释放

C字符串跟SDS的区别？为什么用SDS？

--------------------

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

Redis 底层的程序语言是由 C 语言编写的，C 语言默认字符串则是以空字符结尾的字符数组（简称 C 字符串）。但 Redis 默认的字符串并非 C 字符串，而是名为 SDS ( Simple Dynamic String ）简单动态字符串的抽象结构。

>  *  在 Redis 里面， C 字符串只会作为字符串字面量（string literal）， 用在一些无须对字符串值进行修改的地方， 比如打印日志。
>  *  当 Redis 需要的不仅仅是一个字符串字面量， 而是一个可以被修改的字符串值时， Redis 就会使用 SDS 来表示字符串值： 比如在 Redis 的数据库里面， 包含字符串值的键值对在底层都是由 SDS 实现的。

####  ####

#### SDS结构示例 ####

##### 概述 #####

***Redis 采用一段连续的内存空间来存储 SDS 结构，***具体结构如下图所示，free 代表指这个字符串剩余可用空间的长度，而 len 代表这个字符串已占用空间的长度，buf \[\] 就是字符数组。

![232ffdebed05473dab227f735e4ce8e3.png][]

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

一个字符串为 'Redis' 在 SDS 结构中的存储例子：

![6c259435e29b4057845cd788f987e93c.png][]

图中 SDS 保留了 C 字符串以空字符结尾的传统，但这个空字符的长度1字节空间并不会计算在 SDS 的 len 属性里面，而是为这个空字符分配额外的1字节空间，每次由 SDS 相关函数默认添加到字符串末尾，Redis 这样设计的好处是 SDS 可以直接重用一部分 C 字符串相关函数。

> 这个 SDS 结构为字符串 'Redis' 分配了5字节的已使用长度，也为其分配了5字节的可用空间长度。

##### 空间预分配 #####

SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联： 在 SDS 中， `buf` 数组的长度不一定就是字符数量加一， 数组里面可以包含未使用的字节， 而这些字节的数量就由 SDS 的 `free` 属性记录。

空间预分配用于优化 SDS 的字符串增长操作： 当 SDS 的 API 对一个 SDS 进行修改， 并且需要对 SDS 进行空间扩展的时候， 程序不仅会为 SDS 分配修改所必须要的空间， 还会为 SDS 分配额外的未使用空间。通过空间预分配策略， Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。

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

> 进行修改之后， SDS 的 `len` 将变成 `14` 字节， 那么程序也会分配 `14` 字节的未使用空间， SDS 的 `buf` 数组的实际长度将变成 `14` `+ 14` `+ 1 = 28`字节（额外的一字节用于保存空字符）。

*  如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将大于等于1MB，那么程序会分配1MB的未使用空间。

> 进行修改之后， SDS 的 `len` 将变成 `30 MB` ， 那么程序会分配 `1 MB` 的未使用空间， SDS 的 `buf` 数组的实际长度将为 `30 MB + 1 MB + 1 byte` 。

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

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

##### 惰性空间释放 #####

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

通过惰性空间释放策略， SDS 避免了缩短字符串时所需的内存重分配操作， 并为将来可能有的增长操作提供了优化。

#### C字符串跟SDS的区别？为什么用SDS？ ####

<table style="width:600px;"> 
 <tbody> 
  <tr> 
   <td style="width:100px;"></td> 
   <td style="width:138px;">C字符串</td> 
   <td style="width:361px;">SDS</td> 
  </tr> 
  <tr> 
   <td style="width:100px;">字符串长度处理 len</td> 
   <td style="width:138px;">需要从头开始遍历，直到遇到“/0'为止时间复杂度O(N)</td> 
   <td style="width:361px;">记录当前字符串的长度，直接读取即可，时间复杂度 O(1)</td> 
  </tr> 
  <tr> 
   <td style="width:100px;">内存重新分配alloc</td> 
   <td style="width:138px;">分配内存空间超过后，会导致数组下标越级或者内存分配溢出</td> 
   <td style="width:361px;"> <p><span style="color:#fe2c24;">空间预分配</span><br> SDS 修改后，len 长度小于 1M，那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于 1M，那么将分配1M的使用空间。</p> <p><span style="color:#fe2c24;">惰性空间释放</span></p> <p>有空间分配对应的就有空间释放。SDS 缩短时并不会回收多余的内存空间，而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作，直接使用 free 中记录的空间，减少了内存的分配。</p> </td> 
  </tr> 
  <tr> 
   <td style="width:100px;">二进制安全buf</td> 
   <td style="width:138px;">二进制数据并不是规则的字符串格式可能会包含一些特殊的字符，比如“\0"等。C中字符串遇到“0会结束，那"\0"之后的数据就读取不上</td> 
   <td style="width:361px;">根据 len 长度来判断字符串结束的，二进制安全的问题就解决了</td> 
  </tr> 
 </tbody> 
</table>

[232ffdebed05473dab227f735e4ce8e3.png]: https://img-blog.csdnimg.cn/232ffdebed05473dab227f735e4ce8e3.png
[6c259435e29b4057845cd788f987e93c.png]: https://img-blog.csdnimg.cn/6c259435e29b4057845cd788f987e93c.png