【重学Redis】Redis里的字符串SDS(下)

开课吧樵夫2022-01-07 17:31

  Redis自定字符串存储结构,关于Redis,你需要知道什么!我们对此有一个简要的解释。

  Redis的底层是用C语言编写的,但在字符存储中,并没有使用C原始的String类型,而是定义了自己的字符串结构SimpledynamicStirng,简称SDS。

【重学Redis】Redis里的字符串SDS(下)

  基础方法

  在sds.h里定义了一些基础方法,用于操作sds,以便其他方法使用,类似于java里的get和set

  sds.h

//返回现有字符串的长度len
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    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;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}
//返回SDS剩余可用空间 alloc-len
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;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}
//设置SDS的len长度字段
static inline void sdssetlen(sds s, size_t newlen) {
    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;
    }
}
//把len增加inc
static inline void sdsinclen(sds s, size_t inc) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len += inc;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len += inc;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len += inc;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len += inc;
            break;
    }
}
/* sdsalloc() = sdsavail() + sdslen() */
//返回alloc
static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}
//设置alloc
static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

  扩容:sdsMakeRoomFor

  sds.c

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //获取可用长度
    size_t avail = sdsavail(s);
    size_t len, newlen;
    //oldtype:原来的SDS的类型
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    /* Return ASAP if there is enough space left. */
    //可用空间avail大于等于要追加的字符串的长度addlen
    if (avail >= addlen) return s;
    //空间不足,进行扩容
    //原字符串长度
    len = sdslen(s);
    //SDS结构的起始地址
    sh = (char*)s-sdsHdrSize(oldtype);
    //字符串新的长度=原来的长度+需要增加的长度
    newlen = (len+addlen);
    // #define SDS_MAX_PREALLOC (1024*1024)
    // 当新的长度小于 1M 的时候,长度会增长一倍
    // 当新的长度达到 1M 之后,最多就增长 1M 了
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        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. */
    //不要使用类型5:用户正在追加字符串,而类型5是无法记住空格的
    //因此在每次追加操作中必须调用sdsMakeRoomFor()
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    //元数据的长度
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {//sds类型不变
        //重新分配空间,返回新的空间的地址(数据被拷贝到新的空间)
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        //字符数组的起始地址
        s = (char*)newsh+hdrlen;
    } else {//sds类型发生变化
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        //由于sds类型变化 ,header大小也发生变化,需要移动字符串,并且不能使用realloc
        //根据header大小+变化后的字符长度+1字节结束符号"\0"  开辟空间,返回新的空间的地址
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        //拷贝原来的字符串到新的地址
        memcpy((char*)newsh+hdrlen, s, len+1);
        //释放原来的SDS的空间
        s_free(sh);
        //字符数组的起始地址
        s = (char*)newsh+hdrlen;
        //设置flags
        s[-1] = type;
        //设置长度
        sdssetlen(s, len);
    }
    //设置alloc
    sdssetalloc(s, newlen);
    return s;
}

  扩容主要分为一下几步:

  1、比较原来申请的空间剩余的空闲空间和需要增加的空间,如果空间有剩余并且够用就不用扩容了

  2、如果需要扩容,计算需要的总空间,如果小于1M,就扩容为原来的2倍,如果大于1M,就在扩容1M

  3、根据扩容后的空间选择合适的SDS类型,如果是类型5.改为使用类型8

  4、如果sds类型不变,就重新申请空间,并把字符数组指向新的地址,如果类型发生变化,除了要改变字符数组的指针,还需要改变长度len和类型flags

  5、无论类型是否变化,只要扩容了,都要修改申请的空间alloc字段

  缩容:sdsRemoveFreeSpace

  sds.c

