当今天在网上寻找Redis字符串的实现相关的文章时，我找到的依然是一堆Redis3时代的文章，大量老旧的sds相关的内容，仿佛无论新旧，Redis的字符串就是这样实现的。但事实上，早在Redis3.2之后，字符串早就不是之前的sds了结构了。那Redis3.2.0是什么时候发布的呢？答：2016年5月，没错，一个已经过时6年的方案，至今天还流行在很多文章之中~
一、Redis3.0时代的字符串
1.sds基本结构
这个基本就不用多说了，在 sds.h 文件内可以看到 sdshdr 的定义
struct sdshdr {
unsigned int len;
unsigned int free;
char buf[];
};
len 表示长度，free 表示剩余容量，buf 就是字符串数据。
字符串使用 len 来表示长度，而不是 c 中的以 '\0' 结尾，这样可以保证字符串二进制安全，即字符串内即使有 '\0' 也不会出错，同时也使获取长度的时间复杂度从 O(n) 降到了 O(1)
2.sds字符串拼接
sds字符串的拼接函数在 sds.c 内，较为值得看一下，可以更好的理解下sds结构。
#define SDS_MAX_PREALLOC (1024*1024)
typedef char *sds;
sds sdscatlen(sds s, const void *t, size_t len) {
struct sdshdr *sh;
size_t curlen = sdslen(s);
s = sdsMakeRoomFor(s,len); //先扩容
if (s == NULL) return NULL;
sh = (void*) (s-(sizeof(struct sdshdr)));
memcpy(s+curlen, t, len); //将新字符串拷贝到原字符串后
sh->len = curlen+len;
sh->free = sh->free-len;
// 在末尾增加 '\0'
// 为什么已经有len表示长度了，还要在末尾增加 '\0' 呢？
// 其实是为了兼容 <string.h> 部分库函数，如 strcasecmp 一类的
s[curlen+len] = '\0';
return s;
}
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
size_t free = sdsavail(s);
size_t len, newlen;
if (free >= addlen) return s; \\如果剩余空间足够，直接返回
len = sdslen(s);
// 变量s是sdshdr结构体中buf的指针，所以s-(sizeof(struct sdshdr))其实就是将指针向前移动一个sdshdr的长度，也就是指向了sdshdr结构体的头部。
// 而将其指向头部的原因就是为了覆盖原有的sdshdr
sh = (void*) (s-(sizeof(struct sdshdr)));
newlen = (len+addlen);
// SDS_MAX_PREALLOC 是1mb，如果新字符串小于1mb，则每次扩容会翻倍，如果大于1mb，每次扩容会在后面在加1mb
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
if (newsh == NULL) return NULL;
newsh->free = newlen - len; //更新剩余空间大小
return newsh->buf;
}
所以原有的sds字符串结构可以说很好理解。
二、Redis3.2之后的字符串结构
1.hisds字符串
在查看新版Redis的源码时，我们可以看一以 sds.h 内已经没有原来的 sdshdr 结构体了，取而代之的是 hisdshdr
typedef char *hisds;
/* 注意：hisdshdr5 并未使用 */
struct __attribute__ ((__packed__)) hisdshdr5 {
unsigned char flags; /* 低三位表类型，高五位表长度 */
char buf[];
};
struct __attribute__ ((__packed__)) hisdshdr8 {
uint8_t len;
uint8_t alloc; /* 不包括头部和结尾的 '\0' */
unsigned char flags; /* 低三位表类型，高五位未使用 */
char buf[];
};
struct __attribute__ ((__packed__)) hisdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) hisdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) hisdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];
};
我们可能看到，hisdshdr 并不是一个结构体，而是多个。
__attribute__ ((__packed__)) 表示结构体不使用内存对齐。
举个例子:
struct A {
int dat;
char buf[];
}
请问上面的结构体占用了几个字节？
int 为 32 位，需要4个字节，而 char[] 则只是指向第一个字符，所以只需要1个字节，那结构体A应该占用5个字节。
然后我们 sizeof 一下试试，结果竟然是 8
原因就是内存对齐，char[] 会和 int 对齐，使其也占用了4个字节。
__attribute__ ((__packed__)) 则表示该结构体不使用内存对齐。
struct __attribute__ ((__packed__)) A {
int dat;
char buf[];
}
此时的 A 在 sizeof 一下，结果就是5了。
2.hisds字符串的拼接
为了进一步了解hisds，我们在来看看它的拼接函数，和sdshdr的拼接有何不同。
#define HI_SDS_TYPE_5 0
#define HI_SDS_TYPE_8 1
#define HI_SDS_TYPE_16 2
#define HI_SDS_TYPE_32 3
#define HI_SDS_TYPE_64 4
#define HI_SDS_TYPE_BITS 3 // flag中表示类型的位数，只有低三位表示类型
#define HI_SDS_TYPE_MASK 7 // 只有低三位表类型，所以使用00000111 & flag 来取类型
// 通过 s 返回 hisdshdr 即 hisds 的头部指针，hisdshdr##T 表示将参数 T 转成文本
// 例如：HI_SDS_HDR(8,s) hisdshdr##T 即会变成 hisdshdr8
#define HI_SDS_HDR(T,s) ((struct hisdshdr##T *)((s)-(sizeof(struct hisdshdr##T))))
// 由于 hisdshdr5 中，使用flag的高5位表示长度，所以它的长度是 flag >> 3
#define HI_SDS_TYPE_5_LEN(f) ((f)>>HI_SDS_TYPE_BITS
hisds hi_sdscatlen(hisds s, const void *t, size_t len) {
size_t curlen = hi_sdslen(s);
s = hi_sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
memcpy(s+curlen, t, len);
hi_sdssetlen(s, curlen+len);
s[curlen+len] = '\0';
return s;
}
static inline void hi_sdssetlen(hisds s, size_t newlen) {
unsigned char flags = s[-1];
switch(flags&HI_SDS_TYPE_MASK) {
case HI_SDS_TYPE_5:
{
unsigned char *fp = ((unsigned char*)s)-1;
*fp = (unsigned char)(HI_SDS_TYPE_5 | (newlen << HI_SDS_TYPE_BITS));
}
break;
case HI_SDS_TYPE_8:
HI_SDS_HDR(8,s)->len = (uint8_t)newlen;
break;
case HI_SDS_TYPE_16:
HI_SDS_HDR(16,s)->len = (uint16_t)newlen;
break;
case HI_SDS_TYPE_32:
HI_SDS_HDR(32,s)->len = (uint32_t)newlen;
break;
case HI_SDS_TYPE_64:
HI_SDS_HDR(64,s)->len = (uint64_t)newlen;
break;
}
}
和之前sdscatlen的函数相比，新的 hi_sdscatlen 基本没太大变化。
其中的 hi_sdsMakeRoomFor 函数即使我们不看，也能猜到其是用于扩容的，那我们一会在看它。
与之前相比，hi_sdscatlen 还用了一个 hi_sdssetlen 替代了之前直接设置len和free的代码。
而 hi_sdssetlen 的定义则比较有趣。首先，s[-1]来获取flag，因为 s 正是 hisdshdr 中的 char buf[] 而它的上一个字段正是 unsigned char flag 所以可以直接用 s[-1]的方式拿到 flag。
然后通过 flag 判断类型，并设置新的长度。
现在呢，我们在来看看 hi_sdsMakeRoomFor 虽然我们知道这个函数是扩容用的，但也要看看它的实现
hisds hi_sdsMakeRoomFor(hisds s, size_t addlen) {
void *sh, *newsh;
size_t avail = hi_sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & HI_SDS_TYPE_MASK;
int hdrlen;
/* 如果剩余空间足够，则直接返回 */
if (avail >= addlen) return s;
len = hi_sdslen(s);
sh = (char*)s-hi_sdsHdrSize(oldtype);
newlen = (len+addlen);
if (newlen < HI_SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += HI_SDS_MAX_PREALLOC;
/* 通过新长度判断新类型 */
type = hi_sdsReqType(newlen);
/* 不使用 hisdshdr5 */
if (type == HI_SDS_TYPE_5) type = HI_SDS_TYPE_8;
hdrlen = hi_sdsHdrSize(type);
/* 如果头部类型没变，那直接在原内存上重写 */
if (oldtype==type) {
newsh = hi_s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* 如果头部类型变了，那它所需的空间也会变化，所以需要重新分配内存空间 */
newsh = hi_s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
hi_s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
hi_sdssetlen(s, len); //设置长度
}
hi_sdssetalloc(s, newlen); //设置剩余空间
return s;
}
可以看到，hi_sdsMakeRoomFor 的逻辑和 sdsMakeRoomFor 是基本一致的，但部分位置不同。
比如，长度扩展都是一样的，如果小于1mb，每次扩容则翻倍，如果大于1mb，则每次只增加1mb。
但不同的是，hisds 需要通过新长度判断类型。即 type = hi_sdsReqType(newlen);
比如当新长度大于 256，那就要换用 hisdshdr16 来表示了。其它同理。
而 hi_sdsReqType 就是最简单的大小判断。定义如下：
static inline char hi_sdsReqType(size_t string_size) {
if (string_size < 32)
return HI_SDS_TYPE_5;
if (string_size < 0xff)
return HI_SDS_TYPE_8;
if (string_size < 0xffff)
return HI_SDS_TYPE_16;
if (string_size < 0xffffffff)
return HI_SDS_TYPE_32;
return HI_SDS_TYPE_64;
}
其实Redis的代码并不多，也很好理解，只需要几个实例就基本可以窥其一二，通过理解拼接函数，我们基本可以看懂大部分的sds中的代码了。
三、结语
相对而言，hisds也只是头部变了，本身和 sds 并没有太大区别。那为什么Redis要这么改？
其实答案就是为了剩那一捏捏的内存~
一个 sdshdr 占多少内存？
len 和 free 都是 uint ,各占4个字节；
buf 是 char[] 占1个字节，但由于sdshdr是内存对齐的，所以也占了4个字节；
也就是说，sdshdr占了12个字节。
那 hisdshdr 占多少字节呢？
hisdshdr8 的话，len 和 alloc 都是 uint8，各占1个字节；
flag 是 char 类型，占1个字节；
buf 是 char[] 类型，占1个字节；
也就是说，hisdshdr8 只占用 4个字节。同理，hisdshdr16占用6个字节，hisdshdr32占用10个字节，hisdshdr64占用18个字节。
所以 hisdshdr 不仅可以表达更长的uint64位长度的字符串，而且在一般情况下还只占用更小的内存。
所以说，Redis也真不愧是一个把内存省到极致的工具~
Q.E.D.