Redis数据结构2：REDIS_STRING（SDS）

REDIS_STRING(SDS)

SDS全称Simple Dynamic String(简单动态字符串)，是专为Redis设计的简易字符串实现。

Redis并未采用C语言传统字符串char*，而是自己设计了一套字符串实现标准。

传统字符串的缺陷

C语言字符串实际上就是一个以'\0'结尾的字符数组。

例如：

char* myName = "ErickRen";

的结构即为：

该结构有个弊端，如果字符串内部有'\0'，则C语言会误认为该字符串结束。

这个限制使得传统C语言字符串只能保存文本数据，不能保存图片、音频、视频等的二进制数据。

此外，C语言标准库中字符串操作函数非常不安全，一不小心就会缓冲区溢出。

例如，当使用strcat("Erick", "Ren")函数拼接字符串时，C语言并不会检查该字符串是否有足够的空间，而是会直接操作。

而当C语言每次使用strlen()函数时，实际上是将字符串从头至尾遍历一遍，遇到'\0'为止，每次获取字符串长度的时间复杂度都是O(n)。

C语言的确实现了大部分的字符串函数，但这些函数风险太高，并不适合用来构建业务。

SDS

而为了业务开发，Redis作者构建了一套新的字符串标准，简称为SDS。

SDS一共有5个实现，都为sdshdr(Simple Dynamic Strings Header)系列，分别为sdshdr5, sdshdr8, sdshdr16, sdshdr32, sdshdr64：

/* 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[];
};

从注释信息来看，sdshdr5从未使用过，但**存疑**。不在本文讨论范围内。

除了sdshdr5之外，其他的结构都有四个共同结构：len, alloc, flags和buf[]。

结构分析

len

len存储了该SDS长度，在通过函数获取字符串长度时，可以直接返回该值，将时间复杂度优化到了O(1)。

alloc

alloc是分配给字符数组的空间长度，该变量是为了在修改字符串时，通过alloc - len来推导出剩余的空间大小，以判断是否需要扩容操作。alloc和通过alloc推导剩余空间大小是解决缓冲区溢出的根本。

flags

flags主要用来表示不同类型的SDS实现。即表明该字符串是上述五种实现的何种。

buf[]

buf[]是一个字符数组，用来保存实际数据。

用SDS标准实现的字符串，不会存在上述的缓冲区溢出问题，可以存储任意二进制数据并且获取字符串长度的时间复杂度为O(1)。

扩容机制

上面提到SDS不存在缓冲区溢出问题，这是因为SDS在数据量不足时会进行自动扩容。

当操作字符串时，通过公式alloc - len即可获取当前剩余空间，以判断是否要进行扩容。

hisds hi_sdsMakeRoomFor(hisds s, size_t addlen) {
    ... ...
    // s目前的剩余空间已足够，无需扩展，直接返回
    if (avail >= addlen)
        return s;
    //获取目前s的长度
    len = hi_sdslen(s);
    sh = (char *)s - hi_sdsHdrSize(oldtype);
    //扩展之后 s 至少需要的长度
    newlen = (len + addlen);
    //根据新长度，为s分配新空间所需要的大小
    if (newlen < HI_SDS_MAX_PREALLOC)
        //新长度<HI_SDS_MAX_PREALLOC 则分配所需空间*2的空间
        newlen *= 2;
    else
        //否则，分配长度为目前长度 + 1MB
        newlen += HI_SDS_MAX_PREALLOC;
       ...
}

如果该SDS小于1MB，那么就将它的容量翻倍。

如果该SDS大于1MB，那么每次扩容就为它的容量加上1MB。

不同实现的差异

前文提到，sdshdr中有flags存储sds的实现。

这五种实现的主要差异在len和alloc的数据类型。

例如sdshdr16和sdshdr32：

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[];
};

sdshdr16中的len和alloc都是uint16_t，长度和分配空间最多只有2¹⁶。

而sdshdr32为uint32_t，可以存储更多数据。

此举是为了能灵活保存不同大小的字符串，从而有效节省内存空间。比如，在保存小型字符串时，结构头占用空间会更少。

编译优化

sdshdr声明了 __attribute__ ((packed)) ，它是为了告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐。

以sdshdr8举例，如果不进行此优化，则实际的结构体大小为：

而进行了优化后，占用的内存即为：

节省了一部分内存空间。