《Redis设计与实现》之简单动态字符串

• 前言
• SDS定义
• SDS与C字符串的区别
• • 常数复杂度获取字符串
  • 杜绝缓冲区溢出
  • 减少修改字符串时带来的内存重分配次数
  • • 空间预分配
    • 惰性空间释放
  • 二进制安全
  • 兼容了部分C字符串的库函数

Redis没有直接使用C语言的传统字符串，而是自己构建了一种名为简单动态字符串（simple dynamic string），简称SDS，所有Redis使用SDS作为默认的字符串。

//在源码的sds.h中定义了sds的结构
struct sdshdr{
	//记录buf数组已经使用过的字节数量
	//等于SDS所保存的字符串长度
	int len;
	//记录buf数组中未使用过的字节数量
	int free;
	//字节数组，用于保存字符串
	char buf[];
};

图2-1描述了一个SDS对象，它的len属性表示当前字符串长度为5，free属性表示当前未使用的字节数量为0，仔细观察，buf数组还是以’’结尾的。所以buf的实际长度其实是free+len+1，这个1是为空字符分配的。

在C语言的字符串当中，如果要获取一个C字符串长度的话，需要对字符串遍历，直到遇到空字符为止，才能获取字符串的长度，时间复杂度为O(n)。而Redis中SDS的len属性就是表示了buf数组所保存的字符串的长度，所以获取一个字符串的长度是O(1)。

在C语言的字符串当中，是没有对字符串的边界进行判断的，容易造成缓冲区溢出问题。比如，C语言的strcat拼接函数，strcat(char* dest,char* src)，是将一个源字符串拼接到目标字符串当中，但执行这个函数是在假设dest字符串已经分配足够多的内存。但假设一旦不成立后，就造成了缓冲区溢出。

为了避免缓冲区溢出问题，redis为SDS提供的API会先检查SDS的空间是否满足了修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至满足修改所需大小为止，然后才执行实际的修改操作。

在C语言的字符串当中，如果对一个C字符串连续执行N次的字符串增长或缩短操作，那么必须执行N次的内存重分配操作。而Redis是一个频繁对字符串进行修改操作的数据库，如果对一个字符串不断执行增长或缩短操作，那么执行内存重分配操作的时间可能比修改字符串的时间更长，为了不让内存重分配对性能造成很大的影响，SDS的空间预分配和惰性空间释放策略可以减少修改字符串时带来的内存重分配次数。

空间预分配是用于优化字符串增长操作：当SDS的API对一个SDS进行增长操作时（append)，并且需要对SDS进行空间扩展的时候，程序不仅为SDS分配修改所需要的空间大小，还会额外的分配未使用空间。

额外分配的未使用空间策略：
1）当执行修改操作后，SDS所保存的字符串长度小于1MB时，额外分配的未使用空间大小等于SDS所保存的字符串长度(len属性)。
比如，一个SDS对象在修改之后，len属性为13字节，那么额外分配free也等于13字节。如果下次修改操作可用于free能够满足，那么就不需要执行内存重分配。
2）当执行修改操作后，SDS的len属性大于1MB，那么额外分配的未使用空间大小等于1MB。
比如，一个SDS对象在修改之后，len属性为30MB，那么额外分配free等于1MB。

惰性空间释放是用于优化字符串缩短操作：当SDS的API对一个SDS进行缩短操作时(trim)，程序并不回立即使用内存重分配来回收缩短后多出来的字节，而是使用了free属性将这些字节的数量记录下来，并等待将来使用。
可能读者担心的点在于，这些free未使用空间永远不会释放掉吗，也不是的，redis提供了相对于的API，在我们需要真正需要释放的时候，可以使用API释放掉free空间。

通过SDS的空间预分配和惰性空间释放策略，在执行连续N次的字符串修改操作时，从必须执行N次的内存重分配操作变成了最多需要执行N次内存重分配操作。

C语言的字符串只能存储文本数据，因为它是以空字符（‘’）结尾的，如果字符串需要以特殊字符（如空字符）为分割呢？那么C字符串显然不满足了。Redis的SDS中存在len属性，所以它也能够存储特殊的字符，不仅能够存储文本数据，也能够存储二进制。

Redis的SDS中buf数组也是以空字符结尾的，这也让它能够兼容部分的C字符串的库函数。比如，一些存储文本数据的SDS，也能够使用C字符串的库函数。