字符串
- SDS设计思想(简单动态字符串)
- SDS的内部使用

字符串

字符串的实现需要考虑操作高效、能保存任意二进制数据，以及节省内存的需求

C语言字符串 —- char字符数组一块连续的内存空间，依次存放了字符串中的每一个字符。字符数组的最后一个字符是“\0”，char 指针只是指向字符数组的起始位置，而字符数组的结尾位置就用“\0”指字符串的结束。 strlen 函数就是一种字符串操作函数，它可以返回一个字符串的长度。这个函数会遍历字符数组中的每一个字符，并进行计数，直到检查的字符为“\0”。此时，strlen 函数会停止计数，返回已经统计到的字符个数如果我们要保存的数据中，本身就有“\0”，那么数据在“\0”处就会被截断，而这就不符合 Redis 希望能保存任意二进制数据的需求了。

SDS设计思想(简单动态字符串)

一个字符数组 buf[]，用来保存实际数据。

三个元数据

字符数组现有长度 len、操作效率高：获取长度O(1)复杂度二进制安全：可存储包含 \0 的数据
分配给字符数组的空间长度 alloc
SDS 类型 flags。

其中，Redis 给 len 和 alloc 这两个元数据定义了多种数据类型，进而可以用来表示不同类型的 SDS。

创建SDS

Redis 源码SDS 的定义，使用 typedef 给 char* 类型定义了一个别名sds，如下所示：

typedef char *sds;

同时，在创建新的字符串时，Redis 会调用 SDS 创建函数 sdsnewlen。
sdsnewlen 函数会新建 sds 类型变量（也就是 char* 类型变量兼容 C 字符串函数,直接用API），并新建 SDS 结构体，把 SDS 结构体中的数组 buf[] 赋给 sds 类型变量。
最后，sdsnewlen 函数会把要创建的字符串拷贝给 sds 变量。下面的代码就显示了 sdsnewlen 函数的这个操作逻辑


sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;  //指向SDS结构体的指针
    sds s;     //sds类型变量，即char*字符数组

    ...
    sh = s_malloc(hdrlen+initlen+1);   //新建SDS结构，并分配内存空间
    ...
    s = (char*)sh+hdrlen;              //sds类型变量指向SDS结构体中的buf数组，sh指向SDS结构体起始位置，hdrlen是SDS结构体中元数据的长度
    ...
    if (initlen && init)
        memcpy(s, init, initlen);    //将要传入的字符串拷贝给sds变量s
    s[initlen] = '\0';               //变量s末尾增加\0，表示字符串结束
    return s;
}

追加函数

Redis 中实现字符串追加的函数是 sds.c 文件中的 sdscatlen 函数。这个函数的参数一共有三个，分别是目标字符串 s、源字符串 t 和要追加的长度 len，

首先，获取目标字符串的当前长度，并调用 sdsMakeRoomFor 函数，根据当前长度和要追加的长度，判断是否要给目标字符串新增空间。这一步主要是保证，目标字符串有足够的空间接收追加的字符串。
其次，在保证了目标字符串的空间足够后，将源字符串中指定长度 len 的数据追加到目标字符串。
最后，设置目标字符串的最新长度。


sds sdscatlen(sds s, const void *t, size_t len) {
    //获取目标字符串s的当前长度
    size_t curlen = sdslen(s);
    //根据要追加的长度len和目标字符串s的现有长度，判断是否要增加新的空间
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    //将源字符串t中len长度的数据拷贝到目标字符串结尾
    memcpy(s+curlen, t, len);
    //设置目标字符串的最新长度：拷贝前长度curlen加上拷贝长度
    sdssetlen(s, curlen+len);
    //拷贝后，在目标字符串结尾加上\0
    s[curlen+len] = '\0';
    return s;
}

内存开销优化

sds.c 的 sdsMakeRoomFor 函数:
内存预分配策略，目标字符串的空间检查和扩容，并且在涉及字符串空间变化的操作中，如追加、复制等，会直接调用该函数。
这一设计实现，就避免了开发人员因忘记给目标字符串扩容，而导致操作失败的情况。比如，我们使用函数 strcpy (char dest, const char src) 时，如果 src 的长度大于 dest 的长度，代码中我们也没有做检查的话，就会造成内存溢出。

另外 Redis 在操作 SDS 时，为了避免频繁操作字符串时，每次「申请、释放」内存的开销，还做了这些优化：
- 内存预分配：SDS 扩容，会多申请一些内存（小于 1MB 翻倍扩容，大于 1MB 按 1MB 扩容）
- 多余内存不释放：SDS 缩容，不释放多余的内存，下次使用可直接复用这些内存
这种策略，是以多占一些内存的方式，换取「追加」操作的速度。

紧凑型内存布局

SDS 中是通过设计不同 SDS 类型来表示不同大小的字符串，并使用attribute ((packed))这个编程小技巧，来实现紧凑型内存布局，达到节省内存的目的。

