SDS实现原理

在 Redis 中，SDS（Simple Dynamic String）是一种用于存储字符串的数据结构，是 Redis 为了解决 C 语言中字符串操作的一些问题而设计的，主要包括以下几个方面：

字符串长度计算问题：在 C 语言中，字符串是以 '\0' 结尾的字符数组，获取字符串长度需要遍历整个数组，直到遇到 '\0' 为止，这种方式效率较低。而 SDS 通过记录字符串的长度，能够在 O (1) 的时间复杂度内获取字符串的长度。
内存管理问题：C 语言中的字符串操作容易导致内存泄漏和缓冲区溢出等问题。因为 strcat 函数假定程序员在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立，就会发生缓冲区溢出将可能会造成程序运行终止。SDS 通过动态分配内存，可以自动扩展和收缩字符串的存储空间，避免了这些问题。
二进制安全问题：C 语言中的字符串只能存储文本数据，如果存储二进制数据，可能会因为其中的 '\0' 字符被误判为字符串的结束，导致数据丢失。SDS 可以存储任意二进制数据，保证了数据的完整性。

原理及源码

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

解释如下：

len，记录了字符串长度
alloc，分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出的问题。
flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64
buf[]，字符数组，用来保存实际数据

内存空间设计

Redis 一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。

它们数据结构中的 len 和 alloc 成员变量的数据类型不同。

例如：sdshdr16使用uint16_t，表示长度和空间不能超过 $2^16$

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

SDS 设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。比如，在保存小字符串时，结构头占用空间也比较少。

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

编译对齐，例如下面的结构体，实际会使用8个字节，：
struct test1 {
    char a;
    int b;
 } test1;
优点：

提高性能：对齐的数据可以提高内存访问的效率，尤其是对于现代计算机体系结构来说，对齐的内存访问通常更快，因为它可以减少内存访问的次数和延迟。

兼容性：某些硬件或操作系统可能对数据的对齐有要求，如果数据没有正确对齐，可能会导致运行时错误或性能下降。通过编译对齐，可以确保程序在不同的平台上具有更好的兼容性。

简化代码：对齐可以使数据结构在内存中更加规整，从而简化代码的编写和维护。例如，在处理数组或结构体时，对齐可以确保每个元素或成员都按照相同的方式进行访问。

缺点：

内存浪费：为了实现对齐，可能会在数据结构中添加一些填充字节，这会导致内存的浪费。特别是在处理小数据结构或数据元素大小不一致的情况时，浪费的内存可能会比较明显。

增加编译时间：编译对齐可能需要额外的计算和处理，这可能会增加编译的时间和复杂度。

灵活性受限：对齐可能会限制数据结构的布局和设计，使得在某些情况下难以实现最优的内存布局。

SDS扩容

如果长度小于最大预分配长度，扩容为两倍
否则，每次扩容加上最大预分配长度

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) { // 扩展sds字符串末尾的空闲空间，以便调用者在调用此函数后可以覆盖字符串末尾后的addlen字节，再加上一个空终止符。
    void *sh, *newsh; // 定义两个指针变量sh和newsh
    size_t avail = sdsavail(s); // 获取sds字符串的可用空间
    size_t len, newlen; // 定义两个变量len和newlen
    char type, oldtype = s[-1] & SDS_TYPE_MASK; // 获取sds字符串的类型
    int hdrlen; // 定义一个变量hdrlen

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s; // 如果有足够的空间，立即返回s

    len = sdslen(s); // 获取sds字符串的长度
    sh = (char*)s-sdsHdrSize(oldtype); // 获取sds字符串的头部指针
    newlen = (len+addlen); // 计算新的长度
    if (newlen < SDS_MAX_PREALLOC) // 如果新的长度小于最大预分配长度
        newlen *= 2; // 将新的长度乘以2
    else
        newlen += SDS_MAX_PREALLOC; // 否则，将新的长度加上最大预分配长度

    type = sdsReqType(newlen); // 获取新的sds字符串类型

    /* 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. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8; // 如果类型是5，将其改为8

    hdrlen = sdsHdrSize(type); // 获取新的头部长度
    if (oldtype==type) { // 如果旧类型和新类型相同
        newsh = s_realloc(sh, hdrlen+newlen+1); // 重新分配内存
        if (newsh == NULL) { // 如果分配失败
            s_free(sh); // 释放旧内存
            return NULL; // 返回NULL
        }
        s = (char*)newsh+hdrlen; // 更新s指针
    } 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; // 如果分配失败，返回NULL
        memcpy((char*)newsh+hdrlen, s, len+1); // 复制旧数据到新内存
        s_free(sh); // 释放旧内存
        s = (char*)newsh+hdrlen; // 更新s指针
        s[-1] = type; // 更新类型
        sdssetlen(s, len); // 设置sds字符串长度
    }
    sdssetalloc(s, newlen); // 设置sds字符串的分配长度
    return s; // 返回s
}

参考资料

小林Coding SDS

SDS实现原理

原理及源码​

内存空间设计​

SDS扩容​

参考资料​

原理及源码

内存空间设计

SDS扩容

参考资料