[Redis]-[Redis底层数据结构]-SDS

前言

Redis 没有直接使用 C 语言的字符串，而是自己构建了一种名为 简单动态字符串 ($SimpleDynamicString$，SDS)

结构定义

struct sdshdr{
    
	int len;    //记录buf数组中已使用字节的数量，也即该变量所保存字符串的长度
	int free;   //记录buf数组中未被使用的字节数
	char buf[]; //字节数组用于保存字符串实际内容
};

SDS 遵循 C 字符串以空字符 ‘0’ 为结尾的惯例，但这个字符不算在字符串长度，即 len 属性之中。对于这个空字符的操作，SDS 的接口都已经封装好了，对用户来说这个空字符就是透明的；保留这个惯例的好处在于，可以直接使用 C 字符串函数库里的一些函数

SDS 的特点

常数复杂度获取字符串的长度

C 字符串本身并不记录自身的长度，每次获取字符串的长度都需要去遍历整个字符串，复杂度为 O(N)；

而 SDS 使用一个变量 len 维护字符串内容的长度，每次获取长度只需访问 len 属性的值即可，复杂度为 O(1)
确保了获取字符串的长度的操作的时间复杂度从 O(N) 降低为 O(1)，保证这个操作不会是影响性能的瓶颈，特别是在频繁获取字符串长度的场景下

杜绝了缓冲区溢出

由于 C 字符串不记录本身的长度，容易造成 缓冲区溢出 的问题。例如，<String.h>/strcat 函数，在对一个字符串拼接到另外一个字符串末尾时，由于不知道目标字符串的长度，执行函数会默认目标字符串所占空间是足够拼接被拼接的字符串的，所以会直接将被拼接的字符串接到目标字符串的后续空间中，这样就可能导致原来目标字符串后续空间中的内容被被拼接字符串给覆盖掉，即发生了缓冲区溢出的问题

而 SDS 记录了字符串本身的长度，在执行类似的拼接操作时，会先判断目标字符串的所占空间大小是否足以拼接被拼接字符串，如果不够的话，就会先扩展目标字符串的空间大小再进行拼接操作

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

一个包含 N 个字符的 C 字符串总是占用 N + 1 个字符长的数组，所以每次增长或者缩短一个 C 字符串，都会对这个字符串的数组进行一次重分配操作
内存重分配需要耗费一定的时间，如果这种操作不是频繁出现，那么每次修改字符串都进行一次内存重分配还是可以接受的；但 Redis 作为数据库，经常用于速度要求严格，数据修改频繁的场景，每次修改都耗费一定时间来内存重分配就会对性能造成一定的影响

SDS 使用了 未使用空间 的方法，即 buf 数组中可以包含未使用的字节，字节的数目由 free 属性维护。通过 未使用空间，SDS 实现了 空间预分配 和 惰性空间释放 两种优化策略

空间预分配

当需要对一个 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间：

1. 如果对 SDS 进行修改之后 SDS 的长度 (len 属性) 将小于 1 MB，那么程序分配和 len 属性同样大小的未使用空间
2. 如果对 SDS 进行修改之后 SDS 的长度将大于等于 1 MB，那么程序就会分配 1 MB的未使用空间

通过 空间预分配 策略，就可以减少连续对字符串进行增长操作所需的内存重分配次数，在操作之前，会先判断未使用空间的大小是否足够，足够的话直接使用未使用空间
通过这种策略，SDS 将连续增长 N 次字符串所需的内存重分配次数从 必定 N 次 降低为 最多 N 次

惰性空间释放

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

通过这种策略，SDS 避免了缩短字符串时所需的内存重分配操作，并为将来可能出现的增长操作提供了优化：后续需要增长字符串时，如果增长所需的空间小于未使用空间的大小，那就可以直接进行增长操作而不需要进行内存重分配来扩展字符串的空间

二进制安全

C 字符串中的字符必须符合某种编码；而且除了字符串的末尾之外，字符串里面不能包含空字符，否则就会导致字符串保存的内容与预期的不符。这些性质使得 C 字符串不符合二进制安全的性质

而 SDS 的 API 都是二进制安全的，API 会以处理二进制的方式来处理 SDS 存放在 buf 数组中的内容，不会对其中的数据做任何限制，过滤，或者假设，数据在写入时是什么样的，被读取时就是什么样的，在这里没有任何 “特殊字符” 的概念，所有字符都是其本身而已。另外，SDS 使用 len 属性来判断字符串是否结束，而不是使用空字符，这就避免了空字符会造成的影响

有了二进制安全的特性，Redis 不仅可以存储文本数据，还可以保存任意格式的二进制数据

兼容部分 C 字符串函数

SDS 遵循 C 字符串中以空字符为结尾的惯例，这使得其可以重用一部分字符串函数库的函数，避免了不必要的代码重复