Redis设计与实现-数据结构篇（1）--简单动态字符串SDS

发表于 | 分类于 |

Redis中的SDS结构

sds结构

Redis并没有使用C语言传统的字符串结构，而是实现了自己的字符串结构sdshdr。具有以下特点：

  • 兼容传统C语言字符串类型，C语言字符串能够使用的函数，sds也能够使用
  • 可以O(1)获取字符串长度和空闲空间
  • 以数组的形式存储真正的字符串，保证了字符串二进制安全。
  • 避免了缓冲区溢出的情况

V71x3R.md.jpg

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

sds字符串获取和长度获取

在sds结构中，sds指向的buf成员是一个柔性数组，它只起到占位符的作用，并不占用空间。所以sizeof(struct sdshdr)的大小为8字节。

由于sds类型的内存是通过动态内存分配的，所以它存储的内存位置在堆区，结构如下图。因此sds指针减区sizeof(struct sdshdr)的大小就得到了表头的地址，然后就可以通过”->”访问表头的成员。
所以我们看到在sds.c中，几乎所有的函数的参数都是sds类型，而非表头地址。就是使用了通过sds指针运算可以获得表头地址的技巧。
V71vC9.jpg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * 返回 sds 实际保存的字符串的长度
 *
 * T = O(1)
 */
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

/*
 * 返回 sds 可用空间的长度
 *
 * T = O(1)
 */
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

sds申请

  1. 根据是否需要初始化，使用zmalloc和zcalloc两个不同函数。
  2. 一个字符串刚开始申请的时候，其free空间为0。第一次申请的实际申请空间位sizeof(sdshds)+len+1。
  3. 由于返回的是sh->buf，那么如果需要计算sh的长度或空闲空间怎么办？根据前面的sdslen函数，我们可以知道是通过减去两个int长度就得到了sh的地址。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    sds sdsnewlen(const void *init, size_t initlen) {
        struct sdshdr *sh;

        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;
        if (initlen && init)
            memcpy(sh->buf, init, initlen);
        sh->buf[initlen] = '\0';
        return (char*)sh->buf;
    }

sds预分配

  1. 如果空闲长度大于需要增加的长度，则不会申请
  2. 如果新sds长度=（原sds长度+需要增加的长度）小于SDS_MAX_PREALLOC（1M）则申请新sds长度的2倍，否则每次只申请1M的空间
    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
    /* 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 sdsMakeRoomFor(sds s, size_t addlen) {
        struct sdshdr *sh, *newsh;
        size_t free = sdsavail(s);
        size_t len, newlen;

        if (free >= addlen) return s;
        len = sdslen(s);
        sh = (void*) (s-(sizeof(struct sdshdr)));
        newlen = (len+addlen);
        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;
    }

sds惰性删除

惰性空闲释放用于优化sds的字符串缩短操作。
当要缩短sds保存的字符串时，程序并不会立即进行内存回收操作，而是使用表头的free成员将这些字节记录，等待以后使用。

1
2
3
4
5
6
void sdsclear(sds s) {  //重置sds的buf空间，懒惰释放
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    sh->free += sh->len;    //表头free成员+已使用空间的长度len = 新的free
    sh->len = 0;            //已使用空间变为0
    sh->buf[0] = '\0';         //字符串置空
}

函数 作用 时间复杂度
sdsnew 创建一个包含给定C字符串的SDS O(N)
sdsempty 创建一个内容为空的SDS O(1)
sdsfree 释放给定的SDS O(N)
sdslen 返回SDS已使用空间字节数 O(1)
sdsavail 返回SDS未使用的空间字节数 O(1)
sdsdup 创建一个给定的SDS副本 O(N)
sdsclear 清空SDS保存的字符串内容 O(1)
sdscat 将给定的C字符串拼接到SDS末尾 O(N)
sdscatsds 将给定的SDS字符串拼接到SDS末尾 O(N)
sdscpy 将给定C字符串复制到SDS中，覆盖原有的字符串 O(N)
sdsgrowzero 用空字符串扩展至给定长度 O(N)
sdsrange 保留SDS给定区间的数据，不在区间内的数据将会被清除 O(N)
sdstrim 将SDS中出现的C字符串给清除 O(M*N)
sdscmp 对比两个SDS是否相同 O(N)