【Redis】一、Redis的简单动态字符串SDS

Redis没有直接使用C语言传统的字符串表示(以空字符 \0 结尾的字符数组)，而是构建了一种名为简单动态字符串SDS的抽象类型，并将SDS用作Redis的默认字符串表示。

SDS的数据结构

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

SDS结构

上图中是一个 SDS对象, 字符串的值是 Redis; 长度为5,剩余可用空间为3 ； ‘\0’ 是SDS遵循了C字符串以空字符串结尾的惯例(之所以遵循是因为可以让SDS重用C语言的一些库函数 ), 保存这个空字符串的一个字节空间不计算在 len中；

SDS与C字符串的区别

C语言使用长度为N+1的字符数组来表示长度为N的字符串，并且数字最后一个元素总是 空字符串’\0’.

C语言的字符串

对比两个结构，我们来分析一下 为何 Redis要自己定义SDS

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

因为C字符串不自己记录自身的长度信息,所以为了获取长度，那么必须每次都要遍历整个字符串才能获取,时间复杂度是O(N).

而SDS自身有个属性len保存了自身的长度,所以只需要获取这个属性就行了,时间复杂度是 O(1).

而且设置和更新SDS的长度是用SDS的API在执行时自动完成。 所以确保了 获取长度STRLEN命令不会成为我们的瓶颈。

2. 杜绝缓冲区溢出

C字符串不记录len 除了获取长度的复杂度高之外,还会容易造成缓冲区溢出。 比如C字符串拼接 char *strcat(char *dest,const char *src) 操作; 需要事先为dest 分配足够的内存, 如果事先忘记给dest 分配内存，就会产生缓冲区溢出。举个例子

缓冲区溢出

与C字符不同的是,SDS的空间分配策略杜绝了发生缓冲区溢出的可能性; 当SDS API需要对SDS进行修改时，API会先检查SDS空间是否满足修改所需的要求，如果不满足 API会自动SDS的空间扩展至执行修改所需大小。因为扩容自动由API进行,所以不会发生缓冲区溢出！

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

因为C字符串的每次增长或者缩短都需要程序进行一次内存重分配的操作:

-- 增长,程序需要先通过内存重分配来扩展底层数组的空间大小----如果忘记了,则会产生上面2的缓冲区溢出
-- 缩短,比如 阶段操作(trim),那么执行这个操作之后,需要内存重分配来释放多余的那部分空间，如果忘记会发生内存泄露；

因为内存重分配涉及复杂的算法，并且可能需要执行系统调用，它通常是一个比较耗时的操作 Redis作为数据库，如果每次都要重新内存分配会影响性能 SDS 有个字段 free 为未使用空间，通过它可以实现 空间预分配和惰性空间释放两种优化策略

空间预分配

空间预分配用户优化SDS字符串增长操作.当API对一个SDS进行修改,并且需要扩展空间的时候，程序会为SDS分配额外的未使用空间 – 如果对SDS进行修改之后，SDS长度(len 属性的值)将小于1M,那么程序分配和len属性同样大小的未使用空间。 例如 len增长之后等于13字节,那么预分配之后的内存大小等于 13+13+1 = 27(额外的1字节是 空字符串) – 如果SDS长度大于1M; 那么会分配未使用空间1M; 例如增长之后SDS长度将变成30M ,那么再分配1M的未使用空间 30M+1M +1byte ; 也可以说增长之后大于1M,那么最多只会预分配出1M的未使用空间；

通过预分配策略，Redis可以减少连续执行字符串增长操作所需要的内存重分配次数

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作，当API需要缩短字符串时候，程序不会立即使用内存重新分配来回收多余的字节； 但是SDS提供了相应的API,让我们可以在有需要的时候真正的释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费！

4.二进制安全

C字符串必须符合某种编码(比如ASCII),并且除了末尾之外，字符串里面不能包含空字符 ‘\n’ ，否则最先被程序读入空字符串将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存像 图片，音频，视频等等二进制文件。

SDS就不存在这样的问题，Redis的buf数组是用来保存一系列的二进制数据。

总结

1.Redis 什么时候用C语言字符串？

redis里面，C字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方，例如打印日志；

2.SDS与C字符串的区别

①. C字符串获取字符串长度复杂度O(N);SDS是O(1),因为SDS有个专门的len属性; ②.C字符串可能发生缓冲区溢出,SDS不会，因为SDS的API会自动内存分配 ③.C字符串每次增长缩短都需要重新内存分配,而SDS有自己的优化策略：空间预分配 和 惰性空间释放 ④.C字符串只能存文本数据,SDS存的二进制数据