Redis SDS简单动态字符串与C字符串的区别

本文只解析SDS与C字符串区别，建议搭配相关实现源码阅读，关于SDS源码实现，可以参考笔者之前的文章Redis 5.0数据结构之SDS简单动态字符串实现源码详解

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

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

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

此外，在设计时为了减少代码冗余，SDS与C字符串一样保存了字符数组最后一位为空字符’’，这样可以重用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;        
  uint32_t alloc;      
  unsigned char flags; 
  char buf[];
};

Redis 5.0的SDS数据结构示意图如下：

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

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

在C字符串的场景下，假设现有两个非空字符串s1和s2，在物理地址上字符串s1紧接着字符串s2，即s1的末尾空字符’’的下一个地址就是字符串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[]末尾空字符’’)，当扩容时

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

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

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

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

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

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

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

SDS的主要操作API如下表

部分内容参考/摘自：《Redis设计与实现》——黄健宏