SDS概述

Redis基于C语言实现，但Redis并没有采用C语言中传统的字符串表示，而是特别构建了一种叫做简单动态字符串（simple dynamic string）的数据结构，简称SDS，SDS是Redis中默认的字符串表示。

C字符串只在无须对字符串值修改的场景下作为字面量使用，如日志打印，而在字符串值可能被修改的场景下，均使用SDS表示字符串值。

SDS与C字符串异同

相同点

C字符串底层本质就是一个char类型数组，SDS就是在该数组的基础上额外定义了几个属性和一系列实现策略，在字符串存储本质上与C字符串相同，都是使用一个字符数组存储。

此外，在设计时为了减少代码冗余，SDS与C字符串一样保存了字符数组最后一位为空字符’\0’，这样可以重用string.h中的部分函数。

区别

数据结构

前文提及，SDS在用于存放字符串的字符数组buf[]基础上增加了几个额外的属性存储信息，这些属性主要用于保存buf[]数组相关的长度，SDS的设计以极少量的空间代价换来了许多好处（见下文）。

在Redis 3.2以前的版本，增加的属性是unsigned int型的len和free属性，len用来记录buf[]数组中已使用的长度，free用来记录buf[]数组未被使用的长度。

Redis 3.2以前SDS的数据结构源码如下：

struct sdshdr {
    unsigned int len;   //表示buf[]数组中已使用的长度
    unsigned int free;  //表示buf[]数组中未使用的长度
    char buf[];         //用于存储字符串的字节数组buf[]
};

为了对SDS进行优化，在Redis 3.2版本对SDS的数据结构做了较大的改动，体现在以下两点

相较C字符串所附加的额外属性改变。额外属性变为了三个，分别为len、alloc和flag，其中len仍记用于记录buf[]数组已使用的长度，而alloc用于记录buf[]数组分配空间的总长度，flag记录当前SDS的类型。
提供了五种不同的SDS类型供使用。分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64，flag属性就是用来区分这五个SDS类型。以sdshdr16和sdshdr32为例，二者的区别是sdshdr16的len和alloc属性定义实际使用的基本数据类型为unsigned short，sdshdr32使用的是unsigned int，实际上就是可供使用的字节位不同，这样的改动使得SDS更加灵活。

以sdshdr32为例，在Redis 5.0中的数据结构源码如下：

typedef unsigned   uint32_t;

struct __attribute__((__packed__)) sdshdr32 {
  uint32_t len;        /* used */
  uint32_t alloc;      /* excluding the header and null terminator */
  unsigned char flags; /* 3 lsb of type, 5 unused bits */
  char buf[];
};

Redis 5.0的SDS数据结构示意图如下：
在这里插入图片描述

SDS获取字符串长度简单高效

C字符串的底层实现只有一个字符数组，这意味着想要获取C字符串的长度必须要经过一次遍历，对每个字符进行计数后返回，直到遍历到字符串末尾的空字符’\0’为止，这样的事件复杂度为O(N)，其中N为字符串长度。

而SDS得益于额外记录的属性，无论是哪个版本的Redis，只需要直接返回len的值就可以满足需求，时间复杂度为O(1)。

避免了缓冲区溢出

在C字符串的场景下，假设现有两个非空字符串s1和s2，在物理地址上字符串s1紧接着字符串s2，即s1的末尾空字符’\0’的下一个地址就是字符串s2的首地址。在这种场景下，使用字符串拼接strcat等操作追加字符串s1的长度，如果追加操作执行前没有为s1分配足够的空间，那么s2字符串就一定会被s1的追加部分所覆盖，导致字符串s2被错误修改，造成缓冲区溢出。

而由于SDS记录了buf[]数组的相关信息，在追加字符串长度前，可以预先知晓当前空间的空余长度（Redis 3.2前是free，Redis 3.2后是alloc-len），当剩余空间 < 追加字符串长度时，会进行自动扩容操作，扩容确保剩余空间足够时才会检修执行字符串修改操作。从根本上渡劫了缓冲区溢出问题，同时也不需要手动操作。

尽量少的内存重分配

字符串修改操作分为增长字符串和缩短字符串，此处分开讨论。

扩容

由于C字符串不记录buf[]数组相关长度，对于一个C字符串，他的字符数组长度总是其所存储字符串长度+1，因此每一次增长字符串的操作都需要通过内存重分配扩容，如果不扩容则会出现上文所述的缓冲区溢出问题。