//缩容,重新分配sds字符串,使其结尾没有可用空间。字符串内容保持不变
//调用后,原来sds的字符串的指针不在有效,必须用返回的新指针代替
sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    //新的sds类型和老的sds类型
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    //新的header长度和老的header长度
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    //字符串长度
    size_t len = sdslen(s);
    //可用空间
    size_t avail = sdsavail(s);
    //SDS的起始地址
    sh = (char*)s-oldhdrlen;
    /* Return ASAP if there is no space left. */
    //没有多余空间直接返回
    if (avail == 0) return s;
    /* Check what would be the minimum SDS header that is just good enough to
     * fit this string. */
    //根据现有字符串长度返回合适的类型
    type = sdsReqType(len);
    //返回合适的类型对应的header的长度
    hdrlen = sdsHdrSize(type);
    /* If the type is the same, or at least a large enough type is still
     * required, we just realloc(), letting the allocator to do the copy
     * only if really needed. Otherwise if the change is huge, we manually
     * reallocate the string to use the different header type. */
    if (oldtype==type || type > SDS_TYPE_8) {//sds类型相同
        //重新分配整个SDS的空间
        newsh = s_realloc(sh, oldhdrlen+len+1);
        if (newsh == NULL) return NULL;
        //改变sds字符串的起始地址
        s = (char*)newsh+oldhdrlen;
    } else {//sds类型不同
        //根据长度和对应的类型开辟空间
        newsh = s_malloc(hdrlen+len+1);
        if (newsh == NULL) return NULL;
        //复制字符数组
        memcpy((char*)newsh+hdrlen, s, len+1);
        //释放原空间
        s_free(sh);
        //新的字符数组的起始地址
        s = (char*)newsh+hdrlen;
        //设置flags
        s[-1] = type;
        //设置len
        sdssetlen(s, len);
    }
    //设置alloc
    sdssetalloc(s, len);
    return s;
}

  缩容分为以下几步:

  1、如果SDS没有空闲的空间,即len==alloc,就不用进行缩容了

  2、根据现有字符串长度选择合适的类型

  3、如果缩容不需要改变sds的类型,就重新分配一块刚好够存储原来数据的空间,把数据复制过去,并把字符数组的指针指向新的地址

  4、如果缩容需要改变sds的类型,那么header的大小也会发生变化,需要根据变化后的header大小和字符串长度申请新的空间,然后把字符数组拷贝到新的地址,并把字符数组的指针指向新的地址,设置len 和flags

  5、无论类型是否变化,只要缩容了,都要修改申请的空间alloc字段

  拼接:sdscatlen

  sds.c

//对s追加t指向的字符串的前len个字符
sds sdscatlen(sds s, const void *t, size_t len) {
    //获取目标字符串s的当前长度
    size_t curlen = sdslen(s);
    //根据要追加的长度len和目标字符串s的现有长度,进行扩容
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    //将源字符串t中len长度的数据拷贝到目标字符串结尾
    memcpy(s+curlen, t, len);
    //设置目标字符串的最新长度:拷贝前长度curlen加上拷贝长度
    sdssetlen(s, curlen+len);
    //拷贝后,在目标字符串结尾加上\0
    s[curlen+len] = '\0';
    return s;
}
 

  剪切:sdstrim

  对 sds 左右两端进行修剪,清除其中 cset 指定的所有字符

  比如 sdsstrim("AA...AA.a.aa.aHelloWorld :::", "Aa. :") 将返回 "HelloWorld"

  sds sdstrim(sds s, const char *cset) { char *start, *end, *sp, *ep; size_t len;

sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;
    ep = end = s+sdslen(s)-1;
    //从左遍历找到s里包含在cset指向的字符串里的距离s开头最远的一个字符
    while(sp <= end && strchr(cset, *sp)) sp++;
    //从右遍历找到s里包含在cset指向的字符串里的距离s结尾最远的一个字符
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    //移动s中间的字符串到开头并添加结束符"\0"
    if (s != sp) memmove(s, sp, len);
    s[len] = '\0';
    //设置长度
    sdssetlen(s,len);
    return s;
}

  比较:sdscmp

  将两个sds字符串s1和s2进行比较。

  返回值:如果s1>s2.则为正值。如果s1

  如果两个字符串拥有完全相同的前缀,但其中一个具有附加字符,则认为较长的字符串大于较小的字符串。

