Simple Dynamic String

Posted on

Sds(Simple Dynamic String) 是redis底层所使用的字符串

1.1 用途

  • 实现字符串对象
  • 替代 char* 类型

1.2 结构

sds如下所示，只是普通的char指针

1
typedef char *sds

而 redis 使用[sds header(sdshdr) + char *] 的形式来存放一个字符串

sdshdr 存放的是字符串的相关信息, 一共有5种不同的类型

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

之所以有5种，是为了能让不同长度的字符串可以使用不同大小的header。这样，短字符串就能使用较小的header，从而节省内存, 这点我们可以从每一种header中的 len 的类型可以看出

在每一个 sdshdr[n] 中，最后一个成员是一个柔性数组(flexible array)buf，该数组相当于一个标志，并不占用该结构体的空间，在某些编译器下，柔性数组的使用方式是声明一个长度为0的数组 a[0]

在sdshdr的声明中，有个编译选项 __attribute__ ((__packed__)) 在加入该选项之后，结构体就不会进行对齐，而是紧凑压缩，结构体的大小等于内部成员的大小之和

1.3 相关的宏

1
2
3
4
5
#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)
  • SDSHDRVAR(T,s) : 声明一个sdshdr的结构体指针sh，指向s所在的sdshdr
  • SDSHDR(T,s) : 获得s所在的sdshdr，不声明变量
  • SDSTYPE5LEN : 获得sdshdr5的长度，sdshdr5的长度在flags里面，flags有8位，前3位作为类型，后5位作为长度，详情见 sdshdr 的注释

1.4 相关操作

1.4.1 获取sds的长度

由于flag的前三位是sds的长度, 因此，首先要获得sdshdr的flags，s[-1]获得的正是flags，随后将flags与SDSTYPEMASK进行按位与操作，获得flags的前三位，得到该sdshdr的类型

之所以进行按位与操作，是因为sdshdr5的特殊性

之后，根据不同的sdstype使用SDSHDR来进行相应的sdshdr获取(主要是不同的type，len和alloc的类型不同，因此需要进行不同距离的指针偏移)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

1.4.2 获得sds的容量

由于预分配策略，除了sdstype5外的其他sds的容量并不等于当前长度，因此要使用sdsalloc获取sds的容量，操作与sdslen差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}

1.4.3 其他类似的函数

1
2
3
4
static inline size_t sdsavail(const sds s) //获取剩余长度，用alloc - len
static inline void sdssetlen(sds s, size_t newlen) //重新设置长度
static inline void sdsinclen(sds s, size_t inc) //增加长度
static inline void sdssetalloc(sds s, size_t newlen) //重新设置容量
  • Q:重新设置长度/容量为什么不需要重新分配空间？
  • A:因为这些函数的功能只是修改某个属性，真正对内存空间进行修改的是调用它们的函数

1.4.4 核心操作

使用现有字符串创建新的字符串

该函数的使用方式为 mystring = sdsnewlen("abc", 3);

该函数使用 sdsReqType 获取现有字符串 init 的 sdstype , 该函数利用字符串的长度进行类型的选择

然后利用 sdsHdrSize 获取相应 sds hdr 的长度(也就是 sizeof(sds hdr type))

接着调用 s_malloc(zmalloc) 为整个 sds(sds hdr + char *) 分配内存

在 zmalloc 中，先调用 malloc 进行内存的分配，如果分配失败则中断程序，如果分配成功则精确地更新 used_memory 变量维护实际分配的内存大小

为什么要说精确的呢？因为 malloc 会在分配内存的时候进行内存对齐，因此我们可能分配到的内存会比我们想要的内存大那么一些，因此需要对多出来的部分进行一个计算然后才能更细全局的已分配内存大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void *zmalloc(size_t size) {
    void *ptr = malloc(size+PREFIX_SIZE); //尝试分配内存

    if (!ptr) zmalloc_oom_handler(size); //oom(out of memory) 错误, 打印错误，程序终止

    /*
    #define update_zmalloc_stat_alloc(__n) do { \
    size_t _n = (__n); \
    if (_n&(sizeof(long)-1)) _n += sizeof(long)-(_n&(sizeof(long)-1)); \
    atomicIncr(used_memory,__n); \
    } while(0)
    */

    //下面更新used_memory变量
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_alloc(zmalloc_size(ptr)); 
        return ptr;
#else
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)ptr+PREFIX_SIZE;
#endif
}

接下来检查 sds，如果 sds 不是空指针而且不等于 SDS_NOINIT ，那么就将所分配的空间进行清零

然后根据 init 的 sds hdr 类型填充所分配的空间的 sds hdr 部分，最后拷贝 init 所指向的字符串

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/* Create a new sds string with the content specified by the 'init' pointer
 * and 'initlen'.
 * If NULL is used for 'init' the string is initialized with zero bytes.
 * If SDS_NOINIT is used, the buffer is left uninitialized;
 *
 * The string is always null-termined (all the sds strings are, always) so
 * even if you create an sds string with:
 *
 * mystring = sdsnewlen("abc",3);
 *
 * You can print the string with printf() as there is an implicit \0 at the
 * end of the string. However the string is binary safe and can contain
 * \0 characters in the middle, as the length is stored in the sds header. */
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); //实际调用的是zmalloc

    //检查init
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;

    //获取sds hdr位置
    s = (char*)sh+hdrlen;

    //获取flags的地址，为sds type 5的flags填充作准备
    fp = ((unsigned char*)s)-1;

    //往sdshdr中写入字符串的相关信息
    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;
}
扩容

扩容的话其实需要注意的就是 sdshdr 类型在扩容之后的改变

如果 sdshdr 没有改变，那么就使用 realloc 直接修改内存大小

如果改变了，那么就重新设置新的 sdshdr

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
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)
        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. */

     // 因为type5不支持剩余长度，因此使用type8
    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;
}
回收 sds 中的未使用空间

既然是回收空间，那么修改的地方就是 sdshdr

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
/* Reallocate the sds string so that it has no free space at the end. The
 * contained string remains not altered, but next concatenation operations
 * will require a reallocation.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
    size_t len = sdslen(s);
    //获得剩余的长度
    size_t avail = sdsavail(s);
    //获得sdshdr的位置
    sh = (char*)s-oldhdrlen;

    /* Return ASAP if there is no space left. */
    if (avail == 0) return s;

    /* Check what would be the minimum SDS header that is just good enough to
     * fit this string. */
    //以字符串的真实长度为参数，获取该长度所对应的sdshdr
    type = sdsReqType(len);
    hdrlen = sdsHdrSize(type);

    /* If the type is the same, or at least a large enough type is still
     * required, we just realloc(), letting the allocator to do the copy
     * only if really needed. Otherwise if the change is huge, we manually
     * reallocate the string to use the different header type. */
     //由于原先的长度>=新的长度，那么原先的hdr也是完全够用的
     //那么就检查新的sdshdr类型是否太小，比如比SDS_TYPE8还小，如果太小那么就没有必要使用那么大的sdshdr，而是重新分配
    if (oldtype==type || type > SDS_TYPE_8) {
        newsh = s_realloc(sh, oldhdrlen+len+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+oldhdrlen;
    } else {
        newsh = s_malloc(hdrlen+len+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, len);
    return s;
}