SDS 详解

[toc]

为什么Redis没有使用C语言中的字符串？

  • 获取字符串长度需要运算
  • 非二进制安全：C语言字符串的结束标志是’\0’，如果字符串中间出现了’\0’，读取就会提前结束
  • 不可修改：字面值存储在字符串常量池中，不可修改

C语言的字符串底层都是字符数组char[]，例如

1
2
char* s = "hello"
// 底层是{'h','e','l','l','o','\0'},其中'\0'是结束标志

因此，Redis实现了SDS（Simple Dynamic String）- 简单动态字符串。

sds优点：
  • 获取字符串长度的的时间复杂度为O(1)
  • 支持动态扩容
  • 减少了内存分配次数
  • 二进制安全
sds结构体：
1
2
3
4
5
6
7
8
9
10
11
12
13
struct __attribute__ ((__packed__)) sdshdr8 {// sdshdrx:x字节头部的SDS结构体，各种结构体支持的长度和内存分配不同,以8为示例
    uint8_t len; 	// buf[]数组已经保存的字符串字节数，不包含结束标志符（uint64_t: unsigned int 68bit;）
    // 所以sdshdr64支持的字符串最大长度为2^8-1-1个字节（因为buf中也有\0要多减1）
    uint8_t alloc; 	// buf[]申请的总字节数，不包含结束标志符
    unsigned char flags; // 不同SDS的头类型，用来控制SDS的头大小
    char buf[];		// 字符数组，保存了SDS的实际数据
};
// flags实际取值
#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

以实际字符串”name”为例，它用sds8即可存储，结构如下：

image-20240913181310379

  • 其中’\0’是为了兼容C语言字符串，也使得它可以使用C语言字符串的函数。
sds扩容

假设有一个初始sds，内容为”hi”，如下图

image-20240913181535065

现在我们要给它追加”,Amy”，显然需要申请新的空间。检查新字符串大小：

  • 如果新字符串小于1M，新的空间为拓展后字符串的2倍+1，如图：
    • 具体地，”hi,Amy”长度为6，因此len为6，新空间为6*2+1=13，但这个13包含了’\0’，而alloc不包含，所以alloc为12；长度还没达到flags=1表示的最大值，因此flags仍为1.

image-20240919173241500

  • 如果新字符串大于1M，新的空间为拓展后字符串+1M+1，这是内存预分配
    • 因为分配内存需要进行用户态到内核态的状态转变，因此预分配可以减少后续再次追加字符串导致的状态切换。
sds API

//TODO