Was ist der Quellcode für Redis SDS?-Redis-php.cn

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

sdshdr数据结构

redis提供了sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64这几种sds的实现，其中除了sdshdr5比较特殊外，其他几种sdshdr差不只在于两个字段的类型差别。以下是我举例说明的两个结构体 sdshdr8 和 sdshdr16 的定义。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用空间大小 */
    uint8_t alloc; /* 总共可用的字符空间大小，应该是实际buf的大小减1(因为c字符串末尾必须是\0,不计算在内) */
    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[];
};

Nach dem Login kopieren

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

下一个问题，为什么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] = '\0';
    return s;
}

Nach dem Login kopieren

SDS的使用

上面代码中我特意标注了一个注意，sdsnewlen()返回的sds指针并不是直接指向sdshdr的地址，而是直接指向了sdshdr中buf的地址。这样做有啥好处？好处就是这样可以兼容c原生字符串。buf其实就是C 原生字符串+部分空余空间，中间是特殊符号'\0'隔开，‘\0’有是标识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]));
}

Nach dem Login kopieren

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;
}

Nach dem Login kopieren

常用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空间

Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonWas ist der Quellcode für Redis SDS?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!