Redis 源码解析（一）简单动态字符串 SDS

作者: Tubetrue01 | 来源:发表于2021-02-08 15:38 被阅读0次

引言

本系列文章开始讲解 Redis 相关源码，文章不定时更新，并且周期可能会很长，请大家谅解。作为系列文章的开篇，我们从最简单的数据结构 SDS 开始讲解，源码取自 6.0.8 版本。

简单动态字符串

简单动态字符串（Simple Dynamic Strings，SDS）是Redis的基本数据结构之一，用于存储字符串和整型数据。SDS 兼容 C 语言标准字符串处理函数，且在此基础上保证了二进制安全。

二进制安全

什么是二进制安全？通俗地讲，C 语言中，用 “\0” 表示字符串的结束，如果字符串中本身就有 “\0” 字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则是二进制安全。

数据结构

SDS 既然是字符串，那么首先需要一个字符串指针；为了方便上层接口调用，该结构还需要记录一些统计信息，如当前数据长度和剩余容量等，如：

struct sds { 
  int len;     // buf 中已占用字节数 
  int free;    // buf 中剩余可用字节数 
  char buf[];  // 数据空间
};

在 64 位系统下，字段 len 和字段 free 各占 4 个字节，紧接着存放字符串。我们分析一下这样设计有什么好处？

优势

有单独的统计变量 len 和 free（称为头部）。可以很方便地得到字符串长度。
内容存放在柔性数组 buf 中，SDS 对上层暴露的指针不是指向结构体 SDS 的指针，而是直接指向柔性数组 buf 的指针。上层可像读取 C 字符串一样读取 SDS 的内容，兼容 C 语言处理字符串的各种函数。
由于有长度统计变量 len 的存在，读写字符串时不依赖 “\0” 终止符，保证了二进制安全。

image.png
Tips

上例中的 buf[] 是一个柔性数组。柔性数组成员（flexible array member），也叫伸缩性数组成员，只能被放在结构体的末尾。包含柔性数组成员的结构体，通过 malloc 函数为柔性数组动态分配内存。之所以用柔性数组存放字符串，是因为柔性数组的地址和结构体是连续的，这样查找内存更快（因为不需要额外通过指针找到字符串的位置）；可以很方便地通过柔性数组的首地址偏移得到结构体首地址，进而能很方便地获取其余变量。

改进

我们实现了一个最基本的动态字符串，但是该结构是否有改进的空间呢？我们从一个简单的问题开始思考：不同长度的字符串是否有必要占用相同大小的头部？一个 int 占 4 字节，在实际应用中，存放于 Redis 中的字符串往往没有这么长，每个字符串都用 4 字节存储未免太浪费空间了。我们考虑三种情况：短字符串，len 和 free 的长度为 1 字节就够了；长字符串，用 2 字节或 4 字节；更长的字符串，用 8 字节。这样确实更省内存，但依然存在以下问题：

如何区分这 3 种情况？
对于短字符串来说，头部还是太长了。以长度为 1 字节的字符串为例，len 和 free 本身就占了 2 个字节，能不能进一步压缩呢？

对于问题 1，我们考虑增加一个字段 flags 来标识类型，用最小的 1 字节来存储，且把 flags 加在柔性数组 buf 之前，这样虽然多了1 字节，但通过偏移柔性数组的指针即能快速定位 flags，区分类型，也可以接受；对于问题 2，由于len已经是最小的1字节了，再压缩只能考虑用位来存储长度了。
结合两个问题，5 种类型（长度 1 字节、2 字节、4 字节、8 字节、小于 1 字节）的 SDS 至少要用 3 位来存储类型（2 ^ 3 ＝8），1 个字节 8 位，剩余的 5 位存储长度，可以满足长度小于 32 的短字符串。我们用如下结构来存储长度小于 32 的短字符串：

sds.h

/* 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 位存储类型, 高 5 位存储长度 */
    char buf[];
};

sdshdr5 结构中，flags 占 1 个字节，其低 3 位（bit）表示 type，高 5 位（bit）表示长度，能表示的长度区间为 0～31（2^5 -1）， flags 后面就是字符串的内容。
Tips

__attribute__ ((__packed__)) 的作用就是避免编译器进行字节对齐优化，采用实际的字节对齐。这样做的好处就是节省内存，同时可以通过指针灵活的获取各个字段的地址（如果对齐优化了，那么指针可能获取到填充的地址空间）。

image.png

而长度大于 31 的字符串，1 个字节依然存不下。我们按之前的思路，将 len 和 free 单独存放。sdshdr8、sdshdr16、sdshdr32 和 sdshdr64 的结构相同，sdshdr16 结构如图所示。

image.png

其中“表头”共占用了 S[2(len) + 2(alloc) + 1(flags)] 个字节。flags 的内容与 sdshdr5 类似，依然采用 3 位存储类型，但剩余 5 位不存储长度。
在 Redis 的源代码中，对类型的宏定义如下：

sds.h

#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

sdshdr8、sdshdr16、sdshdr32 和 sdshdr64 的数据结构如下：

