Redis 简单动态字符(SDS)

• 后续所有未标注版本的Redis源码都源于5.0

简单动态字符串SDS

• Redis里的字符串默认为sds类型，例如所有的key就都是sds。

SDS的定义

// V3.2之前
struct sds {
 // 记录 buf 数组中未使用字节的数量
 int free;
 // 记录 buf 数组中已使用字节的数量
 int len;
 // 字节数组，用于保存字符串
 char buf[];
};

// V3.2之后，sdshdr16/sdshdr32同理
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用 */
    uint8_t alloc; /* 总长 */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

• sds用到了柔性数组，数组放在结构体最后时，可以根据需要动态分配，如前面len和free各需要4字节，申请16字节时，除去结束符\0的位置，剩下7字节就是buf的使用长度了，需要注意结束符\0不算到len中。
• 以上展示了两个版本sds结构体代码，V3.2之前free和len各占4字节，比较浪费空间，最节省的办法就是按位算len和free的个数，进而出现了sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。
• 新版sds中，flags低3位就代表了sdshdrN中的某一个，3位就可以区分出5种结构，可以发现sdshdr5中没有len、alloc，由flags高5位表示len，sdshdr8 sdshdr16 sdshdr32 sdshdr64就比较容易理解了，flags低3位和sdshdr5一样，高5位是空闲状态。

SDS与C字符串的区别

• 性能优化：记录后获取字符长度时，时间复杂度降到O(1)，避免遍历。
• 函数库兼容：SDS遵循C的惯例，结尾以'\0'结束，这样很多C的函数库避免重复。
• 保证安全：有len字段不用依赖“/0”终止符，保证二进制安全。

SDS拼接时扩容策略

• sds有空余空间时直接扩容即可。空间不足时分两种情况，扩容后总长小于1M时按两倍扩容，大于1M时按总长+1M扩容，最后根据长度重新选择结构sdshdrN并选择是否重新开辟空间。
• 在《Redis运维与开发》中也提到，尽量减少sds的拼接操作，避免预分配造成空间浪费。