动态字符串SDS

SDS 简介

无论是 Redis 的 Key 还是 Value，其基础数据类型都是字符串。例如，Hash 型 Value 的field 与 value 的类型、List 型、Set 型、ZSet 型 Value 的元素的类型等都是字符串。虽然 Redis是使用标准 C 语言开发的，但并没有直接使用 C 语言中传统的字符串表示，而是自定义了一种字符串。这种字符串本身的结构比较简单，但功能却非常强大，称为简单动态字符串，Simple Dynamic String，简称 SDS。

注意，Redis 中的所有字符串并不都是 SDS，也会出现 C 字符串。C 字符串只会出现在字符串“字面常量”中，并且该字符串不可能发生变更。

SDS 结构

SDS 不同于 C 字符串。C 字符串本身是一个以双引号括起来，以空字符’\0’结尾的字符序列。但 SDS 是一个结构体，定义在 Redis 安装目录下的 src/sds.h 中：

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

例如执行 SET country “China”命令时，键 country 与值”China”都是 SDS 类型的，只不过一个是 SDS 的变量，一个是 SDS 的字面常量。”China”在内存中的结构如下：

通过以上结构可以看出，SDS 的 buf 值实际是一个 C 字符串，包含空字符’\0’共占 6 个字节。但 SDS 的 len 是不包含空字符’\0’的。

该结构与前面不同的是，这里有 3 字节未使用空间。

SDS 的优势

C 字符串使用 Len+1 长度的字符数组来表示实际长度为 Len 的字符串，字符数组最后以空字符’\0’结尾，表示字符串结束。这种结构简单，但不能满足 Redis 对字符串功能性、安全性及高效性等的要求。

防止”字符串长度获取”性能瓶颈

对于 C 字符串，若要获取其长度，则必须要通过遍历整个字符串才可获取到的。对于超长字符串的遍历，会成为系统的性能瓶颈。

但，由于 SDS 结构体中直接就存放着字符串的长度数据，所以对于获取字符串长度需要消耗的系统性能，与字符串本身长度是无关的，不会成为 Redis 的性能瓶颈。

保障二进制安全

C 字符串中只能包含符合某种编码格式的字符，例如 ASCII、UTF-8 等，并且除了字符串末尾外，其它位置是不能包含空字符’\0’的，否则该字符串就会被程序误解为提前结束。而在图片、音频、视频、压缩文件、office 文件等二进制数据中以空字符’\0’作为分隔符的情况是很常见的。故而在 C 字符串中是不能保存像图片、音频、视频、压缩文件、office 文件等二进制数据的。

但 SDS 不是以空字符’\0’作为字符串结束标志的，其是通过 len 属性来判断字符串是否结束的。所以，对于程序处理 SDS 中的字符串数据，无需对数据做任何限制、过滤、假设，只需读取即可。数据写入的是什么，读到的就是什么。

减少内存再分配次数

SDS 采用了空间预分配策略与惰性空间释放策略来避免内存再分配问题。

空间预分配策略是指，每次 SDS 进行空间扩展时，程序不但为其分配所需的空间，还会为其分配额外的未使用空间，以减少内存再分配次数。而额外分配的未使用空间大小取决于空间扩展后 SDS 的 len 属性值。

• 如果 len 属性值小于 1M，那么分配的未使用空间 free 的大小与 len 属性值相同。
• 如果 len 属性值大于等于 1M ，那么分配的未使用空间 free 的大小固定是 1M。

SDS 对于空间释放采用的是惰性空间释放策略。该策略是指，SDS 字符串长度如果缩短，那么多出的未使用空间将暂时不释放，而是增加到 free 中。以使后期扩展 SDS 时减少内存再分配次数。

兼容 C 函数

Redis 中提供了很多的 SDS 的 API，以方便用户对 Redis 进行二次开发。为了能够兼容 C函数，SDS 的底层数组 buf[]中的字符串仍以空字符’\0’结尾。

现在要比较的双方，一个是 SDS，一个是 C 字符串，此时可以通过 C 语言函数strcmp(sds_str->buf，c_str)

新版本的SDS

SDS结构大致上可以分为2大部分：header部分和buff部分，并且header部分和buff部分在内存中是连续的。