sds.h

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;          /* 已用的长度 */
    uint8_t alloc;        /* 总的长度 */
    unsigned char flags;  /* 低 3 为代表类型，高 5 位未使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;  
    uint16_t alloc;  
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; 
    uint32_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; 
    uint64_t alloc; 
    unsigned char flags; 
    char buf[];
};

可以看到，这 4 种结构的成员变量类似，唯一的区别是 len 和 alloc 的类型不同。结构体中 4 个字段的具体含义分别如下。

len ：表示 buf 中已占用字节数。
alloc ：表示buf中已分配字节数，不同于 free，记录的是为 buf 分配的总长度。
flags ：标识当前结构体的类型，低 3 位用作标识位，高 5 位预留。
buf ：柔性数组，真正存储字符串的数据空间。

基本操作

数据结构的基本操作不外乎增、删、改、查，SDS 也不例外。

c 函数中很大一部分用到了宏运算，这里先介绍一下相关的宏以及常量

// sds 是 char 类型的指针
typedef char *sds;

// 类型掩码，按位与可求出对应的数据类型
#define SDS_TYPE_MASK 7

// 初始化 sh 指针，让 sh 指向对应结构体的首地址。T 就是对应的结构体类型，s 是指向 buf 的指针
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)));

// 与 SDS_HDR_VAR 类似，只不过这里返回的是结构对象，需要 "SDS_HDR(T,s) -> len "方式使用
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))


// 1M 内存分配量
#define SDS_MAX_PREALLOC (1024*1024)

创建字符串

Redis 通过 sdsnewlen 函数创建 SDS。在函数中会根据字符串长度选择合适的类型，初始化完相应的统计值后，返回指向字符串内容的指针，根据字符串长度选择不同的类型：

sds.c

/*
 * init 指向字符串的指针，initlen 字符串的长度；如：
 * mystring = sdsnewlen("abc",3); 
 */
