Redis源码解读之SDS详解

我们知道redis是用C语言开发的，源代码开源（小伙伴们可以去网上下载下来进行阅读）今天我们主要看的是SDS(Simple dynamic string) ,它是redis字符串类型的底层实现。

1. 什么是SDS(源文件sds.h/sds.c)

看下源代码的定义

typedef char *sds;

从此段代码可以看出sds是char类型的指针。

我们知道C语言中的字符串是用char[]数组来表示的，并且数组的最后一个是以'\0'结尾的，那redis里面也保留了这部分的特性，但是redis的字符串是二进制安全的，另外字符串的中间可以包含'\0' 字符，（C语言字符必须符合某种编码 比如ASCII，并且除了字符串的末尾之外，字符串里面不能包含空字符），因为在sds的头部保存了字符串的长度，不再是根据'\0' 这个符号去判断字符串是否结束。
注：二进制安全简单来说就是我们保存的数据，比如字符串,不会因为一些操作出现损坏,比如一个字符串中包含'\0'，那我们的C语言在读取的时候就不会读取'\0'后面的字符，因为它在读取字符串的时候当它读到''字符时认为字符串已经结束，比如：" hello'\0'world",那最终读到的会是hello。

2.Redis中的几种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. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
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[];
};
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[];
};
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[];
};
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[];
};

这里展示了5种sds,这些其实是字符串的头（header），真正的字符串是保存在buf中的，那为啥会有5中不同的类型呢？那是因为redis会根据字符串的长度使用不同的header头，从而达到内存优化的目的,下面列举下不同的使用场景：
a. 当字符串的长度小于 2^5 且不为空的字符串的时候使用的是sdshdr5 ；
b. 当字符串的长度大于等于2^5 小于 2^8 或者字符串为空的时候使用sdshdr8；
c. 当字符串的长度大于等于2^8 小于 2^16时候使用sdshdr16；
d. 当字符串的长度大于等于2^16 小于 2^32并且系统是64位的时候使用sdshdr32；
f. 其他的情况使用sdshdr64；
接下来我们具体看下sds header 头里面的字段，我们发现除了sdshdr5外其他的类型结构是一样的，那下面我先来简单介绍下除sdshdr5外的4中类型中的字段

1. len; //sds 字符串的实际长度.
2. alloc; //分配给字符串的总容量，这个容量是不包含header和'\0'字符的容量，初始化的时候这个值和sds长度是一样的，当有修改的时候往往会分配大于实际需要用到的长度.
3. flags;// 类型的标志，用一个字节的低3位保存，主要有 SDS_TYPE_5，SDS_TYPE_8，SDS_TYPE_16，SDS_TYPE_32，SDS_TYPE_64 这几种类型，它们分别数字对应0,1,2,3,4.
4. buf[];// 字符数组

那sdshdr5里面的字段又表示什么意思呢？再次贴上源代码

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

我们发现它只有flags 和bufs[] 两个字段，下面来分别解释下

1. flags;// 低三位保存类型，高5位保存字符串的长度，也就是相比其他几种类型sdshdr5把类型和字符串的长度保存在了一个字段。
2. char buf[] ; //这个和其他类型是一样的，这里不再赘叙。
   注：大家不要被Note: sdshdr5 is never used 这句英文给误导，其实sdshdr5 是有使用的。

下面我用一张图来大致展示下sds的结构

sds.png
我这里简单的展示了下sdshdr8 这种类型，其他的类型就不展示了，细心的小伙伴可以注意到图中的alloc的长度是大于字符串的实际长度的的，那这是为啥呢？接下来向大家介绍下字符串这种类型的内存分配问题。

3. SDS内存分配和释放

当字符串发生修改时就需要给字符串分配或者释放一些空间，我们先看下内存的分配规则。

1. 初始的alloc的值和字符串的实际长度大小是一样的。
2. 当字符串发生修改的时候，比如追加字符，这个时候有三种情况：
   a. 当alloc的空闲空间足够时不进行操作。
   b. alloc空闲空间不足时并且新的字符串的长度(newlen)小于1M的时候，redis会分配2倍新的字符串的长度(2*newlen)给alloc,等于说buf数组一般时空闲的。
   c. 当新的字符串长度大于1M,那这个时候redis会分配newlen+1M的空间给alloc。
   以上具体的源代码片段如下：

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;

