对Redis有一定了解的人一定听过SDS与柔性数组，它们是Redis工作高效的秘密之一，本文主要介绍SDS的实现以及相比于传统字符串char*的优势。

# SDS 基础结构

简单动态字符串(SDS, Simple Dynamic Strings) 是Redis基本数据结构之一，Redis内大量数据都是以字符串形式储存的，因此一个高效且安全的数据存储结构尤为重要。

SDS结构经过了几次演变，基础数据结构由三部分构成：

struct sds{
  int len; //buf占用字节数
  int free; // buf中剩余字节数
  char buf[];	// 真正储存字符串的数据空间
}
1
2
3
4
5

其中len和free是SDS的固定头部，用于标识数据空间的总大小和剩余大小；buf被称为柔性数组，用于储存字符串。

之所以用柔性数组存放字符串，是因为柔性数组的地址和结构体是连续的，这样查找内存更快（因为不需要额外通过指针找到字符串的位置）；可以很方便地通过柔性数组的首地址偏移得到结构体首地址，进而能很方便地获取其余变量。

# SDS 对比char*的优点

# 1. 防止缓冲区溢出

SDS 相比于普通字符串 char*， 多了标示其长度和剩余空间的属性，当我们对SDS进行修改、追加、合并等操作时，可以很轻松的进行边界检查，防止操作越界产生错误。

# 2. 二进制安全

什么是二进制安全？

通俗地讲，C语言中，用“\0”表示字符串的结束，如果字符串中本身就有“\0”字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则是二进制安全。

SDS 通过边界属性的设置，巧妙的实现了二进制安全：SDS对内容结束的检查不再依赖于'\0'，而是通过对len和free的计算，实现内容的读取。由于有长度统计变量len的存在，读写字符串时不依赖“\0”终止符，保证了二进制安全。

# 3. 获取字符串长度

一个显而易见的优点是，SDS可以在O(1)时间复杂度直接返回字符串的长度（char* 是 O(n)，必须遍历到末尾)。

# 4. 空间预分配 与 惰性释放

空间预分配与惰性释放是基于SDS特点实现的，SDS中柔性数组的容量和字符串的长度可以是不一致的，基于这一特点，可以提前分配一定的储存空间，或是当字符串长度变小时仅修改其内容而不回收储存空间，减少因空间分配带来的额外消耗，提高程序的性能。

# SDS的改进

# 1. 头部优化

分析SDS的数据结构我们还可以对其进一步优化：如果我们储存字符串的长度大部分时间都不超过1个字节，甚至是2个字节，那么此时SDS的头部数据（2个int, 8字节）反而成为占用空间较大的部分。如果每个字符串不论大小，其头部都占用了8个字节，那对内存的使用效率就太低了。

Redis PR#2509在SDS的基础上做了进一步改进，将SDS分为5类：

/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
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; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    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[];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

改进后的SDS：

  1. 增加了一个flags用于区别不同的类型（char类型，低3位用于区别不同的结构，高5位暂未使用）；

  2. 将free未使用空间改为了alloc已分配空间；

  3. 不同类型之间主要是字符串长度的区别：sdshdr8用8位变量储存长度和分配空间，字符串长度最大为2^8-1 = 63，整个结构体头部只有3字节，sdshdr5头部只有1字节等等；

# 2. 内存分配空间优化

源码中每个结构体都有一个__packed__标记。一般情况下，结构体会按其所有变量大小的最小公倍数做字节对齐，**而用packed修饰后，结构体则变为按1字节对齐。**1字节对齐带来的好处是巨大的：

image-20200215002330155

SDS结构体返回给上层的并非是结构体地址，而是buf地址。因此按照1字节对齐后，不仅可以节省内存；而且可以根据buf-1直接获取flags地址，并通过类型计算得到结构体地址。若没有packed的修饰，还需要对不同结构进行处理，实现更复杂。

# 3. 增加了柔性数组容量

基础的SDS只能储存最多 2^32 -1 个字符，字符串上限是 2^32 Bytes = 4GB

现在最大的sdshdr64 提供了 2^64 Bytes = 16 GB 字符串容量

# SDS 扩容

当我们对SDS执行合并、追加等操作时，可能会发生字符串长度大于柔性数组长度的情况，这时候就要进行扩容。

SDS扩容有以下几个规则：

  1. 如果SDS中剩余长度大于新增内容长度，直接在柔性数组末尾添加，不进行扩容；
  2. 如果新增后的总长度 < 1MB，按照新增长度的2倍进行扩容；
  3. 如果新增后的总长度 >= 1MB, 按照新长度+1MB进行扩容；

如果扩容后数据类型不再满足当前需求，则需要重新开辟地址，将原buf内容移到新的位置。

总的来说，SDS通过添加统计变量的方法，提高了字符串储存的安全性与效率，以空间换取时间，使诸多操作达到了O(1)级别，大幅提高了程序的运行效率。

参考资料： 《Redis5 设计与源码分析》