Redis 数据结构 简单动态字符串(SDS)

Redis绝大部分操作都会涉及到key,使用特别广泛,从系统设计的角度来看,我们该如何设计实现字符串呢?

Redis 设计了简单动态字符串(Simple Dynamic String)的结构,用来表示字符串。相比于 C 语言中的字符串实现,SDS 这种字符串的实现方式,会提升字符串的操作效率,并且可以用来保存二进制数据。

(1) SDS是什么

Redis 是 Simple Dynamic String 的缩写,中文是简单动态字符串

SDS结构里包含了一个字符数组 buf[],用来保存实际数据。
同时,SDS结构里还包含了三个元数据,分别是字符数组现有长度 len、分配给字符数组的空间长度 alloc,以及 SDS 类型 flags。

sdshdr结构

(1.1) 为什么Redis里的字符串不用char*?

Redis是用c语言编写的,为什么Redis的key不直接使用char* ?

来看看 char* 字符数组的结构。
char字符数组的结构比较简单,用一块连续的内存空间,依次存放了字符串中的每一个字符数组结构,结尾位置就用”\0”表示,表示结束。

C语言字符串

不使用char*的原因

  1. 操作效率低:获取字符串长度需遍历整个字符数组,O(N)复杂度
  2. 二进制不安全:无法存储包含 \0 的数据
  3. 修改字符串忘记分配内存容易造成缓冲区溢出 (buffer overflow) 。
  4. 修改字符串需要重新分配内存,涉及系统调用。

(1.2) SDS优势

  1. 操作效率高:获取长度无需遍历,O(1)复杂度
  2. 二进制安全:因单独记录长度字段,所以可存储包含 “\0” 的数据
  3. 兼容 C 字符串函数,可直接使用字符串 API

另外 Redis 在操作 SDS 时,为了避免频繁操作字符串时,每次「申请、释放」内存的开销,还做了这些优化:

  • 内存预分配:SDS 扩容,会多申请一些内存(小于 1MB 翻倍扩容,大于 1MB 按 1MB 扩容)
  • 多余内存不释放:SDS 缩容,不释放多余的内存,下次使用可直接复用这些内存

(2) 为什么要用SDS

  1. 能支持丰富且高效的字符串操作,比如字符串追加、拷贝、比较、获取长度等;
  2. 能保存二进制数据,比如byte[]等;
  3. 节省内存开销。

(3) SDS提供的功能

函数 作用 算法复杂度
sdsnewlen 创建一个指定长度的 sds ,接受一个 C 字符串作为初始化值 O(N)
sdsempty 创建一个只包含空白字符串 “” 的 sds O(1)
sdsnew 根据给定 C 字符串,创建一个相应的 sds O(N)
sdsdup 复制给定 sds O(N)
sdsfree 释放给定 sds O(N)
sdsupdatelen 更新给定 sds 所对应 sdshdr 结构的 free 和 len O(N)
sdsclear 清除给定 sds 的内容,将它初始化为 “” O(1)
sdsMakeRoomFor 对 sds 所对应 sdshdr 结构的 buf 进行扩展 O(N)
sdsRemoveFreeSpace 在不改动 buf 的情况下,将 buf 内多余的空间释放出去 O(N)
sdsAllocSize 计算给定 sds 的 buf 所占用的内存总数 O(1)
sdsIncrLen 对 sds 的 buf 的右端进行扩展(expand)或修剪(trim) O(1)
sdsgrowzero 将给定 sds 的 buf 扩展至指定长度,无内容的部分用 \0 来填充 O(N)
sdscatlen 按给定长度对 sds 进行扩展,并将一个 C 字符串追加到 sds 的末尾 O(N)
sdscat 将一个 C 字符串追加到 sds 末尾 O(N)
sdscatsds 将一个 sds 追加到另一个 sds 末尾 O(N)
sdscpylen 将一个 C 字符串的部分内容复制到另一个 sds 中,需要时对 sds 进行扩展 O(N)
sdscpy 将一个 C 字符串复制到 sds O(N)

(4) SDS原理

redis 6.0版本源码 https://github.com/redis/redis/blob/6.0/src/sds.c

(4.1) SDS定义

SDS 结构里包含了一个字符数组 buf[],用来保存实际数据。
同时,SDS结构里还包含了三个元数据,分别是字符数组现有长度 len、分配给字符数组的空间长度 alloc,以及 SDS 类型 flags。

