Redis没有直接使用C语言传统的字符串表示，而是构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型，并将SDS作为默认的字符串表示。
1 SDS定义
struct sdshdr{
// 记录buf数组已经使用字节的数量
// 等于SDS所保存字符串的长度
int len;
// 记录buf数组中未使用字节的数量
int free;
// 字节数组
char buf[];
}
SDS示例
上图展示了一个SDS示例：
(1) free属性值为3，表示这个SDS还有3个未使用的空间。
(2) len属性的值为5，表示这个SDS保存了一个5个字节长的字符串。
(3) buf属性是一个char类型的数组，数据的前5个字节分别了‘R’、'e'、 'd'、 'i'、 's' 五个字符，而最后一个字节保存了空字符‘\0’。
SDS遵循C字符串结尾的惯例，保存空字符串的1个字节空你就按不计算在SDS的len属性里面，并且为空字符分配额外的1个字节空间。
2 SDS与C字符串的区别
2.1 常数复杂度获取字符串的长度
C字符串不记录自身的长度信息，所以为了获取一个C字符串的长度，需要遍历整个字符串，直到遇到代表字符串结尾的空字符为止，这个操作的复杂度为O(N)。而SDS在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度为O(1)。
2.2 杜绝缓冲区溢出
C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow）。例如，假设程序里有两个在内存中紧邻的C字符串s1和s2，其中s1字符串是“Redis”，s2字符串是“MongoDB”，如下图所示：
如果一个要执行：
strcat(s1," Cluster");
将s1的内容修改为“Redis Cluster”，但是却执行前没有给s1分配足够的内存空间，那么在执行之后，s1的数据将会溢出到s2的空间中，导致s2保存的内容被意外的修改，如下图所示。
image.png
SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性，当SDS API需要对SDS修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS空间扩展至执行修改所需的大小。
注意：上图的拼接操作之后，它还为SDS分配了13个字节未使用空间。
2.3 减少修改字符串时带来的内存重分配次数
因为C字符串不记录自身的长度，所以对于一个包含了N个字符的C字符串来说，这个C字符串底层实现总是一个N+1个字符长的数组（额外的一个字符空间用于保存空字符）。正是因为C字符串的长度和底层数组的长度之间存在这这种关联性，所以每次增长或缩短一个C字符串，程序总是要对保存这个C字符串的数组进行一次内存重分配操作。
(1) 如果执行增长字符串的操作，那么在执行之前，需要先通过内存重分配扩展底层数组的空间大小，如果没有执行这一步那么会导致缓冲区溢出。
(2) 如果执行缩短字符串的操作，那么在执行之后，需要通过内存重分配释放不再使用的那部分内存，如果没有则导致内存泄漏。
SDS通过未使用未使用空间解除了字符串长度和底层数组的关联：在SDS中，buf数组的长度不一定是字符数量加1，数组中可以包含未使用字节，而这些字节数量就是SDS的free属性。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。
(1) 空间预分配
空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个SDS 进行修改并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。
额外未使用空间的分配规则：
(1) 如果对SDS进行修改之后，SDS的长度（也即是len属性的值） 将小于1MB，那么程序分配和len属性同样大小的未使用空间， 这时SDS的len属性的值将和 free属性的值相同，如上一小节图所示。
(2) 如果对SDS进行修改之后，SDS 的长度将大于等千1MB, 那么程序会分配1MB的未用空间。例如，如果进行修改之后，SDS的len将变成30MB, 那么程序会分配1MB的未使用空间，SDS的buf数组的实际长度将为30 MB + 1MB + 1byte。
通过空间预分配策略，Redis可以减少连续执行字符串增长所需的内存重分配次数。
(2) 惰性空间释放
惰性空间释放用于优化 SDS的字符串缩短操作：当 SDS的API需要缩短 SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。
例如，sdstrim函数接受一个 SDS和一个C字符串作为参数， 移除 SDS中所有在C字符串中出现过的字符。
// 移除SDS字符串中的所有“X”和“Y”
sdstrim(s,"XY");
执行sdstrim之后SDS没有释放多余的8个字节的空间，而是将这8个字节的空间作为未使用的空间保留在SDS里面，如果将来要对SDS进行增长操作，这些未使用的空间就可以使用。
2.4 二进制安全
C字符串中的字符必须符合某种编码（比如ASCII)，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读人的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据。SDS的API都是二进制安全的，所有SDS API都会已处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤或者假设，数据写入时是什么样子的，读取的时候就是什么样的。所以SDS不仅可以保存文本数据，还可以保存任意格式的二进制数据。
3 小结
(1) Redis只会使用C字符串作为字面量，在大多数情况下，Redis使用SDS（Simple Dynamic String，简单动态字符串）作为字符串表示。
(2) 比起C字符串，SDS具有以下优点：
1 常数复杂度获取字符串长度。
2 杜绝缓冲区溢出。
3 减少修改字符串长度时所需的内存重分配次数。修改字符串长度N次最多需要执行N次内存重分配。
4 二进制安全，可以保存任何格式的二进制数据。
本文完
注：本文参考《Redis设计与实现》，如发现错误，请指正！
网友评论