Redis 字符串

介绍和分析Redis数据类型sds。

基本结构

在redis中，字符串的基本结构如下，其中，len表示字符串的长度，alloc表示字符串的最大容量，flags表示header的类型。

1
2
3
4
5
6
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已占用buf长度 */
    uint8_t alloc; /* 申请的buf长度 */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

buf表示需要存储的字符数组，数组的长度为len+1（由于需要存储一个结束符’\0’）。

具体结构如下，

类型

除了上面提到的sdshdr8，还包含sdshdr5、sdshdr16、sdshdr32、sdshdr64。

在读取字符串时，首先需要获取当字符串的存储类型，

1
2
3
4
5
6
7
8
9
10
11
12
13
// 类型 - flags取值
#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

// 用来获取字符串内容
#define SDS_TYPE_MASK 7 
#define SDS_TYPE_BITS 3
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

其中，SDS_HDR和SDS_HDR_VAR可以从sds字符串中获取header的起始位置。

函数实现

sds包含很多功能，

1
2
3
4
5
6
7
8
sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
void sdsfree(sds s);
sds sdsgrowzero(sds s, size_t len);
sds sdscatlen(sds s, const void *t, size_t len);
...

这里只详细介绍下初始化和追加函数，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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); // 申请内存空间：header长度+buf长度+1
    if (!init)
        memset(sh, 0, hdrlen+initlen+1); // 全部设置为0
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen; // 获取buf指针位置
    fp = ((unsigned char*)s)-1; // 获取类型flag字段
    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;
        }
        ...
    }
    if (initlen && init)
        memcpy(s, init, initlen); // 拷贝数据
    s[initlen] = '\0'; // buf最后一位置为'\0'
    return s;
}

为sds增加可用空间，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;

    /* 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) // 2倍的新长度
        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); // 如果类型发生改变，则重新申请新类型数据，并拷贝buf数据
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

sds与普通string的区别

获取字符串长度复杂度

string获取字符串长度的时间复杂度为O(N)，需要遍历整个字符串；而sds不再需要遍历字符串，通过len字段可以直接获取存储在buf内字符串的长度，时间复杂度为O(1)。

空间分配和释放

对于C语言来说，每一次字符串长度的增加，都会造成一次内存分配的操作；每一次字符串长度的减少，都会造成一次内存释放操作。如果redis同样需要平凡的内存分配和释放，对性能会造成严重的影响。

sds通过alloc字段来记录预分配空间的大小，len字段来记录当前存储字符串的长度。

当有资源需要释放时，sds只是减少len的大小；当需要增加空间时，只有当剩余的空位不足，才会重新申请新的空间，否则只需要增加len的大小。