本文使用的paddingRedis5.0源码概述-本文源码

Redis 5.0 本文用到的源码

概览

我最近正在通过 Redis 学习 C 语言。不得不说Redis的代码真的是很整洁。本文将对Redis数据结构字符串的源码实现进行全面深入的讲解,希望大家能从中有所收获。

Redis的字符串源码主要放在sds.c和sds.h这两个文件中。具体实现已被剥离到一个单独的库中:.

Redis的动态字符串结构如下图所示:

SDS大致由header和data segment两部分组成,其中header还包含len、alloc和flags 3个字段。 len代表数据长度,alloc代表分配的内存长度,flags代表sds的数据类型。

在以前的版本中,sds header实际上占用了固定的8字节大小,所以如果所有小字符串都存储在redis中,sds header会占用大量内存空间。

但是随着sds版本的变化,在内存使用方面做了一些优化:

在 sds 2.0 之前,header 的大小是固定的 int 类型。在 2.0 版本之后,会根据传入的字符大小调整 header 的 len 和 alloc 类型,以节省内存使用。 header的结构用__attribute__修饰,主要是为了防止编译器自动对齐内存,这样可以减少编译器由于内存对齐导致的填充次数占用的内存。

当前版本定义了五种sds headers,其中sdshdr5没用,所以不画了:

源码分析sds的创建

sds的创建主要包括以下功能:

sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);

所以通过上面的创建,我们可以知道最终会调用sdsnewlen来创建一个字符串,那么我们来看看这个函数是怎么实现的。

sdsnewlen

其实对于一个字符串对象的创建,其实是做了三件事:申请内存,构造一个结构体,把字符串拷贝到字符串内存区。下面我们来看看Redis的具体实现。

请求内存

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh; //指向SDS结构体的指针
    sds s; //sds类型变量,即char*字符数组
    char type = sdsReqType(initlen); //根据数据大小获取sds header 类型
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type); // 根据类型获取sds header大小
    unsigned char *fp; /* flags pointer. */
    assert(hdrlen+initlen+1 > initlen); /* Catch size_t overflow */
    sh = s_malloc(hdrlen+initlen+1); //新建SDS结构,并分配内存空间,这里加1是因为需要在最后加上
    ...
    return s;
}

在内存分配之前,需要做以下事情:

因为sds会根据传入的size来设计header类型,所以需要调用sdsReqType函数根据initlen获取header类型;然后调用sdsHdrSize根据header类型获取header占用的字节数;最后根据header长度和字符调用s_malloc字符串长度分配内存,这里需要加1,因为c中的字符串以结尾,为了兼容c的字符串格式。

既然说到了header类型,我们来看看header类型的定义:

struct __attribute__ ((__packed__)) sdshdr8 { // 占用 3 byte
    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 { // 占用 5 byte
    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 { // 占用 9 byte
    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 { // 占用 17 byte
    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[];
};

这里__attribute__用来防止内存对齐,否则会浪费一些存储空间。关于内存对齐相关的知识,我也在《Going for WaitGroup引起的内存对齐思考》一文中解释过。知识点比较笼统,有兴趣可以回溯过去。

看完上面的定义,我们自然可以认为Redis会根据传入的大小来判断生成的sds header类型:

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5) // 小于 32
        return SDS_TYPE_5;
    if (string_size < 1<<8) // 小于 256
        return SDS_TYPE_8;
    if (string_size < 1<<16) // 小于 65,536
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32) 
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

可以看到sdsReqType是根据传入字符串的长度来判断字符类型的。

构造结构

对于Redis来说,如果你没用过C语言,你会觉得这里构造结构的方式比较hacky。首先直接根据需要的内存大小申请一块内存,然后初始化头结构的指针指向的位置,最后给头结构的指针设置值。

#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
sds sdsnewlen(const void *init, size_t initlen) {
	...
    sh = s_malloc(hdrlen+initlen+1); // 1.申请内存,这里长度加1是为了在最后面存放一个 
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);// 2.将内存的值都设置为0
    s = (char*)sh+hdrlen; 				//3.将s指针指向数据起始位置
    fp = ((unsigned char*)s)-1; 		//4.将fp指针指向sds header的flags字段
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen <len = initlen; // 初始化 header len字段
            sh->alloc = initlen; // 初始化 header alloc字段
            *fp = type; // 初始化 header flag字段
            break;
        }
        ...
    }
    ...
    return s;
}

