Redis实现 -- 动态字符串

简单的动态字符串

一、C语言中的字符串

字符串是一种非常重要的数据类型，在Java中，有专门的数据类型来表示字符串。比如String类型、StringBuffer类型等。但是在C语言中不存在显示的字符串类型，都是以字符串常量的形式出现或存储在字符数组中。

1、字符串常量

所谓的字符串常量，就是：以’/0’结尾的多个字符组成的序列。字符串常量是不可被修改的。

比如：”Hello world”，””，”字符串”。

字符串常量可以为空，但是依旧会存在终止符”/0”。

前面说过，C语言中不能直接进行字符串赋值。因此在C语言中，通常声明一个指向char类型的指针并将其初始化为一个字符串常量的方式来访问一个字符串。

//声明一个指向char类型的指针
char *name = "Jiang Zhwiei";

2、字符数组

字符数组就是：char类型的数组。

char charArray[] = {'J','Z','W'};

上面的代码，声明并且初始化了一个字符数组。数组的长度是4，因为会自动添加’\0’。

我们可以简化上述的字符串初始化。

char charArray = "JZW";

二、Redis中的字符串

在Redis中，没有直接使用C语言中传统的字符串。而是自己构建了一种名为简单动态字符串（Simple Dynamic String，SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。

SDS 的定义

在源文件sds.h中有SDS的定义：

struct sdshdr {
    // 记录buf数组中已使用字节的数量
    // 等于SDS所保存字符串的长度
    int len;

    // 记录buf数组中未使用字节数量
    int free;

    // 字节数组   用于保存字符串
    char buf[];
};

上图中是一个SDS字符串的实例。

buf[] 记录了字符串的内容。数组的前五个是保存的字符，最后一个是结束符。

len 记录了SDS字符串的长度。当前记录了五个字节长度的字符串。

free 记录了SDS中还未分配空间。当前还未分配字符的空间未0。

SDS遵循了C语言串以空字符结尾的惯例。并且最后的’\0’没有记录在len属性中。

这个空字符’\0’对于SDS来说是透明的。因此关于这个空字符的操作都是由SDS函数自动完成的。比如：添加空字符到字符串末尾、未空字符分配额外的1字节空间。

三、SDS与C字符串的区别

1、常量复杂度获取字符串长度

在C语言字符串中并不记录自身的长度。因此为了获取C字符串的长度，就必须遍历整个字符串。**时间复杂度是O(N)**。

与C字符串不同，因为SDS在len属性中记录了SDS本身的长度。时间复杂度是O(1)。设置和更新SDS长度的工作是由SDS的API在执行时自动完成的。使用SDS无须无需进行任何手动修改长度的工作。

2、杜绝缓冲区溢出

在C字符串不记录自身长度带来的另一个问题就是缓冲区溢出。

在C语言库函数中，有字符串拼接函数，比如：

char *strcat(char *dest,const char *src)

此时如果执行：

strcat(s1,"hello world");

因为s1中缓冲区长度不够，那么就会出现溢出。就会覆盖s2的内容。

对于SDS来说，因为记录了缓冲区的长度。因此在执行拼接操作之前，会检查给定的SDS的空间是否足够。 在之后的API中我们可以具体来查看源码。

3、减少修改字符串时带来的内存重分配次数

C语言中的重分配

C语言不记录字符串长度，因此在增长或缩短一个字符串时，程序总是会对保存这个C字符串的数组进行一个内存的重分配操作。

• 如果程序执行的是增长字符串的操作。比如拼接操作(append)。那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小。否则会出现缓冲区溢出。
• 如果程序执行的是缩短字符串的操作。比如截断操作(trim)。那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间。否则会出现内存泄漏。

Redis作为数据库，速度要求严苛，数据修改频繁。如果每次修改字符串的长度都需要执行一次内存重分配的话，会对性能会造成影响。

Redis中的改进

因此，为了避免C字符串的这种缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。在SDS中，buf数组长度不一定是字符数量加1。数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。

1. 空间预分配

   空间预分配用于优化SDS的字符串增长操作，当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所需要的空间，还会为SDS分配额外的未使用空间。

   SDS额外分配未使用空间数量由以下公式来决定：

   • 如果修改SDS之后的长度小于1 MB。那么程序分配和len属性同样大小的未使用空间。这是SDS中len属性和free属性的值相同。

     比如：如果进行修改之后，SDS的len属性变成了13字节，那么程序也会分配13字节的未使用空间。此时SDS的buf[]数组的长度将变成27字节(13 B + 13 B + 1 B)。

   • 如果修改SDS之后的长度大于1 MB。那么程序会分配1 MB的未使用空间。

     如果：如果进行修改之后，SDS的len变成30 MB，那么程序会分配1 MB的未使用空间。此时buf[]数组中的长度将变成30 MB+1 MB+1 B。

​ 通过这种方式，SDS会先检查未使用空间是否足够，如果足够的话，API就会直接使用未使用空间，而无需执行内存重分配。

