Redis 简单动态字符串

1.介绍

Redis没有直接使用C语言传统的字符串表示（以空字符结尾的字符数组，以下简称C字符串），而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS ）的抽象类型，并将SDS用作Redis的默认字符串表示.

比如Redis的字符串对象，当字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用SDS来保存这个字符串值.

2.SDS的定义

SDS定义在redis源码根目录下的sds.h中：

typedef char *sds;

SDS有一个表头header用于存放SDS的信息，其中在redis-3.2.0版本之前是这样的：

struct sdshdr {
    
    unsigned int len;   //buf中已占用空间的长度
    unsigned int free;  //buf中剩余可用空间的长度
    char buf[];         //初始化sds分配的数据空间
};

结构体中有三个字段，分别是buf中已占用空间的长度、buf中剩余可用的长度以及存储字符串的数组，注意字符串数组末尾的'\0'不计算在SDS的len属性里面. 其中buf数组是一个柔性数组. 关于柔性数组可以看一下这篇博客：C语言结构体里的成员数组和指针.

根据这个结构体，我们展示一个SDS示例：

• free属性的值为0，表示这个SDS没有分配任何未使用的空间.
• len属性的值为5，表示这个SDS保存了一个五字节长的字符串.
• buf属性是一个char类型的数组，数组的前五个字节分别保存了'R'、'e'、'd'、'i'、's'五个字符，而最后一个字节则保存了空字符'\0'.

从redis-3.2.0版本之后（包括3.2.0），关于SDS表头的定义是这样的：

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

表头的大体思路是一样的，但是高版本一共有五种关于Header的定义，目的是为不同长度的字符串提供不同大小的Header，以节省内存. 以 sdshdr8 为例，其 len 属性为 uint8_t 类型，占用内存大小为 1 字节，则存储的字符串最大长度为256.

Header主要包含了四个字段：

• len：字符串的长度，不包含终止字符.
• alloc：除去表头和'\0'的buf数组长度.
• flags：标志header的类型.
• buf：储存字符串的数组.

3. SDS的优点

3.1 兼容C的部分函数

SDS字符串采用'\0'结尾，兼容传统的C风格字符串，因此可以直接使用C的部分字符串函数.

3.2 常数复杂度获取字符串长度

SDS在表头的len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度仅为O(1).

3.3 杜绝缓冲区溢出

SDS字符串表头的free成员记录着buf字符数组中未使用空间的字节数，所以在追加字符串的时候，如果不够用会进行内存扩展，再进行追加.

3.4 二进制安全

传统的C风格字符串的特点是遇零则止，如果保存的二进制数据（图片、视频等）中含有'\0'，相关操作在这里就会被截断.

而SDS表头的buf字段是一个字节数组，判断是否到达字符串结尾的依据是表头的len成员，因此可以存放任何二进制数据和文本数据不被截断，如下图：

4. 部分源码剖析

4.1 空间预分配策略

• 如果对SDS进行修改后，SDS表头的len成员小于1MB，那么就会分配和len长度相同的未使用空间，free和len成员大小相等.
• 如果对SDS进行修改后，SDS的长度大于等于1MB，那么就会分配1MB的未使用空间

通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数.

sds sdsMakeRoomFor(sds s, size_t addlen)   // addlen 需要增加的空间长度
{
    
    struct sdshdr *sh, *newsh;
    // 获得s的未使用空间的长度
    size_t free = sdsavail(s);
    size_t len, newlen;

    // 剩余空间可以满足需求，无须扩展
    if (free >= addlen) return s;

		// 获取表头地址
    sh = (void*) (s-(sizeof(struct sdshdr)));
    // 目前 buf 长度
    len = sdslen(s);
    // 新 buf 长度
    newlen = (len+addlen);
    // 如果新 buf 长度小于 SDS_MAX_PREALLOC（1024*1024）长度
    // 那么将 buf 的长度设为新 buf 长度的两倍
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    // 获得新扩展空间的地址
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    if (newsh == NULL) return NULL;
    
		// 更新free
    newsh->free = newlen - len;
    return newsh->buf;
}

4.2 惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作，当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用.

void sdsclear(sds s) {
    
	// 获取表头地址
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    // 表头free成员+已使用空间的长度len = 新的free
    sh->free += sh->len;
    // 已使用的空间变为0
    sh->len = 0;
    // 字符串置为空
    sh->buf[0] = '\0';
}

4.3 其它部分源码

Redis为SDS提供了非常丰富的API，这里只展示一小部分.

4.3.1 获取SDS的长度

sdslen是一个定义在sds.h中的内联函数，获取字符串的长度其实就是获取SDS表头的len字段.

