Redis--简单动态字符串

简介

Redis构建了一种名为简单动态字符串(simple dynamic string ,SDS)的抽象类型,用来保存字符串。

SDS 实现

shs.h文件中sdshdr结构体表示了一个SDS的值:

1
2
3
4
5
6
7
8
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};

SDS结构

  • SDS和C字符串一样,使用空字符结尾,保存空字符串的1字节空间不包含在SDS的len属性里面,因此需要分配N+1个字节空间来保存数据。
  • len属性表示SDS保存字符串的长度,不包含字符串结尾的空字符串。
  • free属性表示数组中未使用的字节数量
  • buf属性是char类型的数组,用来保存SDS字符串数据。

    SDS 特点

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

    在更新和添加字符串到SDS的过程中,SDS的API会自动更新SDS的len属性,不需要手动更改,因此获取字符串长度的时间复杂度是O(1)。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /*
    * 返回 sds 实际保存的字符串的长度
    *
    * T = O(1)
    */
    static inline size_t sdslen(const sds s) {
    //// 取出 sdshdr
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
    }

    防止缓存区溢出

    C字符串不记录自身的长度,容易发生缓冲区溢出。SDS的free属性记录数组中未使用的字节数量,SDS的API操作SDS会首先检查剩余空间是否满足要求,所以不会发生缓冲区溢出的情况。

    内容重分配策略

    空间预分配

    需要对SDS进行空间扩展时,程序不仅会为SDS分配所必须的空间,还会分配额外未使用的空间。
  • 对SDS修改之后,SDS的长度小于1MB,那么程序分配和len属性同样大小的空间,假设修改后SDS的大小是13字节,那么将分配13+13+1=27个字节。
  • 如果对SDS修改之后,SDS的长度大于等于1MB,将分配1M未使用空间。假设修改后SDS的长度是30MB,那么程序会分配1MB未使用空间,实际大小为:30MB+1MB+1byte.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    /*
    * 最大预分配长度
    */
    #define SDS_MAX_PREALLOC (1024*1024)
    /*
    * 对 sds 中 buf 的长度进行扩展,确保在函数执行之后,
    * buf 至少会有 addlen + 1 长度的空余空间
    * (额外的 1 字节是为 \0 准备的)
    *
    * 返回值
    * sds :扩展成功返回扩展后的 sds
    * 扩展失败返回 NULL
    *
    * 复杂度
    * T = O(N)
    */
    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 分配新空间所需的大小
    //判断分配后的总长度是否小于1MB
    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;
    }

    惰性空间释放

    惰性空间释放是指不通过内存重分配回收缩短后多出来的字节,而是通过改变free属性,惰性的释放空间。下面的代码就是在不释放空间的情况下,重置SDS字符串为空字符串,也就是惰性空间释放:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /*
    * 在不释放 SDS 的字符串空间的情况下,
    * 重置 SDS 所保存的字符串为空字符串。
    *
    * 复杂度
    * T = O(1)
    */
    /* Modify an sds string on-place to make it empty (zero length).
    * However all the existing buffer is not discarded but set as free space
    * so that next append operations will not require allocations up to the
    * number of bytes previously available. */
    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';
    }

    二进制安全

    C字符串除了字符串的未尾之外,字符串里面不能包含空字符,否则最先被程序读入的空间将被误认为是字符串结尾,这些限制了C字符串只能保存文本数,不能保存图片等二进制数据。SDS没有这种限制,可以保存文本或者二进制数据

    SDS API

    函数 作用 算法复杂度
    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))

学习资料:
[1] 黄健宏. Redis设计与实现[M]. 机械工业出版社, 2014.