Redis(5.0.3)源码分析之sds对象

March 30, 2019
Redis
源码分析
Redis

sds是redis中定义字符串对象，它比C中的字符串类型对象更为高效、安全。

sds额外保存了字符串长度和内存分配大小等信息。获取长度就只用O(1)。
sds对象中可能会包含多余空间，这样可以实现内存预分配和惰性删除，减少系统调用带来的开销。
由于sds记录了长度和剩余可用空间信息，所以strcat类操作也不会导致内存溢出问题。
能够复用C标准库里针对字符串的方法。

《Redis设计与实现》有比较详细介绍sds的使用场景和好处。但里面介绍的sds结构体在新版(5.0.x)中已经不一样了。

1
2
3
4
5
6


// 旧sds结构体
struct sdshdr {
  int len; // buf中已用字节长度
  int free; // buf中未用字节长度
  char buf[] // 存放实际字符串的地方
}

新版代码中提高了sds对内存的利用率，例如两个字节的字符串对应的sds对象，就没必要将len字段定义为int类型了，uint8足够。所以对于不同长度的字符串，实际结构体中len这些字段类型也不同。但sds却对上层使用方保持一致的接口，隐藏底层结构体差异性的细节。

基于5.0.3版本源码

 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的定义
typedef char *sds; // 比较巧妙，sds直接被typedef为char*。那len这些信息存哪？

// 下面sdshdr5\sdshdr8\sdshdr16等等就是针对不同的字符串长度预先给出的sds定义
// __attribute__ ((__packed__)) 的作用是告诉GCC编译器，不要对此结构体做内存对齐。
// 同时看到free字段没了，改成alloc，并增加flags字段

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

但上层代码使用却是sds，是个char*，是怎么提取出len、alloc等字段信息呢？

其实sds是直接指向结构体里的buf数组。当取len等字段信息，只需要减去结构体长度，回退一下指针就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// 获取实际的结构体通过宏实现
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));

static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            // 这里做宏替换
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        // ...
    }
    return 0;
}

创建一个新字符串，怎么判断该选用哪个结构体？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// string_size就是目标字符串长度，比对一下，看用哪个长度的结构体
static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

现在可以看一下，是如何创建一个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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    // 判断该用哪种长度类型的结构体
    char type = sdsReqType(initlen);

    // 虽然有SDS_TYPE_5，但其实不会使用它
    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;
    // 这里fp就是flags字段
    fp = ((unsigned char*)s)-1;
    // 接下来对结构体里的len、alloc、flags字段赋值吧
    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;
        }
        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对象也不例外。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


// 将len字段设置为0，但内存空间不释放。方便下次直接复用
void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

// free方法才是真正释放内容的方法
void sdsfree(sds s) {
    if (s == NULL) return;
    // s[-1]就刚好指向了flags这个字段了
    s_free((char*)s-sdsHdrSize(s[-1]));
}