所有原理实现基于Redis版本6.0.9。
SDS
SDS(Simple Dynamic String)简单动态字符串，是Redis中字符串所采取的数据结构，SDS并不是Redis的独创，只是被Redis采纳的一种数据结构，用以替换C语言原生的字符串类型：sds仓库传送门。使用方法与原生的C语言字符串类似，并能提供很多类似的API。SDS经过了两个版本，目前的解析大都基于v1。
SDS v1 结构
v1版本的sds数据结构很简单：
struct sdshdr{
//现有字符串长度，即buf的长度(不包含标识结束的字符\0)
int len;
//当下sds未使用的字节数
int free;
//字节数组，即实际的字符串
char buf[];
}
比起C语言中单一的字符数组构成的字符串，sds具有以下优势：
存储了字符串长度，相比C语言遍历获取长度，将时间复杂度由O(n)变为O(1);
当SDS每次发生修改时，会为其分配冗余空间，在字符串空间小于1MB时，每次分配实际长度2倍的空间，而在大于1MB时则是分配多1MB的空间，是在空间不足时才会触发分配。避免多次的重分配。
内存空间的释放是惰性的，每次SDS缩短也不会立即释放空间；
由于直接存储二进制数据，所以sds是二进制安全的，不仅可以存储标准编码的字符串，也可以存储纯二进制格式的数据，诸如图片、各种文件流等。
当然，相应地，SDS会耗费更多的内存。
SDS v2 结构
随着SDS的优化，推出了v2版本，Redis也将其的SDS替换为v2，将SDS细分为多个类型，根据实际的字符串长度尽可能地节省内存占用：
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
//sdshdr5 是预留的 没有实际使用到
struct __attribute__((__packed__)) sdshdr5
{
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__((__packed__)) sdshdr8
{
//现有字符串长度，即buf的长度(不包含标识结束的字符\0)
uint8_t len;
//当前分配给sds对象的大小
uint8_t alloc;
//sds的数据类型，仅用到了低3位
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[];
};
Redis中的SDS
初始化
一个简单的创建SDS函数如下：
//sds.h
sds sdsnew(const char *init);
#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
//sds.c
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
//根据初始字符串长度决定sds类型
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5)
return SDS_TYPE_5; //32
if (string_size < 1<<8)
return SDS_TYPE_8; //256
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 sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
char type = sdsReqType(initlen);
//忽略掉了sds5取得的sds类型
/* 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;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
size_t usable;
//分配空间 1是留给 \0结束符
sh = s_malloc_usable(hdrlen+initlen+1, &usable);
if (sh == NULL) return NULL;
if (init==SDS_NOINIT)
init = NULL;
//配置内存
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
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);
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;
}
}
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
return s;
}
指令实现：预分配API——以APPEND为例
只是使用SET命令是不会用到sds的冗余空间的，因为每次都会重新创建sds对象，在创建之初是没有额外空间的。我们以Redis拼接字符串的指令——APPEND为例，讲述空间的扩展API。
让我们简单的看一下命令语句APPEND的方法：
void appendCommand(client *c) {
size_t totlen;
robj *o, *append;
//是否存在该key
o = lookupKeyWrite(c->db,c->argv[1]);
if (o == NULL) {
/* Create the key */
c->argv[2] = tryObjectEncoding(c->argv[2]);
dbAdd(c->db,c->argv[1],c->argv[2]);
incrRefCount(c->argv[2]);
totlen = stringObjectLen(c->argv[2]);
} else {
/* Key exists, check type */
if (checkType(c,o,OBJ_STRING))
return;
//使用sds的API
/* "append" is an argument, so always an sds */
append = c->argv[2];
//总长度
totlen = stringObjectLen(o)+sdslen(append->ptr);
if (checkStringLength(c,totlen) != C_OK)
return;
/* Append the value */
o = dbUnshareStringValue(c->db,c->argv[1],o);
//调用了sdscatlen方法 其实是在这里进行的内存预分配
o->ptr = sdscatlen(o->ptr,append->ptr,sdslen(append->ptr));
totlen = sdslen(o->ptr);
}
signalModifiedKey(c,c->db,c->argv[1]);
notifyKeyspaceEvent(NOTIFY_STRING,"append",c->argv[1],c->db->id);
server.dirty++;
addReplyLongLong(c,totlen);
}
相应的方法实现：
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
* end of the specified sds string 's'.
*
* After the call, the passed sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s);
//在这里分配了多余的内存，事实上sds的内存预分配也都是依赖此方法，传入字符长度
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
memcpy(s+curlen, t, len);
sdssetlen(s, curlen+len);
s[curlen+len] = '\0';
return s;
}
预分配API实现——sdsMakeRoomFor
#define SDS_MAX_PREALLOC (1024*1024)
/* Enlarge the free space at the end of the sds string so that the caller
* is sure that after calling this function can overwrite up to addlen
* bytes after the end of the string, plus one more byte for nul term.
*
* Note: this does not change the *length* of the sds string as returned
* by sdslen(), but only the free buffer space we have. */
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;
size_t usable;
//预分配内存足够的情况下，不进行重分配
/* Return ASAP if there is enough space left. */
if (avail >= addlen) return s;
//sds实际字符串长度
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
//新字符串长度
newlen = (len+addlen);
//#define SDS_MAX_PREALLOC (1024*1024)
//如果小于1MB则多分配一倍空间 多于1MB则多分配1MB
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
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;
//数据体大小 对于常见的SDS_TYPE_8 这一数值是44
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
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 */
newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
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);
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))
usable = sdsTypeMaxSize(type);
sdssetalloc(s, usable);
return s;
}
验证Redis中的内存预分配
我们可以利用Redis的MEMORY USAGE指令获取Redis一个键值的空间占用，对于SDS_TYPE_8，其正常占用为44+2(\0的占用)+key的字节数+val的字节数。
首先set一个简单的测试键，键值为test abc，不难得出其占用内存为53bytes，不计算value占用为50bytes：
接下来我们对键值对重新赋值为abcdefg，由于进行了重分配，没有额外占用则其内存为57bytes：
接下来重新进行赋值为abc并采用append的方式进行追加字符串，可以看到内存也进行了额外的空间分配：
新的内存占用变为66bytes，重分配内存为(3+4+1)*2=16bytes(含\0)，最终分配内存为50+16=66bytes。这样同样的键值对(test : abcdefg)因为扩展分配了额外的内存空间(\0其实是后追加的，原长去掉\0为49bytes)。其实不必纠结分配了多少，只需要注意采用append等字符串操作会使Redis占用额外的内存空间，但是频繁的字符串追加可能会相对快速一些。
总结——Redis中的SDS
Redis中几乎所有的字符串都是SDS对象，包括key、string类型的value、列表、hash类型的value等，相比原生的字符串，其应用主要有：
存储了字符串长度，相比C语言遍历获取长度，将时间复杂度由O(n)变为O(1);
当SDS每次发生修改时，会进行内存空间预分配，在字符串空间小于1MB时，每次分配实际长度2倍的空间，而在大于1MB时则是分配多1MB的空间，是在空间不足时才会触发分配。避免多次的重分配。（其实内存预分配在Redis的API中使用不多，仅在字符串修改操作例如append会用到，直接set不会进行预分配）
内存空间的释放是惰性的，每次SDS缩短也不会立即释放空间；（笔者没有找到关于使用惰性释放的case，因为Redis对字符串的操作一般都是加长，鲜有缩短）
由于直接存储二进制数据，所以sds是二进制安全的，不仅可以存储标准编码的字符串，也可以存储纯二进制格式的数据，诸如图片、各种文件流等。
SDS v2相比v1不同之处在于v2根据字符串长度为结构体分配了不同大小的内存，可能牺牲了很小的性能但是其对象结构体换来了更小的内存空间。
2020-11-16鱼鱼