希望大家都可以去真的阅读源码，去了解第一手知识。而不是只去看各个公众号抄来抄去的几篇文章，有的甚至还是错的。

^_^

感慨一下，最近面试的时候怎么那么多人说 mysql 中的幻读问题是使用 mvcc 解决的？

sds 字符串：名字叫简单动态字符串，但是他可一点也不 simple 。如果你只知道他可以动态扩容，那可就差的太远啦。

动态对象头

首先，sds 对象头定义以及字符串基本函数的实现都在 sds.h 头文件中。一共定义了 5 种 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__)) 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[];
};
复制代码

其中，根据注释来看 sdshdr5 是没有被使用的，我们忽略。

另外几种结构体类型，仅有表示长度的 len 和记录已分配内存的 alloc 的类型长度不同。

取消字节对齐

再着，注意到了结构体上的 __attribute__ ((__packed__)) 修饰，该关键字的作用是取消字节对齐。

为了验证，我写了如下一个小代码：

struct packed_test_a
{
    char i;        
    uint32_t j; 
};
struct __attribute__ ((__packed__)) packed_test_b
{
    char i;        
    uint32_t j; 
};
...

    struct packed_test_a a;
    struct packed_test_b b;

    a.i = 'a';
    b.i = 'b';

    a.j = 1u;
    b.j = 2u;
    printf("%d \n",sizeof(a));    //5
    printf("%d \n",sizeof(b));    //8

复制代码

只是看 sizeof 还是不够，我们再使用 gdb 调试一下：

1 先将断点打在第一个 printf 的位置，使用 r 命令运行至断点处 （第 37 行）。

Thread 2 hit Breakpoint 1, main (argc=1, argv=0x7ffeefbff7d8)
    at packed_test.c:37
37	    printf("%d \n",sizeof(a));
复制代码

2 查看变量 a 处的内存，使用 x/24xb &a

0x7ffeefbff798:	0x61	0x01	0x00	0x00	0x00	0x00	0x00	0x00
...
复制代码

3 查看变量 b 处的内存，使用 x/24xb &b

0x7ffeefbff790:	0x62	0x00	0x00	0x00	0x02	0x00	0x00	0x00
...
复制代码

这样，我们可以很明显的看出，在添加了 __attribute__ ((__packed__)) 修饰的变量 a 上，数据a.i = 0x61 与 a.j = 0x01 在内存中是连续存储的。

而，变量 b 中，b.i = 0x62 与 b.j = 0x02 中间被填充了 3 个字节的 0x00数据用于对齐。

根据长度选择合适的对象头

创建

先看一下创建 sds 字符串的函数：sdsnewlen。

函数签名如下：

sds sdsnewlen(const void *init, size_t initlen) 
复制代码

• 第一步，使用s_malloc分配足够的内存。即对象头长度 + 字符串初始长度 + 1(C语言字符串结束符占位)。

    sh = s_malloc(hdrlen+initlen+1);
复制代码

• 第二步，初始化分配的内存，使用 memset 批量设零值。

• 第三步，设置变量指针s,fp。

    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
复制代码

这里，剧透一下：*fp 指向的是 *s-1 的位置。其中 *s 指向的是数据区的起始地址，结合存储结构来看的话，*s-1 其实就是 sds.flags。

• 第四步，根据类型设置对象头属性：

    switch(type) {
        ...
            case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
       ...
    }
复制代码

• 第五步，数据区设置初始值

    memcpy(s, init, initlen);
复制代码

• 最后，收尾工作

    s[initlen] = '\0';
    return s;
复制代码

注意：这里实际返回的指针为 *s 。也就是 sds 字符串数据区的起始地址。

扩容

扩容这里我们直接看 sdsMakeRoomFor 函数。

当其小于 1MB 时，每次容量直接 *2 ，否则每次扩容 1MB。嗯 就是出自这里。

    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
复制代码

随后，会判断原对象头与扩容后的对象头是否一致，来决定是直接扩，还是…换头？

    hdrlen = sdsHdrSize(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 */
        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);
    }
复制代码

多亏了 redis 的单线程模型，代码也极其简单：分配足够的长度，并将原内存拷贝并释放即可。

缩容

和扩容是一样的，函数见 sdsRemoveFreeSpace。

