【Redis源码】字符串详解（七）

前言：

学过C的人应该都知道C的字符串是以字节数组存在，然后以\0结尾。计算字符串的长度使用strlen函数，这个标准库函数的复杂程度是O(n)。它需要对字节数组进行扫描遍历计算长度。作为redis单线程的应用是这种形式是比较消耗性能的。
Redis实现了字节的字符串叫sds（Simple Dynamic String），它是一个带着长度的信息的结构体，属于柔性字符串。

Redis的字符串形式如下：

一.Redis字符串内部编码介绍：

redis字符串的内部编码分为三种：int、embstr、raw。

注意事项：
（1） embstr 的44个字节是redis3.2版本之后，之前为39；
（2）说raw大于44个字节这个不能说完全对，利用APPEND命令追加后的字符串为raw类型。

1.1 内部编码int

debug object参数解释：

当设置键值test1为9223372036854775807时，因为long的曲直范围是 -9223372036854775808 ～ 9223372036854775807之间。
所以通过debug object第一次打印test1类型为int，当前的长度为20。由于第二次打印是，设置test1为9223372036854775808，超过了long的最大值。并且长度为20，则现打印类型为embstr。

1.2 内部编码embstr和raw

当设置键值test1为0123456789abcdefghijklmnopqrstuvwxyz12345678时，因为<=44个字节。所以编码类型为embstr。
当设置键值test1为0123456789abcdefghijklmnopqrstuvwxyz123456789时，test1此时为45个字节，则编码类型为raw。

1.3 源码解析

setCommand命令源码

void setCommand(client *c) {
    省略...
    c->argv[2] = tryObjectEncoding(c->argv[2]);  //尝试对字符串对象进行编码以节省空间
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

object.c 中tryObjectEncoding函数

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44  //embstr长度限制

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;
    
    /* 确保这是一个字符串对象 */
    serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);

    /*我们只对RAW或EMBSTR编码的，换句话说，仍然是由实际的字符数组表示。*/
    if (!sdsEncodedObject(o)) return o;

    /*对共享对象进行编码是不安全的：共享对象可以共享
     *在Redis的“对象空间”中的任何地方，并且可能在
     *他们没有被处理。我们只将它们作为键空间中的值来处理。*/
     if (o->refcount > 1) return o;

    /* 检查字符串是否为long类型整数，如果len <=20且在LONG_MIN和LONG_MAX范围内，则是int编码 */
    len = sdslen(s);
    if (len <= 20 && string2l(s,len,&value)) {
       /*此对象可编码为long。尝试使用共享对象。
        *注意，当使用maxmemory时，我们避免使用共享整数
        *因为每个对象都需要有一个用于LRU的私有LRU字段
        *算法运行良好。*/
        if ((server.maxmemory == 0 ||
            !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
            value >= 0 &&
            value < OBJ_SHARED_INTEGERS)
        {
            decrRefCount(o);
            incrRefCount(shared.integers[value]);
            return shared.integers[value];
        } else {
            if (o->encoding == OBJ_ENCODING_RAW) sdsfree(o->ptr);
            o->encoding = OBJ_ENCODING_INT;  //设置为int编码
            o->ptr = (void*) value;
            return o;
        }
    }

    //判断长度小于或等于44，返回一个OBJ_ENCODING_EMBSTR编码
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;

        if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
        emb = createEmbeddedStringObject(s,sdslen(s));
        decrRefCount(o);
        return emb;
    }

    /**我们无法对对象进行编码。。。
     *做最后一次尝试，至少优化SDS字符串。
     *字符串对象需要很少的空间，以防大于SDS字符串末尾可用空间的10%。
     *我们这样做只是为了相对较大的字符串仅当字符串长度大于44。
     */
    if (o->encoding == OBJ_ENCODING_RAW &&
        sdsavail(s) > len/10)
    {
        o->ptr = sdsRemoveFreeSpace(o->ptr);
    }
    
    return o;  //返回原始对象
}

