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

前言：

学过C的人应该都知道C的字符串是以字节数组存在，然后以\0结尾。计算字符串的长度使用strlen函数，这个标准库函数的复杂程度是O(n)。它需要对字节数组进行扫描遍历计算长度。作为redis单线程的应用是这种形式是比较消耗性能的。

Redis实现了字节的字符串叫sds（Simple Dynamic String），它是一个带着长度的信息的结构体，属于柔性字符串。

版本：redis4.0.0

Redis的字符串形式如下：

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

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

内部编码	条件	备注
int	满足long取值范围，也就是 -9223372036854775808 ～ 9223372036854775807之间	如果设置字符串为数组类型操作long的范围，小于44字节。比如值为9223372036854775808则类型会变为embstr
embstr	非数组类型，若为数字。则不在long取值范围。且小于44字节。redis 3.2之前则小于39	如果大于44字节，则会变为raw类型，连续内存。注：redis3.2版本后
raw	大于44字节。redis3.2之后	满足等于或大于45字节，非连续内存。

注意事项：

（1） embstr 的44个字节是redis3.2版本之后，之前为39；

（2）说raw大于44个字节这个不能说完全对，利用APPEND命令追加后的字符串为raw类型。

1.1 内部编码int

 

debug object参数解释：

名称	备注
Value at	位于地址
refcount	引用数量
encoding	编码
serializedlength	序列化长度（字符串长度）
lru	LRU时间
lru_seconds_idle	LRU闲置时间

当设置键值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;

edisObject的总大小应该是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。