简述
上次我们讲了redis的value数据结构之跳表，今天我们来学习下Redis数据结构之简单动态字符串(simple dynamic string)，简称SDS。类似我们Java的StringBuilder，是个动态字符串。在Redis中，大部分和字符串相关的都是使用SDS实现的。包括string类型，AOF持久化缓存等使用了SDS。SDS是在redis中很重要的数据类型。以下内容本人也亲自看了redis代码总结了下😊。
简单动态字符串（SDS）
对于普通字符串，字符串是我们常用的数据类型，其实就是char数组，分配空间时候有固定大小的，在C语言中结尾用\0来标识字符串结束。
而SDS可以存储任意二进制数据，不会因为\0而代表字符串结束，而且SDS是动态扩容的，不会受到像普通字符串有大小限制，这就是SDS好处。具体我们分析下SDS数据结构，它是做了什么处理从而解决普通字符串做不到的问题。
SDS类型
我们先看sdshdr的结构体
/* 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[];
};
可以看出，SDS在不同的长度下，变量使用的类型也是不同的，但是大体上结构是相同的（sdshdr5注释上写着没用到，我们不关注）。SDS有四个变量：len、alloc、flags和buf[]。
| 变量名 | 解释 |
|---|---|
| len | 已使用长度 |
| alloc | 分配的长度，等于buf[]的总长度-1，因为包括'/0'结束符 |
| flags | 代表类型，8，16，32和64分别用1，2，3，4代表 |
| buf[] | 实际的字符串 |
当SDS初始化的时候，会根据初始化的长度来决定不同的类型的SDS，然后初始化长度，记录下代表的类型到flags，最后还会分配一个结束符。具体代码可以看下sds.c中的sdsnewlen方法。
扩容代码分析
具体代码在sds.c中的sdsMakeRoomFor方法。
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
/* 获取剩余可用空间 */
size_t avail = sdsavail(s);
size_t len, newlen;
/* 想获取到flags只需要将s向前移动一个字节，所以为s[-1] */
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
/* Return ASAP if there is enough space left. */
/* 如果可用的空间比需要扩容的空间还大，则不需要扩容，直接返回 */
if (avail >= addlen) return s;
/* 已使用长度 */
len = sdslen(s);
/* 获取到sds首部位置，也就是头部指针。结构体尾部-结构体长度*/
sh = (char*)s-sdsHdrSize(oldtype);
/* 新的最小长度，所以使用了已使用长度+需要添加的长度 */
newlen = (len+addlen);
/* 新的最小长度如果小于1024*1024，也就是1m，则会分配两倍的最小长度*/
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
/* 否则就只在1m上加上自己的长度 */
newlen += SDS_MAX_PREALLOC;
/* 获取新的长度类型。因为字符串长度改变了，对头部类型也会发生变化。 */
type = sdsReqType(newlen);
/* Don't use type 5: the user is appending to the string and type 5 is
* not able to remember empty space, so sdsMakeRoomFor() must be called
* at every appending operation. */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
/*
如果类型相同，则使用开始地址直接进行内存分配。
sh是开始地址，hdrlen 是head的长度，即struct本身大小，
newlen 是buf 大小， +1 是为了结束符号
*/
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
/* 如果头部类型有变化，则需要重新拿到一块新内存，并将原本sds数据copy过去*/
newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
/* 释放之前的内存空间 */
s_free(sh);
/* 调整地址空间指向新的buf开始的位置 */
s = (char*)newsh+hdrlen;
/* -1的位置就是存flags */
s[-1] = type;
/* 分配len的值 */
sdssetlen(s, len);
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
/* 分配alloc的值 */
sdssetalloc(s, usable);
/* 返回新的sds */
return s;
}
代码中已经清晰写了sds扩容的流程，其实也是进行了内存分配。如果新的最小长度小于1m，则需要分配两倍最小长度空间；否则分配1m+最小长度空间。如果flags不改变，则使用开始的地址进行内存分配；如果flags改变了，则需要开辟一块新内存，并将原本sds的数据数值复制过去，释放原本内存空间。最后会调整地址位置，分配len和alloc的值。
sds图解
总结
相比普通的字符串类型，sds的特点很明显，二进制安全和可动态扩展。
普通的字符串类型没有长度去标识长度，只能通过\0来标识结束，不能获取\0后面的数据，而sds是可以的，弥补了这个缺点。
sds的动态扩容也做了很大优化，让sds可以进行预分配内存，还会根据flags来决定是在原地址上动态扩容，还是需要开辟新内存，并将原本sds的数据复制过去。
sds在redis中使用甚广，基本所有和字符串相关都是用sds类型来处理的。因为sds巧妙地使用指针完美兼容了字符串，所有对字符串的操作，sds都可以使用。
参考中的第二篇文章中，还介绍了为了完美兼容字符串，redis中使用了内存不对齐方案。具体大家可以看下。
评论区