014.SDS

字符串在 Redis 中很常用，键值对中的键是字符串类型，值有时也是字符串类型

Redis 是用 C 语言实现的，但是它没有直接使用 C 语言的 char* 字符数组来实现字符串，而是自己封装了一个名为简单动态字符串（simple dynamic string，SDS）的数据结构来表示字符串

C 语言字符串的缺陷 §

C 语言的字符串就是一个字符数组，char * 指针指向字符数组的起始位置，字符数组的结尾位置用 '\0' 表示

• C 语言的字符串并不记录自身长度，所以获取长度的复杂度为 O(n)
• C 语言的字符串用 '\0' 表示结束，所以只能存放文本数据，不能存放二进制数据
• C 语言的字符串不会记录自身的缓冲区大小，诸如 strcat 等函数会假定程序员已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立，就会发生缓冲区溢出

SDS 结构设计 §

SDS 结构体包含：

• len：字符串长度
  • 获取长度的复杂度为 O(1)
• alloc：分配给字符数组的空间长度
  • 在修改字符串时，不需要手动修改空间大小，也不会缓冲区溢出
  • 因为修改字符串相关 API 会检查空间是否足够，空间不足会自动扩容，扩容规则：
    • 如果所需的长度小于 1 MB，进行翻倍扩容，即 2 * newlen
    • 否则，最后的扩容长度是 newlen + 1MB
• flags：用来表示不同类型的 SDS
  • 一共设计了 5 种类型：sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64
  • 用于节省内存空间
• buf[]：字符数组，用来保存实际数据
  • 不仅可以保存字符串，也可以保存二进制数据
  • SDS 为了兼容部分 C 语言标准库的函数，字符串结尾还是会加上 '\0' 字符

节省内存空间 §

不同类型 flags 的 SDS 其 len 和 alloc 成员变量的数据类型不同（保存小字符串时，结构头占用空间也比较少）

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};
 
 
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc; 
    unsigned char flags;
    char buf[];
};

在 struct 声明 __attribute__ ((packed))，作用是：告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