21
文章
7
分类
13
标签

redis源码阅读--动态字符串

由于char类型的功能单一，抽象层次比较低，且无法高效支持一些Redis常用的操作（追加操作和长度计算操作），所以redis内部程序大多数时候会使用sds动态字符串类型而并不是char表示。

Redis中的字符串

c语言中，字符串本质为一个使用\0结尾的char数组来表示。
但是这种形式无法支持长度计算和追加操作：

  • 每次计算字符串长度的复杂度为O(N)
  • 对字符串进行N次追加，必定需要对字符串进行N次内存重分配

但是在redis内部，字符串的追加长度和长度计算很常见，而APPEND和STRLEN更是这两种操作，在Redis命令中的直接映射，这两个简单的操作不应该成为性能的瓶颈。而且，Redis除了处理C字符串之外，还需要处理单纯的字节数组，以及服务器协议等，所以为了方便与安全，Redis的字符串表示应该是二进制安全的：程序不应该对字符串里面保存的数据做任何假设，即数据可以是以\0结尾的C字符串，也可以是单纯的字节数组，或者其他格式的数据。
基于此，Redis使用sds类型替换了C语言的默认字符串表示：sds既可以高效地追加和长度计算，同时也是二进制安全的。

sds实现

sds实现主要由两部分构成，第一部分是单纯的c中的char*:

1
typedef char *sds;

第二部分则为其涉及的具体sds数据类型，一共有5种：

结构体类型 作用
sdshdr5 保存5位长度字符串（不再使用）
sdshdr8 保存8位长度字符串
sdshdr16 保存16位长度字符串
sdshdr32 保存32位长度字符串
sdshdr64 保存64位长度字符串

在这些结构中整体都可以提取为以下几个字段：

1
2
3
4
5
6
struct sdshdr{
    len ; 
    alloc ;
    buf[] ;
    flags ;
}

这三个字段所表示的含义为：len代表buf的字符串长度，alloc代表整体的分配空间，buf为实际保存字符串数据的地方，flags保存了字符串的具体数据类型。
整体来看，我们就可以这样去理解整个sds的结构，类型sds是char*的别名，而结构sdshdr则保存了len、alloc、buf、flags四个属性。
使用这个结构来保存helloworld：

1
2
3
4
5
struct sdshdr{
    len = 11;
    alloc = 11;
    buf = {'h','e','l','l','o','w','o','r','l','d','\0'};
}

由此我们就可以理解，redis是怎么优化读取len的速度了。直接读取sdslen属性就可以实现时间复杂度为θ(1) 的长度计算操作。另一点，通过对buf分配一些额外的空间，sdshdr 可以让执行追加操作所需的内存重分配次数大大减少。

字符串追加操作的优化

其实由前面的结构已经可以看出来了，这里实际上是redis在执行append操作时会进行一个内存预先分配的策略，如果内存足够就无需再次分配内存从而提高效率，减少重新分配内存的策略。这个套路好多编程语言软件在其动态数组或者说线性表的结构都会使用，java中的List,Go中的切片等等都有使用。
redis这里sds的分配策略实际是通过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
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. */
    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_MAX_PREALLOC那么为字符串分配2倍于所需长度的空间，否则就分配所需长度加上SDS_MAX_PREALLOC数量的空间。最后的一系列操作就是确认新的sds类型重新分配空间。
在目前版本的 Redis 中， SDS_MAX_PREALLOC 的值为 1024 * 1024 ， 也就是说， 当大小小于 1MB 的字符串执行追加操作时， sdsMakeRoomFor 就为它们分配多于所需大小一倍的空间； 当字符串的大小大于 1MB ， 那么 sdsMakeRoomFor 就为它们额外多分配 1MB 的空间。

最后

对于redis来说，其内部字符串的实现采用sds来实现。我们从sds这一内部结构开始阅读redis的源代码，其数据类型结构部分与其余地方耦合度比较少，阅读起来还是比较容易的。
总结一下，sds大概的特点如下：

  • Redis 的字符串表示为 sds ，而不是 C 字符串（以 \0 结尾的 char*）。
  • 对比 C 字符串， sds 有以下特性：
    • 可以高效地执行长度计算（strlen）；
    • 可以高效地执行追加操作（append）；
    • 二进制安全；
  • sds 会为追加操作进行优化：加快追加操作的速度，并降低内存分配的次数，代价是多占用了一些内存，而且这些内存不会被主动释放。