而在sds.c中，几乎所有的函数传参都是sds类型，而不是表头sdshdr的地址，所以需要使用指针运算来获取表头的地址，表头结构体中一共有三个字段，最后一个buf成员是一个柔性数组，起一个占位符的作用，并不占用该结构体的大小，所以struct sdshdr的大小是固定的，为8字节.

static inline size_t sdslen(const sds s) {
    
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

4.3.2 获取SDS的剩余长度

该函数同样是一个定义在sds.h中的内联函数.

static inline size_t sdsavail(const sds s) {
    
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

4.3.3 创建SDS

// 创建一个长度为initlen的字符串,并保存init字符串中的值
sds sdsnewlen(const void *init, size_t initlen) {
    
    struct sdshdr *sh;

    if (init) {
    
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);  //申请空间：表头+initlen长度+'\0'
    } else {
    
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);  //如果init为空，则将申请的空间初始化为0
    }
    if (sh == NULL) return NULL;
    sh->len = initlen;      //设置表头的len成员
    sh->free = 0;           //设置free，新的sds不预留任何空间
    if (initlen && init)
        memcpy(sh->buf, init, initlen); //将指定的字符串init拷贝到表头的buf中
    sh->buf[initlen] = '\0';    //以'\0'结尾
    return (char*)sh->buf;
}

// 建立一个只有表头，字符串为空"\0"的sds
sds sdsempty(void) {
            
    return sdsnewlen("",0);
}

// 根据字符串init，创建一个与init一样长度字符串的sds（表头+buf）
sds sdsnew(const char *init) {
      
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

// 拷贝一份s的副本
sds sdsdup(const sds s) {
           
    return sdsnewlen(s, sdslen(s));
}

4.3.4 销毁SDS

// 释放字符串和表头
void sdsfree(sds s) {
    
    if (s == NULL) return;
    zfree(s-sizeof(struct sdshdr));
}

4.3.5 SDS的追加

// 将字符串t追加到s表头的buf末尾，追加len个字节
sds sdscatlen(sds s, const void *t, size_t len) {
       
    struct sdshdr *sh;
    size_t curlen = sdslen(s);  //原有的长度

    s = sdsMakeRoomFor(s,len);  //扩展空间
    if (s == NULL) return NULL;
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);   //字符串拼接

    //更新属性
    sh->len = curlen+len;
    sh->free = sh->free-len;
    s[curlen+len] = '\0';
    return s;
}

// 将t字符串拼接到s的末尾
sds sdscat(sds s, const char *t) {
      
    return sdscatlen(s, t, strlen(t));
}

// 将sds追加到s末尾
sds sdscatsds(sds s, const sds t) {
         
    return sdscatlen(s, t, sdslen(t));
}

// 将字符串t覆盖到s表头的buf中，拷贝len个字节
sds sdscpylen(sds s, const char *t, size_t len) {
       
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    size_t totlen = sh->free+sh->len;   //获得总长度

    if (totlen < len) {
             //总长度小于len
        s = sdsMakeRoomFor(s,len-sh->len);  //扩展l空间
        if (s == NULL) return NULL;
        sh = (void*) (s-(sizeof(struct sdshdr)));
        totlen = sh->free+sh->len;  //更新总长度
    }
    memcpy(s, t, len);  //拷贝字符串t覆盖s原有的字符串

    //更新表头
    s[len] = '\0';
    sh->len = len;
    sh->free = totlen-len;
    return s;
}

// 将字符串覆盖到s表头的buf中
sds sdscpy(sds s, const char *t) {
          
    return sdscpylen(s, t, strlen(t));
}

4.3.6 SDS的删除

// 去除sds中包含有cset字符串的部分
sds sdstrim(sds s, const char *cset) {
      
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    char *start, *end, *sp, *ep;
    size_t len;

    //设置和备份指针位置
    sp = start = s;
    ep = end = s+sdslen(s)-1;

    //strchr()函数功能：查找cset中首次出现*sp字符的位置，成功返回第一次出现的位置
    while(sp <= end && strchr(cset, *sp)) sp++;         //从左开始修剪，sp为目标串的左边界
    while(ep > start && strchr(cset, *ep)) ep--;        //从右开始修剪，ep为目标串的右边界

    len = (sp > ep) ? 0 : ((ep-sp)+1);  //目标串的长度
    if (sh->buf != sp) memmove(sh->buf, sp, len);   //将字符串的位置前移到buf开头

    //更新表头
    sh->buf[len] = '\0';
    sh->free = sh->free+(sh->len-len);
    sh->len = len;
    return s;
}

参考资料：

《Redis设计与实现》

Redis源码剖析和注释