Redis字符串SDS设计

redis数据库底层没有直接使用c的字符串表示，而是自己使用名为简单动态字符串(simple dynamic string,SDS)

---

SDS定义

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

---

示例

image.png

• free属性值为0，表示sds没有分配任何为使用空间
• len属性为5，表示这个sds保存了一个5个字节长的字符串
• buf属性表示一个char类型的数组，前五个字节保存"Redis"，而最后一个字节保存空字符'\0'
  注：SDS遵循空字符结尾的好处是：SDS可以直接重用一部分c字符串函数库的函数，比如直接打印字符串printf

---

SDS与C字符串的区别

1. 获取字符串长度时间复杂度不同(提高获取字符串长度性能)

• 普通C字符串获取长度需要遍历整个字符串，因此复杂度为O(N)。
• SDS的len属性直接保存字符串的长度，复杂度为O(1)

2. SDS杜绝缓冲区溢出

• C:比如说，拼接字符串函数char *strcat(char *dest,const char *sec)，当dest不足够存放src所有内容时，就会产生缓冲区溢出
• SDS:SDS有自己的空间分配策略，当SDS的API对字符串操作时，API会先检查SDS的空间是否满足操作，不满足的话API会自动将SDS的空间扩展至所需大小，然后才执行操作

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

• 当C需要修改字符串长度时，我们需要再次对使用内存重新分配，由于内存重新分配设计复杂的算法，并且可能执行系统调用，所以通常是比较耗时的操作
• SDS的空间预分配跟惰性空间释放会对字符串的内存分配次数进行优化

1.空间预分配

• 如果对SDS修改后，SDS的长度(len)<1MB，则程序将分配和len属性同样大小的free空间
• 如果对SDS修改后，SDS的长度(len)>1MB，则程序将分配1MB的free空间

2.惰性空间释放

• 惰性空间释放用于优化SDS缩短的操作，当SDS缩短时，程序不会立即进行内存重新分配，而是用free保存多余出来的字节，方便未来使用

4.二进制安全

• C字符串中的字符除了末尾外，不能包含空字符，否则会被识别成字符串结尾
• SDS可以用来保存二进制数据，所以SDS的API都是二进制安全(binary-safe)的，所有的SDS API 会以处理二进制方式来处理buf的数据。因此数据写入是什么样的，读取出来就是什么样的。

5.兼容部分C字符串函数

• 虽然SDS的API是二进制安全的，但其也遵循C字符串以空字符结尾的惯例：这些API总会将SDS保存的末尾设置为空字符，并且总会在为buf数组分配空间时多分配一个字节来容纳这个空字符，为了让保存文本数据的SDS可以重用<string.h>定义的函数

总结

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