sdshdr结构

Redis里SDS定义,可以看到定义了4种sds,分别是sdshdr8sdshdr16sdshdr32sdshdr64

typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;  // 字符数组已使用长度  uint8_t占用内存空间1字节
    uint8_t alloc;  // 字符数组的已分配空间,不包括结构体和结束字符  uint8_t占用内存空间1字节
    unsigned char flags;  // SDS类型 占用一字节 实际使用了3bit,5bit未使用
    char buf[];    // 字节数组  实际存储的数据
};

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;  // 字符数组已使用长度  uint16_t占用内存空间2字节
    uint16_t alloc;  // 字符数组的已分配空间,不包括结构体和结束字符  uint16_t占用内存空间2字节
    unsigned char flags;    // SDS类型 占用一字节 实际使用了3bit,5bit未使用
    char buf[];    // 字节数组  实际存储的数据
};

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;  // 字符数组已使用长度  uint32_t占用内存空间3字节
    uint32_t alloc;  // 字符数组的已分配空间,不包括结构体和结束字符  uint32_t占用内存空间3字节
    unsigned char flags;    // SDS类型 占用一字节 实际使用了3bit,5bit未使用
    char buf[];    // 字节数组  实际存储的数据
};

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;  // 字符数组已使用长度  uint64_t占用内存空间4字节
    uint64_t alloc;  // 字符数组的已分配空间,不包括结构体和结束字符  uint64_t占用内存空间4字节
    unsigned char flags;  // SDS类型 占用一字节 实际使用了3bit,5bit未使用
    char buf[];  // 字节数组  实际存储的数据
};

类型 sdschar* 的别名(alias),在 Redis 中需要用到字符数组时,就直接使用 sds 这个别名。
结构 sdshdr 则保存了 lenalloc flagsbuf[] 四个属性

各种sdshdr区别

SDS 本质还是字符数组,只是在字符数组基础上增加了额外的元数据。
但是,sds和char*并不等同,sds是二进制安全的,它可以存储任意二进制数据,不能像C语言字符串那样以‘\0’来标识字符串结束

真正的SDS指的是 sdshdr8 sdshdr16 sdshdr32 sdshdr64

__attribute__ ((__packed__)) 此字段是为了让编译器以紧凑模式来分配内存。

// 参考 https://blog.csdn.net/luyee2010/article/details/10240729

#include<string.h>

typedef char * sds;

int main(void){
   sds c1,c2;
   char c3[]="abcd";
   char c4[]="xyz";
   c1=c3;
   c2=c4;
   printf("*c1=%s,*c2=%s,\n",c1,c2);
   return 0;
}

(5) SDS源码解读

redis 6.0版本源码 https://github.com/redis/redis/blob/6.0/src/sds.c

(5.1) 创建字符串

在创建新的字符串时,Redis 会调用 SDS 创建函数 sdsnewlen。

sds内存分配

/* 
 * 使用“init”指针和“initlen”指定的内容创建一个新的 sds 字符串。
 * 
 * 该字符串始终以 null 结尾
 * 所以你可以这么创建一个 sds 字符串:
 *   mystring = sdsnewlen("abc",3);
 * 
 * 您可以使用 printf() 打印字符串,因为字符串末尾有一个隐含的 \0。 
 * 该字符串是二进制安全的,并且可以在中间包含 "\0" 字符,因为长度存储在 sds 头部中。
 */
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s; // sds类型变量 即char*字符数组
    // 获取SDS_TYPE    SDS_TYPE_8 ~ SDS_TYPE_64
    char type = sdsReqType(initlen);
    // 元数据长度
    int hdrlen = sdsHdrSize(type);
    
    // 新建SDS结构,并分配内存空间 
    // hdrlen是结构体的长度  initlen是字符串长度  1是最后结束符"\0"的长度
    sh = s_malloc(hdrlen+initlen+1);

    // sds类型变量指向SDS结构体中的buf数组,sh指向SDS结构体起始位置,hdrlen是SDS结构体中元数据的长度
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;

    switch(type) {
        // 省略部分代码 ...
        // 
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }

    if (initlen && init)
        memcpy(s, init, initlen); //将要传入的字符串拷贝给sds变量s
    s[initlen] = '\0'; // 字符数组 末尾设置成"\0",表示字符串结束
    return s;
}
/*
 * 根据字符长度选取对应的SDS_TYPE
 * 返回结果 数字类型
 */
