【Redis】简单动态字符串（simple dynamic string, SDS）

Redis类型中有string的类型，比如我们用来做缓存的时候，经常会使用到string类型，这里就主要介绍一个Redis中string类型的实现，和C的字符串有什么区别。

SDS的定义

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

图示： 这个图展示了一个len属性为5，free属性为0的一个字符串。如果对Go语言了解的话，会联想到Go中的切片有一个容量和长度的概念。 SDS是遵循C字符串已空字符结尾的惯例，保存空字符的1字节空间不在len属性中。Redis会自动完成的。遵循这一惯例，有一个好处就是可以直接重用C字符串函数库里的部分函数。

SDS与C字符串的区别

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

获取一个C字符串的长度，我们必须要遍历整个字符串来计算，这个操作的复杂度为O(n)。而SDS中定义了len的属性，就把获取字符串的长度由O(n)降到O(1)。

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

对于一个函数N个字符的C字符串来说，底层实现总是一个N+1个字符长的数组(额外的一个用来保存空字符)。因为C字符串和底层数组的长度之间存在着这种关联性，所以对C字符串的修改，总是要对底层数组进行一次内存重分配操作，比如我们要增长字符串，我们需要先对底层数组进行扩容，否则很容易产生缓冲区溢出。又如我们要截断字符串，如果不进行重新分配，则会产生内存泄漏。 为了避免上述的缺陷，SDS通过未使用空间来解除字符串和底层数组长度之间的关联，也就是buf数组不再是字符的数量 + 1，因为数组中包含了一些未使用的字节，也就是free属性来记录。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

• 空间预分配 用来优化字符串的增长操作，当需要对SDS进行扩容的时候，程序不仅会为SDS分配必要的空间，还会分配额外的未使用空间。由一下公式决定：

  进行修改后，如果长度(len属性的值)小于1MB，那么分配和长度同样大小的未使用空间。如果大于等于1MB，则分配1MB未使用的空间。

  通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。将次数从必定N次降低为最多N次。

• 惰性空间释放 用来优化字符串截断操作，当需要对SDS户必须截断操作是，不会立即回收多出来的字节，而是使用free属性将这些字节数量记录下来，等待使用。 通过惰性空间释放策略，可以避免截断字符串时所需的内存重分配操作，并为将来可能的增长操作提供优化。

二进制安全

我们来看一个例子： C:

# include <stdio.h>
# include <strings.h>

int main () {
    char test[] = "hello\0y";
    printf("test length is %lu", strlen(test)); //test length is 5
}

Redis:

redis> SET mykey "Hello\0y"
"OK"
redis> STRLEN mykey
(integer) 7
redis>

因为C字符串结尾是以\0来认定的，所以如果C字符串中含有这种特殊字符，就会忽略后面的字符。而Redis都会以处理二进制的方式来处理SDS存放在buf数组里的数据，不会做任何限制、过滤、或者假设。

兼容部分C字符串函数

前面也提到过，尽管有了len和free这两个属性，SDS还是遵循C字符串结尾的管理，并且总会在为buf数组分配空间是多分配一个字节来容纳这个空字符，这样为了可以重用一部分库定义的函数。

总结

参考：Redis设计与实现