Redis研究院(1)——SDS

Redis数据库里面，包含字符串值的键值对底层都是由SDS来实现的，比如说：

127.0.0.1:6379> set sunshine my
OK
127.0.0.1:6379> append sunshine " sunshine"
(integer) 11

SDS数据结构定义

C语言中，字符串是以\0字符结尾的字符数组来存储的，通常表达为字符指针的形式char *，所以它不允许\0出现在字符串中间，因此它没有很好的办法存储二进制数据。

而sds的定义与C字符串类似，redis/src/sds.h：

typedef char *sds;

SDS和传统C语言字符串保持类型兼容，也就是说，当我们需要一个C语言字符串的地方，也可以传入一个SDS。

但是SDS和char * 并不等同。SDS是二进制安全的，它可以存储任意二进制数据。

所以SDS不能只是简单的只用\0来结束字符串，作为高级对象，SDS还包含一个header结构：

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc;
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc;
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;
    uint64_t alloc;
    unsigned char flags;
    char buf[];
};

这几种类型的header主要包括字符串长度len，最大容量alloc和flags和一个字符数组。

flags会占用一个字节进行一些标识，它会用最低的3个bit表示header的类型，类型定义如下：

#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数据结构如下所示：

而我们读取sds的时候，会直接从字符数组开始读取数据，其他属性是如何定位到的呢？

• 当指针在字符起始位置时，我们可以向低地址方向偏移1字节，得到flags标识位数据。
• 通过flags标识位数据我们可以获得SDS的类型。
• 通过SDS类型，我们可以获取字符串长度，最大容量等信息（sdshdr5除外）。

SDS和C字符串的区别

获取字符串长度时间复杂度为常数

在C语言的字符串中，是不会记录长度等信息的，当我们需要获取一个C字符串的长度时，一般需要遍历整个字符串，时间复杂度是0(n)。

但是在SDS中，由于header中会存储字符串的长度，所以SDS获取字符串长度的时间复杂度是0(1)。在我们需要字符串长度时，获取对应类header的len属性即可，比如上面的字符串，长度就是7。

杜绝缓冲区溢出

C字符串不记录自身长度还可能会造成缓冲区溢出。比如我我们需要向”my”字符串后面追加” sunshine”字符串，如果我们没有分配足够多的内存，那么情况很可能是这样的：

而SDS的空间分配策略完全杜绝了缓冲区溢出的可能性。当需要对SDS进行修改时，会首先检查SDS的空间是否满足修改的需求，如果不满足的话，SDS空间会进行扩容，然后才执行实际的修改。

减少修改字符串带来的内存重分配次数

SDS通过使用未使用空间解除了字符串长度和底层数组大小直接的关联，也就是字符串长度很可能不等于底层数组大小。

通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

在对SDS进行修改时，程序不仅会为SDS分配修改时需要的空间，还会为其申请一块预留空间，我们来看下具体实现：

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    if (avail >= addlen) return s;
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    type = sdsReqType(newlen);
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

具体规则解释如下：

• 首先根据alloc计算可用容量，如果可用容量大于需求容量，直接返回这个SDS对象。
• 如果需要扩容，并且新长度小于SDS_MAX_PREALLOC（目前是1MB），那么按照增加后的长度扩容一倍。
• 如果需要扩容，并且新长度大于SDS_MAX_PREALLOC（目前是1MB），那么按照增加后的长度再扩容1MB容量。
• 接下来就是header扩容，不同的header有不同的范围。

通过这种预分配策略，SDS执行N次修改时，最多需要N次扩容。

惰性空间释放

当SDS执行缩短字符串长度的操作时，程序并不会立即执行内存空间回收操作，剩余的空闲空间将会暂时保留，供下次字符串操作使用：

sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;
    sp = start = s;
    ep = end = s+sdslen(s)-1;
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    if (s != sp) memmove(s, sp, len);
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
}

trim()类型在java里面很常见，意义在于减少字符串的长度，减少字符串长度后，势必会有空闲空间，但是SDS并没有立即回收空闲空间，而只是将header的长度进行了下变更。

空闲空间并不是一直不会回收，redis也有回收空间的方法：

sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    type = sdsReqType(len);
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+len+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        newsh = s_malloc(hdrlen+len+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, len);
    return s;
}

最后调用的sdssetalloc()方法，就是根据计算的len，回收空闲空间。

总结

根据介绍，我们可以总结一下C字符串和SDS字符串之间的区别：