您当前的位置:首页 > 电脑百科 > 数据库 > Redis

Redis源码剖析之SDS

时间:2020-09-27 09:41:37  来源:  作者:

SDS(simple dynamic string)是redis提供的字符串的封装,在redis中也是存在最广泛的数据结构,它也是很多其他数据结构的基础,所以才选择先介绍SDS。 SDS也兼容部分C字符串API(strcmp,strlen),它如何兼容C字符串我觉得也是有个很sao的操作,等看完我这篇博客你就明白了。在开始正式内容前,我先抛几个问题(有些也是面试高频题),带着问题去学习也是一种非常好的学习方法。

  1. C语言中也算是支持String了,为什么Redis还要自己封装一个?
  2. SDS中的D(dynamic)到底是什么含义?
  3. SDS的数据结构是啥样的?为什么要那么设计
  4. SDS是如何兼容C字符串的?

Redis中sds相关的源码都在src/sds.c 和src/sds.h中(链接可以直接跳转到我中文注释版redis源码),其中sds.h中定义了所有SDS的api,当然也实现了部分几个api,比如sds长度、sds剩余可用空间……,不急着看代码,我们先看下sds的数据结构,看完后为什么代码那么写你就一目了然。

sdshdr数据结构

redis提供了sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64这几种sds的实现,其中除了sdshdr5比较特殊外,其他几种sdshdr差不只在于两个字段的类型差别。我就拿 sdshdr8和sdshdr16来举例,其struct定义分别如下。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用空间大小 */
    uint8_t alloc; /* 总共可用的字符空间大小,应该是实际buf的大小减1(因为c字符串末尾必须是,不计算在内) */
    unsigned char flags; /* 标志位,主要是识别这是sdshdr几,目前只用了3位,还有5位空余 */
    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[];
};

sdshdr32 sdshdr64也和上面的结构一致,差别只在于len和alloc的数据类型不一样而已。相较于c原生的字符串,sds多了len、alloc、flag三个字段来存储一些额外的信息,redis考虑到了字符串拼接时带来的巨大损耗,所以每次新建sds的时候会预分配一些空间来应对未来的增长,sds和C string的关系熟悉JAVA的旁友可能会决定就好比java中String和StringBuffer的关系。正是因为预留空间的机制,所以redis需要记录下来已分配和总空间大小,当然可用空间可用直接算出来。
Redis源码剖析之SDS

下一个问题,为什么redis费心费力要提供sdshdr5到sdshdr64这五种SDS呢?我觉着这只能说明Redis作者抠内存抠到机制,牺牲了代码的简洁性换取了每个sds省下来的几个字节的内存空间。从sds初始化方法sdsnew和sdsnewlen中我们就可以看出,redis在新建sds时需要传如初始化长度,然后根据初始化的长度确定用哪种sdshdr,小于2^8长度的用sdshdr8,这样len和alloc只占用两个字节,比较短字符串可能非常多,所以节省下来的内存还是非常可观的,知道了sds的数据结构和设计原理,sdsnewlen的代码就非常好懂了,如下:

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;    sds s;    // 根据初始化的长度确定用哪种sdshdr    char type = sdsReqType(initlen);
    /* 空字符串大概率之后会Append,但sdshdr5不适合用来append,所以直接替换成sdshdr8 */    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    /* 注意:返回的s并不是直接指向sds的指针,而是指向sds中字符串的指针,sds的指针还需要     * 根据s和hdrlen计算出来 */    s = (char*)sh+hdrlen;  
    fp = ((unsigned char*)s)-1;
    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 = initlen;            *fp = type;
            break;
        }        case SDS_TYPE_16: {            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;            *fp = type;
            break;
        }        case SDS_TYPE_32: {            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;            *fp = type;
            break;
        }        case SDS_TYPE_64: {            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;            *fp = type;
            break;
        }    }    if (initlen && init)
        memcpy(s, init, initlen);    s[initlen] = '';
    return s;
}

SDS的使用

上面代码中我特意标注了一个注意sdsnewlen()返回的sds指针并不是直接指向sdshdr的地址,而是直接指向了sdshdr中buf的地址。这样做有啥好处?好处就是这样可以兼容c原生字符串。buf其实就是C 原生字符串+部分空余空间,中间是特殊符号''隔开,‘’有是标识C字符串末尾的符号,这样就实现了和C原生字符串的兼容,部分C字符串的API也就可以直接使用了。 当然这也有坏处,这样就没法直接拿到len和alloc的具体值了,但是也不是没有办法。

当我们拿到一个sds,假设这个sds就叫s吧,其实一开始我们对这个sds一无所知,连他是sdshdr几都不知道,这时候可以看下s的前面一个字节,我们已经知道sdshdr的数据结构了,前一个字节就是flag,根据flag具体的值我们就可以推断出s具体是哪个sdshdr,也可以推断出sds的真正地址,相应的就知道了它的len和alloc,知道了这点,下面这些有点晦涩的代码就很好理解了。

oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7 看下s前面一个字节(flag)推算出sdshdr的类型。 
// 这个宏定义直接推算出sdshdr头部的内存地址#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)// 获取sds支持的长度  static inline size_t sdslen(const sds s) {    unsigned char flags = s[-1];  // -1 相当于获取到了sdshdr中的flag字段  
    switch(flags&SDS_TYPE_MASK) {          case SDS_TYPE_5:            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:            return SDS_HDR(8,s)->len;  // 宏替换获取到sdshdr中的len
        ...        // 省略 SDS_TYPE_16 SDS_TYPE_32的代码……         case SDS_TYPE_64:            return SDS_HDR(64,s)->len;
    }    return 0;
}// 获取sds剩余可用空间大小 static inline size_t sdsavail(const sds s) {    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {        case SDS_TYPE_5: {            return 0;
        }        case SDS_TYPE_8: {            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }        ...         // 省略 SDS_TYPE_16 SDS_TYPE_32的代码……         case SDS_TYPE_64: {            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }    }    return 0;
}/* 返回sds实际的起始位置指针 */void *sdsAllocPtr(sds s) {    return (void*) (s-sdsHdrSize(s[-1]));
}

SDS的扩容

在做字符串拼接的时候,sds可能剩余的可用空间不足,这个时候需要扩容,什么时候该扩容,又该怎么扩? 这是不得不考虑的问题。Java中很多数据结构都有动态扩容的机制,比如和sds很类似的StringBuffer,HashMap,他们都会在使用过程中动态判断是否空间充足,而且基本上都采用了先指数扩容,然后到一定大小限制后才开始线性扩容的方式,Redis也不例外,Redis在10241024以内都是2倍的方式扩容,只要不超出10241024都是先额外申请200%的空间,但一旦总长度超过10241024字节,那每次最多只会扩容10241024字节。 Redis中sds扩容的代码是在sdsMakeRoomFor(),可以看到很多字符串变更的API开头都直接或者间接调用这个。 和Java中StringBuffer扩容不同的是,Redis这里还需要考虑不同字符串长度时sdshdr类型的变化,具体代码如下:

// 扩大sds的实际可用空间,以便后续能拼接更多字符串。 
// 注意:这里实际不会改变sds的长度,只是增加了更多可用的空间(buf) sds sdsMakeRoomFor(sds s, size_t addlen) {    void *sh, *newsh;    size_t avail = sdsavail(s);    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7 
    int hdrlen;    /* 如果有足够的剩余空间,直接返回 */    if (avail >= addlen) return s;
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // 在未超出SDS_MAX_PREALLOC前,扩容都是按2倍的方式扩容,超出后只能递增 
    if (newlen < SDS_MAX_PREALLOC)  // SDS_MAX_PREALLOC = 1024*1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;    type = sdsReqType(newlen);
    /*  在真正使用过程中不会用到type5,如果遇到type5直接使用type8*/    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        // 扩容其实就是申请新的空间,然后把旧数据挪过去          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);    return s;
}

常用API

sds.c还有很多源码我都没有贴到,其他代码本质上都是围绕sdshdr数据结构和各种字符串操作写的(基本上都是各种字符串新建、拼接、拷贝、扩容……),只要知道了sds的设计原理,相信你也能轻易写出来,这里我就列一下所有sds相关的API,对源码有兴趣的旁友可以移步到src/sds.c,中文注释版的API列表见src/sds.c

sds sdsnewlen(const void *init, size_t initlen);  // 新建一个容量为initlen的sds
sds sdsnew(const char *init); // 新建sds,字符串为null,默认长度0 
sds sdsempty(void);  // 新建空字符“” 
sds sdsdup(const sds s); // 根据s的实际长度创建新的sds,目的是降低内存的占用
void sdsfree(sds s); // 释放sds 
sds sdsgrowzero(sds s, size_t len); // 把sds增长到指定的长度,增长出来的新的空间用0填充 
sds sdscatlen(sds s, const void *t, size_t len); // 在sds上拼接字符串t的指定长度部分 
sds sdscat(sds s, const char *t);  // 把字符串t拼接到sds上 
sds sdscatsds(sds s, const sds t); // 把两个sds拼接在一起  
sds sdscpylen(sds s, const char *t, size_t len); //  把字符串t指定长度的部分拷贝到sds上 
sds sdscpy(sds s, const char *t); // 把字符串t拷贝到sds上 
sds sdscatvprintf(sds s, const char *fmt, va_list ap); // 把用printf格式化后的字符拼接到sds上 
sds sdscatfmt(sds s, char const *fmt, ...);   // 将多个参数格式化成一个字符串后拼接到sds上 
sds sdstrim(sds s, const char *cset);  // 在sds中移除开头或者末尾在cset中的字符  
void sdsrange(sds s, ssize_t start, ssize_t end);  // 截取sds的子串 
void sdsupdatelen(sds s); // 更新sds字符串的长度 
void sdsclear(sds s);  // 清空sds中的内容,但不释放空间 
int sdscmp(const sds s1, const sds s2);  // sds字符串比较大小 
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);void sdsfreesplitres(sds *tokens, int count);void sdstolower(sds s); // 字符串转小写
void sdstoupper(sds s);  // 字符串转大写
sds sdsfromlonglong(long long value);  // 把一个long long型的数转成sds  
sds sdscatrepr(sds s, const char *p, size_t len); sds *sdssplitargs(const char *line, int *argc);sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);sds sdsjoin(char **argv, int argc, char *sep); // 把字符串数组按指定的分隔符拼接起来
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen); // 把sds数组按指定的分隔符拼接起来
/* sds底层api */
sds sdsMakeRoomFor(sds s, size_t addlen);  // sds扩容
void sdsIncrLen(sds s, ssize_t incr); // 扩容指定长度
sds sdsRemoveFreeSpace(sds s); // 释放sds占用的多余空间
size_t sdsAllocSize(sds s); // 返回sds总共占用的内存大小
void *sdsAllocPtr(sds s); // 返回sds实际的起始位置指针
void *sds_malloc(size_t size); // 为sds分配空间 
void *sds_realloc(void *ptr, size_t size); // 
void sds_free(void *ptr);  // 释放sds空间 

