redis设计与实现——字符串

发表于

简单动态字符串

Redis没有使用C语言传统的以空字符结尾的字符串表示，而是自己构造了一种名为简单动态字符串(simple dynamic string，SDS)的抽象类型。

除了在诸如打印日志等无需对字符串进行修改的地方使用C字符串之外，其它场合一般使用SDS。其优点：

  • 使用起来更加简单；
  • 二进制安全；
  • 计算效率高；
  • 兼容普通的C字符串函数；

SDS的定义

在sds.h/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
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[];
};

这里flags的低三位表示类型(是sdshdr8还是16)，高五位没被使用；len记录当前字节数组长度，alloc记录当前字节数组分配的内存大小，都不包含'\0'；buf保存真实字符串的值，以及结尾的'\0'。

这里使用了attribute ((packed))，它的作用是编译器取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐。我们可以打印出字节长度分别为：

1
2
3
4
sizeof(struct sdshdr8)  // 3->3, result of llvm
sizeof(struct sdshdr16) // 6->5
sizeof(struct sdshdr32) // 12->9
sizeof(struct sdshdr64) // 24->17

SDS与C字符串的区别

常数复杂度获取字符串长度

这一点得益于结构体重的len字段，与C字符串不同，redis获取字符串长度的复杂度从O(N)降到O(1)。

杜绝缓冲区的溢出

C库中有一个<string.h>/strcat函数可以将两个字符串进行拼接，但C库中这个函数是假设使用者为目的字符串分配了足够多的内存，否则会产生缓冲区溢出。

与C字符串不同，SDS使用了另外的拼接函数：sdscatlen

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
 * end of the specified sds string 's'.
 *
 * 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 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;
}

这里的关键是sdsMakeRoomFor函数，其它部分只是做一些内存拷贝和长度的重新设置。

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
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
  	// sdsavail: 获取可用长度，这里的s是指向buf的，通过buf进行寻址
  	// 获取头部(结构体)指针：#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
  	// sdsavail的计算方式：sh->alloc - sh->len;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK; // s-1就是flags
    int hdrlen;

    /* 有足够的空间就可以直接返回 */
    if (avail >= addlen) return s;

    len = sdslen(s); // O(1)获取字符串长度
    sh = (char*)s-sdsHdrSize(oldtype);// 获取头部(结构体)指针
    newlen = (len+addlen);// 新的字符串使用长度
  	// 新字符串小于1M时，预分配两倍空间
  	// 新字符串大于1M时，预分配多1M的空间
    if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC (1024*1024)
        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. */
  	// SDS_TYPE_5直接按SDS_TYPE_8来计算
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);// 新类型的长度
  	
    if (oldtype==type) { 
      	// #define s_realloc realloc
      	// 如果类型没变化，直接在原sds上重新分配内存
        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 */
      	// 如果类型发生了变化，则重新malloc分配空间
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);// 将原字符串内容拷贝到新开辟的内存中
        s_free(sh); // 释放原sds内存
      	// 设置flag，len和alloc等字段
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

这里的关键策略是针对不同长度的字符串做不同的分配策略：

  • 新字符串小于1M时，预分配两倍空间
  • 新字符串大于1M时，预分配多1M的空间

另外就是不使用SDS5，将其当作SDS8来使用。

由于redis可能出现频繁修改字符串的场景，这种预分配的策略可以使得SDS将连续增长N次字符串所需要的内存重分配次数从必定N次降低为最多N次。

减少修改字符串时带来的内存重分配次数

字符串的创建

直接看源码：

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
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. */
		
  	// +1是因为字符串都以'\0'结尾，但其又是二进制安全的，即字符串中间可以出现字符'\0'，因为sds有长度属性
    sh = s_malloc(hdrlen+initlen+1);
    if (init==SDS_NOINIT) // const char *SDS_NOINIT = "SDS_NOINIT";
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL; // 如果sh是NULL，直接返回NULL
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1; // fp就是flag指针
    switch(type) {
        case SDS_TYPE_5: {
          	// #define SDS_TYPE_BITS 3
          	// flag的前五位保存长度，后三位是类型type，因此结构体中sdshdr5不含有len
            *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'; // 以'\0'结尾
    return s;
}

这里有两个特殊的地方：一是sds都以'\0'结尾；二是sdshdr5用flag这个字段可以同时保存type和len。

惰性空间的释放

惰性空间的释放主要体现在SDS字符串的缩短操作，redis中的sdstrim提供了这样的一个操作：sdstrim 函数接受一个 SDS 和一个 C 字符串作为参数，从 SDS 左右两端分别移除所有在 C 字符串中出现过的字符（《redis设计与实现》一书有误）。源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;
    ep = end = s+sdslen(s)-1;
  	// 分别从头尾开始便利，即移除掉cset中的字符
    while(sp <= end && strchr(cset, *sp)) sp++; 
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    if (s != sp) memmove(s, sp, len); //内存拷贝，即将中间段的字符串拷贝到头部指针
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
}
// s="AA...AA.a.aa.aHelloAWorld     :::" ->sdstrim(s,"Aa. :")-> "HelloAWorld"

由此，可以看到sdstrim并没有释放原空间，即alloc不变，变的是len。这样后续再需要扩展的时候，len后的空间能够再被利用。

事实上，redis的确提供了释放空间的函数：

1
2
3
4
5
/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1])); // #define s_free free
}

二进制的安全

这里的关键是SDS是使用len属性的值而不是空字符来判断字符串是否结束，这种二进制安全的做法使得redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。

兼容部分C字符串的函数

这是基于SDS遵循了C字符串以空字符串结尾的惯例，这些API都会将SDS保存的又用数据的末尾保存位空字符。