Redis源码阅读02-数据结构sds

redis为什么不使用c语言对字符串的实现？

c语言的字符串表示有一下几个缺点： - c语言的字符串是以\0作为判断数组结束的标记，所以如果存储的字符串中包含\0的话，则无法获取全部的字符。 - c语言字符串的获取字符串长度，只能将内容进行遍历后才能获取到长度，时间复杂度是O(n)。 - c语言字符串不记录自身的长度，所以strcat方法已经认为用户在执行此函数时已经为dest分配了足够多的内存，足以容纳src字符串中的所有内容，而一旦这个条件不成立就会产生缓冲区溢出，会把其他数据覆盖掉。

sds解决了以上问题 - 拥有len属性记录字符串长度，获取长度的时间复杂度由O(n)变为直接获取len属性的O(1) - sds在拼接时首先会获取可用空间，并进行判断是否需要进行扩容，所以不会造成缓存区溢出，这点上比c语言的string是更安全的 - sds在扩容时实现了空间预分配，申请内存时会多申请一部分内存出来，一定程度上避免频繁申请内存。

空间预分配

sds预空间分配的实现就在 sds.c的sdsMakeRoomFor方法中，首先通过sdsavail方法获取sds的剩余空间，然后判断剩余空间是否足够新增长度的使用，如果足够使用则直接返回，如果不足够使用，则判断（新增长度+已用长度）所需长度是否是小于1M，如果小于1M，则直接加倍。这种方式相当于预分配了一部分内存，

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //获取sds剩余空间
    size_t avail = sdsavail(s);
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /* Return ASAP if there is enough space left. */
    //判断字符串的剩剩余空间是否足够，如果足够直接返回
    if (avail >= addlen) return s;
    //获取字符串的原长度
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    //字符串的新长度 = 原长度 + 新增长度
    reqlen = newlen = (len+addlen);
    assert(newlen > len);   /* Catch size_t overflow */
    //这里判断新长度是否超过了1M
    if (newlen < SDS_MAX_PREALLOC)
        //没超过直接申请所需长度的2倍
        newlen *= 2;
    else
        //超过了1M则申请newlen + 1M的长度
        newlen += SDS_MAX_PREALLOC;
    // 转换新长度的类型
    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    //根据新长度转换的类型获取hdr结构体的长度
    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > reqlen);  /* Catch size_t overflow */
    //如果类型没有变更 
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}

sds的指针位置

sds新建字符串的方法 sdsnew和sdsnewlen的实现方法，可以看到，s对应的指针，就是buf的所在位置，所以sds也可以直接当做string来使用，巧妙的指针使用也是让sds完美兼容string，另外因为sdshdr的定义是使用的紧凑式内存对齐（参考sds对齐），还可以通过buf的位置-1直接找到flags的位置。

sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    //这里定义了sds的对象s
    sds s;
    //根据长度转换sds的type
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    //根据 type计算出sds sdshdr的长度。
    int hdrlen = sdsHdrSize(type);
    //定义flags的指针
    unsigned char *fp; /* flags pointer. */
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */
    //申请内存
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    //将sds的指针指向 sh+hdrlen，也就是buf数组的位置
    s = (char*)sh+hdrlen;
    //s-1的位置也就是 flags的位置
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

free space 可用空间

free space可用空间（也有文章翻译叫惰性空间），一方面是指空间预分配以后除去占用的空间以外空余的空间，另一方面，在sds进行修改时，并不会将sds已经申请的buf[]空间的内存进行回收，仅是将sds的len值进行重新设置，已经申请的空间在那里留着以后再用。

static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

关于sds的最大长度为512mb

当客户端操作 client 时，一般不会直接使用 sds ，而是通过对象的方式来使用。比如创建的字符串其实是一个对象，间接使用到了 sds 结构。限制 512M 的逻辑在 t_string.c 的 checkStringLength 方法。

在redis3.2.13、redis4.0.14、redis5.0.9版本里面的的一个方法，checkStringLength里面写死了限制512*1024*1024，这个方法常在 SET/HSET的时候被调用。

static int checkStringLength(client *c, long long size) {
    if (size > 512*1024*1024) {
        addReplyError(c,"string exceeds maximum allowed size (512MB)");
        return C_ERR;
    }
    return C_OK;
}

而在redis6.2.7版本里面，这个长度已经改为读取配置 proto-max-bulk-len的长度了。

static int checkStringLength(client *c, long long size) {
    if (!(c->flags & CLIENT_MASTER) && size > server.proto_max_bulk_len) {
        addReplyError(c,"string exceeds maximum allowed size (proto-max-bulk-len)");
        return C_ERR;
    }
    return C_OK;
}