sds sdsnewlen(const void *init, size_t initlen) {  
    void *sh;
    sds s;
    // 根据初始大小获取对应的类型
    char type = sdsReqType(initlen);
    // SDS_TYPE_5 类型会转换成 SDS_TYPE_8 
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    // 根据类型计算出该结构对应的大小
    int hdrlen = sdsHdrSize(type);
    // 指向 flags 指针
    unsigned char *fp;
   /*
    * 分配内存，内存大小包括：结构自身占用的内存 + 数据存储的内存 + 1 * 字节的 '\0'
    */
    sh = s_malloc(hdrlen+initlen+1);
    // 内存分配失败返回 NULL
    if (sh == NULL) return NULL;
    if (init == SDS_NOINIT)
        init = NULL;
    else if (!init)
        // 开始初始化内存
        memset(sh, 0, hdrlen+initlen+1);
    // 此时 s 指向了 buf（sh 是内存的首地址，hdrlen 是结构体大小，注意这里的指针转换）
    s = (char*)sh+hdrlen;
    // 由于内存是紧凑的，这里可以直接算出 flags 的内存地址，所以 fp 指向了 flags
    fp = ((unsigned char*)s)-1;
    // 通过 type 的类型，我们就可以给 flags 赋值了
    switch(type) {
        case SDS_TYPE_5: {
            // 这里不用过多介绍，按位或算出高低位
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            // 这步在做什么？SDS_HDR_VAR 其实是一个宏，该步的操作就是初始化 sh，将 sh 指针强制转换成对应的结构体指针，因为 sh 起初是 void * 指针，所以无法通过指针访问其成员。通过结构体大小（第一个参数）以及分配的内存大小（第二个参数）可以推算出结构体首地址
            SDS_HDR_VAR(8,s);
            // 初始化 len 成员
            sh->len = initlen;
            // 初始化 alloc 成员
            sh->alloc = initlen;
            // 初始化 flag
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    
    if (initlen && init)
        // 将 init 指向的字符串赋值到 s 中（也就是 buf）
        memcpy(s, init, initlen);
    // 不要忘记末尾的 '\0'
    s[initlen] = '\0';
    // 返回字符串地址，即 buf 地址
    return s;
}

// 根据字符串的大小返回其对应的 SDS 类型
static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

Tips

Redis 3.2 后的 SDS 结构由 1 种增至 5 种，且对于 sdshdr5 类型，在创建空字符串时会强制转换为 sdshdr8。原因可能是创建空字符串后，其内容可能会频繁更新而引发扩容，故创建时直接创建为 sdshdr8。

从源码中我们可以看到，其实 s 就是一个字符数组的指针，即结构中的 buf。这样设计的好处在于直接对上层提供了字符串内容指针，兼容了部分 C 函数，且通过偏移能迅速定位到 SDS 结构体的各处成员变量。

释放字符串

SDS 提供了直接释放内存的方法——sdsfree，该方法通过对 s 的偏移，可定位到 SDS 结构体的首部，然后调用 s_free 释放内存：

void sdsfree(sds s) {
    // 如果字符串为空，直接返回
    if (s == NULL) return;
    // 直接释放内存，s[-1] 指向的是 flag，s - flag 得出的就是内存的首地址
    s_free((char*)s-sdsHdrSize(s[-1]));
}

// 通过类型获取对应的结构体内存大小
static inline int sdsHdrSize(char type) {
    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;
}

为了优化性能（减少申请内存的开销），SDS 提供了不直接释放内存，而是通过重置统计值达到清空目的的方法——sdsclear。该方法仅将 SDS 的 len 归零，此处已存在的 buf 并没有真正被清除，新的数据可以覆盖写，而不用重新申请内存。

void sdsclear(sds s) {
    // 将 len 设置成 0
    sdssetlen(s, 0);
    // buf 首位设置成 '\0'
    s[0] = '\0';
}

// 将 len 属性设置成 newlen 对应的值
static inline void sdssetlen(sds s, size_t newlen) {
    // 获取 flags 值
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                // 获取 fp 指针
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

拼接字符串

拼接字符串操作本身不复杂，可用 sdscatsds 来实现，代码如下：

// 注意 const
sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

sdscatsds 是暴露给上层的方法，其最终调用的是 sdscatlen。由于其中可能涉及 SDS 的扩容，sdscatlen 中调用 sdsMakeRoomFor 对带拼接的字符串 s 容量做检查，若无须扩容则直接返回 s；若需要扩容，则返回扩容好的新字符串 s。函数中的 len、curlen 等长度值是不含结束符的，而拼接时用 memcpy 将两个字符串拼接在一起，指定了相关长度，故该过程保证了二进制安全。最后需要加上结束符。

/* 将指针 t 的内容和指针 s 的内容拼接在一起，该操作是二进制安全的 */ 
sds sdscatlen(sds s, const void *t, size_t len) {
    // 计算 s 对应的 len 属性
    size_t curlen = sdslen(s);
    // 根据 s 以及 len 选择合适的扩容策略
    s = sdsMakeRoomFor(s,len);
    // 扩容失败，直接返回
    if (s == NULL) return NULL;
    // 将 t 中的 len 长度的内容复制到 s + curlen 指向的内存地址
    memcpy(s+curlen, t, len);
    // 更新 s 中的 len 属性
    sdssetlen(s, curlen+len);
    // 在 buf 的末尾添加结束符
    s[curlen+len] = '\0';
    return s;
}
// 通过 s（即 buf 地址），获取该结构对应的 len 属性
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    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;
}
// 扩容方法，s 待扩容的 buf，addlen 是目标字符串内存大小
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    // 算出 s 中可用内存（alloc - len）
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    // 如果剩余空间足够容纳目标字符串，那么直接返回 s
    if (avail >= addlen) return s;
    // 获取 s 中的 len
    len = sdslen(s);
    // sh 指向原始 s 的结构首地址
    sh = (char*)s-sdsHdrSize(oldtype);
    
    newlen = (len+addlen);
    
    // 如果新增之后的内存大小 < 1M，那么采用 2 倍内存扩容
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
       // 如果 > 1M，那么以 1M 的内存增量扩容
        newlen += SDS_MAX_PREALLOC;

    // 算出新的 type 类型
    type = sdsReqType(newlen);

    // 如果是 SDS_TYPE_5，强制转换成 SDS_TYPE_8，避免频繁扩容
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    // 算出对应的结构体大小
    hdrlen = sdsHdrSize(type);
    // 类型相同
    if (oldtype==type) {
        // 直接扩容 buf 大小
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        // 新的 s 的地址
        s = (char*)newsh+hdrlen;
    } else {
        // 如果类型不同了，那么需要重新分配内存
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        // 将 s 的内容以及末尾的结束符复制到新的 buf 中
        memcpy((char*)newsh+hdrlen, s, len+1);
        // 释放 sh 内存
        s_free(sh);
        // 获取 s 的地址
        s = (char*)newsh+hdrlen;
        // 设置 type 类型
        s[-1] = type;
        // 设置 len 属性
        sdssetlen(s, len);
    }
    // 设置 alloc 属性
    sdssetalloc(s, newlen);
    return s;
}
// 求出 s 中的剩余空间，也就是 alloc - len 的数值
static inline size_t sdsavail(const sds s) {
    // 第一步都是获取 flags，然后通过 flags 获取其对应的数据类型
    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;
}

扩容流程如图：

image.png

本文主要介绍了 SDS 相关的基础概念以及比较核心方法，SDS 为上层提供了丰富的 API，本文就不再介绍了。通过这几个核心方法的分析，其实大家可以看到，大多数都是围绕 s 以及常用的宏展开的，只要大家把宏看懂记住配合指针操作，那么 SDS 的其他 API 也同样简单。当然，本文主要讲解 Redis 源码，所以默认大家是熟练 C 的，所以对一些相关运算及概念不会做过多介绍。感兴趣的可以看看我的关于 C 系列的文章

Redis 源码解析（一）简单动态字符串 SDS

引言

简单动态字符串

二进制安全

数据结构

优势

改进

基本操作

宏

创建字符串

释放字符串

拼接字符串

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Redis