Redis源码阅读一:简单动态字符串SDS

2019-12-14 | 阅读：次

C字符串缺点
SDS结构体
- 3.0版本的SDS
- 5.0版本的SDS
相关操作函数
- 创建
- 释放
- 拼接

源码阅读基于Redis5.0.9

C字符串缺点

redis 127.0.0.1:6379> SET dbname redis
OK
redis 127.0.0.1:6379> GET dbname
"redis"

从上面的例子可以看到，key为dbname的值是一个字符串“redis” Redis源码是用c写成，但并没有使用c的字符串。c的字符串有以下缺点：

没有储存字符串长度的变量，获取长度只能靠遍历字符串
扩容麻烦。没有相应保护，容易造成缓冲区溢出
更新字符串需要重新分配内存

addr	value
0x0	s
0x1	t
0x2	r
0x3	1
0x4	‘\0’
0x5
0x6
0x7
0x8	a
0x9	b
0xa	‘\0’

解释下2,3点。上图是一段连续的内存，保存了字符串”str1”和“ab”。如果我们用strcat函数，拼接一个“append”在“str1”后面，就会对“ab”产生影响。造成内存的破坏。同样的道理，想要更新字符串，同时又不造成溢出，只能重新分配一段内存。普通的应用程序，上面的操作是可以接受的。但是redis作为数据库，经常增删改查，加上对速度有一定需求，所以没有使用C字符串。这里补充一个二进制安全的概念：C语言中’\0’表示字符串结束。如果字符串本身含有’\0’，那么读取的时候就会造成字符串截断，那么是非二进制安全。如果通过某些机制能保证读取字符串时不损害其中内容，则是二进制安全。

SDS结构体

SDS是Simple Dynamic String的缩写。我们先从redis3.0的实现看起。

3.0版本的SDS

/*
 * 指向 sdshdr 的 buf 成员
 */
typedef char *sds;

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

buf是柔性数组，属于C99标准，具体可参考https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html sds指向buf，通过偏移可以很容易得到sdshdr的地址，即s-(sizeof(struct sdshdr)),进而可以得到len和free的值 3.2版本前的SDS是这样设计的。不仅通过len成员使字符串读取不依赖于’\0’终止，解决了二进制安全问题，而且sds指向的对象buf可以利用C的字符串函数处理。

5.0版本的SDS

到了4.0版本，SDS进行了改进。我们可以看到，3.0版本的SDS，不管buf实际存了几个字节，在64位机器上len和free各占用了4字节。实际可能并不需要占用8字节去记录buf信息，我们可以利用位存储这些信息，实现压缩。例如，buf长度为14(0b1110)，那么我们用4个bit就能表示长度。一个char足够

改进的SDS根据buf的可能最大长度，分成了下面几种类型

#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

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

sdshdr5的flags成员低三位用来表示类型，值可以看宏定义。高5位用来表示buf的长度。所以sdshdr5最大可以表示2^5-1=31位字符(最后一个字符必定是’\0’)。对于超过31字符的buf，就参考了之前3.0SDS的设计,len定义一样，free改成了alloc表示最大容量。

除了sdshdr5，剩下的定义只有长度的区别，成员是一样的。

buf[] 实际存储字符的数组
len 字符串长度
alloc 最大容量。等于sizeof(buf)-1,因为字符串最后一位固定是’\0’。比如sdsnewlen(“abc”,3),len和alloc都是3,而buf的大小是4
flags 低3位是类型，高5位保留

关于该结构体，还需要注意2点：

__attribute__ ((packed))是为了让编译器以紧凑的方式分配内存，否则编译器可能会对结构体的成员进行对齐。对这里不太明白的可以看看struct大小的计算
结构体的最后定义了char buf[]; 这个字段只能作为结构体的最后一个成员。上文提到过，C语言中被称为柔性数组，只是作为一个标记，不占用内存空间。如果明白了以上2点，应该能算出sizeof(sdshdr32)=4+4+1=9Byte

相关操作函数

创建

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    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;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;  //s指向buf
    fp = ((unsigned char*)s)-1;  // buf[-1]，即flag
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);  // 左移3bit置位
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);  // struct sdshdr8 *sh = (void*)((s)-(sizeof(struct sdshdr8)));
            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';
    return s;
}

注意几点：

SDS_TYPE_5类型的空串会被转成SDS_TYPE_8
实际分配内存时，大小是hdrlen+initlen+1，那个1是因为要以’\0’结尾
返回的指针指向的是buf，而不是sdshdr

释放

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

// 软删除，长度置0.方便追加不必再分配空间
void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

拼接

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 sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

sdsMakeRoomFor确保s的buf能够追加进len长度的字符。如果buf剩余空间不够的话会进行扩容。扩容规则：原来字符长度加上追加字符长度如果小于1M，那么alloc翻倍；否则alloc+1M 如果扩容后的type变了，那么需要一个新的sdshdr；否则更改下len和alloc即可

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);  // alloc - len,即3.0sds的free
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

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

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);  // 原来字符长度加上追加字符长度
    if (newlen < SDS_MAX_PREALLOC)  // 小于1M
        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);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        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(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;
}

pusidun