Redis数据结构-SDS
Redis是一个开源（BSD许可），内存存储的数据结构服务器，可用作数据库，高速缓存和消息队列代理。
首先介绍下Redis的基础数据结构 —— SDS
Redis没有使用传统C语言的字符串（字符数组）表示。而是自己构建了一种名为sds(Simple Dymamic String)的抽象类型，作为redis的默认字符类型。 SDS用于保存数据库中的字符串值，用户客户端的输入的缓冲区，AOF模块中的缓冲区都是由SDS实现的。
SDS相比于C字符串的优点：
- 常数复杂度获取字符串长度
- 缓冲区溢出
- 减少改变字符串长度时带来的内存重新分配
- 二进制安全
同时，sds也支持c字符串的部分操作函数。
SDS的数据结构：
以下是SDS的数据结构
/*
* 保存字符串对象的结构
*/
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
// ps: 在redis 3.0中 为了更加节省内存，可用的sdshdr分成4种，len和free属性分别可以是uint8_t，uint16_t，uint32_t，uint64_t 这四种类型，会随着sds所保存的字符串长度不同，而分配为不同的sdshdr。 获取长度；
Redis中获取字符长度的操作是STRLEN key
C语言中的字符串并不记录自身的长度信息。 如果我们想要获取一个c字符串的长度，我们要遍历整个字符串，直到遇到代表结尾符的'/n'为止。 毫无疑问，其复杂度是O(N)。
而在sds中，我们记录了每个sds对象中所存字符串的长度。 sds提供了一系列操作sds的函数，若出现改变数组长度的草走，都会同步更新len字段，保证len字段的实时性。 这样每个STRLEN的复杂度就变成了O(1).
缓存区溢出：
C语言中提供了strcat方法，可以将strSrc字符串拼到strDest字符串尾部。 然而每次执行strcat操作时，都假设了我们已经strDest指针分配了足够多的内存。 然而一旦当分配的内存不足， 机会出现缓存区溢出。如下：
#include <stdio.h>
#include <string.h>
int main(void)
{
char dest[20] = "Hey ";
for(int i = 0; i < 20; i++) {
strcat(dest, ", Man");
printf("%d time, lenght is: %ld \n", i, strlen(dest));
}
return 0;
}执行结果：
0 time, lenght is: 9
1 time, lenght is: 14
2 time, lenght is: 19
[1] 29751 abort ./str可以看到，当执行到第三次的时候，并不会由于dest已经快到其最大容量。 所以第四次strcat执行时，会出现溢出，中断程序。
而在sds中，执行sdscat操作，会判断为目标sds对象所分配的内存是否可以容纳拼接后的字符内存。 代码如下：
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
sds sdscatlen(sds s, const void *t, size_t len) {
struct sdshdr *sh;
// 获取原字符长度
size_t curlen = sdslen(s);
// 扩展空间。 若原指针分配内存不足，则重新分配内存。 返回新的地址
// T = O(N)
s = sdsMakeRoomFor(s,len);
// 若内存不足直接返回
if (s == NULL) return NULL;
// 获取sds句柄sdshdr 的指针位置
sh = (void*) (s-(sizeof(struct sdshdr)));
// 复制将t中字符串复制到目标字符串后面
// T = O(N)
memcpy(s+curlen, t, len);
// 更新属性
sdssetlen(s, curlen+len);
// 添加新结尾符号
s[curlen+len] = '\0';
// 返回新 sds
return s;
}可以看到， 每次执行字符串拼接操作，都会判断所分配的内存是否足够，如果不足，会重新分配内存。 其他操作，例如sdsrange（仅保留部分字符串），sdstrim（裁剪特定字符）都会有以上类似逻辑，保证每次操作都会即时释放多余内存，且不会出现内存不足。
减少改变字符串长度时带来的内存重新分配
然而通过C字符串执行会改变字符串长度的操作， 也可以通过判断字符串长度实现预分配内存。每次内存重新分配都要将原内存中的字符复制到新内存中， 复杂度是O(N)，然而当我们频繁地对一个字符串进行改变长度的操作，会导致每次操作都引起一次O(N)的操作。
在sds中， 每次重新分配内存都会预留一部分作为buffer，我们可以从上文的代码中看到，重新分配内存是通过sdsMakeRoomFor函数调用。 那么我们看下sdsMakeRoomFor中，分配内存的策略：
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
// 获取s目前剩余的空间长度
size_t free = sdsavail(s);
size_t len, newlen;
// s 目前的空余空间已经足够，无须再进行扩展，直接返回
if (free >= addlen) return s;
// 获取 s 目前已占用空间的长度
len = sdslen(s);
// 获取句柄指针位置
sh = (void*) (s-(sizeof(struct sdshdr)));
// 扩展后s至少需要的长度
newlen = (len+addlen);
// 根据新长度，为 s 分配新空间所需的大小
if (newlen < SDS_MAX_PREALLOC)
// 如果新长度小于 SDS_MAX_PREALLOC
// 那么为它分配两倍于所需长度的空间
// 对新建的sds或者重新分配内存的sds，都会采用此策略，保留1倍的长度
newlen *= 2;
else
// 否则，所保留的buffer长度为 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
// T = O(N)
// 分配内存，获取新的指针地址
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
// 若内存不足，分配失败，返回
if (newsh == NULL) return NULL;
// 设置剩余空间长度。
newsh->free = newlen - len;
// 返回 sds
return newsh->buf;
}redis中为了减少内存的重新分配， 使用了预留buffer的方法。 将原来n次字符串操作一定有n次O(N)复杂度的内存分配， 调整为最多有n次O(N)复杂度的内存分配。
tips： 当执行sdstrim这样减少字符串长度的操作时， 即时裁剪后多余的内存大于len的一半，sds也不会立即将多余的空间释放，而是保留下来未将来的增长操作做了优化。 且提供了sdsRemoveFreeSpace这个APi，用于我们可以手动将这样多余的内存释放。
二进制安全
二进制安全是一个主要用来处理字符串操作的编程术语。二进制安全功能本质上是把输入当作一个没有任何特殊的原生流，其在操作上应包含一个字符所能有的256种可能的值（假设为8为字符）。
由于C字符串需要通过'0'判断字符串的结尾。 所以当我们储存字符串时，需要将'0'这样的特殊字符过滤掉。 在sds中，由于我们维护了字符串的长度，所以并没有这样的顾虑。 sds符合二进制安全。
支持c字符串的部分操作函数
由于sds的api提供的入参都是sds格式，指向的都是其buf属性的指针位置。 我们以一个创建sds的api为例：
sds sdsnewlen(const void *init, size_t initlen) {
struct sdshdr *sh;
// do somethings to create sds...
sh->len = initlen;
sh->free = 0;
sh->buf[initlen] = '\0';
// 返回 buf 部分，而不是整个 sdshdr
return (char*)sh->buf;
}我们可以看到，sds对象，我们获取的并不是整个sdshdr指针的位置， 而是其buf属性的指针，也就是存字符串的指针位置，且sds遵守了以'0'作为一个字符串结尾的条件（但并不是通过'0'的位置判断字符串的长度）。 这样就保证了我们对一部分C字符串接口传入sds对象的指针，是可以当作char[]用的。
