Redis源码阅读笔记（1）——简单动态字符串sds实现原理

首先，sds即simple dynamic string，redis实现这个的时候使用了一个技巧，并且C99将其收录为标准，即柔性数组成员（flexible array member），参考资料见这里。柔性数组成员不占用结构体的空间，只作为一个符号地址存在，而且必须是结构体的最后一个成员。柔性数组成员不仅可以用于字符数组，还可以是元素为其它类型的数组。C99中，结构中的最后一个元素允许是未知大小的数组，这就叫做柔性数组成员，但结构中的柔性数组成员前面必须至少一个其他成员。柔性数组成员允许结构中包含一个大小可变的数组。sizeof返回的这种结构大小不包括柔性数组的内存。包含柔性数组成员的结构用malloc()函数进行内存的动态分配，并且分配的内存应该大于结构的大小，以适应柔性数组的预期大小。

Redis使用sds代替C语言中的char*，实现自定义的字符串对象，redis是K-V型DB，数据库的值可以是字符串、集合、列表多种类型，而键则总是字符串对象。Redis中的字符串分两类：二进制安全的和非二进制安全的，对于存储的值是二进制安全的，对于键是非二进制安全的。

对于二进制安全，我的理解就是把处理的字符串作为原始的、无任何特殊格式意义的数据流。

Redis中字符串类型是最基本的类型，redis自己实现的字符串对象相对char*来说，有以下两点优势：

char*计算字符串长度，时间O(n)；
char*对字符串进行追加，追加N次，必定需要对字符串进行N次内存重分配；

作为值存储也是最常用的，其他诸如集合、列表也是基于字符串实现的，redis字符串类型sds在sds.h、shs.c文件中定义。

定义：

// sds 类型
typedef char *sds;

// sdshdr 结构
struct sdshdr {

    // buf 已占用长度
    int len;

    // buf 剩余可用长度
    int free;

    // 实际保存字符串数据的地方
    // 利用c99(C99 specification 6.7.2.1.16)中引入的 flexible array member,通过buf来引用sdshdr后面的地址，
    // 详情google "flexible array member"
    char buf[];
};

因为自定义类型加入了长度，每次获取字符串长度的时间复杂度就是O(1)，而利用len和free属性对追加字符串进行优化，也可以降低重新分配内存的次数。但是这里也有要求就是len和free的更新要小心，不然很容易产生bug。

新建字符串对象：

sds sdsnewlen(const void *init, size_t initlen) {

    struct sdshdr *sh;

    // 有初始值
    // 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] = '

Redis源码阅读笔记（1）——简单动态字符串sds实现原理

相关推荐