redisString

字符串对象

字符串对象的编码方式有int、embstr和raw。

int

使用int编码要求对象是一个整数值，而且可以使用long类型表示

raw

raw编码使用的是sds(simple dynamic string, 简单动态字符串)保存，其数据结构如下：

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    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[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

共有5种sdshdr结构，其中sdshdr5并没有使用。

len

len中存储的是buf中的字符串长度。

buf

buf中存储的是字符串的值，与C中的字符串一样，最后都会又一个额外的字符\0作为结尾。不同的是C中没有存储字符串的长度信息，所以在读取字符串时读到\0便终止，sds中则是直接读取len长度的字符串，所以sds是二进制安全的。

PS：len中不包括\0的长度

alloc

alloc表示的是buf总分配的总长度。出现这个字段是因为redis中的字符串有时会经常进行修改，如果每次都分配len+1的长度，就意味着要经常进行内存分配，所以redis中会对内存空间进行预分配，每次分配alloc的长度。

• 预分配规则：
  • set的时候不预留空间，alloc=len。总分配hdrlen+alloc+1大小的空间，hdrlen指的是对应sdshdr结构体的大小
  • 其余修改(如append)的时候，先计算已分配未使用的空间大小avail(alloc-len)，如果avail够的话，直接添加到buf中，修改len为newlen(二者长度之和)。否则新分配一块（hdrlen+newlen*2+1）大小的内存，alloc改为newlen*2;当newlen>1024*1024(1M)时，每次多分配1M，而非newlen*2

PS：之前的redis版本存的是free，相当于alloc - len。而没有存alloc。

flags

flags表示的是该sds指向的是上述五种sdshdr的哪一种，取值为0-4。

sds

初始化字符串为itlay.top的时候，其结构如下：

从上图可以看到，ptr指向的是buf位置。实际上在给出sdshdr结构体时，就定义了一个sds指针typedef char *sds，redis中对sdshdr的操作全是通过该指针完成。在创建sdshdr结构后，返回就是指向buf的sds指针，然后将其赋值给ptr。

• 指针指向的是buf字段，如何获取该字符串的len和alloc呢？

  在申明sdshdr时，都使用了__attribute__ ((__packed__))，表示该结构体使用1字节对齐。所以，能使用sds[-1]获取到flags的值，然后获取到对应结构体的大小以获取该结构体头部的指针。以下为获取sds长度的代码，获取alloc的代码类似。

/* 根据类型和buf的位置确定sdshdr的位置 */
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    /* SDS_TYPE_MASK=7，因为flags只使用了3位*/
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* sdshdr5的长度存在flags的前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的函数

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    /* sdsReqType 获取需要使用的sdshdr类型*/
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    /* sdsHdrSize 获取该类型的结构体大小*/
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    /* s_trymalloc_usable：返回分配的结果或者空
     * s_malloc_usable：返回分配的结果或者异常
     * 申请分配的大小为 结构体大小 + 字符串大小 + '\0'， usable为实际分配的值*/
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    /* 获取alloc，若大于该类型的最大值，则设其为该类型最大值 */
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            /* 根据s获取指向该结构体头部的指针sh*/
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    /* 将最后一位设为\0 */
    s[initlen] = '\0';
    return s;
}

分配空间的函数

#define SDS_MAX_PREALLOC (1024*1024)

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;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    /* SDS_MAX_PREALLOC为1024*1024 */
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    /* 获取新长度的sdshdr类型 */
    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. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > len);  /* Catch size_t overflow */
    /* 同样申请hdrlen+newlen+1大小的空间，但根据类型是否更改进行不同操作*/
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        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);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}

embstr

当字符串长度小于等于44字节时，使用的是embstr编码。

redis> set a aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK

redis> strlen a
(integer) 44

redis> object encoding a
"embstr"

redis> set a aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK

redis> strlen a
(integer) 45

redis> object encoding a
"raw"

embstr编码的字符串对象，在内存分配的时候会直接分配一整块连续空间，依次包含redisObject和sdshdr。这样内存分配和释放的时候都只需一次，而且对象和数据放在同一内存能更好的访问。

其对象创建代码如下：

robj *createEmbeddedStringObject(const char *ptr, size_t len) {
    /* 一次性分配对象和数据的空间 */
    robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
    /* 获取sdshdr8的首地址 */
    struct sdshdr8 *sh = (void*)(o+1);
    /* 设置对象的字段 */
    o->type = OBJ_STRING;
    o->encoding = OBJ_ENCODING_EMBSTR;
    /* 指向的是buf字段 */
    o->ptr = sh+1;
    o->refcount = 1;
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
    } else {
        o->lru = LRU_CLOCK();
    }
    /* 设置sdshdr8的字段 */
    sh->len = len;
    sh->alloc = len;
    sh->flags = SDS_TYPE_8;
    if (ptr == SDS_NOINIT)
        sh->buf[len] = '\0';
    else if (ptr) {
        memcpy(sh->buf,ptr,len);
        sh->buf[len] = '\0';
    } else {
        memset(sh->buf,0,len+1);
    }
    return o;
}

• 为啥是44字节？

  因为redis使用jemalloc分配内存，可以以8、16、32、64等字节为单位分配内存。在embstr中使用的都是sdshdr8，包含3个固定字节(uint8_t*2+char = 1*2 + 1)，而redisObject占16字节，再加上最后一个\0，于是64-16-3-1 = 44。

redis中没有对embstr编写任何的修改方法，所以embstr是只读的，对其进行修改会将编码方式改为raw。

补充一些sds的函数

最后有一个问题：

为啥sds指向的是buf？

目前看到的稍微靠谱的解答：为了更好的使用C语言中字符串的特性，所以直接指向字符串