简介redis之SDS
前言
在官方对redis的介绍中我们可以看到醒目的一句话：
Redis is not a plain key-value store,it is actually a data structures server
redis访问速度之所以那么快其一要归功于他是内存型数据库。其二就要归功于它对数据存储的数据结构的设计，即上面这句所强调的他更加是数据结构服务器。
关于redis数据结构从使用者角度出发有:
1.string
2.list
3.hash
4.set
5.sorted set
这也是redis服务器提供的外部接口
从底层实现角度出发有:
1.sds
2.dict
3.skiptlist
4.quicklist
5.ziplist
其中 string类型只由单一的sds实现
SDS(Simple Dynamic String)
源码位子:src/sds.c,src/sds.h
在sds.h中 提供了sdshdr5/8/16/32/64这几种的sds的实现
/* 以SDS8为例*/
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 已使用空间大小 */
uint8_t alloc; /* 总共可用的字符空间大小，应该是实际buf的大小减1(因为c字符串末尾必须是\0,不计算在内) */
unsigned char flags; /* 标志位，主要是识别这是sdshdr几，目前只用了3位，还有5位空余 */
char buf[]; /* 真正存储字符串的地方 */
};
其余大致相同通过flag来判断是sds几
为什么称其为简单动态字符串？
1.与C字符串的区别
C语言采用N+1的字符数组来表示字符串，且末尾置'\0'
相较于c原生的字符串，sds多了len、alloc、flag三个字段来存储一些额外的信息，redis考虑到了字符串拼接时带来的巨大损耗，所以每次新建sds的时候会预分配一些空间来应对未来的增长
因此C获取字符串长度的时间复杂度为O(n)，须全部遍历，SDS只需读取计算len字段即可，且因为预分配了额外的空间杜绝了缓存溢出和减少了修改字符串时的内存分配次数，且sds是以len判断字符串结尾中间是否出现'\0'与其无关，是二进制安全的
为啥要设计多种sds
阅读sds.c中的sdsnewlen方法(sds初始化从sdsnew进入到sdsnewlen)
// sds在初始化时需要传入长度initlen
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
//根据初始化长度确定使用哪种sds
char type = sdsReqType(initlen);
//空字符串处理默认类型sds8
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* sds->flag*/
// redis 自己hock内存分配
sh = s_malloc(hdrlen+initlen+1);
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
//注意这里返回的sh并不是直接指向sds的指针，而是指向sds中字符串的指针
// sds指针需要根据sh和hdrlen计算
if (sh == NULL) return NULL;
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
//根据type类型分配内存
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);
//为方便使用C内置字符串函数，末尾置'\0'
s[initlen] = '\0';
return s;
}
阅读switch分支我们可以看到根据初始化长度，小于3的使用sds5(这个基本不用)，小于2^8的长度使用sds8，以此类推，这样子sds8的len和alloc只占用两个字节，比较短字符串可能非常多，所以节省下来的内存还是非常可观的（基本上是扣额外分配的内存）
SDS空间不足要扩容怎么办
常见如字符串拼接，sds可能空间不足。redis采用指数级扩容方法
// 扩大sds的实际可用空间，以便后续能拼接更多字符串。
// 注意：这里实际不会改变sds的长度，只是增加了更多可用的空间(buf)
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7
int hdrlen;
/* 如果有足够的剩余空间，直接返回 */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
// 在未超出SDS_MAX_PREALLOC前，扩容都是按2倍的方式扩容，超出后只能递增
if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC = 1024*1024
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);
/* 在真正使用过程中不会用到type5，如果遇到type5直接使用type8*/
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
// 扩容其实就是申请新的空间，然后把旧数据挪过去
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
sdssetalloc(s, newlen);
return s;
}
对于SDS_MAX_PREALLOC的宏定义为
#define SDS_MAX_PREALLOC (1024*1024)
在SDS_MAX_PREALLOC范围内以指数2倍对buf扩容，超出则每次加SDS_MAX_PREALLOC
总结
sds（简单动态字符串）特点，预先分配内存，记录字符串长度，在原字符串数组里新增加一串字符串。
新长度newlen为原len+addlen，若newlen小于1M，则为SDS分配新的内存大小为2*newlen；若newlen大于等于1M，则SDS分配新的内存大小为newlen + 1M
SDS是以len字段来判断是否到达字符串末尾，而不是以'\0'判断结尾。所以sds存储的字符串中间可以出现'\0'，即sds字符串是二进制安全的。
当要清空一个SDS时，并不真正释放其内存，而是设置len字段为0即可，这样当之后再次使用到该SDS时，可避免重新分配内存，从而提高效率。
SDS的好处就是通过预分配内存和维护字符串长度，实现动态字符串。
试试回答以下问题
1.为啥redis要自己封装一个string类型
2.什么是动态简单
3.如何兼容C字符串
