redis数据结构(一)：简单动态字符串 SDS

背景

redis是用C语言写的。
C语言的字符串是用char数组存的，以'\0'作为结束。

SDS 数据结构

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

SDS数据结构.png

为什么不用C语言的而自己又封了一层呢

1.算字符串长度更快

C语言算字符串的长度，要遍历整个数组，直到找到'\0'结束。时间复杂度为O(n)。
SDS把长度放进len属性中了。获取长度复杂度O(1)。

2.杜绝缓冲区溢出

C语言字符串拼接。假设字符串S1和字符串S2在内存中是紧挨着的。当你在执行stract(s1, "cluster")的时候，就把S2改了，因为C语言事先不计算字符串长度。

S1S2.png

SDS中有free字段，再拼接之前先判断free空闲的字节够不够，不够扩容，再拼接。扩容策略后面说。

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

C语言字符串，在修改的时候，每次修改如果要杜绝内存溢出，都要按长度先扩容。这就意味着每次修改字符串，都要进行一次扩容或者缩容。也就是内存重分配，字符串从老拷贝到新。应用程序暂且还可以接受。但这可是redis，每次都扩容，性能上不允许。

所以，SDS会对空间进行预分配。什么意思呢？
就是每次扩容，不是按照修改后的字符串，可丁可卯的分配内存，而是按规则分配内存。这样做的好处是，分配一次，内存够很多次修改来用。

修改后的字符串，len的值小于1M，那么就分类和len属性同样大小的为使用空间。
修改后的字符串，len的值大于1M，那么分配1M的未使用空间。

预分配.png

扩容完，再进行字符串的修改。
那么，缩容呢。之前len:5，free:5。缩完后len:2，free:8。free会回收么。不会当场回收，留着下次修改时使用。
那会一直不回收么。会有一定的策略，真正的释放，不会造成内存的浪费。

总结：
C语言修改N次必然执行N次的内存分配。
SDS修改N次最多执行N次的内存分配。

4.二进制安全

C语言字符串，以'\0'来判断结束。那么他就存在不了中间有'\0'的字符串。二进制会有大量的'\0'所以他就存不了二进制。

SDS虽然也以'\0'结尾，但不以'\0'来判断字符串的结束。而是以len的长度来判断。所以没有'\0'的限制，SDS可以存二进制。

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

SDS也以'\0'结束，是想延用C语言对字符串从操作的函数。向后兼容性。