背景
- 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语言对字符串从操作的函数。向后兼容性。
网友评论