作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现（SDS）（二）

作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现（SDS）（一）https://developer.aliyun.com/article/1471143

原理剖析

简单动态字符串（SDS）是Simple Dynamic String的缩写，它是Redis中用于表示字符串的核心数据结构。在Redis中，几乎所有的键（key）都是通过SDS来实现的，体现了其高效和灵活性。

从源码层面分析，SDS的实现细节主要集中在sds.h和sds.c文件中。其中，sds.h定义了SDS的数据结构和相关操作接口，而sds.c则提供了这些接口的具体实现。此外，sdsalloc.h文件也扮演着重要角色，它负责SDS内存分配和释放的管理，确保SDS在动态扩展和收缩时能够高效、安全地使用内存。

通过深入分析sds.h头文件，我们可以发现Redis源码为char*类型定义了一个别名，如下所示：

c

复制代码

#ifndef __SDS_H
#define __SDS_H
#define SDS_MAX_PREALLOC (1024*1024)
extern const char *SDS_NOINIT;
#include <sys/types.h>
#include <stdarg.h>
#include <stdint.h>
typedef char *sds;

这种别名的使用在Redis的源代码中非常普遍，尤其是在处理字符串时。通过将char*重命名为sds，Redis不仅使代码更具可读性，还强调了这些指针实际上是指向动态字符串（SDS）的，而不仅仅是普通的C字符串。

数据结构

SDS是Redis用来表示字符串的核心数据结构，它提供了一种动态调整字符串长度的方式，同时还包含了一些额外的元数据，如字符串的长度和已分配的内存大小，还有一个名为flags的元数据字段，该字段的最低3位用于标识SDS的类型。

在SDS的设计中，为了节省内存并适应不同大小的字符串，Redis定义了五种不同大小的SDS头结构，分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64。

这五种类型的主要区别在于它们如何存储和管理字符数组的两个关键元数据：现有长度（len）和分配空间长度（alloc）。这些元数据的数据类型因SDS类型的不同而有所区别。

以下是sds.h中定义的五种sdshdr结构，它们分别代表了五种不同的SDS数据结构模型：

sdshdr8、sdshdr16、sdshdr32和sdshdr64这些头结构的大小分别为5字节、8字节、16字节、32字节和64字节。选择哪种头结构取决于字符串的实际长度和已分配的内存大小。

__attribute__((__packed__))是一个GCC编译器指令，用于确保结构体在内存中的布局是紧凑的，即没有额外的填充字节。这对于嵌入式系统或需要精确控制内存布局的场景非常有用。

分析结构体

接下来，我们将逐一深入剖析这些结构体。在结构模型的设计中，我们主要将其划分为两大类别：sdshdr5与其他类型。那么，为何要进行这样的分类呢？让我们来一探究竟。

sdshdr5（没有使用）

Redis的源码中并没有使用，因为它只包含一个flags字段和一个Buf字段，没有足够的空间来存储字符串的长度信息。

• Flags字段的低3位用于表示SDS的类型（在这个情况下是5），而高5位被浪费了，没有使用。
• Buf字段是字符数组，用于存储实际的字符串数据。

sdshdr8、sdshdr16、sdshdr32和sdshdr64

sdshdr8、sdshdr16、sdshdr32和sdshdr64这些结构体都包含Len、Alloc、Flags和Buf字段。

• Len字段表示当前字符串使用的长度（不包括末尾的空字符'\0'）。
• Alloc字段表示已分配的内存大小（不包括头信息和末尾的空字符'\0'）。
• Flags字段的低3位用于表示SDS的类型（8、16、32或64），而高5位没有被使用。
• Buf字段是字符数组，用于存储实际的字符串数据。

注意，Len和Alloc字段的大小会根据SDS头结构的大小而变化。在sdshdr8中，这两个字段都是uint8_t类型，而在sdshdr64中，这两个字段都是uint64_t类型。这种设计允许Redis根据字符串的实际大小动态地选择最合适的头结构，从而节省内存。

下面是一个底层存储案例，大家应该可以看到对应的存储模型是什么样子的。

特点分析