static inline char sdsReqType(size_t string_size) {
    // 字符长度 < 2^5 
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    // 字符长度 < 2^8    
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    // 字符长度 < 2^16    
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    // 字符长度 < 2^32 
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}
#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
#define SDS_TYPE_MASK 7

/*
 * 不同长度元数据的字节大小
 */
static inline int sdsHdrSize(char type) {
    // 位运算  SDS_TYPE_MASK=7 对应二进制是 0111
    // 也就是说 type与0111取并集,只有后三位参与运算
    switch(type&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return sizeof(struct sdshdr5);
        case SDS_TYPE_8:
            return sizeof(struct sdshdr8);
        case SDS_TYPE_16:
            return sizeof(struct sdshdr16);
        case SDS_TYPE_32:
            return sizeof(struct sdshdr32);
        case SDS_TYPE_64:
            return sizeof(struct sdshdr64);
    }
    return 0;
}
/*
 * 创建一个空的(长度为0) sds 字符串。 
 * 即使在这种情况下,字符串也始终具有隐含的空项。
 */
sds sdsempty(void) {
    return sdsnewlen("",0);
}

(5.2) SDS释放

/*
 * 释放 sds 字符串。
 * 如果“s”为 NULL,则不执行任何操作。
 */
void sdsfree(sds s) {
    if (s == NULL) return;
    // 只释放字符数组
    // 减去header的长度
    s_free((char*)s-sdsHdrSize(s[-1]));
}

(5.3) SDS修改

SDS 结构中记录了字符数组已占用的空间和被分配的空间,这就比传统 C 语言实现的字符串能带来更高的操作效率。

以字符串追加操作为例。Redis 中实现字符串追加的函数是 sds.c 文件中的 sdscatlen 函数。这个函数的参数一共有三个,分别是目标字符串 s、源字符串 t 和要追加的长度 len,源码如下所示:

/* 
 * 将由“t”(共“len”个字节)指向的指定二进制安全字符串附加到指定的 sds 字符串“s”的末尾。
 * 
 * 调用后,传递的 sds 字符串不再有效,所有引用必须替换为调用返回的新指针。
 *
 * @param s
 * @param *t
 * @param len
 */
sds sdscatlen(sds s, const void *t, size_t len) {
    //获取目标字符串s的当前长度
    size_t curlen = sdslen(s);
    //根据要追加的长度len和目标字符串s的现有长度,判断是否要增加新的空间
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    //将源字符串t中len长度的数据拷贝到目标字符串结尾
    memcpy(s+curlen, t, len);
    //设置目标字符串的最新长度:拷贝前长度curlen加上拷贝长度
    sdssetlen(s, curlen+len);
    //拷贝后,在目标字符串结尾加上\0
    s[curlen+len] = '\0';
    return s;
}

首先,根据当前字符串长度和要追加的长度,判断是否要给目标字符串新增空间。
其次,在保证了目标字符串的空间足够后,将源字符串中指定长度 len 的数据追加到目标字符串。
最后,设置目标字符串的最新长度。

SDS 把目标字符串的空间检查和扩容封装在了 sdsMakeRoomFor 函数中,并且在涉及字符串空间变化的操作中,如追加、复制等,会直接调用该函数。


(5.4) 获取字符串长度

/*
 * 已使用字符数据的长度
 */
