简单动态字符串（Simple Dynamic Strings，SDS）是Redis的基本数据结构之一，用于存储字符串和整型数据。SDS兼容C语言标准字符串处理函数，且在此基础上保证了二进制安全。
1、数据结构
1.1、早期设计
早期Redis的SDS结构体如下：
struct sds{
int len;//buf中已占用字节数
int free;//buf中剩余可用字节数
char buf[];//数据空间
}:
所有非buf数组的部分被称为head头。这种结构类似于Java的集合，例如ArrayList：
public class ArraList<E> {
transient Object[] elementData;
private int size;
}
因为Java数组可以直接通过.length获取数组的长度，所以不需要额外的free字段。在sds中，可以发现len和free都是int类型，在64位系统中占4个字节，相当于8个char类型变量。所以为了进一步利用内存，针对不同长度的字符串设计了不同类型的SDS。
1.2 不同长度的SDS设计
首先由于有不同的SDS，所以需要一个标识来区分，考虑到SDS的种类不会太多，不用整个字节来存储标识，所以Redis在结构体中添加了一个unsigned char flags，低三位（从0到7）表示类型共可以存储8种。
第二个问题就是不同长度的SDS的len和free字段，也应该根据长度选用不同数据类型，对于较短的字符串，可以直接使用flags高五位表示数组长度省去了len和free，适用于长度不超过25=32的字符串。较长的字符串可以根据长度，选择len和free的类型。Redis最终设计了五种SDS结构体
#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
/* 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[];
};
不过在源码的的注释中很清楚地写到，sdshdr5从来没被使用过，可能是因为长度在32以下的字符串较少，或者是sdshdr5很容易发生扩容，所以直接使用更大的SDS进行存储。我认为第二种可能性更大。新的SDS中free字段被替换成了alloc字段，alloc表示buf分配到的字节数，即buf数组的总长度。
__attribute__ ((__packed__))
一般结构体会按照所有变量大小的最小公倍数做字节对齐，这样修饰以后，结构体会按照1字节对齐。这样做可以节约内存，如sdshdr64可以省下7个字节。在创建SDS之后，也可以直接根据结构体指针偏移head的长度得出buf数组指针，返回给上层，反过来，不论是那种SDS都可以通过buf指针偏移8位直接找到flags。
2、数据操作
数据结构的基本操作不外乎增、删、改、查，SDS也不例外。由于Redis 3.2后的SDS 涉及多种类型，修改字符串内容带来的长度变化可能会影响SDS的类型而引发扩容。
2.1、 创建SDS字符串
Redis根据字符串的长度创建SDS，并返回buf数组的长度：
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
/* 根据字符串长度选择类型
static inline char sdsReqType(size_t string_size) {
if (string_size < 32)
return SDS_TYPE_5;
if (string_size < 0xff)
return SDS_TYPE_8;
if (string_size < 0xffff)
return SDS_TYPE_16;
if (string_size < 0xffffffff)
return SDS_TYPE_32;
return SDS_TYPE_64;
}*/
char type = sdsReqType(initlen);
/*SDS_TYPE_5直接转换成SDS_TYPE_8 也许可以直接在sdsReqType函数中做到这一点
还可以减少判断步骤*/
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
/*计算SDS中非buf数据，head的长度
static inline int sdsHdrSize(char type) {
这里SDS_TYPE_MASK=7，即为0b00000111，与type按位与获取低三位
switch(type&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return sizeof(struct sdshdr5);
case SDS_TYPE_8:
return sizeof(struct sdshdr8);
case SDS_TYPE_16:
return sizeof(struct sdshdr16);
case SDS_TYPE_32:
return sizeof(struct sdshdr32);
case SDS_TYPE_64:
return sizeof(struct sdshdr64);
}
return 0;
}
*/
int hdrlen = sdsHdrSize(type);
/* flags 指针. */
unsigned char *fp;
/*根据头+字符串长度+1分配内存，+1是结束符'/0'*/
sh = s_malloc(hdrlen+initlen+1);
if (sh == NULL) return NULL;
/*没有初始值 sh所有字节设置为0*/
if (!init)
memset(sh, 0, hdrlen+initlen+1);
/*指向buf数组的指针*/
s = (char*)sh+hdrlen;
/*前面提到的，buf偏移一个字节，得到类型flags位置*/
fp = ((unsigned char*)s)-1;
/*根据type类型，给flags赋值并创建SDS结构体*/
switch(type) {
case SDS_TYPE_5: {
/*SDS_TYPE_BITS=3，将initlen左移三位，低三位变为0，高五位存储长度，
再与type按位或将类型填入低三位中*/
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
/*#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)));
这个宏就是根据type获取结构体指针，并给头部各字段赋值
*/
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;
}
}
/*如果有初始值就拷贝初始值到SDS的buf中*/
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
return s;
}
创建字符串步骤：
- 根据长度判断SDS类型。
- 根据SDS类型和字符串长度初始化结构体并申请内存。
- 给头部各字段赋值，返回字符串指针。
注意点：
- 即使字符串长度在32以内，也不会创建sds5，而是直接创建sds8。
- buf数组长度=字符串长度+1，最后一个char用于存储结束符"\0"。
- 最后返回的指针是buf数组的，而非结构体。
2.2 释放字符串
两个函数用于释放SDS，一个是通过buf指针偏移判断SDS类型，从而再偏移得到结构体指针，然后直接free整个结构体；还有一种是将SDS头部的len字段置为0，并将buf[0]置为结束符"\0".
// 1、直接释放整个结构体
void sdsfree(sds s) {
if (s == NULL) return;
// #define s_free free
s_free((char*)s-sdsHdrSize(s[-1]));
}
// 2、重置整个buf和len
void sdsclear(sds s) {
/*
static inline void sdssetlen(sds s, size_t newlen) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
{
unsigned char *fp = ((unsigned char*)s)-1;
*fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
}
break;
case SDS_TYPE_8:
SDS_HDR(8,s)->len = newlen;
break;
case SDS_TYPE_16:
SDS_HDR(16,s)->len = newlen;
break;
case SDS_TYPE_32:
SDS_HDR(32,s)->len = newlen;
break;
case SDS_TYPE_64:
SDS_HDR(64,s)->len = newlen;
break;
}
}
*/
sdssetlen(s, 0);
s[0] = '\0';
}
2.3 拼接字符串
根据拼接后字符串长度，需要判断是否要改变SDS类型和扩充buf数组。
sds sdscatsds(sds s, const sds t) {
// sdslen函数返回的是其头部的len字段 即sds已使用的buf长度
return sdscatlen(s, t, sdslen(t));
}
sds sdscatlen(sds s, const void *t, size_t len) {
// s字符串已用buf长度
size_t curlen = sdslen(s);
// 这个函数就是用来判断是否扩容buf 是否改变SDS类型 返回的依旧是字符串指针
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
// 拼接字符串
memcpy(s+curlen, t, len);
sdssetlen(s, curlen+len);
s[curlen+len] = '\0';
return s;
}
sds sdsMakeRoomFor(sds s, size_t addlen)是扩容的的关键函数
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
// 计算s的剩余长度
size_t avail = sdsavail(s);
size_t len, newlen;
// 定义拼接后的新SDS类型 并获取s的SDS类型
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
/* 如果剩余的buf长度完全够用 直接返回 */
if (avail >= addlen) return s;
len = sdslen(s);
// 拿到s的结构体指针
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
// #define SDS_MAX_PREALLOC (1024*1024)
// 所以这里就是在判断新字符串是否大于1MB 并以此决定新buf的长度
if (newlen < SDS_MAX_PREALLOC)
// 不超过1MB newlen直接翻倍
newlen *= 2;
else
// 超过1MB newlen再加1MB
newlen += SDS_MAX_PREALLOC;
// 根据newlen得到新SDS类型
type = sdsReqType(newlen);
/*禁止使用SDS5，因为SDS没有字段记录剩余可用长度，不支持扩容，所以直接转为SDS8 */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
// 计算新头部大小
hdrlen = sdsHdrSize(type);
// 如果扩容前后的SDS类型一致
if (oldtype==type) {
// #define s_realloc realloc
// 这里只需要realloc一下结构体
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
// 因为realloc结构体，所以需要更新buf的指针
s = (char*)newsh+hdrlen;
} else {
/*这里SDS类型发生变化，所以不能realloc，而是重新开辟内存*/
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
// 拷贝buf
memcpy((char*)newsh+hdrlen, s, len+1);
// 释放sh结构体内存
s_free(sh);
// 更新buf指针
s = (char*)newsh+hdrlen;
// 给新的结构体赋值类型
s[-1] = type;
// 给新结构体赋值len
sdssetlen(s, len);
}
// 给新结构体alloc赋值 最后返回新的buf指针
sdssetalloc(s, newlen);
return s;
}
拼接字符串步骤总结：
- 即使buf需要扩容，也不代表SDS的类型会改变。
- 只要buf扩容，都需要更新buf的指针。
3、SDS总结
SDS其实就是根据字符串长度，选取不同的存储格式以节省内存，并且SDS往上层返回的其实还是char数组buf的指针，可以很好地兼容C原生字符串。此外SDS5在Redis5中未被使用，所有SDS5都直接转为SDS8。