Redis-简单动态字符串（SDS）

概述

Redis没有直接使用C语言的传统字符串表示，而是自己构建了一种名为简单动态字符串（Simple dynamic string，SDS）的抽象类型，并将SDS用作Redis默认的字符串表示

C语言传统字符串通常用以空字符结尾的字符数组表示

在Redis中，C字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方，比如打印日志

当Redis需要的是一个可以被修改的字符串值的时候，Redis就会使用SDS来表示字符串值

比如在Redis的数据库里面，包含字符串值的键值对在底层都是有SDS实现的

除了用来保存数据库中的字符串值之外，SDS还被用作缓冲区

AOF模块中的AOF缓冲区
客户端状态中的输入缓冲区

SDS的定义

每个sds.h/sdshdr结构表示一个SDS值


/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

free属性的值为0，表示这个SDS没有剩余可用空间了

len属性的值为5，表示这个SDS保存了一个五字节长的字符串

buf属性是一个char类型的数组，数组的前五个字节分别保存R、e、d、i、s五个字符，而最后一个字节则保存了空字符'\0'

SDS遵循了C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面

为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是有SDS函数自动完成的，所以这个空字符对于SDS的使用者（上层调用方）来说是完全透明的

部分函数解析

如下图，sdscatlen函数是用于拼接（追加）字符串到已有SDS的函数，可以看到在函数返回前的最后一步，会在结尾自动填充'\0'

包括在SDS扩容的时候，也会自动多分配1字节的空间留给最后的'\0'使用

如下图，sdsMakeRoomFor函数是用于SDS扩容的函数

遵循空字符结尾这一惯例的好处是，SDS可以直接复用一部分C字符串函数库里面的函数

函数复用例子

可以直接使用<stdio.h>/printf函数打印SDS保存的字符串的值

1
2
3


printf("%s", s->buf);

SDS与C字符串的区别

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

C字符串不会记录长度信息，每次获取一个C字符串的长度都必须遍历整个字符串，对遇到的每个字符串进行计数，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为O(N)

而SDS只需要访问len属性即可

SDSlen和free属性的设置和更新工作都是由SDS的API在执行时自动完成的（通过在写操作冗余存储长度的信息来实现快速读取）

杜绝缓冲区溢出

C字符串不记录自身长度带来的另一个问题就是容易造成缓冲区溢出（buffer overflow）

如<string.h>/strcat函数可以将src字符串中的内容拼接到dest字符串的末尾（一个字符串拼接函数）

1	char strcat(char dest, const char *src);

因为C字符串不记录自身的长度，所以strcat假定用户在执行这个函数之前，已经为dest分配了足够的内存了，可以容纳src字符串中的所有内容，而一旦src没有预留足够的空间，就会产生缓冲区溢出

比如下图中的两个字符串，假设这两个字符串在内存中是紧邻的

此时执行以下代码进行字符串拼接的操作

1	strcat(s1, " Cluster");

由于s1没有预留足够的空间以容纳拼接的Cluster字符串（空间不足也没有提前进行扩容），那么在执行完strcat函数之后，s2的内容会被意外修改，如下图所示

而SDS则在API层面就会进行空间检查，发现空间不足时会自动进行扩容，所以不存在缓冲区溢出问题

以下是SDS字符串拼接的API——sdscatlen函数源码

减少修改字符串时带来的内存重分配次数

对于一个包含N个字符的C字符串来说，底层实现总是一个N+1个字符长的数组（额外的一个字符空间用于保存空字符）

这导致每次增长或缩短一个C字符串时，程序总是要对保存这个C字符串的数组进行一次内存重分配操作

对于增长字符串的操作（比如拼接操作）——执行这个操作之前，程序需要通过内存重分配来扩展底层数组的空间大小（如果忘了这一步就会造成缓冲区溢出）
对于缩短字符串的操作（比如截断操作）——执行这个操作之后，程序需要通过内存重分配来释放字符串不在使用的那部分空间（如果忘了这一步就会造成内存泄漏）

SDS通过len和free属性解除了字符串长度和底层数组长度之间的关联：buf数组的长度不一定就是字符数量+1，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录

通过未使用空间，SDS 实现了空间预分配和惰性空间释放两种优化策略，减少了修改字符串时内存重分配的次数

进行N次字符串操作：

C字符串必须进行N次内存重分配
SDS则降低到最多需要进行N次内存重分配（空间预留）

空间预分配

当需要对SDS 进行扩容的时候，会额外分配未使用的空间

扩容规则

注：Redis3.0源码的扩容规则，可能不适用于其他版本

如果修改之后的长度小于1MB，那么会分配和len属性同样大小的未使用空间（即free属性和len属性相同）

比如，修改后的len为13，那么程序也会分配13字节的未使用空间，SDS 的buf数组的实际长度将变成13+13+1=27字节（额外1字节用于保存空字符，这1字节是申请内存时自动添加的）
如果修改之后的长度大于等于1MB，那么会分配1MB的未使用空间

扩容源码

惰性空间释放

这个策略用于优化SDS的字符串缩短的操作

当SDS 的API需要缩短SDS保存的字符串时，程序不会立即使用内存重分配来回收缩短后的多出来的字节，而是使用free属性将这些字节数量记录起来，并等待将来使用

sdstrim函数接受一个SDS 和一个C字符串作为参数，移除SDS前后前缀中所有在C字符串中出现过的字符

1	sdstrim(s, "XY"); // 移除SDS字符串中的前后前缀中所有'X'和'Y'

代码验证


int main(int argc, char const *argv[])
{
    sds s = sdsnew("XYXabcXYYX");
    printf("s: %s, s->len: %ld, s->free: %ld\n", s, sdslen(s), sdsavail(s));

    s = sdstrim(s, "XY");
    printf("s: %s, s->len: %ld, s->free: %ld\n", s, sdslen(s), sdsavail(s));

    return 0;
}

执行结果：

二进制安全

C字符串中的字符必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为字符串的结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频这样的二进制数据

如果有一种使用空字符来分割多个单词的特殊数据格式，那么这种格式就不能使用C字符串来保存

而SDS使用len属性来判断字符串长度的，所以不存在此问题

兼容部分C字符串函数

SDS底层的数据结构中使用buf属性存储实际的字符串数据，本身的存储还是遵循C字符串的惯例，这使得SDS可以复用部分C字符串的库函数

总结

场景	C 字符串	SDS
字符串长度获取	慢（复杂度为`O(N)`）	快（复杂度为`O(1)`）
API安全性	低（字符串拼接操作需要使用者自行考虑字符串扩容，否则可能会出现缓冲区溢出）	高（字符串拼接操作预先检查容量，不会造成缓冲区溢出）
字符串修改效率	较低（修改字符串N次必然需要执行N次内存重分配）	高（修改字符串N次最多需要执行N次内存重分配）
数据内容	只能保存文本数据	二进制安全的，也适用于二进制数据的保存
库函数兼容性	不存在兼容问题	可以使用部分库函数（底层字符串存储仍然保持`C`字符串的惯例是得以复用部分库函数的关键）