Redis源码分析SDS

克虏伯

发布于 2023-11-05 08:27:47

2190

发布于 2023-11-05 08:27:47

[Redis 源码解析 1：字符串 SDS ]

Redis 中字符串都用自定义的结构**简单动态字符串(Simple Dynamic Strings，SDS)，而不是C语言的字符串。 Redis 中使用到的字符串都是用 SDS，例如 key、string 类型的值、sorted set 的 member、hash 的 field 等等等等

数据结构

旧版本的结构

在 3.2 版本之前，sds 的定义是这样的：

`
struct sdshdr {
// buf 数组中已使用的字节数量，也就是 sds 本身的字符串长度

unsigned int len;

// buf 数组中未使用的字节数量

unsigned int free;

// 字节数组，用于保存字符串

char buf[];
};
`

缺点：

len 和 free 的定义用了 4 个字节，可以表示 2^32 的长度。但是我们实际使用的字符串，往往没有那么长。4 个字节造成了浪费。

新版本的结构

旧版本中我们说到，len 和 free 的缺点是用了太长的变量，新版本解决了这个问题。我们来看一下新版本的 SDS 结构。

在 Redis 3.2 版本之后，Redis 将 SDS 划分为 5 种类型：

类型	字节	位
sdshdr5	< 1	<8
sdshdr8	1	8
sdshdr16	2	16
sdshdr32	4	32
sdshdr64	8	64

新版本新增加了一个 flags 字段来标识类型，长度 1 字节(8 位)。类型只占用了前 3 位。在 sdshdr5 中，后 5 位用来保存字符串的长度。其他类型后 5 位没有用。

`
struct attribute ((packed)) sdshdr5 {
unsigned char flags; /* 前 3 位保存类型，后 5 位保存字符串长度 */

char buf[];
};

struct attribute ((packed)) sdshdr8 {
uint8_t len; /* 字符串长度，1 字节 8 位 */

uint8_t alloc; /* 申请的总长度，1 字节 8 位 */

unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */

char buf[];
};
struct attribute ((packed)) sdshdr16 {
uint16_t len; /* 字符串长度，2 字节 16 位 */

uint16_t alloc; /* 申请的总长度，2 字节 16 位 */

unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */

char buf[];
};
struct attribute ((packed)) sdshdr32 {
uint32_t len; /* 字符串长度，4 字节 32 位 */

uint32_t alloc; /* 申请的总长度，4 字节 32 位 */

unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */

char buf[];
};
struct attribute ((packed)) sdshdr64 {
uint64_t len; /* 字符串长度，8 字节 64 位 */

uint64_t alloc; /* 申请的总长度，8 字节 64 位 */

unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */

char buf[];
};

优点：

旧版本相对于传统 C 字符串的优点，新版本都有
相对于旧版本，新版本可以通过字符串的长度，选择不同的结构，可以节约内存
使用 __attribute__ ((__packed__)) ，让编译器取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐，可以节约内存

SDS的初始化

SDS的初始化如下，开始创建时SDS分配的buf空间大小与字符串长度一致

/* Create a new sds string starting from a null terminated C string. */
//使用C语言字符串创建SDS
sds sdsnew(const char *init) {
    //获取字符串长度
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sds sdsnewlen(const void *init, size_t initlen) {
    return _sdsnewlen(init, initlen, 0);
}

//真正创建SDS
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    //根据字符串长度获取sds类型
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    //// 根据类型获取 struct sdshdr 的长度
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    //根据长度分配hdrlen+inilen+1长度的空间，+1 是为了最后一个的结束符号 \0
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        //清空sh的内存
        memset(sh, 0, hdrlen+initlen+1);
    // s 指向了 buf 开始的地址
    // 从上面结构可以看出，内存地址的顺序： len, alloc, flag, buf
    // 因为 buf 本身不占用空间，hdrlen 实际上就是结构的头(len、alloc、flags)
    s = (char*)sh+hdrlen;
    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);
            //设置len长度
            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;
        }
    }
    // 如果 init 非空，则把 init 字符串赋值给 s，实际上也是 buf 的初始化
    //把字符串拷贝到SDS分配的内存地址
    if (initlen && init)
        memcpy(s, init, initlen);
    //最后加一个结束标志 \0
    s[initlen] = '\0';
    return s;
}

SDS 的扩/缩容

扩容

sds sdsMakeRoomFor(sds s, size_t addlen) {
    return _sdsMakeRoomFor(s, addlen, 1);
}

/* Unlike sdsMakeRoomFor(), this one just grows to the necessary size. */
sds sdsMakeRoomForNonGreedy(sds s, size_t addlen) {
    return _sdsMakeRoomFor(s, addlen, 0);
}

//若SDS s的剩余存储空间还够存储addlen长度的字符，则直接返回旧s，否则创建新的SDS返回
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    // 获取 s 目前的空余空间长度
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    //如果剩余空间还够再存储addlen长度的字符串
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    //sds的len+addlen的长度
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {
        //小于1M，长度是新len的俩倍
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
        //否则，最多再额外申请1M
            newlen += SDS_MAX_PREALLOC;
    }

    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 */
        //否则需要重新malloc一整块空间，然后拷贝
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        //将旧SDS的数据拷贝到新的SDS中
        memcpy((char*)newsh+hdrlen, s, len+1);
        //释放旧的SDS
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        //设置len
        sdssetlen(s, len);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}