​ 通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。

2. 惰性空间释放

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

   

   移除SDS字符串中所有的’B’字符。

   如果执行sdstrim(s,”B”);

​

​ 执行sdstrim之后的SDS并没有释放出来1个字节。而是将这1字节空间作为未使用空间保留在SDS里面。

​ 同时，SDS也提供了相应的API，让我们可以在有需要时，真正地释放SDS的未使用空间，所以不要担心惰性空间释放策略会造成内存浪费。

4、二进制安全

什么是二进制安全？

二进制安全是一种主要用于字符串操作函数相关的计算机编程术语。一个二进制安全的函数，其本质上将操作输入作为原始的、无任何特殊格式意义的数据流。对于每个字符都公平对待，不特殊处理某一个字符。

C语言中以’\0’为结束符。那么C字符串所用的函数只会识别出其中的"ACD"，而忽略"ABC"。

对于Redis来说：

SDS的API都是二进制安全的。所有的SDS API 都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据进行任何的过滤和限制。

5、兼容部分C字符串函数

虽然SDS的API都是二进制安全的，但他们一样遵循C字符串以空字符结尾的惯例。

因此SDS可以重用一部分<String.h>库定义的函数。

四、SDS API

在源代码中，sds.h 和 sds.c中有声明和定义这些SDS API。

在下面的代码中，会大量出现这样的代码。

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

sh是SDS的指针，而s是SDS中buf的指针。

我们通常在SDS函数中，使用的是s来记录SDS。这样可以方便去访问buf缓冲区，还可以轻松去得到SDS的地址。

1、 创建一个 SDS

根据给定的初始化字符串 init 和字符串长度 initlen

//init 字符串   initlen  字符串长度
sds sdsnewlen(const void *init, size_t initlen) {
    //声明sds变量
    struct sdshdr *sh;

    // 根据是否有初始化内容，选择适当的内存分配方式
    // T = O(N)
    if (init) {
        // zmalloc 不初始化所分配的内存
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        // zcalloc 将分配的内存全部初始化为 0
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }

    // 内存分配失败，返回
    if (sh == NULL) return NULL;

    // 设置初始化长度
    sh->len = initlen;
    // 新 sds 不预留任何空间
    sh->free = 0;
    // 如果有指定初始化内容，将它们复制到 sdshdr 的 buf 中
    // T = O(N)
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    // 以 \0 结尾
    sh->buf[initlen] = '\0';

    // 返回 buf 部分，而不是整个 sdshdr
    return (char*)sh->buf;
}

2、释放SDS

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

3、重置SDS内容

void sdsclear(sds s) {

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

    // 重新计算属性
    sh->free += sh->len;
    sh->len = 0;

    // 将结束符放到最前面（相当于惰性地删除 buf 中的内容）
    sh->buf[0] = '\0';
}

4、扩展SDS长度

#define SDS_MAX_PREALLOC (1024*1024)

sds sdsMakeRoomFor(sds s, size_t addlen) {

    struct sdshdr *sh, *newsh;

    // 获取 s 目前的空余空间长度
    size_t free = sdsavail(s);

    size_t len, newlen;

    // s 目前的空余空间已经足够，无须再进行扩展，直接返回
    if (free >= addlen) return s;

    // 获取 s 目前已占用空间的长度
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));

    // s 最少需要的长度
    newlen = (len+addlen);

    // 根据新长度，为 s 分配新空间所需的大小
    if (newlen < SDS_MAX_PREALLOC)
        // 如果新长度小于 SDS_MAX_PREALLOC 
        // 那么为它分配两倍于所需长度的空间
        newlen *= 2;
    else
        // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

    // 内存不足，分配失败，返回
    if (newsh == NULL) return NULL;

    // 更新 sds 的空余长度
    newsh->free = newlen - len;

    // 返回 sds
    return newsh->buf;
}

5、 追加字符串

sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *sh;
    
    // 原有字符串长度
    size_t curlen = sdslen(s);

    // 扩展 sds 空间
    // T = O(N)
    s = sdsMakeRoomFor(s,len);

    // 内存不足？直接返回
    if (s == NULL) return NULL;

    // 复制 t 中的内容到字符串后部
    // T = O(N)
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);

    // 更新属性
    sh->len = curlen+len;
    sh->free = sh->free-len;

    // 添加新结尾符号
    s[curlen+len] = '\0';

    // 返回新 sds
    return s;
}

6、对比两个SDS字符串是否相同

//对比两个 sds ， strcmp 的 sds 版本
int sdscmp(const sds s1, const sds s2) {
    size_t l1, l2, minlen;
    int cmp;

    l1 = sdslen(s1);
    l2 = sdslen(s2);
    minlen = (l1 < l2) ? l1 : l2;
    cmp = memcmp(s1,s2,minlen);

    if (cmp == 0) return l1-l2;

    return cmp;
}