Based on Redis 7.0.11.

SDS 定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
typedef char *sds;

#define SDS_TYPE_5  0   // 0b0000
#define SDS_TYPE_8  1   // 0b0001
#define SDS_TYPE_16 2   // 0b0010
#define SDS_TYPE_32 3   // 0b0011
#define SDS_TYPE_64 4   // 0b0100
#define SDS_TYPE_MASK 7 // 0b0111
#define SDS_TYPE_BITS 3 

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
  • len: 字节数组内容长度，不含结尾空字符 \0。
  • alloc: 字节数组长度，不含结尾空字符 \0。
  • flags: SDS 类型，由字节数组长度在创建 SDS 时决定，目的是节省 len 和 alloc 空间。flags 的 3 lsb（最低有效位）存储 SDS_TYPE_N，除 sdshdr5 将 5 msb（最高有效位）存储字节数组长度外，其余的都没具体用途。
  • buf: 字节数组。柔性数组，sizeof(sdshdrxx) 得到的 hdrlen 不包含柔性数组大小。

typedef char *sds; 定义了 SDS 方法接收对象，实际上指向的是 buf，这样可以方便执行 print("%s", sds);。访问其它结构体成员时，先通过 #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) 拿到结构体指针，再访问。

相比 C 字符串优点

  1. O(1) 复杂度计算内容长度

  2. 避免缓冲区溢出
    比如 strcat(s1, s2)，如果 s1 和 s2 在内存中相邻排布：

    1
    2
    3
    4
     s1               s2
    +-+-+-+-+-+-+-+--+-+-+-+-+-+-+--+
    |A|B|C|D|E|F|G|\0|0|1|2|3|4|5|\0|
    +-+-+-+-+-+-+-+--+-+-+-+-+-+-+--+

    strcat 假定 s1 已被分配足够内存，如果这个假定不成立，就会发生缓冲区溢出，s2 的内容被意外修改。

  3. 减少内存分配释放次数

    1. 空间预分配。对 SDS 修改并需要拓展字节数组时，出了分配必要空间外，还会额外分配一块预留空间，预留空间大小一般与 len 大小一样，最大 1M（#define SDS_MAX_PREALLOC (1024*1024)）。
    2. 空间懒回收。当缩短 SDS 时，只会即时更新 len，不会立即释放多出来的空间。

  4. 二进制安全。C 字符串通过 \0 确定字符串长度，不适用于字符串外的其它数据格式，比如图片等。SDS 通过 len 确定长度，理论上字节数组可以存储任意二进制内容。

  5. 兼容部分 C 字符串函数。SDS 虽然不依赖 \0 确定内容长度，但还是会在 buf 尾部加上一个 \0，兼容部分 C 字符串函数。

关于 SDS 内存重新分配，核心是 realloc 函数：

The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be unchanged in the range from the start of the region up to the minimum of the old and new sizes. If the new size is larger than the old size, the added memory will not be initialized. If ptr is NULL, then the call is equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not NULL, then the call is equivalent to free(ptr). Unless ptr is NULL, it must have been returned by an earlier call to malloc(), calloc(), or realloc(). If the area pointed to was moved, a free(ptr) is done.

简单说就是 realloc 完成了内存分配、内存拷贝以及内存释放等动作。

Key takeaways

sds.h

《Redis 设计与实现》