Redis中的字符串

Redis没有使用原生的C字符数组，它通过自己的SDS(simple dynamic string)来作为默认的字符串表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//sds.h
/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

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

    // 数据空间
    char buf[];
};

封装这个数据结构的好处在于

  • 在O(1)时间里得到字符串长度

  • 避免缓冲区溢出

    缓冲区溢出这个问题的出现是因为没有预先分配足够的内存，然后新数据覆写了原数据后面的内容，在Redis中SDS的API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话API会先将SDS扩容到执行修改所需的大小，然后再执行具体的操作。也就规避的数据覆写的问题。

    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
    /*
     * 将长度为 len 的字符串 t 追加到 sds 的字符串末尾
     *
     * 返回值
     *  sds ：追加成功返回新 sds ，失败返回 NULL
     *
     * 复杂度
     *  T = O(N)
     */
    /* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
     * end of the specified sds string 's'.
     *
     * After the call, the passed sds string is no longer valid and all the
     * references must be substituted with the new pointer returned by the call. */
    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;
    }

  • 避免频繁重分配内存

    C的字符串无论是扩大还是缩减都需要重新分配内存，SDS则是提供一个缓冲区提前申请好内存如果数据增量小于缓冲区的大小则直接放入缓冲区，避免了频繁的重分配。

    • 空间预分配

      缓冲区的大小由以下规则决定：

      • 如果对SDS进行修改后SDS的长度(len的长度)小于1MB，那么将给SDS分配和len同样大小的未使用空间，这是SDS len的值free的值相同。

      • 如果SDS修改后的长度大于1MB，那么将分配1MB的缓冲区。

        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
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        /* Enlarge the free space at the end of the sds string so that the caller
         * is sure that after calling this function can overwrite up to addlen
         * bytes after the end of the string, plus one more byte for nul term.
         * 
         * Note: this does not change the *length* of the sds string as returned
         * by sdslen(), but only the free buffer space we have. */
        /*
         * 对 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 分配新空间所需的大小
            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;
        }

    • 惰性空间释放

      • 当缩容SDS时不会立刻回收原本被占据的空间，而是用free将这些空间记录下来

    • 二进制安全

      SDS的buf不是用来保存字符的，而是用来保存一系列二进制数据。因为SDS使用len属性的值而不是空字符串来判断字符串是否结束。