本文基于redis 5.0.3,
一起来看下，Redis动态字符串 SDS（simple dynamic string）都有哪些秘密
简介
SDS是redis中定义字符串对象，它比C中的字符串类型对象更为高效、安全。
SDS 在 Redis 中的主要作用有以下两个：
1、实现字符串对象（StringObject）
2、在 Redis 程序内部用作 char* 类型的替代品
SDS特性如下：
- 常数复杂度获取字符串长度
- 杜绝缓冲区溢出
- 减少内存重新分配次数
- 二进制安全
- 惰性空间释放
那么下面我们就从源码出发，看看是如何实现的这几个特性。
SDS结构体的定义
redis 4.0之前：
typedef char *sds;
struct sdshdr {
// buf 已占用长度
int len;
// buf 剩余可用长度
int free;
// 实际保存字符串数据的地方
char buf[];
};
redis 4.0以后（PR#2509）：
#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
#define SDS_TYPE_MASK 7
// sds结构体，使用不同的结构体来保存不同长度大小的字符串
typedef char *sds;
// __attribute__ ((__packed__)) 的作用是告诉GCC编译器，不要对此结构体做内存对齐。
// 同时看到free字段没了，改成alloc，并增加flags字段
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* flags共8位，低三位保存类型标志，高5位保存字符串长度，小于32(2^5-1) */
char buf[]; // 保存具体的字符串
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 字符串长度，buf已用的长度 */
uint8_t alloc; /* 为buf分配的总长度，alloc-len就是sds结构体剩余的空间 */
unsigned char flags; /* 低三位保存类型标志 */
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[];
};
想要明白这个结构为什么变化，需要从原本的结构有什么缺点开始：
4.0之前SDS的缺点
- 1）内存浪费。共8 bytes header，即使很短的字符串也需要4字节的len字段
- 2）字符串大小上限4G。len最大值：2^32 - 1，字符串大小上限：2^32 / 1024 / 1024 / 1024 = 4G
4.0 SDS的修改点
PR作者antirez认为，大多数的SDS从未调整大小，且最小的SDS更是不经常调整大小，所以引入了5种SDS接口实现，主要是为了优化内存，节省空间，主要修改为如下两点
1、关键字段就在于flags，这个字段的低3位表明了SDS的类型，其他5位暂时预留。
2、引入sdshdr5，这种SDS是没有单独的len字段的，就是用了flags中的剩余5位存储字符串的长度，这样SDS的header头才一个字节，当然，如果需要增长长度，那就升级SDS的类型
4.0 SDS的改进意义
1、优化内存使用，节约了内存资源
2、支持了4g以上的SDS支持
SDS 的一些操作函数
/**************** 获取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
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
// 因为现在有5种SDS，那就需要在做操作时区分处理
static inline size_t sdslen(const sds s) {
// 注意获取flags的方式，直接找flags的地址
// 对于`SDS_TYPE_8`及以上，有len字段就可以直接读取
// 而对于`SDS_TYPE_5`，则取`flags`高5位的值
unsigned char flags = s[-1];
switch(flags & SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}
/**************** 创建SDS ***************/
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
// 判断该用哪种长度类型的结构体
char type = sdsReqType(initlen);
// 虽然有SDS_TYPE_5，但其实不会使用它
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
// 获取结构体长度
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
// 分配内存 字符串长度+结构体长度
sh = s_malloc(hdrlen+initlen+1);
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
if (sh == NULL) return NULL;
s = (char*)sh+hdrlen;
// 这里fp就是flags字段
fp = ((unsigned char*)s)-1;
// 接下来对结构体里的len、alloc、flags字段赋值吧
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);
s[initlen] = '\0';
return s;
}
// string_size就是目标字符串长度，比对一下，看用哪个长度的结构体
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5)
return SDS_TYPE_5;
if (string_size < 1<<8)
return SDS_TYPE_8;
if (string_size < 1<<16)
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
/**************** 获取SDS可用长度 ***************/
// 获取实际的结构体通过宏实现
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
static inline size_t sdsavail(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5: {
return 0;
}
case SDS_TYPE_8: {
// 这里做宏替换
SDS_HDR_VAR(8,s);
return sh->alloc - sh->len;
}
// ...
}
return 0;
}
/**************** 清理SDS ***************/
// 将len字段设置为0，但内存空间不释放。方便下次直接复用
void sdsclear(sds s) {
sdssetlen(s, 0);
s[0] = '\0';
}
// free方法才是真正释放内容的方法
void sdsfree(sds s) {
if (s == NULL) return;
// s[-1]就刚好指向了flags这个字段了
s_free((char*)s-sdsHdrSize(s[-1]));
}
SDS的特性
下面我们再来回顾下SDS的特性，并一一源码解析下
-
常数复杂度获取字符串长度
这一点想必通过上面的获取len函数sdslen的实现大家都看到了，除了SDS_TYPE_5，其他都是有对应字段直接返回的，当然即使SDS_TYPE_5，一个位运算的成本也是很低的 -
杜绝缓冲区溢出
SDS在修改字符串时，会经由一个sdsMakeRoomFor函数判断是否需要扩容，是否能够满足修改需求，再进行修改，从而杜绝了缓冲区的溢出，当然，这个函数中也包含了扩容的逻辑，正好可以诠释下一个特性
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s);
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 sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
- 减少内存重新分配次数
sdsMakeRoomFor函数实现如下，如果修改后长度小于1M，则空间乘2，如果大于1M，则增加1M，基于这个策略，内存分配次数会大大减少。当然在4.0之后，还会多了类型变更的操作，如SDS_TYPE_5变成SDS_TYPE_8
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;
int hdrlen;
/* 只有有足够空间就马上返回，否则就继续执行分配空间的操作 */
if (avail >= addlen) return s;
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
// SDS_MAX_PREALLOC == 1MB，如果修改后的长度小于1M，则分配的空间是原来的2倍，否则增加1MB的空间
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
// 重新计算type
type = sdsReqType(newlen);
// 只要有改动，SDS_TYPE_5就变为 SDS_TYPE_8
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 {
/* 新增空间后超过当前类型的长度，使用malloc，并把原字符串拷贝过去 */
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;
}
- 二进制安全
二进制安全指的是只关心二进制化的字符串，不关心具体格式。只会严格的按照二进制的数据存取，不会妄图以某种特殊格式解析数据。比如遇到’\0’字符不会停止解析。
对于C字符串来说，strlen是判断遇到’\0’之前的字符数量。如果需要保存二进制的数据，就不能通过传统的C字符串来保存，因为获取不到它真实的长度。而sds字符串是通过len属性保存字符串的大小，所以它是二进制安全的。
- 惰性空间释放
如果操作后减少了字符串的大小，比如下面的sdstrim函数，只是在最后修改len属性，不会马上释放多余的空间，而是继续保留多余的空间，这样在下次需要增加SDS字符串的大小时，就不需要再为其分配空间了。当然，如果之后检查到SDS的大小实在太大，也会调用sdsRemoveFreeSpace函数释放多余的空间。
sds sdstrim(sds s, const char *cset) {
char *start, *end, *sp, *ep;
size_t len;
sp = start = s;
ep = end = s+sdslen(s)-1;
/* 从头部和尾部逐个字符遍历往中间靠拢，如果字符在cest中，则继续前进 */
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > sp && strchr(cset, *ep)) ep--;
len = (sp > ep) ? 0 : ((ep-sp)+1); // 全部被去除了，长度就是0
if (s != sp) memmove(s, sp, len); // 拷贝内容
s[len] = '\0';
sdssetlen(s,len);
return s;
}
总结
SDS是redis中的一个基本结构，会有很多地方用到，比如kv中的key。希望这篇文章是我打开redis学习大门的一把钥匙。
感觉很多时候，其实是相对不那么复杂的一个特性或者方案，但是起到的效果却是相当强大，这种情况下，我更需要做的是充分了解问题，然后做出合适的选择。基于一个个如此的思考、学习，期待自己终究能够做出创造性的“选择”，给他人提供帮助。