Redis底层数据结构-简单动态字符串SDS

简单动态字符串（simple dynamic string，SDS）。Redis没有直接使用C语言传统的字符串，而是自己构建了一种简单动态字符串(SDS)的抽象类型。C字符串只会作为字符串字面量（string literal）用在一些无须对字符串值进行修改的地方。

实现

sds.h/sdshdr

struct __attribute__ ((__packed__)) sdshdr<T> {
    // 记录buf数组中已使用字节的数量,等于SDS所保存字符串的长度
    T len;
    // 字符数组的已分配空间，不包括结构体和\0结束字符
    T alloc;
    // SDS 类型sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64
    unsigned char flags;
    // 柔性数组，用于保存字符串 (空间长度为alloc+1)，\0结尾
    char buf[];
};

• __attribute__ ((__packed__))是用来告诉编译器不要对结构体进行默认的对齐优化，而是按照结构体成员在内存中实际占用的字节数进行紧凑排列的一个特性。
• 柔性数组（Flexible Array Member）是 C 语言中的一个特性，它允许在结构体的末尾定义一个大小不定的数组。这种数组的大小可以在运行时动态确定，并且紧跟在结构体的末尾，没有指定数组大小的语法（即不指定具体的元素个数）。
• \0空字符，SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，所以这个空字符对于SDS的使用者来说是完全透明的。但SDS使用len属性的值而不是空字符来判断字符串是否结束。

flags

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

因为 sdshdr5 这一类型 Redis 已经不再使用了，举例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 字节。

优化

flags 不同类型

SDS 之所以设计不同的结构头（即不同类型），是为了能灵活保存不同大小的字符串，从而有效节省内存空间。

结构体内存紧凑

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

#include <stdio.h>
  int main() {
     struct s1 {
        char a;   // 占用 1 个字节
        int b;    // 占用 4 个字节
     } ts1;
     printf("%lu\n", sizeof(ts1));     // 打印为8
     return 0;
  }

这就是因为在默认情况下，编译器会给 s1 结构体分配 8 个字节的空间，而这样其中就有 3 个字节被浪费掉了。

所以，Redis 采用了 __attribute__ ((__packed__))属性定义结构体，结构体实际占用多少内存空间，编译器就分配多少空间。

空间预分配

空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。

• 如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，即alloc=len*2。
  • 举个例子，如果进行修改之后，SDS的len将变成13字节，那么程序也会分配13字节的未使用空间，SDS的buf数组的实际长度将变成13+13+1=27字节（额外的一字节用于保存空字符）。
• 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。
  • 举个例子，如果进行修改之后，SDS的len将变成30MB，那么程序会分配1MB的未使用空间，SDS的buf数组的实际长度将为30MB+1MB+1byte。

通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。

扩容策略总结：字符串修改后，如果字符串长度小于1MB，则空间加倍分配。如果长度大于1MB，为了避免冗余空间过大，则只增加1MB的冗余空间。

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是通过alloc与len属性将这些字节的数量记录起来，并等待将来使用。

通过惰性空间释放策略，SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。与此同时，SDS也提供了相应的API，让我们可以在有需要时，真正地释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

对于C字符串的区别与优化

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

C字符串不记录自身的长度信息，所以求len()需要遍历，复杂度为O(N)。

SDS则直接读取len字段的值。复杂度为O(1)。设置和更新SDS长度的工作是由SDS的API在执行时自动完成的，使用SDS无须进行任何手动修改长度的工作。

STRLEN：即使我们对一个非常长的字符串键反复执行STRLEN命令，也不会造成任何性能影响。

杜绝缓冲区溢出

C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow）。

例如<string.h>/strcat函数可以将src字符串中的内容拼接到dest字符串的末尾。

char *strcat(char *dest, const char *src);

因为C字符串不记录自身的长度，所以strcat假定用户在执行这个函数时，已经为dest分配了足够多的内存，可以容纳src字符串中的所有内容，而一旦这个假定不成立时，就会产生缓冲区溢出。

而SDS在拼接时，会先校验，如果容量不够会先进行扩容，然后再进行拼接。

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

因为C字符串并不记录自身的长度，所以对于一个包含了N个字符的C字符串来说，这个C字符串的底层实现总是一个N+1个字符长的数组（额外的一个字符空间用于保存空字符）。因为C字符串的长度和底层数组的长度之间存在着这种关联性，所以每次增长或者缩短一个C字符串，程序都总要对保存这个C字符串的数组进行一次内存重分配操作！