上面的流程我已经标注清楚了。直接看代码可能很难理解构造头结构的过程。我会用下图来展示指针所指向的位置:

字符串复制

sds sdsnewlen(const void *init, size_t initlen) {
    ...
    if (initlen && init)  
        memcpy(s, init, initlen); //将要传入的字符串拷贝给sds变量s
    s[initlen] = ''; //变量s末尾增加,表示字符串结束
    return s;
}

memcpy函数会将字符串逐字节复制到s对应的内存区域。

sdscatlen 字符串追加

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s); // 获取字符串 len 大小
    //根据要追加的长度len和目标字符串s的现有长度,判断是否要增加新的空间
    //返回的还是字符串起始内存地址
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    // 将新追加的字符串拷贝到末尾
    memcpy(s+curlen, t, len);
    // 重新设置字符串长度
    sdssetlen(s, curlen+len);
    s[curlen+len] = '';
    return s;
}

在这种字符串追加的方法中,空间检查和扩展其实都封装在了sdsMakeRoomFor函数中,只需要:

是否还有剩余空间,如果有,直接返回;如果没有剩余空间,那么需要扩展,多少?字符串是否可以在原位置追加空格,或者需要重新申请内存区域。

那我将sdsMakeRoomFor函数分为扩展和内存申请两部分。

扩展

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s); //这里是用 alloc-len,表示可用资源
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    if (avail >= addlen) return s; // 如果有空间剩余,那么直接返回
    len = sdslen(s); // 获取字符串 len 长度
    sh = (char*)s-sdsHdrSize(oldtype); //获取到header的指针
    newlen = (len+addlen); // 新的内存空间
    if (newlen < SDS_MAX_PREALLOC) //如果小于 1m, 那么存储空间直接翻倍
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC; //超过了1m,那么只会多增加1m空间
    ...
    return s;
}

对于扩容,首先检查空间是否足够,即根据alloc-len,如果有剩余空间则直接返回。

然后Redis会根据sds的大小进行扩展。如果len+addlen空间小于1m,则直接增加一倍新空间;如果len+addlen空间大于1m,新空间只会增加1m。

内存请求

sds sdsMakeRoomFor(sds s, size_t addlen) {
    ...
    type = sdsReqType(newlen); // 根据新的空间占用计算 sds 类型 
    hdrlen = sdsHdrSize(type); // header 长度
    if (oldtype==type) { // 和原来header一样,那么可以复用原来的空间
        newsh = s_realloc(sh, hdrlen+newlen+1); // 申请一块内存,并追加大小
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else { 
        //如果header 类型变了,表示内存头变了,那么需要重新申请内存
        //因为如果使用s_realloc只会向后追加内存
        newsh = s_malloc(hdrlen+newlen+1);
        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);
    }
    sdssetalloc(s, newlen);//重新设置alloc字段
    return s;
}

在内存申请中,Redis分为两种情况,一种是sds头类型没有改变,那么可以直接调用realloc在原内存后面增加一块新的内存区域;

另一个是sds头类型发生了变化。一般情况下,header占用的空间变大了。因为realloc不能向前添加内存区,所以只能调用malloc重新申请一块内存区,然后用memcpy把改变字符的字符串复制到新地址。

总结

通过这篇文章,我们深入了解了 Redis 字符串是如何实现的,以及通过版本变化做了哪些改变。您可以将 sds 与您熟悉的语言的字符串进行比较。看看在实现上有什么不同,哪个更好。

参考

© 版权声明
THE END
喜欢就支持一下吧
点赞204 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片