Redis--简单动态字符串

发表于 2018-03-19 分类于 Redis 阅读次数：

简介

Redis构建了一种名为简单动态字符串（simple dynamic string ，SDS）的抽象类型，用来保存字符串。

SDS 实现

shs.h文件中sdshdr结构体表示了一个SDS的值：

struct sdshdr {
    // buf 中已占用空间的长度  
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[];
};

SDS结构

SDS和C字符串一样，使用空字符结尾，保存空字符串的1字节空间不包含在SDS的len属性里面，因此需要分配N+1个字节空间来保存数据。
len属性表示SDS保存字符串的长度，不包含字符串结尾的空字符串。
free属性表示数组中未使用的字节数量

buf属性是char类型的数组，用来保存SDS字符串数据。

SDS 特点

常数复杂度获取字符串长度

在更新和添加字符串到SDS的过程中，SDS的API会自动更新SDS的len属性，不需要手动更改，因此获取字符串长度的时间复杂度是O(1)。

/*
 * 返回 sds 实际保存的字符串的长度
 *
 * T = O(1)
 */
static inline size_t sdslen(const sds s) {
    //// 取出 sdshdr
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

防止缓存区溢出

C字符串不记录自身的长度，容易发生缓冲区溢出。SDS的free属性记录数组中未使用的字节数量，SDS的API操作SDS会首先检查剩余空间是否满足要求，所以不会发生缓冲区溢出的情况。

内容重分配策略

空间预分配

需要对SDS进行空间扩展时，程序不仅会为SDS分配所必须的空间，还会分配额外未使用的空间。

对SDS修改之后，SDS的长度小于1MB，那么程序分配和len属性同样大小的空间，假设修改后SDS的大小是13字节，那么将分配13+13+1=27个字节。

如果对SDS修改之后，SDS的长度大于等于1MB，将分配1M未使用空间。假设修改后SDS的长度是30MB，那么程序会分配1MB未使用空间，实际大小为：30MB+1MB+1byte.

/*
 * 最大预分配长度
 */
#define SDS_MAX_PREALLOC (1024*1024)
/*
 * 对 sds 中 buf 的长度进行扩展，确保在函数执行之后，
 * buf 至少会有 addlen + 1 长度的空余空间
 * （额外的 1 字节是为 \0 准备的）
 *
 * 返回值
 *  sds ：扩展成功返回扩展后的 sds
 *        扩展失败返回 NULL
 *
 * 复杂度
 *  T = O(N)
 */
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 分配新空间所需的大小
    //判断分配后的总长度是否小于1MB
    if (newlen < SDS_MAX_PREALLOC)
        // 如果新长度小于 SDS_MAX_PREALLOC 
        // 那么为它分配两倍于所需长度的空间
        newlen *= 2;
    else
        // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    // 内存不足，分配失败，返回
    if (newsh == NULL) return NULL;
    // 更新 sds 的空余长度
    newsh->free = newlen - len;
    // 返回 sds
    return newsh->buf;
}

惰性空间释放

惰性空间释放是指不通过内存重分配回收缩短后多出来的字节，而是通过改变free属性，惰性的释放空间。下面的代码就是在不释放空间的情况下，重置SDS字符串为空字符串，也就是惰性空间释放：

/*
 * 在不释放 SDS 的字符串空间的情况下，
 * 重置 SDS 所保存的字符串为空字符串。
 *
 * 复杂度
 *  T = O(1)
 */
/* Modify an sds string on-place to make it empty (zero length).
 * However all the existing buffer is not discarded but set as free space
 * so that next append operations will not require allocations up to the
 * number of bytes previously available. */
void sdsclear(sds s) {

    // 取出 sdshdr
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));

    // 重新计算属性
    sh->free += sh->len;
    sh->len = 0;

    // 将结束符放到最前面（相当于惰性地删除 buf 中的内容）
    sh->buf[0] = '\0';
}

二进制安全

C字符串除了字符串的未尾之外，字符串里面不能包含空字符，否则最先被程序读入的空间将被误认为是字符串结尾，这些限制了C字符串只能保存文本数，不能保存图片等二进制数据。SDS没有这种限制,可以保存文本或者二进制数据

SDS API

函数	作用	算法复杂度
sdsnewlen	创建一个指定长度的 sds ，接受一个 C 字符串作为初始化值	(O(N))
sdsempty	创建一个只包含空白字符串 “” 的 sds	(O(1))
sdsnew	根据给定 C 字符串，创建一个相应的 sds	(O(N))
sdsdup	复制给定 sds	(O(N))
sdsfree	释放给定 sds	(O(N))
sdsupdatelen	更新给定 sds 所对应 sdshdr 结构的 free 和 len	(O(N))
sdsclear	清除给定 sds 的内容，将它初始化为 “”	(O(1))
sdsMakeRoomFor	对 sds 所对应 sdshdr 结构的 buf 进行扩展	(O(N))
sdsRemoveFreeSpace	在不改动 buf 的情况下，将 buf 内多余的空间释放出去	(O(N))
sdsAllocSize	计算给定 sds 的 buf 所占用的内存总数	(O(1))
sdsIncrLen	对 sds 的 buf 的右端进行扩展（expand）或修剪（trim）	(O(1))
sdsgrowzero	将给定 sds 的 buf 扩展至指定长度，无内容的部分用 \0 来填充	(O(N))
sdscatlen	按给定长度对 sds 进行扩展，并将一个 C 字符串追加到 sds 的末尾	(O(N))
sdscat	将一个 C 字符串追加到 sds 末尾	(O(N))
sdscatsds	将一个 sds 追加到另一个 sds 末尾	(O(N))
sdscpylen	将一个 C 字符串的部分内容复制到另一个 sds 中，需要时对 sds 进行扩展	(O(N))
sdscpy	将一个 C 字符串复制到 sds	(O(N))

学习资料：
[1] 黄健宏. Redis设计与实现[M]. 机械工业出版社, 2014.