值得注意的是，缩容函数是把 sds 中尚未分配的空间还回去。字符串本身的值并不会发生变化。

    /* If the type is the same, or at least a large enough type is still
     * required, we just realloc(), letting the allocator to do the copy
     * only if really needed. Otherwise if the change is huge, we manually
     * reallocate the string to use the different header type. */
    if (oldtype==type || type > SDS_TYPE_8) {
        newsh = s_realloc(sh, oldhdrlen+len+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+oldhdrlen;
    } 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);
    }
复制代码

原类型与目标类型相同，或原类型在 sdshdr8 之上时，并不做类型的替换，只是重新使用 s_realloc 重新分配一个恰好的容量使用。

有没有注意到代码中存在一个 s[-1] ? 数组下标还能是负数？很奇怪对吧 稍等~

存储结构

看了 sds 字符串的结构体定义，我们就可以将其在内存中的存储结构画出来（我们以sdshdr8为例）：

除 sdshdr5 之外，其余 4 种的存储结构都是一样的。

注意一下，正是因为上面在结构体上加了 __attribute__ ((__packed__)) 修饰，这里才可以确定 len,alloc,flags,*buf 这些属性在内存中一定是紧凑连接的。

代码中的那些’骚’操作

负数数组下标

如果仔细看代码的话，会发现存在着大量这样的写法：

    unsigned char flags = s[-1];
复制代码

在某些语言中，数组下标为负数时表示的是访问倒数第几个元素。但是，作为鄙视链的顶端，C 语言可就不一样了~

C 语言中，数组其实就是一个指针，s[-1] 的效果其实和 *s-1 是一样的。

所以，这样我们就可以知道，s[-1] 访问的就是结构体中的 flags 属性。

那么，为什么要这样使用呢？

因为已经看过了创建 sds 的函数。我们知道创建完成后，暴露给外界的指针指向的仅仅是数据区的位置，也就是*buf这个属性。

那么，先看这个问题：为什么直接返回的只有数据区地址，而不是整个 sds 头部地址

• *buf就是一个原生的 C 语言数组，stl 中提供的所有字符串相关函数都可以直接对其使用。
• sds 头是动态的，仅仅一个 sds 头部地址的话，因为不知道当前数据是怎么分布的，无法访问任何属性。

这样，如果我们返回的指针指向 flags 与 *buf 中间的地址。

因为我们知道flags是定长的，前移一个 char 的位置就可以完整的取到整个 flags 数据。而一但有了 flags 我们就可以知道对象头中的数据分布，进而来访问其他 len,alloc 属性。

编译器预处理宏

现在让我们看一下在已经有 *s 指针以及flags后，如何取到头中的其他字段。

如何还是继续使用负数下标：-(1+1)，-(1+1+1) 这样，那真的是完全没有可读性。

我们看一下取 len 字段的方法：

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
       ...
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}
复制代码

可以看到，针对不同的类型(除SDS_TYPE_5)，都使用了同一个SDS_HDR宏，只是第一个参数不一样。

来看一下他的宏定义：

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
复制代码

只有短短一行代码，其中有一个这样的符号 ##：也是属于预处理宏的一种，两个井号被称为连接符，会将两个 token 连接为一个。

举例来说，SDS_HDR(8,s) 在被编译器预处理后，就会变成下面这样：

((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))
复制代码

是不是很神奇？宏参数也变成了代码本身的一部分。

那么，我们再看一下这段代码做了什么：

首先，后半部分：参数 s 为数据区起始指针，将指针减去 sizeof(struct sdshdr8) ，回想下 sds 的存储结构：那不就是将指针移动到 sds 的头部位置吗~

然后，前半部分：就是一个强制类型转换，因为我们已经得到了 sds 的头部指针，那么只需要强制转换一下，后面就可以任意发挥啦。

总结

简单动态字符串：作为 redis 中出镜率最高的一种数据结构，他可是一点都不简单。不仅仅是长度实现了动态扩容，为了把空间使用到极致，就连头部也做到了动态扩容。

并且，头部中还额外存储了当前字符串的长度，好处也很明显：虽然 *buf 指向的是一个标准 C 语言字符串，但对其使用 strlen 函数求长度也不得不遍历整个字符串。

如果额外储存的话，就完全不一样了。

而且，也多亏了 redis 的单线程，让本来很复杂的操作，变得异常简单。