0、引言
Redis没有直接使用C语言传统的字符串表示（以'\0'结尾的字符数组），而是构建了一种名为简单动态字符串（simple dynamic string, sds）的类型，用于Redis默认字符串的表示。
从2009年3月的1st commit到目前的最新版5.0.4，sds的变化相对是比较小的，中间只有一次较大的改动。commit记录（PR#2509）如下：
PR#2509 commit记录
主要是优化了内存使用、提高了字符串最大长度。该修改最早出现在3.2.0 RC1（Redis 3.2.0 RC1 (version 3.1.101) ）Release date: 23 dec 2015）：
* [NEW] SDS improvements for speed and maximum string length.
This makes Redis more memory efficient in different use cases.
(Design and implementation by Oran Agra, some additional work
by Salvatore Sanfilippo)
本文尝试从源码角度解析Redis SDS的设计、实现和演化。
1、SDS的定义
这里的定义是PR#2509之前的定义：
struct sdshdr {
unsigned int len;
unsigned int free;
char buf[];
};
len：记录buf数组中已使用字节的数量，不计'\0'
free：记录buf数组中未使用字节的数量，不计'\0'
buf：字节数组，用于保存字符串。
SDS遵循C字符串以'\0'结尾的惯例，这样做的好处是：SDS可以直接重用一部分C字符串函数库里面的函数。如：
printf("%s", s->buf);
sds内存示意图
2、SDS与C字符串的区别
SDS相比C字符串，在安全性、性能、功能性具有优势：
1、安全性：防止缓冲区溢出、二进制安全
2、性能：获取字符串长度、空间预分配、惰性释放
3、功能性：二进制安全、兼容部分C字符串函数
2.1、缓冲区溢出
缓冲区溢出（buffer overflow）：是这样的一种异常，当程序将数据写入缓冲区时，会超过缓冲区的边界，并覆盖相邻的内存位置。
C字符串不记录自身长度，不会自动进行边界检测，增加了溢出风险。如下面这种情形：
char* strcat(char* dest, const char* src);
s1 = 'Redis'，s2 = 'MongoDB'，当执行strcat(s1, " Cluster")时，未给s1分配足够内存空间，s1的数据将溢出到s2所在的内存空间，导致s2保存的内容被意外地修改。
内存溢出示意图1
内存溢出示意图2
而SDS记录了自身长度，同时在修改时，API会按照如下步骤进行：
1）先检查SDS的空间是否满足修改所需的要求；
2）如果不满足要求的话，API会自动将SDS的空间扩展至执行修改所需的大小（realloc）；
3）然后才执行实际的修改操作。
例子可见：sds.c/sdscat
2.2、二进制安全
二进制安全（binary-safe）：指能处理任意的二进制数据，包括非ASCII和null字节。
C字符串中的字符必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符会被误认为是字符串的结尾。这些限制使得C字符串只能保存文本数据，不能保存图像、视频、音频等二进制数据。
而SDS不会对数据做任何限制、过滤、假设，数据在写入时是什么样子的，它被读取时就是什么样的。因此Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。
2.3、获取字符串长度
C字符串并不记录自身的长度信息，因此为了获取一个C字符串的长度，必须遍历整个字符串，直至'\0'，其复杂度时O(n)。
而SDS记录了自身长度len，因此通过O(1)复杂度就能获取字符串的长度。
2.4、空间预分配
当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须的空间，还会为SDS分配额外的未使用空间。具体策略见sds.c/sdsMakeRoomFor
/* 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) {
struct sdshdr *sh, *newsh;
size_t free = sdsavail(s);
size_t len, newlen;
if (free >= addlen) return s;
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
newlen = (len+addlen);
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;
}
#define SDS_MAX_PREALLOC (1024*1024)
2.5、惰性释放
当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。
惰性释放示意图1
惰性释放示意图1
下面这个api是将sds置空，但并未真正释放内存：
/* Modify an sds string in-place to make it empty (zero length).
* However all the existing buffer is not discarded but set as free space
* so that next append operations will not require allocations up to the
* number of bytes previously available. */
void sdsclear(sds s) {
struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
sh->free += sh->len;
sh->len = 0;
sh->buf[0] = '\0';
}
真正释放sds内存的api：
/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
if (s == NULL) return;
zfree(s-sizeof(struct sdshdr));
}
回收free内存的api：
/* Reallocate the sds string so that it has no free space at the end. The
* contained string remains not altered, but next concatenation operations
* will require a reallocation.
*
* 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 sdsRemoveFreeSpace(sds s) {
struct sdshdr *sh;
sh = (void*) (s-(sizeof(struct sdshdr)));
sh = zrealloc(sh, sizeof(struct sdshdr)+sh->len+1);
sh->free = 0;
return sh->buf;
}
2.6、兼容部分C字符串函数
SDS的buf数组会以'\0'结尾，这样SDS就可以重用C字符串函数库里的一些函数，避免了不必要的代码重复。
3、SDS的演化
这里主要介绍的是PR#2509和紧接着的antirez的“New sds type 5 implemented”。
commit记录
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. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
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[];
};
首先，sdshdr结构体由1个变成了5个。__attribute__ ((__packed__))的作用就是告诉编译器取消结构体在编译过程中的优化对齐,按照实际占用字节数进行对齐。
在解释新的SDS结构为何能优化内存前，先看一个测试：
#include <iostream>
#include <cstdint>
using namespace std;
struct sdshdr
{
unsigned int len;
unsigned int free;
char buf[];
};
struct sdshdr2
{
unsigned int len;
unsigned int free;
};
struct sdshdr3
{
char buf[];
};
int main() {
cout << sizeof(struct sdshdr) << endl; // 8
cout << sizeof(unsigned int) << endl << endl; // 4
cout << sizeof(uint8_t) << endl; // 1
cout << sizeof(uint16_t) << endl; // 2
cout << sizeof(uint32_t) << endl; // 4
cout << sizeof(uint64_t) << endl << endl; // 8
cout << sizeof(struct sdshdr2) << endl; // 8
cout << sizeof(struct sdshdr3) << endl; // 1
cout << sizeof(char) << endl; // 1
return 0;
}
typedef unsigned int uint32_t;
为什么要如此优化，或者说之前的sds结构存在什么问题呢？
之前sds存在的问题：
1）浪费内存。共8 bytes header，即使很短的字符串也需要4字节的len字段
2）字符串大小上限4G。len最大值：2^32 - 1，字符串大小上限：2^32 / 1024 / 1024 / 1024 = 4G
PR#2509的改进：
sdshdr8 3 bytes header
sdshdr16 5 bytes header
sdshdr32 9 bytes header
sdshdr64 17 bytes header
在antirez的“New sds type 5 implemented”提交中，有2点修改：
1）修改了flags
char flags; /* 2 lsb of type, and 6 msb of refcount */
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
oranagra的PR用2位表示类型，antirez则认为，大多数SDS字符串从未调整大小，并且最小的它们不太可能调整大小，因此可以使用3位代替。oranagra设想其他几位可以用作引用计数，antirez则暂时放弃了这种考虑，暂时将这些bit预留，可能用于非常小的字符串的额外编码。
2）增加了sdshdr5
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
用低3位表示类型，剩余5位表示sds字符串长度，那么可以表示长度为31(2^5-1)的字符串，这种情况下，最多才1个字节的header。如果需要对该字符串调整大小，可以直接升级到下一级（SDS_TYPE_8，3 bytes header）。
下面看新的sds结构怎么用，以sdslen为例：
#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)
static inline size_t sdslen(const sds s) {
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_TYPE_32，类型为3，二进制0011
SDS_TYPE_MASK，mask为7，二进制0111
0011
& 0111
————
0011
作者验证了速度提升在大多数命令中都不是很明显，除了具有依赖于大量sdscatlen（）或sdcatfmt（）的工作负载的命令，其中可以使用高达25％的性能。但最重要的是这次改进添加了很重要的一项功能：为Redis提供了超过4G字符串的能力。
本文的不足之处，未对修改前后内存对齐的问题做研究分析，参考资料3中有相关讨论。对于该内容，是以后学习的一个方向。
参考资料：
3、sds size classes - memory optimization #2509（记录了antirez和oranagra关于优化的详细对话细节）
4、Redis设计与实现 （黄建宏）
网友评论