• 如果程序执行的是增长字符串的操作，比如拼接操作（append），那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小----如果忘了这一步就会产生缓冲区溢出。
• 如果程序执行的是缩短字符串的操作，比如截断操作（trim），那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间----如果忘了这一步就会产生内存泄漏。

为了避免C字符串的这种缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联：

在SDS中，buf数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的alloc属性记录。

• 增长字符串，空间预分配，额外分配空间，为再次增长做预备。
• 缩短字符串，惰性空间释放空间暂不回收，为再次增长做预备。

二进制安全

SDS使用len属性的值而不是空字符来判断字符串是否结束。

C字符串中的字符必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

为了确保Redis可以适用于各种不同的使用场景，SDS的API都是二进制安全的（binary-safe），所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。

这也是我们将SDS的buf属性称为字节数组的原因——Redis不是用这个数组来保存字符，而是用它来保存一系列二进制数据。

通过使用二进制安全的SDS，而不是C字符串，使得Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。

兼容部分C字符串函数

虽然SDS的API都是二进制安全的，但它们一样遵循C字符串以空字符结尾的惯例：这些API总会将SDS保存的数据的末尾设置为空字符，并且总会在为buf数组分配空间时多分配一个字节来容纳这个空字符，这是为了让那些保存文本数据的SDS可以重用一部分<string.h>库定义的函数。

embstr vs raw

Redis 的字符串有两种存储方式，在长度特别短时，使用 emb 形式存储 (embeded)，当长度超过 44 时，使用 raw 形式存储。

这两种类型有什么区别呢？为什么分界线是 44 呢？

注意上面 debug object 输出中有个 encoding 字段，一个字符的差别，存储形式就发生了变化。这是为什么呢？

为了解释这种现象，我们首先来了解一下 Redis 对象头结构体，所有的 Redis 对象都有下面的这个结构头:

struct RedisObject {
    int4 type; // 4bits
    int4 encoding; // 4bits
    int24 lru; // 24bits
    int32 refcount; // 4bytes
    void *ptr; // 8bytes，64-bit system
} robj;

不同的对象具有不同的类型 type(4bit)，同一个类型的 type 会有不同的存储形式 encoding(4bit)，为了记录对象的 LRU 信息，使用了 24 个 bit 来记录 LRU 信息。每个对象都有个引用计数，当引用计数为零时，对象就会被销毁，内存被回收。ptr 指针将指向对象内容 (body) 的具体存储位置。这样一个 RedisObject 对象头需要占据 16 字节的存储空间。

接着我们再看 SDS 结构体的大小，在字符串比较小时，Redis3.2之后针对短字符串的embstr使用最小的sdshdr8，SDS 对象头的大小是buf长度 + 3，至少是 3。意味着分配一个字符串的最小空间占用为 19 字节 (16+3)。

struct SDS {
    int8 alloc; // 1byte
    int8 len; // 1byte
    int8 flags; // 1byte
    char buf[]; // 内联数组，长度为 alloc+1
}

如图所示，embstr 存储形式是这样一种存储形式，它将 RedisObject 对象头和 SDS 对象连续存在一起，使用 malloc 方法一次分配。而 raw 存储形式不一样，它需要两次 malloc，两个对象头在内存地址上一般是不连续的。

而内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等，为了能容纳一个完整的 embstr 对象，jemalloc 最少会分配 32 字节的空间，如果字符串再稍微长一点，那就是 64 字节的空间。如果总体超出了 64 字节，Redis 认为它是一个大字符串，不再使用 emdstr 形式存储，而该用 raw 形式。

当内存分配器分配了 64 空间时，那这个字符串的长度最大可以是多少呢？64-19为45字节，再去掉字符串中以字节\0结尾的一字节，正好为44字节。

API

• sds.h
• sds.c

应用

• 保存数据库中的字符串
• 缓冲区（buffer）AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区

总结

• Redis 只会使用 C 字符串作为字面量， 在大多数情况下， Redis 使用 SDS （Simple Dynamic String，简单动态字符串）作为字符串表示。

• 比起 C 字符串， SDS 具有以下优点：

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

  • 杜绝缓冲区溢出。

  • 减少修改字符串长度时所需的内存重分配次数。

  • 二进制安全。

  • 兼容部分 C 字符串函数。

参考：《Redis设计与实现-黄健宏》、《Redis深度历险-钱文品》、《Redis核心技术与实战-蒋德钧》