1.4 为什么OBJ_ENCODING_EMBSTR_SIZE_LIMIT是44个字节

redisObject结构体：

 typedef struct redisObject {
    unsigned type:4;       //4bit
    unsigned encoding:4;   //4bit
    unsigned lru:LRU_BITS; //24bit
    int refcount;          //4byte
    void *ptr;             //8byte
} robj

redisObject的总大小应该是16字节 = （4bit + 4bit + 24bit) + 4byte + 8byte。32bit = 4byte
sds结构体的最小单位应该是sdshdr8(sdshdr5默认会转化为sdshdr8)，接下来会说到。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;          //1byte
    uint8_t alloc;        //1byte
    unsigned char flags;  //1byte
    char buf[];
};

内存分配器jemalloc/tcmalloc分配内存大小单位为：2、4、8、16、32、64。为了能完整容纳一个embstr对象，最小分配32个字节空间。如果稍微长一点就是64个字节空间。如果超出64个字节，Redis认为它是一个大字符串。形式就变为RAW，不在是一个连续内存。

64 - 16 - 3 - 1 = 44，64减去redisObject结构体的16个字节再减去sds结构体的3个字节和一个\0字符的1个字节。

二.SDS介绍：

2.1 SDS数据结构

sds的5种数据结构，sds.h中

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

看到以上宏可能不是特别容易理解，接下来我们看一段源码,sds.c中：

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)  //2的5次方
        return SDS_TYPE_5; 
    if (string_size < 1<<8)  //2的8次方
        return SDS_TYPE_8;
    if (string_size < 1<<16) //2的16次方
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32) //2的32次方
        return SDS_TYPE_32;
#endif
    return SDS_TYPE_64;       
}

/*
 根据长度创建一个sds字符串
*/
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen); //获取字符串类型
    //空字符串默认type为SDS_TYPE_8
    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 (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    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';  //字符串结尾添加一个\0
    return s;
}

sds的数据结构取值范围：

2.2 SDS字符串扩容

可以先看一下追加字符串函数，在sds.c中:

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s); //获取当前字符串长度

    s = sdsMakeRoomFor(s,len); //按照需要空间调整字符串空间
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);  //追加到目标字符串数组中
    sdssetlen(s, curlen+len);  //设置追加后长度
    s[curlen+len] = '\0';      //追加后
    return s;
}

sds字符串调整空间函数，在sds.c中

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;
    int hdrlen;

    /* 如果空间足够时返回原来的 */
    if (avail >= addlen) return s;

    len = sdslen(s);                   //获取长度
    sh = (char*)s-sdsHdrSize(oldtype); //获取数据
        newlen = (len+addlen);         //计算新的长度
    if (newlen < SDS_MAX_PREALLOC)      // < 1M 2倍扩容,1M = 1024 * 1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;    // > 1M 扩容1M

    type = sdsReqType(newlen);  //获得新长度的sds类型

    if (type == SDS_TYPE_5) type = SDS_TYPE_8;  //type5 默认转成 type8

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

扩容时，字符串长度小于1M之前，扩容空间都是成倍增加。当长度大于1M之后，为了避免空间过大浪费。
每次扩容只会多分配1M。

三.总结：

(1) redis的字符串为了节省开销采用sds结构作为字符串结构，sds结构分为：sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64 五种，字符串会根据不同的大小通过sdsReqType函数获取对应的类型。
(2) redis字符串的编码分为三种，int，embstr，raw。int的范围为min long到max long的整数之间，embstr为非整数44字节内，raw为大于44字节字符串。通过append命令追加字符串不够字节影响，编码类型直接时raw。
(3)redis字符串扩容，小于1M成倍增加，大于或等于1M每次只增加1M。这种做法是避免资源浪费。
(4)OBJ_ENCODING_EMBSTR_SIZE_LIMIT等于44字节，是因为64字节减去redisObject结构体的16个字节再减去sds结构体的3个字节和一个\0字符的1个字节。
(5)sdshdr5默认为变为sdshdr8。

加V信进群交流