渐进式解析 Redis 源码 - 动态字符串

2018-10-22 阅读量

动态字符串SDS 是 Redis 众多数据结构中最简单的一个，但其实也并不那么简单…

Redis 使用了自主定义的 SDS数据结构重新实现字符串相关操作，这一看似多此一举的操作，实际上设计及其精妙…

与普通 C 字符串相比，其突出特点如下：

获取字符串长度复杂度 O(1)
拒绝缓冲区溢出
优化动态字符串的内存分配
二进制安全
兼容 C 字符串部分函数

突出特点

/* 动态字符串结构体 */
// sds 兼容 char
typedef char *sds;
// 为了适应不同长度的字符串，配备了不同空间的结构体
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
// 这个结构实际没有被使用过，仅仅用来读取 flag 字段，作为初始 flag
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
// uint8_t 长度，最大 255
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
// uint16_t 长度，最大 65535
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
// uint32_t 长度，最大 4294967295
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
// uint64_t 长度，最大 18446744073709551615
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

获取字符串长度复杂度 O(1)

众所周知 C 字符串获取长度的原理是遍历字符串，对遇到的每个字符进行计数，直到遇到结束空字符 \0，复杂度为 O(n)

而 SDS 则不同，通过上面的 SDS 结构体可以看出，如果需要获取 SDS 的长度，则直接读取 len 属性即可，复杂度就是 O(1)，这是一个典型的 空间换取时间 的案例。而且即使修改 SDS 字符串内容，那么也会有对应的 API 去更新 len 属性

拒绝缓冲区溢出

C 字符串由于没有记录 len，还会出现一个隐患就是缓冲区溢出；比如现在有两个字符串 str1 和 str2 是连续的，分别存储 “hello” 和 “nihao”，突然需要对 str1 里追加 “ world”，那么如果没有进行容量判断，则有可能会出现 str1 的内容溢出到 str2 空间，造成数据污染

反观 SDS 则是由 API 先判断 str1 剩余空间是否足够，如果不够，则会自动升级存储空间，然后再进行数据修改

优化动态字符串的内存分配

针对 C 字符串进行增加、缩减操作的时候，实际都会重新分配内存变量；比如对字符串追加字符内容做拼接操作，则会扩展变量内存空间大小，如果忘了，则会缓冲区溢出；那么如果对字符串删减字符内容做剪切操作，则会在操作之后对多余的变量内存空间进行释放，否则就会内存泄露

为了防止内存分配操作成为 Redis 的瓶颈，所以 SDS 在这方面也做了优化，主要是空间预分配、惰性空间释放等方式，也是极其典型的 空间换取时间 的案例，可见这一理念在软件设计方面的应用之广泛…

二进制安全

C 字符串内容必须是类似 ASCII 一样的编码，并且除了字符串结尾不能有空字符，否则会被提前当做结尾，这样的话就没法存储图片、音频、视频、压缩文件等二进制数据

而SDS 就不同了，依赖自带的 len 属性，不会按照字符串内容里的空字符串判断结尾。所以这一特性，使得 Redis 不仅支持文本存储，还支持多样性的二进制数据存储

兼容 C 字符串部分函数

SDS 虽然有很多优秀的特性，但是根据上面提到的 typedef char *sds;，本质上还是兼容 char 的，完全可以使用大部分 char 操作函数，SDS 还会往字符串结尾添加空字符（虽然不依赖）…

源码解析

由于有些方法里的代码量比较大，我们这里按照典型的代码片段进行解析，同志们可以根据文章提示的代码位置和代码里面的关键词在源码中搜素，可能数据结构一些元素看不太懂什么意思，没关系，先混个脸熟，后面看完回头再看过来就明白了

结构体

接上面【突出特点】部分的 SDS 结构体代码，结构字段主要有如下内容

-------- 字符串 header ----------
#len        字符串真实长度，不包括终止符
#alloc      字符串最大容量，不包括终止符
#flags      header 类型
-------- 字符串主体 --------------
#buf[]
-------- flag 的类型，内容为 0~4 --
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

SDS 一般是采用了一段连续的内存空间来存储动态字符串 header (len / alloc / flags) + buf
SDS 结构体内存空间结构

而且为了防止编译器的 C 内存对其原则优化，所以结构体前添加了 __attribute__ ((__packed__))，否则经过优化就不能保证 header 和 buf数据部分是紧紧相邻的内存空间了。所以现在获取 flag 的值可以直接往前便宜1个字节即可：unsigned char flags = s[-1]

另外SDS 提供了一些宏，方便进行操作

1
2
3

#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