SDS为了减少内存重分配次数，采用了空间预分配策略，即当SDS需要扩容的时候，在满足存储当前字符串的基础上，再额外分配一些内存空间以应对未来可能再次出现的字符串增长。

空间预分配策略所分配的额外空间数量取决于当前字符串所占大小，假设当前字符串所需空间大小为x(包括buf[]末尾空字符’\0’)，当扩容时

如果当前的字符串所占空间大小小于1MB，则额外分配x大小的空间，即扩容后总容量为2*x。
如果当前的字符串所占空间大小大于等于1MB，则额外分配1MB的空间，即扩容后的总容量为x + 1MB。

缩容

与字符串增长同理，每一次缩短字符串的操作都需要内存重分配以实现缩容，如果不进行缩容则会出现内存泄漏。

SDS对此采用惰性空间释放策略。由于可以通过记录的额外属性知晓字符数组总长度，所以在缩短字符串时不立即释放也不会出现内存泄漏的情况。当字符串缩短时，SDS不会立即释放未被使用的部分，而是等待将来使用，当真的有需要释放空间需求时，会调用相关函数进行内存重分配，使得buf[]数组总长度正好是当前字符串长度+1。

通过空间预分配和惰性空间释放策略，保证了SDS的内存空间重分配次数<=C字符串内存空间重新分配次数。

二进制安全

C字符串以结尾空字符’\0’判断字符串是否结束，这种读取字符串的方式决定了C字符串只能存储文本数据，在文本数据存储上，可以保证’\0’一定不会作为数据的一部分出现，但在保存图片、音视频、压缩文件等二进制数据时，这种可能是存在的，即如果用C字符串保存上述类型数据，很可能将数据部分的00(空字符对应ASCII码00)误判为数据结束符。

而SDS的存储是二进制安全的，虽然SDS末尾也保存一个空字符’\0’，但目的只是为了复用函数库里的部分函数，并非是作为结尾判断，SDS使用属性len进行结尾判断，这使得Redis可以保存任意格式的二进制数据。

总结

C字符串与SDS区别总结如下：

C字符串	SDS
获取字符串长度的时间复杂度为O(n)，n为字符串长度	获取字符串长度的时间复杂度为O(1)
API不安全，可能造成缓冲区溢出、内存泄漏问题	API安全，杜绝了缓冲区溢出和内存泄漏问题
修改字符串长度N次必然执行N次内存重分配	修改字符串长度N次至多执行N次内存重分配
只能保存文本数据	可以保存文本和任何二进制数据
可以使用全部<string.h>库内函数	可以复用部分<string.h>库内函数

SDS API

SDS的主要操作API如下表

函数	作用	时间复杂度
sdsnew	创建一个包含给定C字符串的SDS	O(n)，n为给定C字符串长度
sdsempty	创建一个不包含任何内容的空SDS	O(1)
sdsfree	释放给定SDS	O(n)，n为被释放SDS长度
sdslen	返回SDS已使用空间字节数	O(1)，直接读取len属性值
sdsavail	返回SDS未使用空间字节数	O(1)，Redis3.2前读取free属性值，3.2后为alloc-len
sdsdup	创建一个给定的SDS副本	O(n)，n为给定SDS长度
sdsclear	清空SDS保存的字符串内容	O(1)
sdscat	将给定的C字符串拼接到SDS字符串末尾	O(n)，n为被拼接C字符串长度
sdscatsds	将给定的SDS字符串拼接到SDS字符串末尾	O(n)，n为被拼接SDS的长度
sdscpy	将给定的C字符串赋值到SDS里面，覆盖SDS原有的字符串	O(n)，n为被复制C字符串长度
sdsgrowzero	用空字符串将SDS扩展到指定长度	O(n)，n为扩展新增的字节数
sdsrange	保留SDS给定区间的数据，不在区间内的数据会被覆盖或清除	O(n)，n为被保留数据的字节数
sdstrim	接受一个SDS和一个C字符串作为参数，从SDS左右两段分别移除所有在C字符串中出现过的字符	O(m*n)，m为SDS的长度，n为C字符串的长度
sdscmp	对比两个SDS字符串是否相同	O(n)，n为两个SDS中较短的那个的长度