结语

回到开篇的几个问题,相信看完上面的内容后你都能回答上来了,如果回答不上来那就再多看两遍,本博客+源码搭配服用效果更佳。

为了控制博客篇幅,这里只讲解了核心代码,很多API的源码我都没有贴上来(毕竟太多),有兴趣的同学可以再看下源码 https://github.com/xindoo/redis/。

本文是Redis源码剖析系列博文,同时也有与之对应的Redis中文注释版,有想深入学习Redis的同学,欢迎star和关注。 Redis中文注解版仓库:https://github.com/xindoo/redis
Redis源码剖析专栏:https://zxs.io/s/1h
本文来自https://blog.csdn.net/xindoo



Tags:Redis SDS   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
SDS(simple dynamic string)是Redis提供的字符串的封装,在redis中也是存在最广泛的数据结构,它也是很多其他数据结构的基础,所以才选择先介绍SDS。 SDS也兼容部分C字符串API(st...【详细内容】
2020-09-27  Tags: Redis SDS  点击:(107)  评论:(0)  加入收藏
字符串是redis中最为常见的存储数据存储类型,其底层实现是简单的动态字符串sds(simple dynamic string),可以修改的字符串。sds 介绍sds本质上是 char *,因为有了表头sdshdr...【详细内容】
2020-01-09  Tags: Redis SDS  点击:(102)  评论:(0)  加入收藏
▌简易百科推荐
来源: my.oschina.net/xiaomu0082/blog/2990388首先说下问题现象:内网sandbox环境API持续1周出现应用卡死,所有api无响应现象刚开始当测试抱怨环境响应慢的时候 ,我们重启一下应...【详细内容】
2021-12-08  Java识堂    Tags:Redis   点击:(16)  评论:(0)  加入收藏
我不知道为什么你会选择对特定数量的“错误”(或警告)如此具体。听起来您正在寻找将要发布到 Yahoo! 的某些文章的内容。 Insider (N Foos to Blah for the BlahBlah)。那说:...【详细内容】
2021-12-07  富集云科技有限公司    Tags:Redis   点击:(14)  评论:(0)  加入收藏
目录 一、背景 二、步骤 0.理论支持 1、获取数据 2、结果 3、分析数据并评估大小 三、关于repl-backlog-size 一、背景 repl-backlog-size控制这个环形缓冲区. ​ 主从断...【详细内容】
2021-11-05  弈秋的美好生活    Tags:redis   点击:(41)  评论:(0)  加入收藏
Redis 性能测试是通过同时执行多个命令实现的。1,Redis-benchmarkRedis性能命令:redis性能命令格式: redis-benchmark [option] [option value] redis 性能测试工具可选参数如...【详细内容】
2021-11-02  川石信息    Tags:Redis   点击:(41)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  JavaEdge    Tags:Redis   点击:(28)  评论:(0)  加入收藏
普通java中使用引用Java redis 驱动,即可连接:import redis.clients.jedis.Jedis; public class RedisTestJava { public static void main(String[] args) { //连...【详细内容】
2021-10-13  faesuite    Tags:Redis   点击:(34)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  语霖    Tags:Redis   点击:(36)  评论:(0)  加入收藏
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。> LPUSH fruit apple(integer) 1> RPUSH fruit banana(integer)...【详细内容】
2021-09-17  深夜敲代码    Tags:Redis   点击:(54)  评论:(0)  加入收藏
Redis持久化意义 是做灾难恢复,数据恢复,也可以归类到高可用的一个环节里面去,比如你的redis整个挂了,然后redis就不可用了,你要做的事情是让redis变得可用,尽快变得可用 大量的请...【详细内容】
2021-08-12  小李说IT    Tags:Redis   点击:(77)  评论:(0)  加入收藏
当查询Redis中没有的数据时,该查询会下沉到数据库层,同时数据库层也没有该数据,当这种情况大量出现或被恶意攻击时,接口的访问全部透过Redis访问数据库,而数据库中也没有这些数据...【详细内容】
2021-07-30  随便t    Tags:缓存穿透   点击:(90)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条