Redis 的作者 antirez 在前些日子，通过博客文章《 The first release candidate of Redis 4.0 is out 》发布了 redis 4.0 版本。在网上看到了一些文章，对于4.0新特性的介绍：
- Lazyfree，之前的版本，在对一个较大的key执行删除时，会造成 redis-server 阻塞，现在可以使用
UNLINK异步删除，FLUSHDB和FLUSHALL都新增了ASYNC选项，支持在后台线程进行； - LFU，新添加了 Last Frequently Used 缓存驱逐策略，具体见 antirez的另一篇文章；
- 内存命令，新添加了一个 MEMORY 命令， 可以用于内存使用情况；
- 混合 RDB-AOF 持久化格式，之前大部分的做法，都是同时开启 RDB 和 AOF 两种持久化，这种模式会在 AOF rewrite 文件里同时包含 RDB 格式的内容和 AOF 格式的内容，可以发生问题时迅速载入数据（RDB 优点），还能快速的生成重写文件
- 更多的可以查看 https://raw.githubusercontent.com/antirez/redis/4.0/00-RELEASENOTES
有了这么几个优化点，带着好奇心，决定看看新版本的源码和之前相比有什么不同。
新版本的 SDS
我们都知道，sds 是 Redis 用来表示字符串键值对，在3.0版本中，sds的结构体是这样子的:
struct sdshdr {
int len; // 记录 buf 数组中已使用字节的数量，等于SDS所保存字符串的长度
int free; // 记录 buf 数组中未使用字节的数量
char buf[]; // 字节数组，用于保存字符串
}
新版本的sds根据保存字符串长度的不同，分别对应5种结构体：
/* 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[];
};
新的结构体，其中 len 表示字符串的长度（不包含结尾’\0’的空字符）；alloc 表示为字符串分配的空间，flags 中最低三个bit，表示类型， buf 存储着具体的字符串
常数复杂度获取字符串长度
sds 和 C 字符串都是以一个空字符 “\0” 结尾。C 字符串本身不记录长度，要想得到长度，必须遍历计算，时间复杂度 O(N)，而 sds 结构体中的 len 记录了本身的长度，所以获取一个 sds 字符串的长度的复杂度是 O(1)。
sds 在每次初始化或者长度有变化时，相应的 api 都会有这样的计算，可以直接使用而无需关心是怎么样做的，有兴趣的可以看源码的 src/sds.h 中的 sdslen 方法（86行）
杜绝缓冲区的溢出
在做字符串拼接的时候，在 C 语言里，比如执行 strcat(char *hello, const char *world ) 拼接两个字符串时，在内存中与 hello 紧邻的还有另一个字符串 “hello1”，假定未为 hello 分配足够多的内存，在 strcat 执行后，hello 的数据溢出到 “hello1”，导致其中 “hello” 被 “world” 在不知情的情况下被替换掉，这种情况是非常危险的…
sds 在字符串修改时，在拼接之前，会先检查 sds 的空间是否满足，如果不满足的话，会自动（通过调用 sdsMakeRoomFor）修改至所需的大小，然后才执行实际的修改，这样保证了新的字符串不会因为溢出而污染其他相邻内存上的数据。
空间分配策略
C 字符串在每次增加或者缩短字符串时，程序总是要对这个 C 字符串的数组进行一次内存重新分配：
如果是增长字符串，那么在执行这个操作之前，需要通过内存重新分配来扩展底层数组的大小，否则就会造成 缓冲区溢出
如果是缩短字符串，那么在执行这个操作之后，需要通过内存重新分配来释放字符串不再使用的那部分空间，否则就会造成 内存泄露
每一次内存分配，都是比较耗时的操作，涉及到复杂的算法和内存的IO，如果出于性能的考虑，就要更可能少的去做这样的事情。
作者的初衷，相信也是将 Redis 定位成更高效，性能更好的NoSQL。为了优化 这种缺陷，sds做了预分配和惰性释放来分别应对这两种内存重新分配的情况。
- 空间预分配
空间预分配主要作用于 sds 字符串增长操作，通过 API sdsMakeRoomFor 来重新计算分配空间，具体规则在 src/sds.c 210行：
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
总结一下就是：如果新的字符串大小 小于 1MB，那么会分配 2倍的新的字符串的大小，即 newlen *= 2，buf 的大小则为 newlen * 2 + 1，一字节用来存结尾空字符 “\0”；如果新字符串的长度 大于 1MB，那么会分配 新字符串大小 + 1MB，即 newlen += SDS_MAX_PREALLOC。
这样做的话，会将原本增长N次，便会重新进行N次内存分配，变成了，最多会重新分配内存N次，就是说，如果一次预分配后的大小，满足 sds 修改后的大小，就不需要再对内存重新分配，直接增长即可。
- 空间惰性释放
空间惰性释放是指缩短 sds 时，不是立即使用内存重新分配来回收缩短后多出来的空间，而是继续保留，以便将来使用。
以 sdstrim 这个 api 为例，看下它的源码
sds sdstrim(sds s, const char *cset) {
char *start, *end, *sp, *ep;
size_t len;
sp = start = s;
ep = end = s+sdslen(s)-1;
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > sp && strchr(cset, *ep)) ep--;
len = (sp > ep) ? 0 : ((ep-sp)+1);
if (s != sp) memmove(s, sp, len);
s[len] = '\0';
sdssetlen(s,len);
return s;
}
只做了 memmove 操作，并没有真正重新分配内存，倘若此时，需要执行 sdscat，拼接上一个较短字符串，就可以直接使用，避免了再次分配内存。
如果有需要，必须使用释放掉这部分内存，可以调用 sdsRemoveFreeSpace 来真正释放掉。
二进制安全
我们都知道，C 字符串除了在末尾的空字符外，其他位置不允许有空字符，否则最先被读到的空字符，就会被误认为是字符串结尾。这样限制了只能存储纯文本内容，不能保存二进制数据。
sds 就不会有这样的要求，它可以满足你存储任何数据，即使字符串中间有空字符也不受影响，因为它有 len 来表示字符串是否结尾。sds 所有 API 都是二进制安全的，和 C 字符串一样，是以空字符结尾，因此可以复用 C 字符串的一些函数。
以上就是我对 sds 字符串的认识，觉得作者真的是非常用心的设计，既遵循了规范，并且还有很好的优化点在里面，越来越有兴趣继续研究下去了~