SDS 结构中有一个元数据 flags，表示的是 SDS 类型。事实上，SDS 一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。这 5 种类型的主要区别就在于，它们数据结构中的字符数组现有长度 len 和分配空间长度 alloc，这两个元数据的数据类型不同。

因为 sdshdr5 这一类型 Redis 已经不再使用了，所以我们这里主要来了解下剩余的 4 种类型。以 sdshdr8 为例，它的定义如下所示：


struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 字符数组现有长度*/
    uint8_t alloc; /* 字符数组的已分配空间，不包括结构体和\0结束字符*/
    unsigned char flags; /* SDS类型*/
    char buf[]; /*字符数组*/
};

我们可以看到，现有长度 len 和已分配空间 alloc 的数据类型都是 uint8_t。uint8_t 是 8 位无符号整型，会占用 1 字节的内存空间。当字符串类型是 sdshdr8 时，它能表示的字符数组长度（包括数组最后一位\0）不会超过 256 字节（2 的 8 次方等于 256）。而对于 sdshdr16、sdshdr32、sdshdr64 三种类型来说，它们的 len 和 alloc 数据类型分别是 uint16_t、uint32_t、uint64_t，即它们能表示的字符数组长度，分别不超过 2 的 16 次方、32 次方和 64 次方。这两个元数据各自占用的内存空间在 sdshdr16、sdshdr32、sdshdr64 类型中，则分别是 2 字节、4 字节和 8 字节。实际上，SDS 之所以设计不同的结构头（即不同类型），是为了能灵活保存不同大小的字符串，从而有效节省内存空间。因为在保存不同大小的字符串时，结构头占用的内存空间也不一样，这样一来，在保存小字符串时，结构头占用空间也比较少。否则，假设 SDS 都设计一样大小的结构头，比如都使用 uint64_t 类型表示 len 和 alloc，那么假设要保存的字符串是 10 个字节，而此时结构头中 len 和 alloc 本身就占用了 16 个字节了，比保存的数据都多了。所以这样的设计对内存并不友好，也不满足 Redis 节省内存的需求。

除了设计不同类型的结构头，Redis 在编程上还使用了专门的编译优化来节省内存空间。在刚才介绍的 sdshdr8 结构定义中，我们可以看到，在 struct 和 sdshdr8 之间使用了attribute ((packed))

struct __attribute__ ((__packed__)) sdshdr8

其实这里，attribute ((packed))的作用就是告诉编译器，在编译 sdshdr8 结构时，不要使用字节对齐的方式，而是采用紧凑的方式分配内存。这是因为在默认情况下，编译器会按照 8 字节对齐的方式，给变量分配内存。也就是说，即使一个变量的大小不到 8 个字节，编译器也会给它分配 8 个字节。

为了方便你理解，我给你举个例子。假设我定义了一个结构体 s1，它有两个成员变量，类型分别是 char 和 int，如下所示：


  #include <stdio.h>
  int main() {
     struct s1 {
        char a;
        int b;
     } ts1;
     printf("%lu\n", sizeof(ts1));
     return 0;
  }

虽然 char 类型占用 1 个字节，int 类型占用 4 个字节，但是如果你运行这段代码，就会发现打印出来的结果是 8。这就是因为在默认情况下，编译器会给 s1 结构体分配 8 个字节的空间，而这样其中就有 3 个字节被浪费掉了。为了节省内存，Redis 在这方面的设计上可以说是精打细算的。所以，Redis 采用了attribute ((packed))属性定义结构体，这样一来，结构体实际占用多少内存空间，编译器就分配多少空间。比如，我用attribute ((packed))属性定义结构体 s2，同样包含 char 和 int 两个类型的成员变量，代码如下所示：


  #include <stdio.h>
  int main() {
     struct __attribute__((packed)) s2{
        char a;
        int b;
     } ts2;
     printf("%lu\n", sizeof(ts2));
     return 0;
  }

当你运行这段代码时，你可以看到，打印的结果是 5，表示编译器用了紧凑型内存分配，s2 结构体只占用 5 个字节的空间。好了，总而言之，如果你在开发程序时，希望能节省数据结构的内存开销，就可以把attribute ((packed))这个编程方法用起来。

SDS的内部使用

SDS 字符串在 Redis 内部模块实现中也被广泛使用，你能在 Redis server 和客户端的实现中，找到使用 SDS 字符串的地方么？

1、Redis 中所有 key 的类型就是 SDS（详见 db.c 的 dbAdd 函数）

2、Redis Server 在读取 Client 发来的请求时，会先读到一个缓冲区中，这个缓冲区也是 SDS（详见 server.h 中 struct client 的 querybuf 字段）

3、写操作追加到 AOF 时，也会先写到 AOF 缓冲区，这个缓冲区也是 SDS （详见 server.h 中 struct client 的 aof_buf 字段）

数据存储

Redis数据结构