• 空字符结尾：SDS遵循C字符串的传统做法，即在字符串末尾添加一个空字符（null terminator），以确保字符串的正确终止。这个空字符所占用的1字节空间并不计算在SDS的len属性中，这意味着对于SDS的使用者来说，这个空字符是完全不可见的。
  
• 额外的分配：为了确保空字符的存在，SDS会自动为其分配额外的1字节空间，并在需要时在字符串末尾添加空字符。这些操作都是由SDS函数自动完成的，因此用户无需关心。
  
• 兼容C方法：SDS可以直接使用C标准库中的头文件所提供的printf函数来展示其内部保存的字符串内容。录例如，通过执行printf("%s", s->buf);语句，可以方便地打印出SDS结构体中buf指针所指向的字符数组。
  

空字符结尾优点

1. SDS能够直接重用C标准库中的一部分字符串函数，从而提高了代码的复用性和可维护性。
2. 空字符的存在也有助于确保字符串的正确性和安全性，防止了越界访问等潜在问题。

特性对比

数据长度分析

sdslen 函数通过解析 SDS 字符串的标志位和头结构来获取字符串的长度，并根据字符串的类型选择相应的计算方式。这种设计允许 Redis 使用不同大小的头结构来存储不同长度的字符串，从而节省内存空间。

c

复制代码

#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
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

这段代码是 Redis 中用于获取 SDS（Simple Dynamic String，简单动态字符串）长度的函数 sdslen 的实现。SDS 是 Redis 用于表示字符串的内部数据结构，它包含了一个长度字段和一个预分配的空间字段，以便在需要时能够快速地扩展或收缩字符串。

分析代码

1. 方法参数以及返回值

• size_t：这是函数的返回类型，表示字符串的长度。
• const sds s：这是函数的参数，s 是一个指向 SDS 字符串的指针。

2. 获取标志位：unsigned char flags = s[-1];* 这行代码从 SDS 字符串的末尾获取标志位。因为 SDS 字符串的实际数据存储在头结构之后，所以通过 s[-1] 可以访问到存储标志位的字节。
3. 判断 SDS 类型并返回长度：switch(flags&SDS_TYPE_MASK)*使用了一个位掩码 SDS_TYPE_MASK来提取标志位中的 SDS 类型信息。SDS_TYPE_MASK 的值通常是一个只有低三位设置为 1 的值（例如 0x07），这样可以将标志位中的类型字段提取出来。

• switch 语句根据提取出来的类型字段的值来选择相应的代码分支，每个分支都返回相应类型 SDS 字符串的长度。

• case SDS_TYPE_5：如果 SDS 类型是 5，则使用 SDS_TYPE_5_LEN(Flags) 来计算字符串的长度。这个宏通常会从标志位中提取出长度信息。
• case SDS_TYPE_8、case SDS_TYPE_16、case SDS_TYPE_32、case SDS_TYPE_64：对于其他类型的 SDS 字符串，通过调用 SDS_HDR(size, s) 宏来获取头结构的指针，然后返回头结构中的 len 字段的值，即字符串的实际长度。

4. 默认返回值：return 0;* 如果 switch 语句中没有匹配到任何类型，函数将返回 0。这通常表示输入的 s 不是一个有效的 SDS 字符串，或者它的类型字段的值不正确。

计算剩余容量

sdsavail 函数用于快速获取 SDS 字符串的剩余容量。该函数的实现基于 SDS 字符串的 alloc（总容量）和 len（已使用长度）字段。通过简单的数学运算 alloc - len，即可得到剩余容量。这种计算方式的时间复杂度为 O(1)，意味着无论 SDS 字符串的长度如何，获取剩余容量的操作都是常数时间复杂度的，因此非常高效。

c

复制代码

static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

简而言之，sdsavail 函数提供了一种快速、简便的方法来查询 SDS 字符串当前剩余的可用空间，这对于需要动态调整字符串大小的应用来说非常有用。

至此，还有还有很多关于SDS源码的其他内容，由于篇幅过长，再次就不过多介绍，本次我们主要是将核心SDS的核心特细和原理以及结构，以及基本的核心方法进行介绍和说明，特别是针对于SDS和C字符串的区别和选择的问题，做了较为深入的介绍和分析。

作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现（SDS）（三）https://developer.aliyun.com/article/1471145