Redis字符串的实现

当今天在网上寻找Redis字符串的实现相关的文章时，我找到的依然是一堆Redis3时代的文章，大量老旧的sds相关的内容，仿佛无论新旧，Redis的字符串就是这样实现的。但事实上，早在Redis3.2之后，字符串早就不是之前的sds了结构了。那Redis3.2.0是什么时候发布的呢？答：2016年5月，没错，一个已经过时6年的方案，至今天还流行在很多文章之中~

一、Redis3.0时代的字符串

1.sds基本结构

这个基本就不用多说了，在 sds.h 文件内可以看到 sdshdr 的定义

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

len 表示长度，free 表示剩余容量，buf 就是字符串数据。
字符串使用 len 来表示长度，而不是 c 中的以 '\0' 结尾，这样可以保证字符串二进制安全，即字符串内即使有 '\0' 也不会出错，同时也使获取长度的时间复杂度从 O(n) 降到了 O(1)

2.sds字符串拼接

sds字符串的拼接函数在 sds.c 内，较为值得看一下，可以更好的理解下sds结构。

#define SDS_MAX_PREALLOC (1024*1024)
typedef char *sds;

sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *sh;
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len); //先扩容
    if (s == NULL) return NULL;
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);  //将新字符串拷贝到原字符串后
    sh->len = curlen+len;
    sh->free = sh->free-len;

    // 在末尾增加 '\0'
    // 为什么已经有len表示长度了，还要在末尾增加 '\0' 呢？
    // 其实是为了兼容 <string.h> 部分库函数，如 strcasecmp 一类的
    s[curlen+len] = '\0';
    return s;
}

sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s);
    size_t len, newlen;

    if (free >= addlen) return s;    \\如果剩余空间足够，直接返回
    len = sdslen(s);

    // 变量s是sdshdr结构体中buf的指针，所以s-(sizeof(struct sdshdr))其实就是将指针向前移动一个sdshdr的长度，也就是指向了sdshdr结构体的头部。
    // 而将其指向头部的原因就是为了覆盖原有的sdshdr
    sh = (void*) (s-(sizeof(struct sdshdr)));
    newlen = (len+addlen);

    // SDS_MAX_PREALLOC 是1mb，如果新字符串小于1mb，则每次扩容会翻倍，如果大于1mb，每次扩容会在后面在加1mb
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    if (newsh == NULL) return NULL;

    newsh->free = newlen - len; //更新剩余空间大小
    return newsh->buf;
}

所以原有的sds字符串结构可以说很好理解。

二、Redis3.2之后的字符串结构

1.hisds字符串

在查看新版Redis的源码时，我们可以看一以 sds.h 内已经没有原来的 sdshdr 结构体了，取而代之的是 hisdshdr

typedef char *hisds;

/* 注意：hisdshdr5 并未使用 */
struct __attribute__ ((__packed__)) hisdshdr5 {
    unsigned char flags; /* 低三位表类型，高五位表长度 */
    char buf[];
};
struct __attribute__ ((__packed__)) hisdshdr8 {
    uint8_t len;
    uint8_t alloc; /* 不包括头部和结尾的 '\0' */
    unsigned char flags; /* 低三位表类型，高五位未使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) hisdshdr16 {
    uint16_t len;
    uint16_t alloc;
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) hisdshdr32 {
    uint32_t len;
    uint32_t alloc;
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) hisdshdr64 {
    uint64_t len;
    uint64_t alloc;
    unsigned char flags;
    char buf[];
};

我们可能看到，hisdshdr 并不是一个结构体，而是多个。
__attribute__ ((__packed__)) 表示结构体不使用内存对齐。
举个例子:

struct A {
    int dat;
    char buf[];
}

请问上面的结构体占用了几个字节？
int 为 32 位，需要4个字节，而 char[] 则只是指向第一个字符，所以只需要1个字节，那结构体A应该占用5个字节。
然后我们 sizeof 一下试试，结果竟然是 8
原因就是内存对齐，char[] 会和 int 对齐，使其也占用了4个字节。
__attribute__ ((__packed__)) 则表示该结构体不使用内存对齐。

struct __attribute__ ((__packed__)) A {
    int dat;
    char buf[];
}

此时的 A 在 sizeof 一下，结果就是5了。

2.hisds字符串的拼接

为了进一步了解hisds，我们在来看看它的拼接函数，和sdshdr的拼接有何不同。

#define HI_SDS_TYPE_5  0
#define HI_SDS_TYPE_8  1
#define HI_SDS_TYPE_16 2
#define HI_SDS_TYPE_32 3
#define HI_SDS_TYPE_64 4
#define HI_SDS_TYPE_BITS 3 // flag中表示类型的位数，只有低三位表示类型
#define HI_SDS_TYPE_MASK 7 // 只有低三位表类型，所以使用00000111 & flag 来取类型

// 通过 s 返回 hisdshdr 即 hisds 的头部指针，hisdshdr##T 表示将参数 T 转成文本
// 例如：HI_SDS_HDR(8,s) hisdshdr##T 即会变成 hisdshdr8
#define HI_SDS_HDR(T,s) ((struct hisdshdr##T *)((s)-(sizeof(struct hisdshdr##T))))

// 由于 hisdshdr5 中，使用flag的高5位表示长度，所以它的长度是 flag >> 3
#define HI_SDS_TYPE_5_LEN(f) ((f)>>HI_SDS_TYPE_BITS

hisds hi_sdscatlen(hisds s, const void *t, size_t len) {
    size_t curlen = hi_sdslen(s);

    s = hi_sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    hi_sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

static inline void hi_sdssetlen(hisds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&HI_SDS_TYPE_MASK) {
        case HI_SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = (unsigned char)(HI_SDS_TYPE_5 | (newlen << HI_SDS_TYPE_BITS));
            }
            break;
        case HI_SDS_TYPE_8:
            HI_SDS_HDR(8,s)->len = (uint8_t)newlen;
            break;
        case HI_SDS_TYPE_16:
            HI_SDS_HDR(16,s)->len = (uint16_t)newlen;
            break;
        case HI_SDS_TYPE_32:
            HI_SDS_HDR(32,s)->len = (uint32_t)newlen;
            break;
        case HI_SDS_TYPE_64:
            HI_SDS_HDR(64,s)->len = (uint64_t)newlen;
            break;
    }
}

和之前sdscatlen的函数相比，新的 hi_sdscatlen 基本没太大变化。
其中的 hi_sdsMakeRoomFor 函数即使我们不看，也能猜到其是用于扩容的，那我们一会在看它。
与之前相比，hi_sdscatlen 还用了一个 hi_sdssetlen 替代了之前直接设置len和free的代码。

而 hi_sdssetlen 的定义则比较有趣。首先，s[-1]来获取flag，因为 s 正是 hisdshdr 中的 char buf[] 而它的上一个字段正是 unsigned char flag 所以可以直接用 s[-1]的方式拿到 flag。
然后通过 flag 判断类型，并设置新的长度。

现在呢，我们在来看看 hi_sdsMakeRoomFor 虽然我们知道这个函数是扩容用的，但也要看看它的实现

hisds hi_sdsMakeRoomFor(hisds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = hi_sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & HI_SDS_TYPE_MASK;
    int hdrlen;

    /* 如果剩余空间足够，则直接返回 */
    if (avail >= addlen) return s;

