Redis的设计和实现笔记-第二章 简单动态字符串

zzx -

简单动态字符串（Simple Dynamic String，SDS）是什么？

简单动态字符串是Redis构建的一种抽象数据类型，我们简称为SDS。

SDS的作用

Redis并没有使用C语言传统的字符串（以空字符结尾的字符数组）。而是使用SDS作为Redis的默认字符串表示。
Redis中，C字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方，比如打印日志。
Redis中，包含字符串的键值都是有SDS实现的。

SDS的数据结构定义

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

SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，所以这个空字符对于SDS的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是，SDS可以直接重用一部分C字符串函数库里面的函数

SDS字符串和C字符串的对比

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

因为SDS数据结构中存储了内容的长度，所以可以直接获取，时间复杂度是O（1）。

杜绝缓冲区溢出

可以通过len和free检查字符串和buf空间，杜绝了缓冲区溢出的安全问题。

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

C字符串的扩容都需要重新进行内存的分配。这样会比较耗时。SDS通过设计未使用空间来缓解这种情况的发生。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

1. 空间预分配

SDS进行扩展时，会分配额外的未使用空间。
公式如下：

  1. 小于1MB。程序分配和len属性同样大小的未使用空间。 eg： 如果进行修改之后，SDS的len将变成13字节，那么程序也会分配13字节的未使用空间，SDS的buf数组的实际长度将变成13+13+1=27字节（额外的一字节用于保存空字符）
  2. 大于1MB。会分配额外1MB的空间。

2. 惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作。SDS的API执行缩短操作，并不会立即使用内存重新分配回收缩短的字节，使用free属性将这些字节的数量记录下来。

二进制安全性

C字符串中的字符必须符合某种编码，并且出了字符串的末尾之外，字符串里面不能包含空字符，否则最先被读入的的空字符将被误认为时字符串结尾。这个限制C字符串只能保存文本数据，不能保存图片，音频，视频，压缩文件的。
但是SDS是通过len来判断长度的，所以可以存储上述的数据。