header部分

header部分保存的是SDS一些源数据信息。

其中:

• len表示: 字符串的长度;
• alloc表示：字符串的长度 + 额外预留空间的长度。alloc代表可用来存储字符空间的总大小，但是不包括null-term，所以是比实际分配出来的buff长度减1;

除了我们上面提到过的len和alloc，这里还多了一个flag字段。flag字段决定len和alloc的变量类型。具体什么意思呢？因为字符串大小不固定有长有短，比如我们要保存"hello"这个字符串，那么对于len和alloc变量来说，最合适的变量类型应该是uint8，用一个字节来存储就够了，如果用uint16、uint32或uint64都显得有点太浪费。基于此SDS根据需要保存的字符串长度设计了如下5种flag类型，flag本身占用1个字节，如下表所示:

假设我们要保存的字符串长度为len:

• SDS_TYPE_5：这个比较特殊，注释上说未被使用，但是也不完全准确，无论如何这个类型都不是我们讨论的重点。
• SDS_TYPE_8: 当len 小于 1 << 8，也就是小于256时，变量len和alloc用uint8类型。
• SDS_TYPE_16: 当len 小于 1 << 16，也就是小于65536时，变量len和alloc用uint16类型。
• SDS_TYPE_32: 当len 小于 1 << 32，也就是小于4294967296时，变量len和alloc用uint32类型。
• SDS_TYPE_64: 当len 大于等于 1 << 32，也就是大于等于4294967296时，变量len和alloc用uint64类型。

我们来举个简单例子，假设我们要用SDS(“hello”)保存"hello"这个字符串。"hello"长度为5个字节，len为5，是小于 1 << 8。因此flag为SDS_TYPE_8，len、alloc变量类型为uint8各自占用一个字节，flag始终占用1个字节，如下图所示：

len值为5：表示hello字符串长度为5个字节；

alloc值为12: 表示一共分配出来可用空间12字节。buff总长度为13字节，由于null-term要额外占用1字节不能计算在内，因此需要减1；

flag值为1: 表示的是SDS_TYPE_8类型；

buff部分

Buff比较简单主要分为2个部分: 第一个部分是原生的C字符串，以null-term结尾，第二个部分是还未使用的额外空间，如下图所示。

前面说过SDS可以在一定程度上兼容C字符串，只要C-String部分是binary-safe，用户可以拿到SDS的buff起始地址（图中return to user），在只读场景当作原生C字符串使用。

还是以前面的"hello"字符串为例：

buff部分索引0~5存储"hello"的C字符串，索引6到索引12是预留空间还未使用。如果后续需要追加字符串并且在8个字节以内，即可直接修改，无需重新分配内存空间。

SDS扩容规则

当我们要往原SDS追加字符串时会触发SDS的扩容，为了阐述方便，我们定义如下变量：

len = 原SDS长度;

avail = 原SDS剩余预留空间长度;

addlen = 追加字符串的长度;

newlen = len + addlen 追加后字符串的总长度;

SDS的扩容规则如下：

• 如果原SDS预留空间空间avail大于等于追加字符串的长度addlen，不会触发扩容。
• 如果追加后的字符串总长度newlen小于1MB(1024*1024)，将newlen扩容为2倍再加1(null-term)，也就是newlen = newlen * 2 + 1。
• 如果追加后的字符串总长度newlen大于等于1MB(1024*1024)，将newlen额外扩容1MB再加1(null-term)，也就是newlen = newlen + 1MB + 1。

需要注意的是，如果newlen大于flag所指定的范围，flag的类型也需要随之变大。

我们来举几个例子，依次看一下这2个扩容规则：

规则1：假设有如下图的SDS(“hello”)，我们要追加字符串",world"。

变量初始化如下：

len = 5;

avail = alloc - len = 12 - 5 = 7;

addlen = “,world”的长度 = 6;

newlen = 5 + 6 = 11;

按照扩容规则，avail > addlen，不会触发扩容，因此可以原地追加，追加后的SDS如下图所示：

Redis系列-3.Redis底层数据结构原理（下）:https://developer.aliyun.com/article/1414380