    len = hi_sdslen(s);
    sh = (char*)s-hi_sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < HI_SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += HI_SDS_MAX_PREALLOC;
    
    /* 通过新长度判断新类型 */
    type = hi_sdsReqType(newlen);

    /* 不使用 hisdshdr5 */
    if (type == HI_SDS_TYPE_5) type = HI_SDS_TYPE_8;

    hdrlen = hi_sdsHdrSize(type);
    /* 如果头部类型没变，那直接在原内存上重写 */
    if (oldtype==type) {
        newsh = hi_s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* 如果头部类型变了，那它所需的空间也会变化，所以需要重新分配内存空间 */
        newsh = hi_s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        hi_s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        hi_sdssetlen(s, len); //设置长度
    }
    hi_sdssetalloc(s, newlen); //设置剩余空间
    return s;
}

可以看到，hi_sdsMakeRoomFor 的逻辑和 sdsMakeRoomFor 是基本一致的，但部分位置不同。
比如，长度扩展都是一样的，如果小于1mb，每次扩容则翻倍，如果大于1mb，则每次只增加1mb。
但不同的是，hisds 需要通过新长度判断类型。即 type = hi_sdsReqType(newlen);
比如当新长度大于 256，那就要换用 hisdshdr16 来表示了。其它同理。
而 hi_sdsReqType 就是最简单的大小判断。定义如下：

static inline char hi_sdsReqType(size_t string_size) {
    if (string_size < 32)
        return HI_SDS_TYPE_5;
    if (string_size < 0xff)
        return HI_SDS_TYPE_8;
    if (string_size < 0xffff)
        return HI_SDS_TYPE_16;
    if (string_size < 0xffffffff)
        return HI_SDS_TYPE_32;
    return HI_SDS_TYPE_64;
}

其实Redis的代码并不多，也很好理解，只需要几个实例就基本可以窥其一二，通过理解拼接函数，我们基本可以看懂大部分的sds中的代码了。

三、结语

相对而言，hisds也只是头部变了，本身和 sds 并没有太大区别。那为什么Redis要这么改？
其实答案就是为了剩那一捏捏的内存~
一个 sdshdr 占多少内存？
len 和 free 都是 uint ,各占4个字节；
buf 是 char[] 占1个字节，但由于sdshdr是内存对齐的，所以也占了4个字节；
也就是说，sdshdr占了12个字节。

那 hisdshdr 占多少字节呢？
hisdshdr8 的话，len 和 alloc 都是 uint8，各占1个字节；
flag 是 char 类型，占1个字节；
buf 是 char[] 类型，占1个字节；
也就是说，hisdshdr8 只占用 4个字节。同理，hisdshdr16占用6个字节，hisdshdr32占用10个字节，hisdshdr64占用18个字节。
所以 hisdshdr 不仅可以表达更长的uint64位长度的字符串，而且在一般情况下还只占用更小的内存。

所以说，Redis也真不愧是一个把内存省到极致的工具~