int sdscmp(const sds s1, const sds s2) {
    size_t l1, l2, minlen;
    int cmp;

    l1 = sdslen(s1);
    l2 = sdslen(s2);
    minlen = (l1 < l2) ? l1 : l2;
    cmp = memcmp(s1,s2,minlen);
    if (cmp == 0) return l1>l2? 1: (l1<l2? -1: 0);
    return cmp;
}

  扩展

  sdsnewlen也有很多扩展方法,都是在sds.c文件里的,我们来简单看一下

  sdsempty用于创建一个空(零长度)的sds字符串

sds sdsempty(void) {
    return sdsnewlen("",0);
}

  sdsnew用于创建一个SDS,字符串的内容为init指向的字符串,返回sds的字符数组buf的起始地址

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

  sdsdup用于复制SDS字符串

sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}

  sdsfree将会释放sds的全部空间,包括header(len,alloc,flags)和字符数组buf,如果参数为空则什么都不做

void sdsfree(sds s) {
    if (s == NULL) return;
    //s是char字符数组的指针,减去元数据的大小就是SDS开始的指针
    s_free((char*)s-sdsHdrSize(s[-1]));
}

  sdsupdatelen方法非常简单,就是重新计算字符串的长度,然后赋值给len字段

//更新SDS的len字段
void sdsupdatelen(sds s) {
    size_t reallen = strlen(s);
    sdssetlen(s, reallen);
}

  sdsclear用于清空sds,就是把字符数组的第一个字符设置为结束符"\0",设置len为0

//SDS字符串设置为NULL,并把长度设置为0
void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

  sdsAllocSize返回指定sds分配的总大小,包括:header的大小(len,alloc,flags),字符数组的长度,末尾结束符"\0",空闲的区域

size_t sdsAllocSize(sds s) {
    size_t alloc = sdsalloc(s);
    return sdsHdrSize(s[-1])+alloc+1;
}

  sdsAllocPtr返回SDS结构的开头地址

void *sdsAllocPtr(sds s) {
    return (void*) (s-sdsHdrSize(s[-1]));
}

  sdsIncrLen可以增加字符串长度,不过只是单纯的把len字段加incr

void sdsIncrLen(sds s, ssize_t incr) {
    unsigned char flags = s[-1];
    size_t len;
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            unsigned char *fp = ((unsigned char*)s)-1;
            unsigned char oldlen = SDS_TYPE_5_LEN(flags);
            assert((incr > 0 && oldlen+incr < 32) || (incr < 0 && oldlen >= (unsigned int)(-incr)));
            *fp = SDS_TYPE_5 | ((oldlen+incr) << SDS_TYPE_BITS);
            len = oldlen+incr;
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
            len = (sh->len += incr);
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            assert((incr >= 0 && sh->alloc-sh->len >= incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
            len = (sh->len += incr);
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            assert((incr >= 0 && sh->alloc-sh->len >= (unsigned int)incr) || (incr < 0 && sh->len >= (unsigned int)(-incr)));
            len = (sh->len += incr);
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            assert((incr >= 0 && sh->alloc-sh->len >= (uint64_t)incr) || (incr < 0 && sh->len >= (uint64_t)(-incr)));
            len = (sh->len += incr);
            break;
        }
        //只是为了避免编译警告
        default: len = 0; /* Just to avoid compilation warnings. */
    }
    s[len] = '\0';
}

  sdsgrowzero可以将sds增长到指定长度len。不属于sds原始长度的字节将设置为零。如果指定的长度len小于当前长度,则不执行任何操作

sds sdsgrowzero(sds s, size_t len) {
    //当前长度
    size_t curlen = sdslen(s);
    //指定长度小于当前长度
    if (len <= curlen) return s;
    //扩容
    s = sdsMakeRoomFor(s,len-curlen);
    if (s == NULL) return NULL;


    /* Make sure added region doesn't contain garbage */
    //在新增的长度上设置"0",并在末尾添加结束符"\0"
    memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
    //设置长度
    sdssetlen(s, len);
    return s;
}

  sdscat对s追加t指向的字符串的全部,就只调用了一下sdscatlen

sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

  sdscatsds对s追加t指向的字符串,和sdscat一样,只是换了一个形参

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

  sdscpylen把t指向的字符串的前len个复制到原字符串s的开头,覆盖原来的数据

sds sdscpylen(sds s, const char *t, size_t len) {
    if (sdsalloc(s) < len) {
        s = sdsMakeRoomFor(s,len-sdslen(s));
        if (s == NULL) return NULL;
    }
    memcpy(s, t, len);
    s[len] = '\0';
    sdssetlen(s, len);
    return s;
}

  sdscpy把t指向的字符串的复制到原字符串s的开头,覆盖原来的数据

sds sdscpy(sds s, const char *t) {
    return sdscpylen(s, t, strlen(t));
}

  sdsrange按索引截取 sds 字符串的其中一段,该字符串仅包含“start”和“end”索引指定的子字符串。

  start”和“end”可以是负数,其中-1表示字符串的最后一个字符,-2表示倒数第二个字符,依此类推。

void sdsrange(sds s, ssize_t start, ssize_t end) {
    size_t newlen, len = sdslen(s);


    if (len == 0) return;
    if (start < 0) {
        start = len+start;
        if (start < 0) start = 0;
    }
    if (end < 0) {
        end = len+end;
        if (end < 0) end = 0;
    }
    newlen = (start > end) ? 0 : (end-start)+1;
    if (newlen != 0) {
        if (start >= (ssize_t)len) {
            newlen = 0;
        } else if (end >= (ssize_t)len) {
            end = len-1;
            newlen = (start > end) ? 0 : (end-start)+1;
        }
    } else {
        start = 0;
    }
    // 如果有需要,对字符串进行移动
    if (start && newlen) memmove(s, s+start, newlen);
    s[newlen] = 0;
    sdssetlen(s,newlen);
}

  sdstolower将 sds 字符串中的所有字符转换为小写

void sdstolower(sds s) {
    size_t len = sdslen(s), j;
    for (j = 0; j < len; j++) s[j] = tolower(s[j]);
}

  sdstoupper将 sds 字符串中的所有字符转换为大写

void sdstoupper(sds s) {
    size_t len = sdslen(s), j;
    for (j = 0; j < len; j++) s[j] = toupper(s[j]);
}

  总结

  SDS 通过在结构体中记录字符数组的使用长度和申请的空间大小,减少了对字符串遍历获取字符串长度的操作,提高了效率

  SDS 一共设计了 5 种类型,分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64.他们的区别就在于 len 和 alloc字段的类型不同,这样的话在存储比较小的数据时使用比较小的类型,就更能节省内存,这其实是一种以复杂度提升换取空间的做法,可见redis把内存节省到了极致

  Redis 在设计类型的时候使用了__attribute__ ((__packed__)),其实这里__attribute__ ((__packed__))的作用就是告诉编译器,在编译不要使用字节对齐的方式,而是采用紧凑的方式分配内存。因为在默认情况下,编译器会按照 8 字节对齐的方式,给变量分配内存。也就是说,即使一个变量的大小不到 8 个字节,编译器也会给它分配 8 个字节。采用这种方式,结构体实际占用多少内存空间,编译器就分配多少空间

  通过上边的源码,我们可以看到,redis还会使用缩容函数对SDS里空闲的空间释放出来,这也是对内存空间的优化

  关于SDS的方法我们基本上都了解了一下,剩余几个不常用的方法,如果大家有兴趣可以自己再了解一下,通过我们上边这些源码的阅读,相信剩下的方法都不难理解

  以上就是开课吧小编为大家整理发布的“【重学Redis】Redis里的字符串SDS(下)”一文,更多相关内容尽在开课吧广场Java教程频道。

免责声明:本站所提供的内容均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用。如涉及版权问题,请联系本站管理员予以更改或删除。
有用1
分享