鲤鱼笔记

简单动态字符串 SDS

2021-05-15 Redis Redis 原理

SDS，全称「Simple Dynamic Strings」，译作「简单动态字符串」，是 Redis 中最基本的数据结构之一，用于存储字符串和整型数据。

SDS 兼容 C 语言标准字符串及其处理函数，且在此基础上保证了二进制安全。下面将详细讲解 SDS 的实现，为后面理解 Redis 的原理和各种命令的实现打下基础。

# 一、预备知识

# 1.1 什么是二进制安全？

通俗地讲，C 语言中，用 "\0" 表示字符串的结束，如果字符串中本身就有 "\0" 字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则是二进制安全。

# 二、数据结构

在 Redis 中，SDS 根据字符串的长短定义了 5 种数据结构，分别叫 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，其结构体如下。

sdshdr5：

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 低三位存类型, 高五位存长度 */
    char buf[]; /* 柔性数组，存放实际内容 */
};
1
2
3
4

sdshdr8：

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已使用长度，用 1 字节存 */
    uint8_t alloc; /* 总长度，用 1 字节存 */
    unsigned char flags; /* 低三位存类型, 高五位预留 */
    char buf[]; /* 柔性数组，存放实际内容 */
};
1
2
3
4
5
6

sdshdr16：

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* 已使用长度，用 2 字节存 */
    uint16_t alloc; /* 总长度，用 2 字节存 */
    unsigned char flags; /* 低三位存类型, 高五位预留 */
    char buf[]; /* 柔性数组，存放实际内容 */
};
1
2
3
4
5
6

sdshdr32：

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* 已使用长度，用 4 字节存 */
    uint32_t alloc; /* 总长度，用 4 字节存 */
    unsigned char flags; /* 低三位存类型, 高五位预留 */
    char buf[]; /* 柔性数组，存放实际内容 */
};
1
2
3
4
5
6

sdshdr64：

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* 已使用长度，用 8 字节存 */
    uint64_t alloc; /* 总长度，用 8 字节存 */
    unsigned char flags; /* 低三位存类型, 高五位预留 */
    char buf[]; /* 柔性数组，存放实际内容 */
};
1
2
3
4
5
6

sdshdr5 的结构较简单，后四种结构体中 4 个字段的具体含义如下：

  • len：表示 buf 中已占用的字节数；
  • alloc：表示 buf 中已分配的字节数，记录的是 buf 分配的总长度；
  • flags：标识当前结构体的类型，低三位存类型, 高五位预留；
  • buf：柔性数组，真正存储字符串的数据空间。

从上面结构体的定义可以看出，这 4 种结构的成员变量类似，唯一的区别是 len 和 alloc 的类型的区别。

注意

结构体中最后的一个元素 buf 是个柔性数组，通过对该数组首地址作 “减一” 操作，能很方便地定位到 flags。

之所以分成这么多个结构体，是因为对于不同长度的字符串，用来表示长度的 len 和分配长度的 alloc 可以用不同的类型来表示，这样可以对空间的使用做一些节约，比如 uint8_t 的长度比 uint32_t 少了 3 字节。虽然每个字符串节约的内存看起来微不足道，但在实际应用中，字符串是海量的，那么就可以节省很多内存。

此外，这样设计还有以下几个优点：

  1. 有单独的统计变量 len 和 alloc（称为头部），可以很方便地得到字符串长度。
  2. 内容存放在柔性数组 buf 中，SDS 对上层暴露的指针不是指向结构体 SDS 的指针，而是直接指向柔性数组 buf 的指针。上层可像读取 C 字符串一样读取 SDS 的内容，兼容 C 语言处理字符串的各种函数。
  3. 由于有长度统计变量 len 的存在，读写字符串时不依赖 "\0" 终止符，保证了二进制安全。

下面来详细看一下这几种 sdshdr 的结构，sdshdr8、sdshdr16、sdshdr32 和 sdshdr64 的结构相同，sdshdr16 结构如下所示。

sdshdr5 则做了进一步的压缩，用 flags 中预留的 5 位存长度，把 len 和 alloc 也省掉了，其结构如下所示。

