Redis的数据结构(一)：简单动态字符串

开场白

作为redis的使用者，我们最常用的操作可能就是set了，而最常用的数据结构则是string了，我们常常会使用命令:

127.0.0.1:6379> set key value

这个命令中，key和value都被保存到一个字符串中。需要注意的是，这个字符串并非C语言的字符串结构，而是redis自己实现的一个名为sds的数据结构

SDS的定义

我们翻到redis3.0的源码，找到src/sds.h,先看看这个sds的结构体定义：

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

• 字段free：表示可分配的空间的字节长度
• 字段len：表示已占用空间的字节长度
• 字段buf：表示装载实际字符串的字符数组

举一个最简单的例子，比如Redis这个字符串，在sds的保存则是这样的：

image.png

为什么要在后面加上这个\0呢？这么设计的目标是为了遵循C语言字符结尾的惯例，同时能够兼容一部分C语言字符串操作库函数，比如strlen。同时这个\0是不会记录进去len字段的。

使用SDS的好处

1.有效提升处理长字符串的性能

C语言的字符串类型，计算长度是必须要遍历字符的，也就是如果长度为5的字符串，那么计算长度必须要遍历五次才能得出结果，计算复杂度是O(N)。如果使用了sds的话，可以在分配字符串的时候就直接把长度记录在len字段，那么这个计算复杂度将会是O(1)，这么做能够解决redis处理大型字符串长度的性能瓶颈问题。

2.防止缓冲区溢出，优化内存分配

普通的C语言字符串会存在缓冲区溢出的问题，举个最简单的例子，如字符串s1是redis，字符串s2是mongodb，并假设他们在内存中是紧紧相邻的。假如一个粗心的程序员没有为s1去分配更多空间的前提下就调用了strcat进行了字符串拼接，如strcat(s1, "cluster")，那么这个s1就会溢出并且可能擦写s2的内存，就会出现一些很坑爹但又难以发现的bug了。但是使用sds就能规避这个问题，比如src/sds.c文件中有一个函数叫sdscat,我们看一下代码

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);

    // 扩展 sds 空间
    // T = O(N)
    s = sdsMakeRoomFor(s,len);

    // 内存不足？直接返回
    if (s == NULL) return NULL;

    // 复制 t 中的内容到字符串后部
    // T = O(N)
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);

    // 更新属性
    sh->len = curlen+len;
    sh->free = sh->free-len;

    // 添加新结尾符号
    s[curlen+len] = '\0';

    // 返回新 sds
    return s;
}

// 着重看这个函数
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 
        // 那么为它分配两倍于所需长度的空间
        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;
}

我们着重看看sdsMakeRoomFor函数，它展示了redis的sds是如何分配内存的，还是举个栗子：我们有字符串s1="redis"，我们调用sdscat(s1, "cluster")，那么s1会变为redis cluster，因为原来的s1的len字段只有5字节，因此连接cluster需要进行内存扩展操作，可以从代码看到，如果s1的free的长度大于等于cluster的长度，那么会把free这部分让出来进行分配给cluster字符串，但如果不够长又会产生两种分配策略：

1. 如果连接后新的字符串的长度尚未超过宏定义SDS_MAX_PREALLOC(默认是1MB)，那么会分配两倍于新字符串的长度。比如连接后的字符串s1是redis cluster，长度即是13，那么会多分配出13个字节，并把长度保存在free字段，那么最终扩容后buf的空间就是13 + 13 + 1 = 27个字节。
2. 如果连接后的字符串长度超过宏定义SDS_MAX_PREALLOC（默认是1MB），那么会比新字符串长度分配多SDS_MAX_PREALLOC（默认是1MB）的内存。比如连接后的字符串s1长度是10MB，那么buf扩容分配后的空间就是30MB + 1MB + 1Byte。

除此之外，redis的sds api也有惰性释放的机制。假如一个字符串需要被裁减，比如redis cluster变为redis，sds的api不会马上把cluster这7个字节空间马上释放掉，而是会继续保留，并记录在free字段中，也就是free=7，这么做是为了日后如果redis这个字符串要增长的时候就不用去重新分配内存了。当然，如果你真的觉得这部分空间用不着了，也可以通过sdsRemoveFreeSpace这个函数去释放掉这部分free的空间。

3.保证二进制安全

C语言字符串必须符合某种编码，并且除了字符串末尾之外，字符串里面不能包含空字符串，否则会认为是结尾了，因此也导致C语言字符串没办法保存、图片、视频、压缩文件等二进制数据。
redis的sds使用了字符数组作为字符串的保存结构的好处就显现出来了，正因为是字符数组，那么可以用来保存任何的二进制数据，并且保证读入数据是什么，读出的数据就是什么。

以上就是redis简单动态字符串的特点和优势的总结，后面会继续redis的其他数据结构，敬请期待！

文章参考自：<<Redis设计与实现>> 第二版