2.redis数据结构t_string：广泛使用的sds

1. sds基本结构

​
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[];
};

注意：这里的buf是不占空间的，比如下面的test，求sizeof是0，后面指针的运算都有这个前提在里面

typedef struct test{
    char buf[];
};

首先sds在redis里面直接被typedef成了char，也就是说sds就是char，并且在字符串结尾还会追加\0，在c语言里面，默认的字符串就是这样定义的，所以redis为了能直接复用一些库函数，把sds定义成了char*一样的规则。

但是sds是支持预先分配大小，并且当空间没用完的时候进行原地的扩容。于是，redis在sds的前面定义了一个head，但是实际暴露的是字符串的起始位置。

2. 三种编码

2.1 整数编码OBJ_ENCODING_INT

redis中用的最多的应该就是sds了，最基础的数据结构，下面看下这个sds是如何实现的。

上一节讲到redisObject，数据结构如下：

struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
};

redis的string为了优化节省内存，当string保存的是数字的时候，是直接用ptr存的，相比ptr指向一个sds减少了一次额外的内存分配，这是string的OBJ_ENCODING_INT编码方式。

2.2 紧凑内存编码OBJ_ENCODING_EMBSTR

为了更好的命中cpu缓存，redis的字符串有一种紧凑的编码格式，redisObject和sds一起分配内存，减少了ptr的寻址过程，优点就是有更好的数据局部性，提升cpu的cache命中。

2.3 原始编码OBJ_ENCODING_RAW

redis的string还有一个常规的编码，和紧凑编码唯一区别就是ptr指向的内存不是在ptr指针之后的，而且可能在任意的内存地址。

3. 创建sds

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    // 根据需要的长度计算用什么sds的head
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    // sds5 已经不使用了，全部转成sds8
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    // 计算sds的head的长度
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    size_t usable;
​
    // 防止溢出
    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    // 分配内存 = sds的head + 字符串长度 + 结束字符1
    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)
        // 初始化内存为0
        memset(sh, 0, hdrlen+initlen+1);
    // 获取字符串起始位置，除去sds的head后的
    s = (char*)sh+hdrlen;// buf的位置，因为buf不占空间，所以s就是buf
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    // 初始化sds头部
    switch(type) {
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        /*....*/
    }
    if (initlen && init)
        // 如果传入了字符串，需要拷贝过来，用memcpy直接拷贝内存，不使用strcpy，效率更高
        memcpy(s, init, initlen);
    // 最后一个\0，兼容c的原始字符串
    s[initlen] = '\0';
    // 返回的是字符串的起始位置，不是头部的起始位置
    return s;
}

所有的创建字符串都会走到这里，大概逻辑如下

1. 根据长度选择合适的sds头部
2. 分配sds头部+字符串长度+1的内存，初始化头部信息
3. 如果需要根据另外一个字符串初始化，进行内存拷贝（不是字符串拷贝），内存拷贝效率更高
4. 最后添加\0
5. 返回buf处的地址（字符串的起始位置）

4. 字符串的扩容

redis的字符串可以预留空间，也可以进行扩容，函数是_sdsMakeRoomFor

/*
 * 扩容sds
 * addlen 需要扩大的长度
 * greedy=1 会分配比需要的更大的空间，
 * 新长度小于SDS_MAX_PREALLOC的，分配两倍，
 * 大于SDS_MAX_PREALLOC的，分配SDS_MAX_PREALLOC的冗余空间
 */
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    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);
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {
        // 分配冗余空间
        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. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
​
    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    if (oldtype==type) {
        // sds的head没有变化， realloc就行
        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 */
        // sds 的head 变化了，字符串的位置因为head的长度变化，会发生偏移，所以需要重新拷贝下字符串的位置，并且重新分配head的每个字段
        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;
}

sds的扩容，大概有以下几点

1. 新长度小于1024*1024，会进行二倍扩容
2. 大于10241020，会额外分配10241020作为冗余空间
3. 检查sds的头部需不需要重新分配
4. 需要重新分配的话，重新申请一块内存，把数据拷贝过去，因为原来的长度字段已经装不下新的长度了，这就需要把数据全部往后挪动
5. 不需要重新分配head，就使用realloc进行扩容内存