Redis源码阅读：Redis字符串SDS

刺骨的言语ヽ痛彻心扉 2022-05-22 09:39 237阅读 0赞

### SDS 基本概念 ###

简单动态字符串（Simple Dynamic String）SDS，用作Redis 的默认字符串。  
C语言中的字符串：以空字符结尾的字符数组

#### SDS实现举例 ####

redis > SET msg "hello world"
    OK

我们通过 `SET` 在 `Redis` 数据库中创建了一个数据键对象为 `"msg"` 和 数据值对象为 `"hello world"` 的键值对，其中数据键和数据值对象底层的字符串实现都是 `SDS` 。同时， `SDS` 还被用于 `AOF` 缓冲区。

#### SDS 定义 ####

struct sdshdr {
    
        # 记录 buf 数组中已使用字节的数量，即当前字符串长度值 
    
        # 等于 SDS 所保存字符串的字节长度
    
        int len;
    
        # 记录 buf 数组中未使用字节的数量，buf空余可用的长度，append时使用 
    
        int free;
    
        # 字节char数组，用于保存字符串，实际保存字符串数据，最后一个字节保存了空字符 '\0'
    
        char buf[];
    };

`buf` 属性的字节数组中的字符串长度等于 `len` 属性值加上1，因为 `Redis`遵循 C语言的规范，在SDS数据类型字符串的结尾加上了 空字符串，额外占用 1 个字节空间，这1个字节空间不计算在 SDS 的 `len`属性里面。

由于SDS将字符串的结尾加上了 空字符串符合C语言字符串规范，Redis 字符串操作可以兼容C语言中一部分字符串库中的函数，Redis 无需专门为 SDS在编写一套函数。

## SDS的优点 ##

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

1.  C字符串需要遍历整个字符串，计数，直到碰到空字符，停止计数，复杂度为O(N)
2.  SDS获取 len 属性值即可，复杂度为 O(1) 。所以 STRLEN 的复杂度也为 O(1)

### API安全，杜绝缓冲区溢出 ###

1.  C字符串在进行字符串拼接 `strcat` 时，需要预先分配足够的空间，来容纳拼接的字符串，否则会造成缓冲区溢出的问题，比如临近的空间有另外一个字符串。
2.  SDS 在进行字符串拼接时，会先检查 `len` 的长度是否足够，如果不够，会先扩展 `len`，再进行字符串拼接。

### 减少修改字符串长度时所需的内存重分配次数 ###

1.  空间预分配  
    当对 `SDS` 进行空间扩展时，计算扩展之后的 `len`值如果小于 `1mb`，那么久会分配 扩展之后的 `len` 值给 `free` 属性作为，为下次扩展时预分配的未使用空间，如果下次扩展所需字节空间小于 `free` 的值，那么就无需进行空间扩展，直接使用未使用空间。
2.  惰性空间释放  
    同样，默认情况下，对 `SDS` 进行缩减时，缩减的空间不会立刻被这个SDS释放，而是分配给 `free` ，如果之后再进行扩展时，有可能会用到。

Redis 的 SDS 类型通过这两种空间分配策略，减少了字符串增长缩减时所需的内存重分配操作，为内存分配提供了优化。

### 二进制安全 ###

Redis 通过 `len`属性的值来判断是否结束，而不是C字符串的 `\0` 作为结束。

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

上面已经提到SDS在末尾添加了 `\0` ，这样可以兼容部分C字符串函数，可以直接使用 `<string.h>` 函数库。