static inline size_t sdslen(const sds s) {
    // SDS_TYPE  
    unsigned char flags = s[-1];
    // #define SDS_TYPE_MASK 7 也就是 SDS_TYPE_MASK 对应二进制是 0111  
    // flags的右边3位 按位与  
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            // 返回对应的字符长度
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

flags & SDS_TYPE_MASK 进行与运算,SDS_TYPE_MASK 对应二进制是 0000 0000 0000 0111,无论flags是多少,最大是0111,也就是7

#define SDS_TYPE_5  0  // 对应二进制 0000
#define SDS_TYPE_8  1  // 对应二进制 0001
#define SDS_TYPE_16 2  // 对应二进制 0010
#define SDS_TYPE_32 3  // 对应二进制 0011
#define SDS_TYPE_64 4  // 对应二进制 0100
#define SDS_TYPE_MASK 7
/*
 * 可用长度 = 已分配 - 已使用
 * avail = alloc - len 
 *
 * @param s 
 */
static inline size_t sdsavail(const sds s) {
    // SDS_TYPE
    unsigned char flags = s[-1];
    // 
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

(5.5) 内存预分配

sds内存分配

// file:  src/sds.c

/* 
 * 扩大 sds 字符串末尾的可用空间,以便调用者确定调用此函数后可以覆盖字符串末尾后的 addlen 个字节,再加上一个 nul 项的字节。
 *
 * 注意:这不会改变 sdslen() 返回的 sds 字符串的长度,而只会改变我们拥有的可用缓冲区空间。
 * 
 * @param s 
 * @param addlen 要添加的长度
 */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // 可用长度
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen; // 结构体长度

    /* 如果剩余空间足够,请尽快返回。 */
    if (avail >= addlen) return s;

    len = sdslen(s); // 字符串长度 // 已使用字符数组长度
    sh = (char*)s-sdsHdrSize(oldtype);
    reqlen = newlen = (len+addlen); // 需要的字符长度 = 现在的字符串长度 + 需要增加的字符长度
    assert(newlen > len);   /* Catch size_t overflow */
    // 申请的字符串长度newlen < 1KB 分配 newlen*2 的内存空间
    // 否则分配 newlen + 1KB 的内存空间
    if (newlen < SDS_MAX_PREALLOC) // 申请的新字符串长度 newlen < 1024*1024 (1KB) 
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC; 

    // 判断SDS_TYPE
    type = sdsReqType(newlen);

    // 不要使用SDS_TYPE_5:用户追加到字符串,SDS_TYPE_5 无法记住空格,因此必须在每次追加操作时调用 sdsMakeRoomFor()。
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    // header长度 / 结构体长度
    hdrlen = sdsHdrSize(type);
    // 确保 结构体长度 + 申请字符串长度 + 结束字符长度 > 申请的长度
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    // 判断 SDS_TYPE 有没有变化 
    if (oldtype==type) { // SDS_TYPE_8 == SDS_TYPE_8 
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else { // SDS_TYPE_8 != SDS_TYPE_16
        // 由于标头大小发生变化,需要将字符串向前移动,并且无法使用 realloc
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        // 将字符串拷贝给sds变量s
        memcpy((char*)newsh+hdrlen, s, len+1);
        // 释放老的sh 
        s_free(sh);
        // sds类型变量指向SDS结构体中的buf数组,sh指向SDS结构体起始位置,hdrlen是SDS结构体中元数据的长度
        s = (char*)newsh+hdrlen;
        // 字符数组 设置 SDS_TYPE
        s[-1] = type;
        // 设置sds字符串长度
        sdssetlen(s, len);
    }
    // 设置已分配空间的长度
    sdssetalloc(s, newlen);
    return s;
}

在代码里可以看到,申请的字符串长度newlen < 1KB,分配 newlen*2 的内存空间,否则分配 newlen + 1KB 的内存空间
newlen = 需要的字符长度 = 现在的字符串长度 + 需要增加的字符长度

备注

// file:  src/sds.c

#define SDS_MAX_PREALLOC (1024*1024)

(6) SDS内存优化

SDS在内存上做了哪些优化?

(6.1) 紧凑型设计

SDS 结构中有一个元数据 flags,表示的是 SDS 类型。
事实上,SDS 一共设计了 5 种类型,分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
这 5 种类型的主要区别就在于,它们数据结构中的字符数组现有长度 len 和分配空间长度 alloc,这两个元数据的数据类型不同。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;  // 字符数组已使用长度  uint8_t占用内存空间1字节
    uint8_t alloc;  // 字符数组的已分配空间,不包括结构体和结束字符  uint8_t占用内存空间1字节
    unsigned char flags;  // SDS类型 占用一字节 实际使用了3bit,5bit未使用
    char buf[];    // 实际存储的数据
};

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;  // 字符数组已使用长度  uint16_t占用内存空间2字节
    uint16_t alloc;  // 字符数组的已分配空间,不包括结构体和结束字符  uint16_t占用内存空间2字节
    unsigned char flags;    // SDS类型 占用一字节 实际使用了3bit,5bit未使用
    char buf[];    // 实际存储的数据
};

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;  // 字符数组已使用长度  uint32_t占用内存空间3字节
    uint32_t alloc;  // 字符数组的已分配空间,不包括结构体和结束字符  uint32_t占用内存空间3字节
    unsigned char flags;    // SDS类型 占用一字节 实际使用了3bit,5bit未使用
    char buf[];    // 实际存储的数据
};

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len;  // 字符数组已使用长度  uint64_t占用内存空间4字节
    uint64_t alloc;  // 字符数组的已分配空间,不包括结构体和结束字符  uint64_t占用内存空间4字节
    unsigned char flags;  // SDS类型 占用一字节 实际使用了3bit,5bit未使用
    char buf[];  // 实际存储的数据
};

