redis7.x源码分析:(1) sds动态字符串

sds(Simple Dynamic String)是redis中最基础也是最重要的数据结构之一，其内部使用的key、协议、回复等等都会用它来存储。sds主要设计被用来替代C原生字符串 char *（数组），以便更便捷、更高效、更安全的进行字符串操作管理。其实它和C++标准库中的string在一定程度上是比较类似的，都是用来完成对字符串缓冲区的动态分配、管理以及其它一些相应操作的。

// sds的定义：
typedef char *sds;

sds的定义非常简单，直接就是一个char*的别名，因此sds本身具备C字符串的特性，可以使用strcpy、strlen等函数。
sds相关数据结构中真正重要的是sdshdr的定义，最初老版本的定义如下：

struct sdshdr {
    int len;    // SDS字符串的长度
    int free;   // 未使用的空间大小
    char buf[]; // 字符串数据
};

现在的sdshdr已经重新定义成5个不同的结构了：

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

#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

这么定义的主要目的是节省存储空间，针对不同的字符串长度使用不同的头。另外结构中新增了flags标记，用来表示使用的是哪个头。如果flags类型是SDS_TYPE_5则高5bit还表示数据长度，因为sdshdr5中并没有长度的成员定义。
sds在分配空间时，是包含头结构的，但真正返回的却是buf成员的地址，这就是sds具备C字符串的特性的原因。由于结构体中设置了 attribute((packed))，表示按单字节对齐，因此可以通过sds[- 1]来获取flags的值，而后获取对应的结构体指针。

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

// 获取SDS_TYPE_16对应的结构体指针
struct sdshdr16 *hdr = SDS_HDR(16,s)

接下来先看一下sds分配释放的主要实现 _sdsnewlen和 sdsfree，对外提供的分配函数最终都会调用它来实现。

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    // 根据数据长度获取合适的结构体类型
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    // inilen为0时, 升级类型预留空间
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    size_t usable;

    // 分配: 头 + 数据长度 + 1的空间
    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    // init不为空并且不是SDS_NOINIT, 则重置内存为0
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    // 对外返回的 sds 指针位置, 向后偏移头大小
    s = (char*)sh+hdrlen;
    // 存储flags的指针位置
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    // 根据类型,设置结构体中相应的值
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    // 拷贝需要初始化的内容
    if (initlen && init)
        memcpy(s, init, initlen);
    // buf末尾赋0
    s[initlen] = '\0';
    return s;
}

......

void sdsfree(sds s) {
    if (s == NULL) return;
    // 释放时,需要把指针重定向到相应结构体的起始位置
    s_free((char*)s-sdsHdrSize(s[-1]));
}

下面再看下扩容的函数 _sdsMakeRoomFor，它的实现也非常清晰，内部的一些扩容操作都会调用它。

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    // 获取剩余空间大小
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    // 获取当前type
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    // 空间够用则直接退出
    if (avail >= addlen) return s;

    len = sdslen(s);
    // 获取sds结构体分配内存的起始地址
    sh = (char*)s-sdsHdrSize(oldtype);
    // 新的需要分配的空间大小
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {
        // greedy为1时需要预留空间, 如果新分配空间小于1MB, 则分配空间调整为2倍大小; 如果大于1MB则分配成 + 1MB大小
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }

    // 按新长度获取新的type
    type = sdsReqType(newlen);

    /* 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;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        // 如果类型不变,则直接按照新大小realloc
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        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_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        // 设置flags
        s[-1] = type;
        // 设置新的长度
        sdssetlen(s, len);
    }
    // 设置可用空间大小
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}

另外，sds在设计中本身也是二进制安全的，而且sds会在末尾多分配1字节并且置’\0’，用于防止一些字符串操作的越界问题。因此它除了用作字符串外，还可以作为二进制数据的存储buf，在redis内部也有着广泛用途。