简单动态字符串（Simple Dynamic Strings, SDS）是Redis的基本数据结构之一，用于存储字符串和整型数据。几乎所有的Redis模块都用了SDS。

Redis 3.2版本以前的SDS

Redis 3.2版本之前sds的结构定义：

struct sdshdr {
    // buf数组中已使用字节数量，即SDS所保存字符串的长度
    unsigned int len;
    // buf数组中未使用的字节数量
    unsigned int free;
    // 字节数组，真正保存字符串的数据空间
    char buf[];
};

在64位系统下，字段len和字段free各占4个字节，紧接着存放字符串。

Redis SDS结构示意图

底层存储结构如图所示：

Redis SDS结构

SDS遵循C语言字符串以空字符\0结尾的管理，空字符不会计算到len属性里，为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作都是SDS函数自动完成的。

SDS相比C字符串的优点

1. 方便获取字符串长度

C字符串不会记录本身的长度信息，如果要获取字符串长度，程序就需要遍历字符串并计数，直到遇到空字符\0，所以C字符串获取长度的操作复杂度是O(N)。

SDS因为在len属性里面已经记录了字符串长度，所以操作复杂度是O(1)，这样避免了获取字符串长度的工作成为Redis的性能瓶颈。

2. 避免缓冲区溢出

C字符串不记录自身长度带来的另外一个问题就是容易造成缓冲区溢出，比如程序里面有两个在内存中紧邻的C字符串s1和s2，我们使用strcat函数对字符串s1进行追加，但是粗心的忘了在strcat之前为s1分配足够的空间，执行完之后s1的数据就溢出到了s2的空间中，导致s2被意外修改。

C字符串缓冲区溢出

为了解决这个问题，当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改需求，如果不满足，API会自动扩展SDS空间，然后再执行实际的修改操作。所以SDS不会出现前面所说的缓冲区溢出问题。

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

C字符串的长度和底层数组长度相差1（用来存储末尾空字符），每次增长或者缩短一个C字符串的时候，程序都要对C字符串的数组进行内存重分配。增长字符串就需要扩展数组空间，缩短字符串就要回收不再使用的空间。

内存重分配涉及复杂算法，并且可能需要执行系统调用，所以通常比较耗时。如果修改字符串长度的情况很少出现，那么可以接受内存重分配，但是Redis经常被用到对速度、性能有要求，并且数据会被频繁修改的场景，所以如果存在大量的内存重分配，就会严重影响性能。

为了解决这个问题，SDS增加了free属性，用来存放未使用的字节数。据此，SDS实现了空间预分配和惰性空间释放两种优化策略。

3.1 空间预分配

空间预分配主要是优化SDS字符串增长的场景，当需要对SDS进行空间扩容时，程序除了分配修改必需的空间大小，同事还会分配一部分额外的未使用的空间。分配策略如下：

  • 如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。比如如果修改后，SDS的len变成13字节，那么程序还会分配额外的13字节未使用空间，最终buf数组实际长度是13 + 13 + 1 = 27字节。
  • 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。比如修改后SDS的ken变为30MB，那么最终buf数组的实际长度是30MB + 1MB + 1byte。

这样有了预分配的空间，如果要继续对字符串进行增长，SDS API就会先检查未使用的空间是否够用，如果够用那么就会直接使用未使用的空间，而不需要在进行内存重分配。

3.2 惰性空间释放

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

通过惰性空间释放策略，SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。

4.二进制安全

C字符串因为是以\0空字符作为字符串结束标志，所以只能用来保存文本数据，而不能保存图片、音频、视频这样的二进制数据。

而SDS是通过len属性的值来判断字符串结束，所以SDS是二进制安全的，可以用来保存任意格式的二进制数据。

5. 兼容部分字符串函数

比如要打印SDS保存的字符串值：

printf("%s", s->buf);

问题

这样的设计，不同长度的字符串都要占用相同大小的头部，一个int占4字节，len和free加起来就是8个字节，在实际应用中，存放于Redis中的字符串往往没有这么长，每个字符串这样存储未免太浪费空间了。

Redis 3.2版本后的SDS

因为早期SDS上面的问题，所以从3.2版本开始进行了重构。可以想到的办法是短字符串len和free用1字节表示，长字符串用2字节或者4字节，再长一点的用8字节表示。

实际上Redis定义了五种类型：长度1字节、2字节、4字节、8字节、小于1字节。为了标识5中类型，至少需要3位来存储（$ 2^3=8 $），1个字节8位，剩余的5位存储长度，这样可以满足长度小于32的短字符串。

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

sdshdr5

如果字符串长度大于31，1个字节依然存不下，上面的结构将不再适用。我们按之前的思路，将len和free单独存放。sdshdr8、sdshdr16、sdshdr32和sdshdr64的结构相同，只不过flags的高5位将不会填充数据。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已经使用的长度 */
    uint8_t alloc; /* 总长度 */
    unsigned char flags; /* 低3位存储类型，高5位预留 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

sdshdr16结构如图所示，其中“表头”共占用了S[2(len)+2(alloc)+1(flags)]个字节。flags的内容与sdshdr5类似，依然采用3位存储类型，但剩余5位不存储长度。

sdshdr16

字节对齐

一般情况下，结构体会按其所有变量大小的最小公倍数做字节对齐。但是sdshdr使用了__attribute__((__packed__))做修饰，这样结构体会按照1字节对齐。以sdshdr32为例，修饰前按4字节对齐大小为12(4×3)字节；修饰后按1字节对齐，注意buf是个char类型的柔性数组，地址连续，始终在flags之后。

sds packed

因为flags永远在buf前面，所以通过对数组指针做减一操作，就能方便的定位到flags中。

参考资料