[Redis 源码解析 1：字符串 SDS ]
Redis 中字符串都用自定义的结构**简单动态字符串(Simple Dynamic Strings，SDS)，而不是C语言的字符串。 Redis 中使用到的字符串都是用 SDS，例如 key、string 类型的值、sorted set 的 member、hash 的 field 等等等等
数据结构
旧版本的结构
在 3.2 版本之前，sds 的定义是这样的：
`
struct sdshdr {
// buf 数组中已使用的字节数量，也就是 sds 本身的字符串长度
unsigned int len;
// buf 数组中未使用的字节数量
unsigned int free;
// 字节数组，用于保存字符串
char buf[];
};
` 
缺点：
len和free的定义用了 4 个字节，可以表示2^32的长度。但是我们实际使用的字符串，往往没有那么长。4 个字节造成了浪费。
新版本的结构
旧版本中我们说到，len 和 free 的缺点是用了太长的变量，新版本解决了这个问题。 我们来看一下新版本的 SDS 结构。
在 Redis 3.2 版本之后，Redis 将 SDS 划分为 5 种类型：
类型 | 字节 | 位 |
|---|---|---|
sdshdr5 | < 1 | <8 |
sdshdr8 | 1 | 8 |
sdshdr16 | 2 | 16 |
sdshdr32 | 4 | 32 |
sdshdr64 | 8 | 64 |
新版本新增加了一个 flags 字段来标识类型，长度 1 字节(8 位)。 类型只占用了前 3 位。在 sdshdr5 中，后 5 位用来保存字符串的长度。其他类型后 5 位没有用。
`
struct attribute ((packed)) sdshdr5 {
unsigned char flags; /* 前 3 位保存类型，后 5 位保存字符串长度 */
char buf[];
};
struct attribute ((packed)) sdshdr8 {
uint8_t len; /* 字符串长度，1 字节 8 位 */
uint8_t alloc; /* 申请的总长度，1 字节 8 位 */
unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */
char buf[];
};
struct attribute ((packed)) sdshdr16 {
uint16_t len; /* 字符串长度，2 字节 16 位 */
uint16_t alloc; /* 申请的总长度，2 字节 16 位 */
unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */
char buf[];
};
struct attribute ((packed)) sdshdr32 {
uint32_t len; /* 字符串长度，4 字节 32 位 */
uint32_t alloc; /* 申请的总长度，4 字节 32 位 */
unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */
char buf[];
};
struct attribute ((packed)) sdshdr64 {
uint64_t len; /* 字符串长度，8 字节 64 位 */
uint64_t alloc; /* 申请的总长度，8 字节 64 位 */
unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */
char buf[];
};`
优点：
- 旧版本相对于传统 C 字符串的优点，新版本都有
- 相对于旧版本，新版本可以通过字符串的长度，选择不同的结构，可以节约内存
- 使用
__attribute__ ((__packed__))，让编译器取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐，可以节约内存
SDS的初始化
SDS的初始化如下，开始创建时SDS分配的buf空间大小与字符串长度一致
代码语言：javascript复制/* Create a new sds string starting from a null terminated C string. */
//使用C语言字符串创建SDS
sds sdsnew(const char *init) {
//获取字符串长度
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
sds sdsnewlen(const void *init, size_t initlen) {
return _sdsnewlen(init, initlen, 0);
}
//真正创建SDS
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
void *sh;
sds s;
//根据字符串长度获取sds类型
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;
//// 根据类型获取 struct sdshdr 的长度
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
size_t usable;
assert(initlen hdrlen 1 > initlen); /* Catch size_t overflow */
//根据长度分配hdrlen inilen 1长度的空间， 1 是为了最后一个的结束符号
sh = trymalloc?
s_trymalloc_usable(hdrlen initlen 1, &usable) :
s_malloc_usable(hdrlen initlen 1, &usable);
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
//清空sh的内存
memset(sh, 0, hdrlen initlen 1);
// s 指向了 buf 开始的地址
// 从上面结构可以看出，内存地址的顺序： len, alloc, flag, buf
// 因为 buf 本身不占用空间，hdrlen 实际上就是结构的头(len、alloc、flags)
s = (char*)sh hdrlen;
fp = ((unsigned char*)s)-1;
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
//设置len长度
sh->len = initlen;
//设置真正存储字符串的内存地址
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = usable;
*fp = type;
break;
}
}
// 如果 init 非空，则把 init 字符串赋值给 s，实际上也是 buf 的初始化
//把字符串拷贝到SDS分配的内存地址
if (initlen && init)
memcpy(s, init, initlen);
//最后加一个结束标志
s[initlen] = ' ';
return s;
}SDS 的扩/缩容
扩容
`
代码语言：javascript复制sds sdsMakeRoomFor(sds s, size_t addlen) {
return _sdsMakeRoomFor(s, addlen, 1);
}
/* Unlike sdsMakeRoomFor(), this one just grows to the necessary size. */
sds sdsMakeRoomForNonGreedy(sds s, size_t addlen) {
return _sdsMakeRoomFor(s, addlen, 0);
}
//若SDS s的剩余存储空间还够存储addlen长度的字符，则直接返回旧s，否则创建新的SDS返回
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
void *sh, *newsh;
// 获取 s 目前的空余空间长度
size_t avail = sdsavail(s);
size_t len, newlen, reqlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
/* Return ASAP if there is enough space left. */
//如果剩余空间还够再存储addlen长度的字符串
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
//sds的len addlen的长度
reqlen = newlen = (len addlen);
assert(newlen > len); /* Catch size_t overflow */
if (greedy == 1) {
//小于1M，长度是新len的俩倍
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);
assert(hdrlen newlen 1 > reqlen); /* Catch size_t overflow */
if (oldtype==type) {
//当原类型与新类型一致，则在原有基础是realloc空间即可
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 */
//否则需要重新malloc一整块空间，然后拷贝
newsh = s_malloc_usable(hdrlen newlen 1, &usable);
if (newsh == NULL) return NULL;
//将旧SDS的数据拷贝到新的SDS中
memcpy((char*)newsh hdrlen, s, len 1);
//释放旧的SDS
s_free(sh);
s = (char*)newsh hdrlen;
s[-1] = type;
//设置len
sdssetlen(s, len);
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
sdssetalloc(s, usable);
return s;
}`
缩容
sds 缩短不会真正缩小 buf，而是只改长度而已，类型也不变。SDS 缩容，不释放多余的内存，下次使用可直接复用这些内存
