Redis数据结构-SDS

为什么要有SDS

在redis当中,key都是字符串类型,value要么是字符串要么是字符串的集合，所以字符串类型是redis中最常用的类型。

而如果使用传统的C当中的字符串，会存在一些问题。
（1）获取长度的时候需要运算(strlen函数的底层实现通常是通过遍历字符串，直到遇到空字符（null terminator，即 ‘\0’）为止来计算字符串的长度的。这是因为 C 语言中的字符串是以空字符结尾的字符数组。时间复杂度是O(n))
（2）二进制不安全等问题
（3）一旦分配不能被修改。我们需要一个更加高效的数据结构SDS（简单动态字符串）。

Redis最显著的特点之一就是具备高性能，第一是因为Redis为内存数据库，避免了频繁的IO操作，另一方面就是具备高性能的数据结构（不是数据类型）

SDS结构

Redis是C实现的，打开源码观察SDS结构体，

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 被使用中 */
    uint8_t alloc; /*不包含标头和终止符*/
    unsigned char flags; /*3个lsb类型，5个未使用的位*/
    char buf[];
};

SDS只是一个统称，实际上表示范围不同，Redis提供了五种SDS。
源码:

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

sdshdr8适合于存储长度在255字节以下的字符串，因为len和alloc都只有1个字节，所以它们可以表示的最大长度是255字节（不包括字符串结束的null字节）
sdshdr16适合于存储长度在65535字节以下的字符串，因为len和alloc都使用了2个字节，所以它们可以表示的最大长度是65535字节（不包括字符串结束的null字节）
注：flags字段为SDS头类型。
源码:

#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

SDS优势

相较于C中的字符串，（1）可以直接从len字段中直接得到他的长度 （2）可以动态扩容 （3）是二进制安全的，SDS并没有用’\0’作为结束符，而是看的len,即使中间出现了’\0’，也会继续往后找。

自动扩容机制

之所以成为动态字符串，是因为SDS具备动态扩容机制。
例如一个内容为“hi”的SDS：

假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：

如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；

如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。