在 Redis 的源代码中，对类型的宏定义如下：

#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
1
2
3
4
5

源码中的 __attribute__((__packed__)) 需要重点关注。一般情况下，结构体会按其所有变量大小的最小公倍数做字节对齐，而用 packed 修饰后，结构体则变为按 1 字节对齐。

以 sdshdr32 为例，修饰前按 4 字节对齐，大小为 12 字节；修饰后按 1 字节对齐，注意 buf 是个 char 类型的柔性数组，地址连续，始终在 flags 之后。packed 修饰前后示意图如下所示。

这样做有以下两个好处：

  1. 节省内存，例如 sdshdr32 可节省 3 个字节；
  2. SDS 返回给上层的，不是结构体首地址，而是指向内容的 buf 指针 s。修饰后，无论是 sdshdr8、sdshdr16 还是 sdshdr32，都能通过 s[-1] 快速找到 flags，因为此时按 1 字节对齐。若没有 packed 的修饰，还需要对不同结构做处理，实现更复杂。

# 三、基本操作

# 3.1 创建字符串

Redis 通过 sdsnewlen 函数创建 SDS。在函数中会根据字符串长度选择合适的类型，初始化完相应的统计值后，返回指向字符串内容的指针：

点击查看代码 
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);  // 根据字符串长度选择不同的类型
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;  // 创建空字符串时，SDS_TYPE_5 强制转化为 SDS_TYPE_8
    int hdrlen = sdsHdrSize(type);  // 计算不同头部所需的长度
    unsigned char *fp;  // 指向 flags 的指针

    sh = s_malloc(hdrlen+initlen+1);  // "+1" 是为了结束符 '\0'
    if (sh == NULL) return NULL;
    if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen;  // s 即是指向 buf 的指针
    fp = ((unsigned char*)s)-1;  // s 是柔性数组 buf 的指针，-1 即指向 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;
}
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

注意

Redis 在 3.2 版本后的 SDS 结构由一种增至五种，且对于 sdshdr5 类型，在创建空字符串时会强制转换为 sdshdr8。 这可能是出于以下考虑：创建空字符串后，其内容可能会频繁更新，引发扩容，故创建时直接创建为 sdshdr8。

创建 SDS 的大致流程为：首先计算好不同类型的头部以及初始长度，然后动态分配内存。这里有三处需要注意：

  1. 创建空字符串时，SDS_TYPE_5 被强转成了 SDS_TYPE_8；
  2. 长度计算时有 "+1" 的操作，是为了算上结束符 "\0"；
  3. 返回值是指向 SDS 结构 buf 字段的指针，兼容部分 C 函数，且可通过偏移量快速定位其他成员变量。

# 3.2 释放字符串

Redis 通过 sdsfree 函数释放字符串占的内存，该方法通过对 s 的偏移，可定位到 SDS 结构的首部，取出长度 len，然后调用 s_free 进行内存的释放：

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));  // 定位到 SDS 首部，直接释放内存
}
1
2
3
4

为了优化性能（减少申请内存的开销），SDS 提供了不直接释放内存，而是通过重置统计值达到清空目的的方法：sdsclear。该方法仅将 SDS 的 len 归零，此处已存在的 buf 并没有真正被清除，新的数据可以覆盖写，而不用重新申请内存。

void sdsclear(sds s) {
    sdssetlen(s, 0);  // 统计值 len 清零
    s[0] = '\0';  // 清空 buf
}
1
2
3
4

# 3.3 拼接字符串

字符串拼接是字符串的常用操作，SDS 中具体函数是 sdscatsds，见代码：

sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}
1
2
3

sdscatsds 是暴露给上层的方法，其最终调用的是函数 sdscatlen。由于其中可能涉及 SDS 的扩容，sdscatlen 中调用 sdsMakeRoomFor 对待拼接的字符串 s 容量做了检查，若无须扩容则直接返回 s；若需要扩容，返回的则是扩容好的新字符串。