比如有个 sdshdr8 类型的 SDS，那么获取长度就可以使用 SDS_HDR(8,s)->len，宏的调用过程如下，由于内存空间是连续的，所以 SDS 指针地址减去 sdshd8 的长度，即往前偏移 header 长度，就获取到了 header 的指针地址

SDS_HDR(8,s)->len
=> ((struct sdshdr##8 *)((s)-(sizeof(struct sdshdr##8))))->len
=> ((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))->len
=> header->len

C 宏定义中『##连接符』详细，可以参照资料 http://www.web-lovers.com/c-joiner.html

SDS API

sdsnewlen() 为 SDS 创建函数

/* sds.c: line 84 */
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    // 根据长度 获取初始 type
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    // 空的字符串通常被创建成 type 8，因为 type 5 已经不实用了
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    // 获取 header 长度
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    // 创建内存空间，空间大小等于 header长度 + 主体长度 + 1，后面加1是因为需要追加 结束符，兼容 C 字符串
    sh = s_malloc(hdrlen+initlen+1);
    if (!init)
        // 初始化
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    // 主体内容 指针地址，相当于整个 SDS 结构体向后偏移了整个 header 长度
    s = (char*)sh+hdrlen;
    // flags 指针为 主体 SDS 内容向前偏移1位（这个上面我们已经解释过了）
    fp = ((unsigned char*)s)-1;
    // 根据 type 值进行 header 各个字段的初始化
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        // 字符串拷贝
        memcpy(s, init, initlen);
    // 兼容 C 函数，在 字符串后添加结束符
    s[initlen] = '\0';
    return s;
}

sdsMakeRoomFor() 容量扩展函数

/* sds.c: line 197 */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // 获取 s 剩余空间
    size_t avail = sdsavail(s);
    size_t len, newlen;
    // 获取原 type 值
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    /* Return ASAP if there is enough space left. */
    // 如果剩余空间 > 需要扩展的长度，则不用扩展
    if (avail >= addlen) return s;
    // 字符串长度
    len = sdslen(s);
    // sds 指针地址
    sh = (char*)s-sdsHdrSize(oldtype);
    // 新的 长度
    newlen = (len+addlen);
    // 如果 新的长度 没有达到 SDS_MAX_PREALLOC = 1024*1024，则 两倍长度得扩展，否则 扩展 一个 SDS_MAX_PREALLOC 长度
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    // 新的 type
    type = sdsReqType(newlen);
    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    // 空的字符串通常被创建成 type 8，因为 type 5 已经不实用了
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    // 获取 header 长度
    hdrlen = sdsHdrSize(type);
    // 如果跟原本 type 保持一致，则只需要 扩展空间，并且 主体内容指针地址变更
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        // 否则只能重新申请内存空间并 copy 字符串
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        // copy 字符串
        memcpy((char*)newsh+hdrlen, s, len+1);
        // 释放原结构
        s_free(sh);
        // 新的 sds 主体字符串地址
        s = (char*)newsh+hdrlen;
        // type 赋值
        s[-1] = type;
        // len 赋值
        sdssetlen(s, len);
    }
    // 更新 s 的 alloc 容量属性
    sdssetalloc(s, newlen);
    return s;
}

sdscatlen() 字符串连接函数

/* sds.c: line 386 */
sds sdscatlen(sds s, const void *t, size_t len) {
    // 当前长度
    size_t curlen = sdslen(s);
    // 扩容
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    // copy 字符串
    memcpy(s+curlen, t, len);
    // 重设 len 属性值
    sdssetlen(s, curlen+len);
    // 添加结尾符
    s[curlen+len] = '\0';
    return s;
}

除却上面比较典型的函数，实际还有一些其他常用的 SDS操作函数：

// 清空sds
sds sdsempty(void);
// 复制字符串
sds sdsdup(const sds s);
// 扩展字符串到指定长度
sds sdsgrowzero(sds s, size_t len);
// 字符串的复制
sds sdscpylen(sds s, const char *t, size_t len);
// 字符串的复制
sds sdscpy(sds s, const char *t);
//字符串格式化输出
sds sdscatfmt(sds s, char const *fmt, ...);
//字符串缩减
sds sdstrim(sds s, const char *cset); 
//字符串截取函数
void sdsrange(sds s, int start, int end);
//更新字符串最新的长度
void sdsupdatelen(sds s);
//字符串清空操作
void sdsclear(sds s);
//sds字符转小写表示
void sdstolower(sds s);
//sds字符统一转大写
void sdstoupper(sds s);
//以分隔符连接字符串子数组构成新的字符串
sds sdsjoin(char **argv, int argc, char *sep);

本文作者： wettper
本文链接： http://www.web-lovers.com/redis-source-sds.html
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！