「Redis」字符串

原文链接：https://www.changxuan.top/?p=1109

简介

Redis 中自定义的字符串结构。

字符串是 Redis 中最常用的一种数据类型，在 Redis 中专门封装了一个字符串结构体——简单动态字符串（Simple Dynamic String, SDS）。其结构体如下：

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

当 len 的值为 8 时，表示在 buf 数组中保存了一个 8 字节长的字符串；当 free 的值为 2 时，表示在 buf 数组中还有两个字节的空间未使用。如果为 0 ，则表示当前 buf 数组的空间已经全部分配完毕；buf 则是一个 char 类型的数组。SDS 遵循了C字符串以空字符结尾的惯例，即存储在 buf 中的字符串末尾都会紧跟一个空字符 \0 ，这个空字符对于用户来说是透明的，它并不会被计入 len 中。

优点

为什么要在 Redis 中要自定义字符串的数据结构？

1 时间复杂度

首先，由上面代码我们可以知道通过 SDS 获取字符串的长度的时间复杂度为 O(1)。而如果使用 C 字符串每次获取字符串长度时的时间复杂度则为 O(N)。即当我们使用 STRLEN 命令获取某个键值的长度时不用担心性能问题。

2 缓冲区溢出

其次，可以避免缓冲区溢出问题。例如，两个C字符串在内存中紧挨着，如果没有提前给前一个字符串分配足够空间的情况下就使用 strcat 函数在其末尾追加新的字符串。那么新拼接的字符串就会溢出到后一个字符串的空间中，从而导致后一个字符串的内容发生改变。但是在 SDS 中，对内容进行修改之前会先检查其内存空间是否满足要求，如果不满足要求，则会自动将空间扩展至所需要的大小。扩展空间大小的操作对于用户来说也是透明的。

另外，为了避免可能由于频繁的修改字符串内容，而导致产生较为耗时的内存重分配问题。SDS 通过以空间换时间的方式即未使用空间来尽量避免这种问题。在 SDS中实现了空间预分配和惰性空间释放两种优化策略。

优化策略

空间预分配

当 SDS 中的字符串变长时，程序先判断当前闲置空间是否满足需求。如果不满足，则按照空间预分配的策略对空间进行扩展。Redis 不仅仅只分配所需要的空间大小，则是根据规则多分配一些空间。当 SDS 修改后的新值长度小于 1MB（len 的长度）。那么程序将会分配和 len 同样大小的闲置空间，即 len = free 。buf 数组的实际长度则是 len + free + 1 字节。如果修改后的新值大于等于 1MB，程序则会分配 1MB 的未使用空间。

如此一来，就不需要每次增加字符串长度时必须对内存重新分配，从而提高了系统性能。

惰性空间释放

当 SDS 中的字符串变短时，程序并不是直接进行内存重分配回收多余的空间，而是使用 free 记录下来。如果将来再变长时，可以直接使用。

通过惰性空间释放，避免了缩短字符串时产生的内存重分配操作。

3 二进制安全

由于C字符串的特殊性，在一些场景中会出现问题。如，一个字符串中存在多个空字符，那么C字符串只能识别出第一个空字符之前的内容。且C字符串只能保存文本数据。

而 SDS 的 API 都是二进制安全的，所有的 API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组中的数据，以保证数据写入前与读取后的一致性。

4 兼容部分C字符串函数

避免了重复造轮子的问题。

SDS API