我们再接着来看下内存释放的规则：
比如我们要去掉字符串中的某些字符串，这个时候多余的空间并没有被释放，redis只是将需要去掉的字符串去掉，修改下len的长度，而不会去修改alloc的长度大小，当然与此同时redis还提供了释放内存的API,可以到真正需要释放内存的时候再释放。
比如清空字符串函数：

void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

这个函数并没有去修改alloc的值，也就是它不会去释放一些内存。
我们知道redis是用C语言去实现的，接下来像大家简单介绍下redis字符串(sds)和C字符串的区别。

4. SDS与C字符串的区别

1. C字符串没有头信息，不能直接获取字符串的长度，获取字符串的长度需要遍历，时间复杂度为O(n)，sds字符串获取字符串的长度为O(1),速度大大提升。
2. 内存分配的方式不一样，在C语言中它是每次追加或者缩短字符串都会发生内存的分配和释放，但是redis就不一样，当追加字符串时它会一次分配大于实际字符串的长度大小，当下次还要追加的时候就不需要再次分配内存了；当缩短字符串的时候不会立马释放多余的空间，以防后面再此使用，还有一点就是C中的内存分配和释放都是手动操作的，如果忘记分配或者释放的话会造成一定的后果，sds内存的分配和释放是自动的，不需要我们自己操作，减少了错误发生。
3. 二进制安全，redis可以存储任何形式的字符串，包括二进制，但是C对字符串有一定的要求，比如字符串中间不能包含'\0'（空）字符。
4. 还有一点就是sds字符串保留了一些C字符串的特性，比如字符串的末尾的字符是\0,这使得sds 字符串可以使用某些C字符串的API,从而避免的重复造轮子。
5. 有小伙伴看到这里可能会说怎么都是优点讷，难道没有缺点吗？目前本人还未发现，如果要说缺点的话可能就是需要多维护一个sds header (头)，需要一定的维护成本吧，当然这个是我们redis去做的，对用户来说是透明的。

5. 常用的API

(1) sds sdsnew(const char *init);//创建一个包含给定C字符串的SDS
/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

(2) sds sdsempty(void);//创建一个空的字符串
/* Create an empty (zero length) sds string. Even in this case the string
 * always has an implicit null term. */
sds sdsempty(void) {
    return sdsnewlen("",0);
}

(3) sds sdsdup(const sds s);// 创建sds副本
/* Duplicate an sds string. */
sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}

(4) void sdsfree(sds s);//释放给定的sds
/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}
(5) sds sdsgrowzero(sds s, size_t len);//使用空字符将给定的sds扩展至给定的长度
/* Grow the sds to have the specified length. Bytes that were not part of
 * the original length of the sds will be set to zero.
 *
 * if the specified length is smaller than the current length, no operation
 * is performed. */
sds sdsgrowzero(sds s, size_t len) {
    size_t curlen = sdslen(s);

    if (len <= curlen) return s;
    s = sdsMakeRoomFor(s,len-curlen);
    if (s == NULL) return NULL;

    /* Make sure added region doesn't contain garbage */
    memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
    sdssetlen(s, len);
    return s;
}

(6) sds sdscat(sds s, const char *t);//将指定的C字符串添加到sds 字符串s 的末尾
/* Append the specified null termianted C string to the sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

(7) sds sdscatsds(sds s, const sds t);//将一个sds添加到另外一个sds的末尾
/* Append the specified sds 't' to the existing sds 's'.
 *
 * After the call, the modified sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}
(8)sds sdscpy(sds s, const char *t);//将给定的C字符串复制到sds里面，覆盖原来的sds 字符串

/* Like sdscpylen() but 't' must be a null-termined string so that the length
 * of the string is obtained with strlen(). */
sds sdscpy(sds s, const char *t) {
    return sdscpylen(s, t, strlen(t));
}

/* Destructively modify the sds string 's' to hold the specified binary
 * safe string pointed by 't' of length 'len' bytes. */
sds sdscpylen(sds s, const char *t, size_t len) {
    if (sdsalloc(s) < len) {
        s = sdsMakeRoomFor(s,len-sdslen(s));
        if (s == NULL) return NULL;
    }
    memcpy(s, t, len);
    s[len] = '\0';
    sdssetlen(s, len);
    return s;
}

暂时写到这里，如有需要补充的地方，欢迎小伙伴在下面留言。