redis底层数据结构 - 简单动态字符串sds

redis底层数据结构是什么

redis为用户提供了五种基本数据类型：字符串(string)、列表(list)、哈希(hash)、集合(set)、有序集合(zset)

这些对用户提供的数据类型，都是基于底层数据结构来实现的

它们的关系如图：

简单动态字符串sds

redis底层是使用c语言进行编写的，redis的string没有直接使用c字符串，而是自己构建了简单动态字符串(simple dynamic string，sds)的抽象类型，作为string的底层实现

这是什么原因呢？我们先了解下c字符串

c字符串

在c语言中，字符串实际上是使用空字符 '\0' 结尾的一维字符数组

空字符(Null character)又称结束符，缩写NUL，是一个数值为0的控制字符，'\0' 是转义字符，意思是告诉编译器，这不是字符0，而是空字符

c字符串的两种表现形式：

// 形式一
char site[7] = {'R', 'U', 'N', 'O', 'O', 'B', '\0'};
// 形式二
char site[] = "RUNOOB";

c字符串存在的问题

c字符串存在以下问题：

1. O(N)时间复杂度获取字符串长度。c字符串并不记录自身的长度信息，所以为了获取一个c字符串的长度，程序需要遍历整个字符串，对遇到的每个字符进行计数，直到遇到空字符 '\0' 结束
2. 二进制不安全。除字符串的末尾外，字符串里面不能包含空字符 '\0'，否则最先被程序读入的空字符将被误认为是字符串结尾，这使得c字符串只能保存文本数据，不能保存图片、视频、音频等格式的二进制数据
3. 每修改一次字符串长度，就需要进行一次内存分配
4. 执行字符串增长操作时，存在缓冲区溢出风险。strcat(s1，s2)函数可以连接字符串s2到字符串s1的末尾，strcat函数假定用户在执行这个函数时，已经为s1分配了足够的内存，可以容纳s2字符串的内容，当这个假定不成立时，就会产生缓冲区溢出

执行函数

strcat(s1, "java")

没有为s1分配足够的内存，则发生缓冲区溢出

1. 执行字符串缩短操作时，存在内存泄露风险。对字符串进行截断操作时，程序需要通过内存重分配来释放字符串不再使用的那部分内存空间，如果忘了释放，就会造成内存泄露

将"redis"截断为"red"，没有释放对应的内存，则发生内存泄露

3.2.0以前的sds

正是因为c字符串存在以上的问题，redis的string没有直接使用c字符串，而是自己构建了简单动态字符串(simple dynamic string，sds)的抽象类型，作为string的底层实现

在3.2.0以前的版本，sdshdr结构如下

struct sdshdr {
    // 已使用的字节数
    unsigned int len;
    // 未使用的字节数
    unsigned int free;
    // 字节数组，用于保存字符串，以\0结尾
    char buf[];
};

sds是如何解决c字符串存在的问题

1. 对于问题1：O(N)时间复杂度获取字符串长度

sds使用len字段记录字符串长度，将获取字符串长度的时间复杂度从O(N)降低到O(1)，同时避免了多次获取字符串长度时，存在的性能问题

1. 对于问题2：二进制不安全

sds使用len属性的值，而不是空字符'\0'来判断字符串是否结束，保证了二进制安全

1. 对于问题3/4/5：内存分配问题

sds通过空间预分配和惰性空间释放两种优化策略，来减少修改字符串时带来的内存重分配次数

当执行字符串增长操作时，sds会进行空间预分配，避免发生缓冲区溢出

• 如果对sds进行修改后，len < 1mb，则分配和len相同的未使用空间free
• 如果对sds进行修改后，len >= 1mb，则分配1mb的未使用空间free

执行字符串缩短操作时，sds会惰性释放空间，程序不会立即进行内存重分配来回收字符串缩短后多出来的字节，而是使用free来记录，以备未来使用。如果有需要，也可以通过api显示释放内存

1. 此外sds中的buf字节数组，遵循'\0'结尾，使用buf内容为文本内容时，可以兼容部分c字符串函数

3.2.0及以后的sds

在3.2.0以前的sds中，len和free属性都使用了4字节来保存。实际上buf字节数组长度可能没这么长，为了追求极致的内存利用，在3.2.0及以后的版本中，对sds进行了进一步优化

在3.2.0及以后的版本，sdshdr结构如下

/* 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[];
};

举个例子：同样是整数，golang语言中，提供了int8、int16、int32、int64四种类型来供用户选择，这里的sds也是一样的优化思路

sds优化后核心思想没变，这里就不再重复分析了