Redis源码学习——简单动态字符串SDS（Simple Dynamic String）

        前两天听了学长们的交流会，偶尔接触到了redis，考虑到redis只有2W多行代码，感觉代码量不是很大，所以决心看看他的源代码。

        由于刚刚接触redis，所以就跟着大牛的文章一步一步的学下去了。

        打算按照《Redis 设计与实现》http://www.redisbook.com/en/latest/#id1 这本书慢慢的学下去，希望今天是一个良好的起点。

SDS是Redis底层使用的字符串的表示形式，因为几乎所有Redis模块都使用了SDS，所以有必要好好了解一下这个实现机制。

1、SDS用途

在介绍SDS之前，先来看看他是如何工作的，这对于更好的理解实现会有帮助。

SDS主要用两方面作用：

1.1实现字符串对像

Redis是键值对数据库，数据库的值（value）可以是字符串、集合、列表等类型对象，但是数据库键（key）总是字符串对象。

举例如下：

redis> SET name "cai"
OK

redis> GET name
"cai"

这里键值对的键和值都是字符串对象，他们都包含一个SDS值。

1.2在Redis内部作为char*的替代品

因为 char* 类型的功能单一， 抽象层次低， 并且不能高效地支持一些 Redis 常用的操作（比如追加操作和长度计算操作）， 所以在 Redis 程序内部， 绝大部分情况下都会使用 SDS 而不是 char* 来表示字符串。

在 C 语言中，字符串可以用一个 \0 结尾的 char 数组来表示。比如说， hello world 在 C 语言中就可以表示为 "hello world\0" 。

这种简单的字符串表示，在大多数情况下都能满足要求，但是，它并不能高效地支持长度计算和追加（append）这两种操作：

每次计算字符串长度（strlen(s)）的复杂度为 θ(N) 。

对字符串进行 N 次追加，必定需要对字符串进行 N 次内存重分配（realloc）。

在 Redis 内部， 字符串的追加和长度计算很常见， 而 APPEND 和 STRLEN 更是这两种操作，在 Redis 命令中的直接映射， 

这两个简单的操作不应该成为性能的瓶颈。稍后将介绍这两个操作如何通过SDS降低复杂度。

2、SDS的实现

// 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。

之后的分析还会看到这样做的好处以及巧妙之处。

3、追加指令APPEND

利用 sd