Redis—简单动态字符串（SDS）

这两天我原本打算学习一下若依这个老生常谈的开源的后端管理系统（如果你没听过，在将来的某一天也会听说甚至用到），拿到这个系统的前后端分离版后，码云项目地址，一启动发现需要Redis服务，遂转战学习Redis

白泽预计将花费一个月的时间去学习Redis的设计与实现，并尽量保证文章的输出，我们共勉~

本次介绍一个Redis的数据类型，简单动态字符串，SDS（simple dynamic string），因为Redis是用C语言写的，而且C语言本身就有字符串这个数据类型，那就要提出疑问：为啥不直接用C语言的字符串，而要新发明一种新的字符串类型呢？

事实上，即使我没学过Redis，也听闻过它可以以键值对的形式存储数据，它很快。但它的快绝不仅仅是键值对的存储形式带来的，SDS的存在就是帮助Redis更快，更安全~

SDS的定义

//sds的存储结构
struct sdshdr {
	int len;	//记录buf数组中已经使用的字节的数量
	int free;	//记录buf数组中还未使用的字节的数量
	char buf[]; //字节数组，用于保存字符串
};

很明显，SDS内部就是一个C语言的字符串（字节数组），只是多了两个变量存放当前的长度和剩余的长度，下面这张图模拟了当sds存放了 ‘Redis’ 字符串后的情况

SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性中，好处是SDS可以直接重用一部分的C字符串函数库中的函数（只要SDS内部的buf也是以’\0’结尾，那就是一个C语言的字符串啊，有啥不能用的~）

当然还可以像下面这张图这样，5为已使用的buf数组的长度，5为未使用的数组的长度，而下面这种场景才是更多的出现在Redis中的。接下来就讲讲通过free，len和C语言字符串buf的配合，如何使Redis比单纯使用C语言的字符串更快，更安全吧

SDS与C字符串的区别

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

因为SDS的free直接就记录了buf数组的使用长度，因此如果要获取buf的长度，SDS只需要O(1)的时间复杂度，而C的字符串需要O(N)，因此更快！

2. 杜绝缓冲区溢出：

如上图：因为C语言字符串不记录本身的长度，如果原本连续的内存中存放了str1 = ‘Redis’，str2 = 'MySQL’两个字符串，此时执行某个操作将str1替换为下方的str1 = ‘Hello BaiZe’，那么str1的内容将会溢出到原本str2的空间中

如果使用SDS的API修改SDS内容时，如果buf剩余空间不足，API将先扩容SDS的空间，然后再修改buf数组的内容。因此更安全！

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

C语言的字符串无论是增长还是缩短，每次都需要程序重新分配内存（因为可能会影响到内存已经存在的数据），这就意味着每次都将消耗一定资源去完成这个任务。

而Redis作为数据库，数据可能会频繁修改，每次都去内存重分配就慢了。而在SDS中，len、free和buf数组相配合，就能从两个角度去优化频繁修改时时间的消耗

• 空间预分配：

  当SDS需要扩容的时候（进行一次内存重新分配），扩容后len小于1MB，那么程序分配和len属性相同大小的free空间，则本次扩容后SDS的free会等于此时SDS的len，当然空字符’\0’依旧会占额外的一字节的空间，本次扩容结束后SDS所占空间为：len + free + 1byte

  如果扩容后len大于1MB，那么程序会分配1MB的未使用free空间（所以最多就是给你分配1MB的free），此时SDS所占用空间为：len + free(1MB) + 1byte

  说到底空间预分配的目的就是每次扩容时多申请一些空间（每次扩容也是一次内存的重新分配），以备下次buf数组长度增长时或许可以不去申请内存的重新分配，但最差的情况下每次多申请的空间都不够下次用的，那依旧退化为C语言字符串扩容时每次都需要重新分配内存的情况

• 惰性空间释放

  有扩容就有缩短，当SDS的buf变短时，程序并不直接进行内存的重新分配，而是只是增加free的值，**这比进行一次内存重新分配缩短buf快很多！**buf数组多余的5个空间依旧保留，如果将来要对SDS进行增长操作还能用上。当然如果有需要SDS也提供了API对这些空间进行真正的释放

4. 二进制安全

C语言字符串以空字符’\0’判断字符串是否结束，那么下面这种含有两个空字符的字符串就无法完整地存入C语言的字符串，因此也无法存储二进制数据（图片、视频、音频等），但是SDS的长度是由len定义的，因此内部也可以存放空字符’\0’，也可以用于保存二进制数据（啥都能存）

小结

C字符串和SDS之间的区别

C字符串	SDS
获取字符串长度的时间复杂度为O(N)	获取字符串长度的时间复杂度为O(1)
API是不安全的，可能会造成缓冲区溢出	API是安全的，不会造成缓冲区溢出
修改字符串长度N次必然需要执行N次内存重分配	修改字符串长度N次最多需要执行N次内存重分配
只能保存文本数据	可以保存文本或者二进制数据
可以使用所有C语言字符串函数库的函数	可以使用部分C语言字符串函数库的函数