SDS是Redis底层使用的字符串的表示形式。
SDS用途
SDS主要用两方面作用：
1.实现字符串对像
Redis是键值对数据库，数据库的值（value）可以是字符串、集合、列表等类型对象，但是数据库键（key）总是字符串对象。
举例如下：
redis> SET name "cai"
OK
redis> GET name
"cai"
这里键值对的键和值都是字符串对象，他们都包含一个SDS值
2.在Redis内部作为char*的替代品
因为 char* 类型的功能单一， 抽象层次低， 并且不能高效地支持一些 Redis 常用的操作（比如追加操作和长度计算操作）， 所以在 Redis 程序内部， 绝大部分情况下都会使用 SDS 而不是 char 来表示字符串*。
在 C 语言中，字符串可以用一个\0结尾的char数组来表示。比如说， hello world 在 C 语言中就可以表示为 "hello world\0" 。这种简单的字符串表示，在大多数情况下都能满足要求，但是，它并不能高效地支持长度计算和追加（append）这两种操作：
- 每次计算字符串长度（strlen(s)）的复杂度为 θ(N) 。
- 对字符串进行N次追加，必定需要对字符串进行N次内存重分配（realloc）。
SDS的实现
在源代码sds.h中定义了sds以及sdshdr结构体。
// sds 类型
typedef char *sds;
// sdshdr 结构
struct sdshdr {
// buf 已占用长度
int len;
// buf 剩余可用长度
int free;
// 实际保存字符串数据的地方
char buf[];
};
从这个定义中无法看出sds与sdshdr之间的关系。
通过查看sds.c中的代码，皆能迎刃而解了。
/*
* 创建一个指定长度的 sds
* 如果给定了初始化值 init 的话，那么将 init 复制到 sds 的 buf 当中
*
* T = O(N)
*/
sds sdsnewlen(const void *init, size_t initlen) {
struct sdshdr *sh;
// 有 init ？
// O(N)
if (init) {
sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
} else {
sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
}
// 内存不足，分配失败
if (sh == NULL) return NULL;
sh->len = initlen;
sh->free = 0;
// 如果给定了 init 且 initlen 不为 0 的话
// 那么将 init 的内容复制至 sds buf
// O(N)
if (initlen && init)
memcpy(sh->buf, init, initlen);
// 加上终结符
sh->buf[initlen] = '\0';
// 返回 buf 而不是整个 sdshdr
return (char*)sh->buf;
}
通过创建函数可以看到，函数返回值是sds，在函数中返回的是sdshdr结构体中数据指向部分。
这就可以知道在创建sds对象的时候，其实是创建了一个sdshdr结构体对象，但是通过巧妙的指针指向，实现了sds。
追加指令APPEND
利用 sdshdr 结构，可以用 θ(1) 复杂度获取字符串的长度，还可以减少追加（append）操作所需的内存重分配次数。
redis> SET msg "hello world"
OK
redis> APPEND msg " again!"
(integer) 18
redis> GET msg
"hello world again!"
首先， SET 命令创建并保存 hello world 到一个 sdshdr 中，这个 sdshdr 的值如下：
struct sdshdr {
len = 11;
free = 0;
buf = "hello world\0";
}
当执行 APPEND 命令时，相应的 sdshdr 被更新，字符串 " again!" 会被追加到原来的 "hello world" 之后：
struct sdshdr {
len = 18;
free = 18;
buf = "hello world again!\0 "; // 空白的地方为预分配空间，共 18 + 18 + 1 个字节
}
当调用 SET 命令创建 sdshdr 时， sdshdr 的 free 属性为 0 ， Redis 也没有为 buf 创建额外的空间，
而在执行 APPEND 之后， Redis 为 buf 创建了多于所需空间一倍的大小。在这个例子中， 保存 "hello world again!" 共需要 18 + 1 个字节， 但程序却为我们分配了 18 + 18 + 1 = 37 个字节 ，
这样一来， 如果将来再次对同一个 sdshdr 进行追加操作，只要追加内容的长度不超过 free 的值， 就不需要对 buf 进行内存重分配。
举例如下：
redis> APPEND msg " again!"
(integer) 25
struct sdshdr {
len = 25;
free = 11;
buf = "hello world again! again!\0 "; // 空白的地方为预
//分配空间，共 18 + 18 + 1 个字节
}
理解了SET和APPEND机制，就能知道为什么使用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 *size* of the sds string as returned
* by sdslen(), but only the free buffer space we have. */
/*
* 对 sds 的 buf 进行扩展，扩展的长度不少于 addlen 。
*
* T = O(N)
*/
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;
sh = (void*) (s-(sizeof(struct sdshdr)));
// 目前 buf 长度
len = sdslen(s);
// 新 buf 长度
newlen = (len+addlen);
// 如果新 buf 长度小于 SDS_MAX_PREALLOC 长度
// 那么将 buf 的长度设为新 buf 长度的两倍
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;
}
如下代码就巧妙的利用了指针的指向，找到sds对应的sdshdr结构体。
sh = (void*) (s-(sizeof(struct sdshdr)));
SDS_MAX_PREALLOC 的值为 1024 * 1024 ， 当大小小于 1MB 的字符串执行追加操作时， sdsMakeRoomFor 就为它们分配多于所需大小一倍的空间； 当字符串的大小大于 1MB ， 那么 sdsMakeRoomFor 就为它们额外多分配 1MB 的空间。
网友评论