原创

redis数据结构-SDS

温馨提示:
本文最后更新于 2023年02月03日,已超过 393 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

sds

在redis中,存储字符串的结构称为 sds (Simple Dynamic String) 简单动态字符串

在源码sds.h中定义如下:

typedef char *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__)) 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其实只是一个char 的一个别名,实现sds的完整数据结构包括了 sdshdr\ 的结构

attribute ((packed))

这个语法是gcc编译器的特有的语法,表示结构体将不使用内存对齐技术,而是使用紧凑模式存储结构体,例如:

#include<stdio.h>
#include<stdlib.h>
#include <string.h>

struct Test1 {
    char a;//1
    uint8_t b;//1
    uint32_t c;//4
    uint64_t d;//8
};
struct __attribute__ ((__packed__))  Test2 {
    char a;//1
    uint8_t b;//1
    uint32_t c;//4
    uint64_t d;//8
};

int main() {
    printf("%ld\n", sizeof(struct Test1));//16
    printf("%ld\n", sizeof(struct Test2));//14
    return 0;
}

在这个例子中,内存存储为:
file

在Test1 中,最大的直接为unit64 占用8字节,为了内存对齐,则会额外分配一个新的8字节,用于存储其他属性,其他属性如果存的下就存,存不下就开辟新的8字节,用于内存对齐
file
而在Test2中,使用了紧凑模式,字节数等于成员占用内存数,节省了一部分内存

sds存储结构

在sds中,8的存储结构如下:

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

如图:
file

可以看到,sdshdr8的内存地址,包含了len,alloc,flags,buff则存储了sds的指针和字符串数据,那么可以发现,sds指针-1的位置,是flag

unsigned char flags = s[-1];

flags低三位表示类型,通过flags能知道具体存储的类型:

    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }

通过类型,可以知道前面的结构体的类型,从而知道结构体的长度,sds的指针位置-结构体长度=sdshdr的指针位置:

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

这样,我们就知道了sds和sdshdr之间的关系

创建字符串

申请长度为 sdshdr结构体长度+字符串长度+1的内存空间,为什么需要+1呢?因为存储字符串时,会额外存储 "\0"用于结尾:

    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);

这样,sds字符串的指针位置,就等于 sdshdr指针+sdshdr长度

    s = (char*)sh+hdrlen;

最后,通过memcpy,将字符串的值复制到sds的上,加上\0,就完成了

    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';

动态扩容字符串

当需要动态扩容字符串时,先计算新的长度数量,贪婪模式下,将扩充为2倍:

    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC;
    }

计算新长度需要使用的sdshdr结构体类型,判断旧结构体类型是否一致

如果类型一致,则只需要额外分配新的内存空间即可

    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    }

如果不一致,则需要类似于新增的逻辑,重新分配一块新的内存空间,将旧数据拷贝到新空间中

  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;
        s[-1] = type;
        sdssetlen(s, len);
正文到此结束
本文目录