此文章已于 9:36:45 2020/10/15 发布到将军上座
2.1 数据结构
Redis 3.2之前的SDS
struct sds {
int len;// buf 中已占用字节数
int free;// buf 中剩余可用字节数
char buf[];// 数据空间
};
sdshdr5结构
在Redis5.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（2 5 -1），flags后面就是字符串的内容。
而长度大于31的字符串，1个字节依然存不下。我们按之前的思路，将len和free单独存放。sdshdr8、sdshdr16、sdshdr32和sdshdr64的结构相同，sdshdr16结构如图2-3所示。
其中"表头"共占用了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字节存储r */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* 已使用长度，用4字节存储 */
uint32_t alloc; /* 总长度，用4字节存储 */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /*已使用长度，用8字节存储 */
uint64_t alloc; /* 总长度，用8字节存储 */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
可以看到，这4种结构的成员变量类似，唯一的区别是len和alloc的类型不同。
结构体中4个字段的具体含义分别如下。
1）len ：表示buf中已占用字节数。
2）alloc ：表示buf中已分配字节数，不同于free，记录的是为buf分配的总长度。
3）flags ：标识当前结构体的类型，低3位用作标识位，高5位预留。
4）buf ：柔性数组，真正存储字符串的数据空间。
结构最后的buf依然是柔性数组，通过对数组指针作"减一"操作，能方便地定位到flags。
源码中的__attribute__((__packed__)) 需要重点关注。一般情况下，结构体会按其所有变量大小的最小公倍数做字节对齐，而用packed修饰后，结构体则变为按1字节对齐。
以sdshdr32为例，修饰前按4字节对齐大小为12(4×3)字节；修饰后按1字节对齐，注意buf是个char类型的柔性数组，地址连续，始终在flags之后。packed修饰前后示意如图2-4所示。
这样做有以下两个好处。
- 节省内存，例如sdshdr32可节省3个字节（12-9）。
2) SDS返回给上层的，不是结构体首地址，而是指向内容的buf指针。因为此时按1字节对齐，故SDS创建成功后，无论是sdshdr8、sdshdr16还是sdshdr32，都能通过(char*)sh+hdrlen得到buf指针地址（其中hdrlen是结构体长度，通过sizeof计算得到）。修饰后，无论是sdshdr8、sdshdr16还是sdshdr32，都能通过buf[-1]找到flags，因为此时按1字节对齐。若没有packed的修饰，还需要对不同结构进行处理，实现更复杂。
2.2 基本操作
本节着重介绍创建、释放、拼接字符串的相关API.
2.2.1 创建字符串
Redis通过sdsnewlen函数创建SDS。在函数中会根据字符串长度选择合适的类型，初始化完相应的统计值后，返回指向字符串内容的指针，根据字符串长度选择不同的类型：
sds sdsnewlen(const void *init, size_t initlen) { void *sh; sds s; char type = sdsReqType(initlen); // 根据字符串长度选择不同的类型 /* Empty strings are usually created in order to append. Use type 8 * since type 5 is not good at this. */ if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8; int hdrlen = sdsHdrSize(type); // 计算不同头部所需的长度 unsigned char *fp; /* flags pointer. 指向flags的指针 */ sh = s_malloc(hdrlen+initlen+1); //分配空间, "+1"是为了结束符' ' if (sh == NULL) return NULL; if (init==SDS_NOINIT) init = NULL; else if (!init) memset(sh, 0, hdrlen+initlen+1); s = (char*)sh+hdrlen; // s是指向buf的指针 fp = ((unsigned char*)s)-1; // s是柔性数组buf的指针,-1即指向flags switch(type) { case SDS_TYPE_5: { *fp = type | (initlen << SDS_TYPE_BITS); break; } case SDS_TYPE_8: { SDS_HDR_VAR(8,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_16: { SDS_HDR_VAR(16,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_32: { SDS_HDR_VAR(32,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } case SDS_TYPE_64: { SDS_HDR_VAR(64,s); sh->len = initlen; sh->alloc = initlen; *fp = type; break; } } if (initlen && init) memcpy(s, init, initlen); s[initlen] = ' '; //添加末尾的结束符 return s; //指向sds结构buf字段的指针 }
注意
Redis 3.2后的SDS结构由1种增至5种，且对于sdshdr5类型，在创建空字符串时会强制转换为sdshdr8。原因可能是创建空字符串后，其内容可能会频繁更新而引发扩容，故创建时直接创建为sdshdr8。
创建SDS的大致流程：
首先计算好不同类型的头部和初始长度，然后动态分配内存。需要注意以下3点。
1）创建空字符串时，SDS_TYPE_5被强制转换为SDS_TYPE_8。
2）长度计算时有"+1"操作，是为了算上结束符" "。
3）返回值是指向sds结构buf字段的指针。
返回值sds的类型定义如下：
typedef char *sds;
从源码中我们可以看到，其实s就是一个字符数组的指针，即结构中的buf。这样设计的好处在于直接对上层提供了字符串内容指针，兼容了部分C函数，且通过偏移能迅速定位到SDS结构体的各处成员变量。
2.2.2 释放字符串
SDS提供了直接释放内存的方法——sdsfree，该方法通过对s的偏移，可定位到SDS结构体的首部，然后调用s_free释放内存：
void sdsfree(sds s) {
if (s == NULL) return;
s_free((char*)s-sdsHdrSize(s[-1])); //此处直接释放内存
}
为了优化性能（减少申请内存的开销），SDS提供了不直接释放内存，而是通过重置统计值达到清空目的的方法——sdsclear。该方法仅将SDS的len归零，此处已存在的buf并没有真正被清除，新的数据可以覆盖写，而不用重新申请内存。
void sdsclear(sds s) {
sdssetlen(s, 0); //统计值len归零
s[0] = ' '; //清空buf
}
2.2.3 拼接字符串
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
sdscatsds是暴露给上层的方法，其最终调用的是sdscatlen。由于其中可能涉及SDS的扩容，sdscatlen中调用sdsMakeRoomFor对带拼接的字符串s容量做检查，若无须扩容则直接返回s；若需要扩容，则返回扩容好的新字符串s。函数中的len、curlen等长度值是不含结束符的，而拼接时用memcpy将两个字符串拼接在一起，指定了相关长度，故该过程保证了二进制安全。最后需要加上结束符;
//将指针t的内容和指针s的内容拼接在一起，该操作是二进制安全的
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s);
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
memcpy(s+curlen, t, len); // 直接拼接，保证了二进制安全
sdssetlen(s, curlen+len);
s[curlen+len] = ' '; // 加上结束符
return s;
}
扩容策略
图2-5描述了sdsMakeRoomFor的实现过程。
1）若sds中剩余空闲长度avail大于新增内容的长度addlen，直接在柔性数组buf末尾追加即可，无须扩容。代码如下：
if (avail >= addlen) return s;
2）若sds中剩余空闲长度avail小于或等于新增内容的长度addlen，则分情况讨论：新增后总长度len+addlen<1MB的，按新长度的2倍扩容；新增后总长度len+addlen>1MB的，按新长度加上1MB扩容。代码如下：
if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC这个宏的值是1MB
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
3）最后根据新长度重新选取存储类型，并分配空间。此处若无须更改类型，通过realloc扩大柔性数组即可；否则需要重新开辟内存，并将原字符串的buf内容移动到新位置。具体代码如下：
type = sdsReqType(newlen);
/* type5的结构不支持扩容，所以这里需要强制转成type8*/
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
/*无须更改类型，通过realloc扩大柔性数组即可，注意这里指向buf的指针s被更新了*/
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* 由于标头大小发生变化，因此需要将字符串向前移动*，并且不能使用realloc */
newsh = s_malloc(hdrlen+newlen+1);//按新长度重新开辟内存
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1); //将原buf内容移动到新位置
s_free(sh); //释放旧指针
s = (char*)newsh+hdrlen; //偏移sds结构的起始地址，得到字符串起始地址
s[-1] = type; //为falgs赋值
sdssetlen(s, len); //为len属性赋值
}
sdssetalloc(s, newlen); //为alloc属性赋值
return s;
2.2.4 其余API
SDS还为上层提供了许多其他API，篇幅所限，不再赘述。表2-1列出了其他常用的API，读者可自行查阅源码学习，学习时把握以下两点。
1）SDS暴露给上层的是指向柔性数组buf的指针。
2）读操作的复杂度多为O(1)，直接读取成员变量；涉及修改的写操作，则可能会触发扩容。
2.3 本章小结
本章介绍了SDS的数据结构及基本API的实现。在源码分析过程中，我们可以知道SDS的以下特性是如何实现的。
1）SDS如何兼容C语言字符串？如何保证二进制安全？
SDS对象中的buf是一个柔性数组，上层调用时，SDS直接返回了buf。由于buf是直接指向内容的指针，故兼容C语言函数。而当真正读取内容时，SDS会通过len来限制读取长度，而非" "，保证了二进制安全。
2）sdshdr5的特殊之处是什么？
sdshdr5只负责存储小于32字节的字符串。一般情况下，小字符串的存储更普遍，故Redis进一步压缩了sdshdr5的数据结构，将sdshdr5的类型和长度放入了同一个属性中，用flags的低3位存储类型，高5位存储长度。创建空字符串时，sdshdr5会被sdshdr8替代。
3）SDS是如何扩容的？
SDS在涉及字符串修改处会调用sdsMakeroomFor函数进行检查，根据不同情况动态扩容，该操作对上层透明。
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
char type = sdsReqType(initlen); // 根据字符串长度选择不同的类型
/* Empty strings are usually created in order to append. Use type 8
* since type 5 is not good at this. */
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type); // 计算不同头部所需的长度
unsigned char *fp; /* flags pointer. 指向flags的指针 */
sh = s_malloc(hdrlen+initlen+1); //分配空间, "+1"是为了结束符' '
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
s = (char*)sh+hdrlen; // s是指向buf的指针
fp = ((unsigned char*)s)-1; // s是柔性数组buf的指针,-1即指向flags
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
}
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = ' '; //添加末尾的结束符
return s; //指向sds结构buf字段的指针
}