总结

SDS的定义

struct sdshdr {

//记录buf阵列中已使用字节的数量, 即SDS中所储存字串的长度

int len;

//记录buf阵列中未使用字节的数量

int free;

//字节阵列，用于储存字串

char buf[];

};

如图，展示了一个SDS示例：

free属性的值为0，表示这个SDS没有分配任何未使用空间。len属性的值为5，表示这个SDS储存了一个5字节的字串。buf属性是一个char型别的阵列，阵列的前5个字节分别储存了\'R\', \'e\',\'d\',\'i\',\'s\', 5个字元，而最后一个字节则储存了空字元\'\'。 SDS遵循C语言字串以空字元结尾的惯例，储存空字元的1字节空间不计算在SDS的len属性里面，并且为空字元分配额外的1字节空间，以及新增空字元到字串末尾等操作，都是由SDS函式自动完成的，所以这个空字元对于SDS的使用者来说是完全透明的。遵循空字元结尾这一惯例的好处是，SDS可以直接重用一部分C字串函式库里的函式。

举个例子，如果我们有一个指定上图所示的SDS的指标s，那么我们可以直接使用/printf函式，通过执行以下语句：

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

来打印出SDS储存的字串值“Redis”，而无须为SDS编写专门的打印函式。

下图展示了另一个SDS示例。这个SDS和之前展示的SDS一样，都储存了字串值“Redis”。这个SDS和之前展示的SDS区别在于，这个SDS的buf阵列分配了3个字节未使用空间，所以它的free属性的值为3；

SDS与C字串的区别

C语言使用的这种简单的字串表示方式，并不能满足Redis对字串在安全性、效率以及功能方面的要求，接下来的内容将详细对比C字串和SDS直接的区别，并说明SDS比C字串更适用于Redis的原因。

常数复杂度获取字串长度

因为C字串并不记录自身的长度资讯，所以为了获取一个C字串的长度，程式必须遍历整个字串，对遇到的每个字元进行计数，直到遇到代表字串结尾的空字元为止，这个操作的复杂度为O(N)。

和C字串不同，因为SDS在len属性中记录的SDS本身的长度，所以获取一个SDS长度的复杂度仅为O(1)。

通过使用SDS而不是C字串，Redis将获取字串长度所需要的复杂度从O(N)降低到了O(1)，这确保了获取字串长度的工作不会成为Redis的效能瓶颈。

杜绝缓冲区溢位

除了获取字串长度的复杂度高之外，C字串不记录自身长度带来的另一个问题是容易造成缓冲区溢位（buffer overflow）。举个例子，/strcat函式可以将src字串中的内容拼接到dest字串的末尾：

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

因为C字串不记录自身的长度，所以strcat假定使用者在执行这个函式时，已经为dest分配了足够多的内容，可以容纳src字串中的所有内容，而一旦这个假定不成立时，就会产生缓冲区溢位。

与C字串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢位的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩充套件至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢位问题。

举个例子，SDS的API里面也有个用于执行拼接操作的sdscat函式，它可以将一个C字串拼接到给的那个SDS所储存到字串的后面，但是在执行拼接操作之前，sdscat会先检查给定SDS的空间是否足够，如果不够的话, sdscat就会先扩充套件SDS的空间，然后才执行拼接操作。

sdscat执行之前的SDS

sdscat执行之后的SDS

图中所示的, sdscat不仅对这个SDS进行了拼接操作，它还为SDS分配了13字节的未使用空间，并且拼接之后的字串也正好是13字节长，这种现象既不是bug也不是巧合，它和SDS的空间分配策略有关。下面将对这一策略进行说明。

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

正如上面所说，因为C字串并不记录自身的长度，所以对于一个包含了N个字元的C字串来说，这个C字串的底层实现总是一个N+1个字元长的阵列（额外的一个字元空间用于储存空字元）。因为C字串的长度和底层阵列之间存在着这种关联性，所以每次增长或缩短一个C字串，程式都总要对储存这个C字串的阵列进行一次内存重分配操作：

如果程式执行的是增长字串的操作，比如拼接操作（append），那么在执行这个操作之前，程式需要先通过内存重分配来扩充套件底层阵列的空间大小（如果忘了这一步就会产生缓冲区溢位）。如果程式执行的是缩短字串的操作，比如截断操作（trim），那么在执行这个操作之后，程式需要通过内存重分配来释放字串不再使用的那部分空间（如果忘了这一步就会产生内存泄漏）。 为了避免C字串的这种缺陷，SDS通过未使用空间解除了字串长度和底层阵列长度之间的关联：在SDS中，buf阵列的长度不一定就是字元数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。

通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

空间预分配用于优化SDS的字串增长操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩充套件的时候，程式不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。

其中，额外分配的未使用空间数量由以下公式决定：

如果对SDS进行修改之后，SDS的长度(即len属性)将小于1MB，那么程式分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。举个例子，如果进行修改之后，SDS的len变成了13字节，那么程式也会分配13字节的未使用空间，SDS的buf阵列的实际长度将变成13+13+1=27字节（额外的一个字节用于储存空字元）。如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程式会分配1MB的未使用空间。通过空间预分配策略，Redis可以减少连续执行字串增长操作所需的内存重分配次数。在扩充套件SDS空间之前，SDS API会先检查未使用空间free是否足够，如果足够的话，API就会直接使用未使用空间，而无须执行内存重分配。通过这种预分配策略，SDS将连续增长N次字串所需的内存重分配次数从必定N次降低为最多N次。

惰性空间释放

惰性空间释放用于优化SDS的字串缩短操作：当SDS的API需要缩短SDS储存的字串时，程式并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。

举个例子，sdstrim函式接受一个SDS和一个C字串作为引数，移除SDS中所有在C字串中出现过的字元。

比如下图所示的SDS值s来说，

执行：

sdstrim(s, "XY"); //移除SDS字串中所有的\'X\'和\'Y\'

会将SDS修改为下图

执行sdstrim之后的SDS

注意执行sdstrim之后的SDS并没有释放出来的8字节空间，而是将这8字节空间作为未使用空间储存在了SDS里面，如果将来要对SDS进行增长操作的话，这些未使用空间就可以派上用场了。

通过惰性空间释放策略，SDS避免了缩短字串时所需要的内存重分配操作，并为将来可能有的增长操作提供了优化。与此同时，SDS也提供了相应的API，让我们可以在有需要时，真正的释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

二进位制安全

C字串中的字元必须符合某种编码（比如ASCII），并且除了字串的末尾之外，字串里面不能包含空字元，否则最先被程式读入的空字元将被误认为是字串结尾，这些限制使得C字串只能储存文字资料，而不能储存像图片、音讯、视讯、压缩档案这样的二进位制资料。

虽然数据库一般用于储存文字资料，但是使用数据库来储存二进位制资料的场景也不少见，因此，为了确保Reis可以适用于各种不同的使用场景，SDS的API都是二进位制安全的（binary-safe）,所有SDS API都会以处理二进位制的方式来处理SDS存放在buf数组里的资料，程式不会对其中的资料做任何限制、过滤，资料再写入时是什么样的，它被读取时就是什么样。

这也是我们将SDS的buf属性成为字节阵列的原因（Redis并不是用这个阵列来储存字元，而是用它来储存一系列二进位制资料）。

相容部分C字串函式

虽然SDS的API都是二进位制安全的，但它们都一样遵循C字串以空字元结尾的惯例：这些API总会将SDS储存资料的末尾设定为空字元，并且总会在为buf阵列分配空间时多分配一个字节来容纳这个空字元，这是为了让那些储存文字资料的SDS可以重用一部分库定义的函式。