2.1 数据结构
在学习SDS源码前，我们先思考一个问题：如何实现一个扩容方便且二进制安全的字符串呢？
注意
什么是二进制安全？通俗地讲，C语言中，用“\0”表示字符串的结束，如果字符串中本身就有“\0”字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则是二进制安全。
SDS既然是字符串，那么首先需要一个字符串指针；为了方便上层的接口调用，该结构还需要记录一些统计信息，如当前数据长度和剩余容量等，例如：
struct sds {
int len; // buf中已占用字节数
int free; // buf中剩余可用字节数
char buf[]; // 数据空间
};
SDS结构示意如图2-1所示，在64位系统下，字段len和字段free各占4个字节，紧接着存放字符串。
图2-1 SDS结构示意
Redis 3.2之前的SDS也是这样设计的。这样设计有以下几个优点。
1）有单独的统计变量len和free（称为头部）。可以很方便地得到字符串长度。
2）内容存放在柔性数组buf中，SDS对上层暴露的指针不是指向结构体SDS的指针，而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容，兼容C语言处理字符串的各种函数。
3）由于有长度统计变量len的存在，读写字符串时不依赖“\0”终止符，保证了二进制安全。
注意
上例中的buf[]是一个柔性数组。柔性数组成员（flexible array member），也叫伸缩性数组成员，只能被放在结构体的末尾。包含柔性数组成员的结构体，通过malloc函数为柔性数组动态分配内存。
之所以用柔性数组存放字符串，是因为柔性数组的地址和结构体是连续的，这样查找内存更快（因为不需要额外通过指针找到字符串的位置）；可以很方便地通过柔性数组的首地址偏移得到结构体首地址，进而能很方便地获取其余变量。
到这里我们实现了一个最基本的动态字符串，但是该结构是否有改进的空间呢？我们从一个简单的问题开始思考：不同长度的字符串是否有必要占用相同大小的头部？一个int占4字节，在实际应用中，存放于Redis中的字符串往往没有这么长，每个字符串都用4字节存储未免太浪费空间了。我们考虑三种情况：短字符串，len和free的长度为1字节就够了；长字符串，用2字节或4字节；更长的字符串，用8字节。
这样确实更省内存，但依然存在以下问题。
问题1：如何区分这3种情况？
问题2：对于短字符串来说，头部还是太长了。以长度为1字节的字符串为例，len和free本身就占了2个字节，能不能进一步压缩呢？
对于问题1，我们考虑增加一个字段flags来标识类型，用最小的1字节来存储，且把flags加在柔性数组buf之前，这样虽然多了1字节，但通过偏移柔性数组的指针即能快速定位flags，区分类型，也可以接受；对于问题2，由于len已经是最小的1字节了，再压缩只能考虑用位来存储长度了。
结合两个问题，5种类型（长度1字节、2字节、4字节、8字节、小于1字节）的SDS至少要用3位来存储类型（23=8）,1个字节8位，剩余的5位存储长度，可以满足长度小于32的短字符串。在Redis 5.0中，我们用如下结构来存储长度小于32的短字符串：
struct __attribute__ ((__packed__))sdshdr5 {
unsigned char flags; /＊ 低3位存储类型，高5位存储长度 ＊/
char buf[]; /＊柔性数组，存放实际内容＊/
};
sdshdr5结构（图2-2）中，flags占1个字节，其低3位（bit）表示type，高5位（bit）表示长度，能表示的长度区间为0～31（25-1）, flags后面就是字符串的内容。
图2-2 sdshdr5结构
而长度大于31的字符串，1个字节依然存不下。我们按之前的思路，将len和free单独存放。sdshdr8、sdshdr16、sdshdr32和sdshdr64的结构相同，sdshdr16结构如图2-3所示。
图2-3 sdshdr16结构
其中“表头”共占用了S[2(len)+2(alloc)+1(flags)]个字节。flags的内容与sdshdr5类似，依然采用3位存储类型，但剩余5位不存储长度。
在Redis的源代码中，对类型的宏定义如下：
#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
在Redis 5.0中，sdshdr8、sdshdr16、sdshdr32和sdshdr64的数据结构如下：
struct __attribute__((__packed__))sdshdr8 {
uint8_t len; /＊ 已使用长度，用1字节存储 ＊/
uint8_t alloc; /＊ 总长度，用1字节存储＊/
unsigned char flags; /＊ 低3位存储类型，高5位预留 ＊/
char buf[]; /＊柔性数组，存放实际内容＊/
};
struct __attribute__((__packed__))sdshdr16 {
uint16_t len; /＊已使用长度，用2字节存储＊/
uint16_t alloc; /＊ 总长度，用2字节存储＊/
unsigned char flags; /＊ 低3位存储类型，高5位预留 ＊/
char buf[]; /＊柔性数组，存放实际内容＊/
};
struct __attribute__((__packed__))sdshdr32 {
uint32_t len; /＊已使用长度，用4字节存储＊/
uint32_t alloc; /＊ 总长度，用4字节存储＊/
unsigned char flags; /＊ 低3位存储类型，高5位预留 ＊/
char buf[]; /＊柔性数组，存放实际内容＊/
};
struct __attribute__((__packed__))sdshdr64 {
uint64_t len; /＊已使用长度，用8字节存储＊/
uint64_t alloc; /＊ 总长度，用8字节存储＊/
unsigned char flags; /＊ 低3位存储类型，高5位预留 ＊/
char buf[]; /＊柔性数组，存放实际内容＊/
};
可以看到，这4种结构的成员变量类似，唯一的区别是len和alloc的类型不同。结构体中4个字段的具体含义分别如下。
1）len：表示buf中已占用字节数。
2）alloc：表示buf中已分配字节数，不同于free，记录的是为buf分配的总长度。
3）flags：标识当前结构体的类型，低3位用作标识位，高5位预留。
4）buf：柔性数组，真正存储字符串的数据空间。
注意
结构最后的buf依然是柔性数组，通过对数组指针作“减一”操作，能方便地定位到flags。在2.2节中，我们能更直观地了解该用法。
源码中的__attribute__((__packed__))需要重点关注。一般情况下，结构体会按其所有变量大小的最小公倍数做字节对齐，而用packed修饰后，结构体则变为按1字节对齐。以sdshdr32为例，修饰前按4字节对齐大小为12(4×3)字节；修饰后按1字节对齐，注意buf是个char类型的柔性数组，地址连续，始终在flags之后。packed修饰前后示意如图2-4所示。
图2-4 packed修饰前后示意
这样做有以下两个好处。
❏ 节省内存，例如sdshdr32可节省3个字节（12-9）。
❏ SDS返回给上层的，不是结构体首地址，而是指向内容的buf指针。因为此时按1字节对齐，故SDS创建成功后，无论是sdshdr8、sdshdr16还是sdshdr32，都能通过(char*)sh+hdrlen得到buf指针地址（其中hdrlen是结构体长度，通过sizeof计算得到）。修饰后，无论是sdshdr8、sdshdr16还是sdshdr32，都能通过buf[-1]找到flags，因为此时按1字节对齐。若没有packed的修饰，还需要对不同结构进行处理，实现更复杂。