各种sdshdr区别

元数据各自占用的内存空间在 sdshdr8sdshdr16sdshdr32sdshdr64 类型中,则分别是 1字节、2字节、4字节 和 8字节。

SDS之所以设计不同的结构头(即不同类型),是为了能灵活保存不同大小的字符串,从而有效节省内存空间。
因为在保存不同大小的字符串时,结构头占用的内存空间也不一样,这样一来,在保存小字符串时,结构头占用空间也比较少。

(6.2) 编译优化

Redis 在编程上还使用了专门的编译优化来节省内存空间。
struct __attribute__ ((__packed__)) sdshdr64 ,attribute ((packed))的作用就是告诉编译器,在编译 sdshdr64 结构时,不要使用字节对齐的方式,而是采用紧凑的方式分配内存。

这是因为在默认情况下,编译器会按照 8 字节对齐的方式,给变量分配内存。也就是说,即使一个变量的大小不到 8 个字节,编译器也会给它分配 8 个字节。
Redis采用了__attribute__ ((packed))属性定义结构体,结构体实际占用多少内存空间,编译器就分配多少空间。

#include <stdio.h>
int main() {
    struct __attribute__((packed)) s2{
      char a;
      int b;
    } ts2;
    printf("%lu\n", sizeof(ts2));
    return 0;
}

当你运行这段代码时,你可以看到,打印的结果是 5,表示编译器用了紧凑型内存分配,s2 结构体只占用 5 个字节的空间。


(7) 使用SDS字符串的地方

  1. server.h 文件中的 redisObject 对象,key 和 value 都是对象,key (键对象)都是 SDS 简单动态字符串对象
  2. cluter.c 的 clusterGenNodesDescription 函数中。这个函数代表以 csv 格式记录当前节点已知所有节点的信息。
  3. client.h 的 clusterLink 结构体中。clusterLink 包含了与其他节点进行通讯所需的全部信息,用 SDS 来存储输出缓冲区和输入缓冲区。
  4. server.h 的 client 结构体中。缓冲区 querybuf、pending_querybuf 用的 sds 数据结构。
  5. networking.c 中的 catClientInfoString 函数。获取客户端的各项信息,将它们储存到 sds 值 s 里面,并返回。
  6. sentinel.c 中的 sentinelGetMasterByName 函数。根据名字查找主服务器,而参数名字会先转化为 SDS 后再去找主服务器。
  7. server.h 中的结构体 redisServer,aof_buf 缓存区用的 是 sds。
  8. slowlog.h 中的结构体 slowlogEntry,用来记录慢查询日志,其他 client 的名字和 ip 地址用的是 sds。

SDS 字符串在 Redis 内部模块实现中也被广泛使用,你能在 Redis server 和客户端的实现中,找到使用 SDS 字符串的地方么?
1、Redis 中所有 key 的类型就是 SDS(详见 db.c 的 dbAdd 函数)
2、Redis Server 在读取 Client 发来的请求时,会先读到一个缓冲区中,这个缓冲区也是 SDS(详见 server.h 中 struct client 的 querybuf 字段)
3、写操作追加到 AOF 时,也会先写到 AOF 缓冲区,这个缓冲区也是 SDS (详见 server.h 中 struct client 的 aof_buf 字段)


参考资料

[1] Redis源码剖析与实战 - 02 键值对中字符串的实现,用char还是结构体?
[2] unsigned long long conflict with uint64_t?
[3] Redis设计与实现 - 简单动态字符串
[4] Redis sds动态字符串学习三