/* 将指针 t 的内容和指针 s 的内容拼在一起，该操作是二进制安全的 */
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;
}
1
2
3
4
5
6
7
8
9
10
11

注意

函数中的 len、curlen 等长度值是不含结束符的，而拼接时又用 memcpy 将两个字符串拼接在一起，指定了相关长度，故这一过程保证了二进制安全。最后需要加上结束符以保持兼容。

下面来看 sdsMakeRoomFor 的实现。

点击查看代码 
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;

    if (avail >= addlen) return s;  // 如果无需扩容，直接返回

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);

    /* 
     * SDS_MAX_PREALLOC 这个宏的值是 1MB
     *
     * - 新增后总长度 len+addlen 小于 1MB 的，按新长度的 2 倍扩容；
     * - 新增后总长度 len+addlen 大于 1MB 的，按新长度加上 1MB 扩容。*/
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /* SDS_TYPE_5 的结构不支持扩容，所以这里需要强制转成 SDS_TYPE_8 */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        /* 无须更改类型，通过 realloc 扩大柔性数组即可，注意这里指向 buf 的指针 s 被更新了 */
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* 扩容后数据类型发生了变化，头部长度发生了变化，此时不再 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;  // 偏移 SDS 的长度，得到字符串起始地址
        s[-1] = type;  // flags 属性赋值
        sdssetlen(s, len);  // len 属性赋值
    }
    sdssetalloc(s, newlen);  // alloc 属性赋值
    return s;
}
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

可以看到，扩容逻辑可分为两个部分，分别是容量计算规则和扩容对象的选择，下面进行说明。

容量计算规则

  • 扩容后长度小于 1MB：按新长度的 2 倍扩容；
  • 扩容后长度超过 1MB：按新长度加上 1MB 扩容。

扩容对象的选择

  • SDS 类型未改变：通过 realloc 扩大柔性数组；
  • SDS 类型发生变化：开辟新内存，拼接完内容后，释放旧指针。

# 3.4 其余 API

函数名 说明
sdsempty 创建一个空字符串，长度为 0，内容为 ""
sdsnew 根据给定的 C 字符串创建 SDS
sdsdup 复制给定的 SDS
sdsupdatelen 手动刷新 SDS 的相关统计值
sdsRemoveFreeSpace 与 sdsMakeRoomFor 相反，对空闲过多的 SDS 做缩容
sdsAllocSize 返回给定 SDS 当前所占用的内存大小
sdsgrowzero 将 SDS 扩容到指定长度，并用 0 填充新增内容
sdscpylen 将 C 字符串复制到给定 SDS 中
sdstrim 从 SDS 两端清除所有给定的字符
sdscmp 比较两个给定 SDS 的实际大小
sdssplitlen 对 SDS 按给定的分隔符进行切分

# 四、总结

本文介绍了 SDS 的数据结构及基本 API 的实现。在源码分析过程中，我们可以知道 SDS 的以下特性是如何实现的：

  • SDS 如何保证二进制安全？

    SDS 对象中的 buf 是个柔性数组，上层调用时，SDS 直接返回了 buf。由于 buf 是直接指向内容的指针，故它兼容 C 语言函数。而当真正读取内容时，SDS 会通过 len 来限制读取长度，而非 "\0"，这保证了二进制安全。

  • sdshdr5 的特殊之处？

    sdshdr5 只负责存储小于 32 字节的字符串。因为一般业务场景下，短字符串的存储更普遍，故 Redis 进一步压缩了 sdshdr5 的数据结构，将 sdshdr5 的类型和长度放进了同一个属性中，用 flags 的低 3 位存类型，高 5 位存长度。需要注意的是，创建空字符串时，sdshdr5 会被 sdshdr8 所替代。

  • SDS 是如何通过扩容的？

    SDS 在涉及字符串修改处会调用 sdsMakeroomFor 函数进行检查，根据不同情况动态扩容，这一操作对上层透明。

# 五、参考资料

  • 《Redis 5 设计与源码分析》– 陈雷
Last Updated: 2023-01-28 4:31:25

跳跃表 SkipList