【每日一博】Redis 中的字符串实现 sds

r囧r小猫 2022-01-27 02:47 205阅读 0赞

在C中子字符串的实现都是用 char \*来实现的，用起来很不方便，而且容易出现内存泄露，并且效率不高，在Redis内部，字符串采用了 sds 的方式进行了封装，似的字符串在Redis中可以方便、高效的使用，Redis字符串的实现如要依赖一下两个数据类型和结构（以下代码可以在 src/sds.h中找到）：

typedef char *sds;
    sds 存放了字符串的具体值
    
    struct sdshdr {
        int len;   //字符串对象已经使用的内存数量
        int free;  //字符串对象剩余的内存数量
        char buf[]; //字符串对象的具体值（其实就是sds字符串）
    };

sdshdr 实现了字符串对象

这样设计的好处有很多，比如使得Redis在获取字符串长度的时候可以达到o(1)的复杂度，在进行追加等字符串操作的时候，可以减少内存分配（提高性能），sdshdr的结构使得根据sds字符串获取对应的sds对象的时候可以非常方便的获取。

创建字符串 init 为需要初始化的字符串值。initlen表示为初始化字符串的长度，该函数创建一个sds字符串对象并返回sds字符串（以下代码可以在 src/sds.c中找到）：

sds sdsnewlen(const void *init, size_t initlen) {
        struct sdshdr *sh; //创建一个空的字符串对象
    
        //如果init为空的时候需要对分配的内存进行初始化
        if (init) {
            sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
        } else {
            sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
        }   
        if (sh == NULL) return NULL;
        //设置字符串对象的已占用长度
        sh->len = initlen;
        sh->free = 0;
        //如果init不为空将其复制到字符串对象中
        if (initlen && init)
            memcpy(sh->buf, init, initlen);
        //在结尾加入终止符（c语言字符串以\0为结尾）
        sh->buf[initlen] = '\0';
        //返回字符串对象中的sds值
        return (char*)sh->buf;
    }

例如你创建了一个sds字符串 为 hello 那么你的代码应该如下：

sds str = sdsnewlen("hello", 5);

这时候，Reids会创建一个sdshdr对象，长度为：

sizeof(struct sdshdr) + 5 + 1

Redis在释放字符串也会分方便，因为是对整个结构进行的分配所以只需要对sds字符串的对象进行释放就可以将字符串值和字符串对象的内存都释放掉，如下：

void sdsfree(sds s) {
        if (s == NULL) return;
        zfree(s-sizeof(struct sdshdr));
    }

释放上例中的sds字符串只需要简单的调用：

sdsfree(str);

1.  根据sds字符串获取对应的字符串对象

如1中你知道了如何创建一个字符串对象并返回它的sds字符串，根据sdshdr的存储结构，你可以方便的通过返回的sds字符串得到字符串对象，如下代码：(下面代码中s表示sds字符串，定义为 sds s;)

struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));

由1中创建的hello的字符串对象在内存中的分配大概如下图：

![image][]

上例中的 s 为 sdshdr结构中的buf元素，上例代码中的 s - sizeof(struct sdshdr) 会将指向buff 的指针，移动到len上，这样通过一个简单的运算就可以获取到sds字符串的对象，并对其进行字符串操作（不知道为啥redis宁可每次手动写，也没有对此进行一个宏定义的封装）。

1.  计算字符串长度

计算长度的方式就非常简单了只需要根据sds字符串获取到sds对象，然后获取其len属性即可，具有o(1)的效率，而不需要去遍历字符列表，如下获取方法（以下代码可以在 src/sds.h中找到）：

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

1.  追加字符串

Redis的追加字符串由于其设计方式可以非常高效，进行追加，直接看代码（以下代码可以在 src/sds.c中找到）：

sds sdscatlen(sds s, const void *t, size_t len) {
        struct sdshdr *sh;      //定义一个字符串对象
        size_t curlen = sdslen(s);   //获取当前sds字符串的长度 可以参考第3条
    
        s = sdsMakeRoomFor(s,len);   //对sds字符串扩展，申请len长度的内存（会根据free决定是否申请，见下文）
        if (s == NULL) return NULL;
        sh = (void*) (s-(sizeof(struct sdshdr)));   //根据新申请空间后的sds字符串获取对应的对象
        memcpy(s+curlen, t, len);    //将新的字符串追加到结尾
        sh->len = curlen+len;     //更新已占用空间
        sh->free = sh->free-len;  //更新剩余空间
        s[curlen+len] = '\0';     //设置字符串结尾
        return s;     //返回修改后的sds字符串
    }

对sds字符串内存进行扩展的函数如下：（以下代码可以在 src/sds.c中找到）：

sds sdsMakeRoomFor(sds s, size_t addlen) {
        struct sdshdr *sh, *newsh;   //初始化两个字符串对象
        size_t free = sdsavail(s);   //字符串剩余内存，定义在src/sds.h中，获取方法与 sdslen()相同
        size_t len, newlen;
    
        if (free >= addlen) return s;
        len = sdslen(s);   //获取当前字符串长度
        sh = (void*) (s-(sizeof(struct sdshdr)));   //获取当前的字符串对象
        newlen = (len+addlen);    //计算扩展后的字符串长度
        //一下为重点：申请字符串会计算，新的长度是否会超过SDS_MAX_PREALLOC（定义在src/sds.h中，默认为1M）
        //如果超过则申请SDS_MAX_PREALLOC大小的内存，否则申请2*扩展后字符串的长度
        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;
    
        newsh->free = newlen - len;  //更新剩余空间
        return newsh->buf;
    }

如上代码所述，系统在扩展内存的时候，会申请新字符串长度的两倍，这样后续在进行追加操作的时候就不进行内存分配处理了，节省了很多内存分配的消耗，当然这样可能会对内存造成一些浪费，Redis的一些配置可以改变这种行为，可以通过字符串函数 sdsRemoveFreeSpace() 对多申请的那部分内存进行释放。

[image]: /images/20220127/90db12653043444c86a95631dc75ce85.png