Redis源码学习——基础数据结构之SDS

2021-11-03 21:13:52

Redis数据结构-SDS

Redis是一个开源（BSD许可），内存存储的数据结构服务器，可用作数据库，高速缓存和消息队列代理。

首先介绍下Redis的基础数据结构 —— SDS
Redis没有使用传统C语言的字符串（字符数组）表示。而是自己构建了一种名为sds(Simple Dymamic String)的抽象类型，作为redis的默认字符类型。 SDS用于保存数据库中的字符串值，用户客户端的输入的缓冲区，AOF模块中的缓冲区都是由SDS实现的。

SDS相比于C字符串的优点：

常数复杂度获取字符串长度
缓冲区溢出
减少改变字符串长度时带来的内存重新分配
二进制安全

同时，sds也支持c字符串的部分操作函数。

SDS的数据结构：

以下是SDS的数据结构

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};
// ps: 在redis 3.0中  为了更加节省内存，可用的sdshdr分成4种，len和free属性分别可以是uint8_t，uint16_t，uint32_t，uint64_t 这四种类型，会随着sds所保存的字符串长度不同，而分配为不同的sdshdr。

获取长度；

Redis中获取字符长度的操作是
STRLEN key

C语言中的字符串并不记录自身的长度信息。如果我们想要获取一个c字符串的长度，我们要遍历整个字符串，直到遇到代表结尾符的'/n'为止。毫无疑问，其复杂度是O(N)。
而在sds中，我们记录了每个sds对象中所存字符串的长度。 sds提供了一系列操作sds的函数，若出现改变数组长度的草走，都会同步更新len字段，保证len字段的实时性。这样每个STRLEN的复杂度就变成了O(1).

缓存区溢出：

C语言中提供了strcat方法，可以将strSrc字符串拼到strDest字符串尾部。然而每次执行strcat操作时，都假设了我们已经strDest指针分配了足够多的内存。然而一旦当分配的内存不足，机会出现缓存区溢出。如下：

#include <stdio.h>
#include <string.h>

int main(void)
{    
    char dest[20] = "Hey ";
    for(int i = 0; i < 20; i++) {
        strcat(dest, ", Man");    
        printf("%d time, lenght is: %ld \n", i, strlen(dest));
    }
    return 0;
}

执行结果：

0 time, lenght is: 9
1 time, lenght is: 14
2 time, lenght is: 19
[1]    29751 abort      ./str

可以看到，当执行到第三次的时候，并不会由于dest已经快到其最大容量。所以第四次strcat执行时，会出现溢出，中断程序。
而在sds中，执行sdscat操作，会判断为目标sds对象所分配的内存是否可以容纳拼接后的字符内存。代码如下：

sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}
sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *sh;
    
    // 获取原字符长度
    size_t curlen = sdslen(s);

    // 扩展空间。 若原指针分配内存不足，则重新分配内存。 返回新的地址
    // T = O(N)
    s = sdsMakeRoomFor(s,len);

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

    // 获取sds句柄sdshdr 的指针位置
    sh = (void*) (s-(sizeof(struct sdshdr)));
    
    // 复制将t中字符串复制到目标字符串后面
    // T = O(N)
    memcpy(s+curlen, t, len);

    // 更新属性
    sdssetlen(s, curlen+len);

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

    // 返回新 sds
    return s;
}

可以看到，每次执行字符串拼接操作，都会判断所分配的内存是否足够，如果不足，会重新分配内存。其他操作，例如sdsrange（仅保留部分字符串），sdstrim（裁剪特定字符）都会有以上类似逻辑，保证每次操作都会即时释放多余内存，且不会出现内存不足。

减少改变字符串长度时带来的内存重新分配

然而通过C字符串执行会改变字符串长度的操作，也可以通过判断字符串长度实现预分配内存。每次内存重新分配都要将原内存中的字符复制到新内存中，复杂度是O(N)，然而当我们频繁地对一个字符串进行改变长度的操作，会导致每次操作都引起一次O(N)的操作。
在sds中，每次重新分配内存都会预留一部分作为buffer，我们可以从上文的代码中看到，重新分配内存是通过sdsMakeRoomFor函数调用。那么我们看下sdsMakeRoomFor中，分配内存的策略：

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 
        // 那么为它分配两倍于所需长度的空间
        // 对新建的sds或者重新分配内存的sds，都会采用此策略，保留1倍的长度
        newlen *= 2;
    else
        // 否则，所保留的buffer长度为 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    
    // T = O(N)
    // 分配内存，获取新的指针地址
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

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

    // 设置剩余空间长度。
    newsh->free = newlen - len;

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

redis中为了减少内存的重新分配，使用了预留buffer的方法。将原来n次字符串操作一定有n次O(N)复杂度的内存分配，调整为最多有n次O(N)复杂度的内存分配。
tips：当执行sdstrim这样减少字符串长度的操作时，即时裁剪后多余的内存大于len的一半，sds也不会立即将多余的空间释放，而是保留下来未将来的增长操作做了优化。且提供了sdsRemoveFreeSpace这个APi，用于我们可以手动将这样多余的内存释放。

二进制安全

二进制安全是一个主要用来处理字符串操作的编程术语。二进制安全功能本质上是把输入当作一个没有任何特殊的原生流，其在操作上应包含一个字符所能有的256种可能的值（假设为8为字符）。
由于C字符串需要通过'0'判断字符串的结尾。所以当我们储存字符串时，需要将'0'这样的特殊字符过滤掉。在sds中，由于我们维护了字符串的长度，所以并没有这样的顾虑。 sds符合二进制安全。

支持c字符串的部分操作函数

由于sds的api提供的入参都是sds格式，指向的都是其buf属性的指针位置。我们以一个创建sds的api为例：

sds sdsnewlen(const void *init, size_t initlen) {

    struct sdshdr *sh;
    // do somethings to create sds...
    
    sh->len = initlen;
    sh->free = 0;
    sh->buf[initlen] = '\0';

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

我们可以看到，sds对象，我们获取的并不是整个sdshdr指针的位置，而是其buf属性的指针，也就是存字符串的指针位置，且sds遵守了以'0'作为一个字符串结尾的条件（但并不是通过'0'的位置判断字符串的长度）。这样就保证了我们对一部分C字符串接口传入sds对象的指针，是可以当作char[]用的。

码农公寓