Redis原理-源码解析:数据结构1 字符串操作&SDS及预分配的实现验证

  created  by  鱼鱼 {{tag}}
创建于 2020年11月09日 01:06:08 最后修改于 2020年11月16日 17:43:23

    所有原理实现基于Redis版本6.0.9。

SDS

    SDS(Simple Dynamic String)简单动态字符串,是Redis中字符串所采取的数据结构,SDS并不是Redis的独创,只是被Redis采纳的一种数据结构,用以替换C语言原生的字符串类型:sds仓库传送门。使用方法与原生的C语言字符串类似,并能提供很多类似的API。SDS经过了两个版本,目前的解析大都基于v1。

SDS v1 结构

    v1版本的sds数据结构很简单:

    struct sdshdr{
        //现有字符串长度,即buf的长度(不包含标识结束的字符\0)
        int len;
        //当下sds未使用的字节数
        int free;
        //字节数组,即实际的字符串
        char buf[];
    }

    比起C语言中单一的字符数组构成的字符串,sds具有以下优势:

  1. 存储了字符串长度,相比C语言遍历获取长度,将时间复杂度由O(n)变为O(1);

  2. 当SDS每次发生修改时,会为其分配冗余空间,在字符串空间小于1MB时,每次分配实际长度2倍的空间,而在大于1MB时则是分配多1MB的空间,是在空间不足时才会触发分配。避免多次的重分配。

  3. 内存空间的释放是惰性的,每次SDS缩短也不会立即释放空间;

  4. 由于直接存储二进制数据,所以sds是二进制安全的,不仅可以存储标准编码的字符串,也可以存储纯二进制格式的数据,诸如图片、各种文件流等。

    

    当然,相应地,SDS会耗费更多的内存。

SDS v2 结构

    随着SDS的优化,推出了v2版本,Redis也将其的SDS替换为v2,将SDS细分为多个类型,根据实际的字符串长度尽可能地节省内存占用:

    /* Note: sdshdr5 is never used, we just access the flags byte directly.
     * However is here to document the layout of type 5 SDS strings. */
    //sdshdr5 是预留的 没有实际使用到
    struct __attribute__((__packed__)) sdshdr5
    {
        unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
        char buf[];
    };
    struct __attribute__((__packed__)) sdshdr8
    {
        //现有字符串长度,即buf的长度(不包含标识结束的字符\0)
        uint8_t len;   
        //当前分配给sds对象的大小
        uint8_t alloc; 
        //sds的数据类型,仅用到了低3位     
        unsigned char flags; 
        //字节数组,即实际的字符串
        char buf[];
    };
    struct __attribute__((__packed__)) sdshdr16
    {
        uint16_t len;        /* used */
        uint16_t alloc;      /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__((__packed__)) sdshdr32
    {
        uint32_t len;        /* used */
        uint32_t alloc;      /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__((__packed__)) sdshdr64
    {
        uint64_t len;        /* used */
        uint64_t alloc;      /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };

Redis中的SDS

初始化

    一个简单的创建SDS函数如下:

    //sds.h
    sds sdsnew(const char *init);
    
    #define SDS_TYPE_5  0    
    #define SDS_TYPE_8  1    
    #define SDS_TYPE_16 2    
    #define SDS_TYPE_32 3    
    #define SDS_TYPE_64 4    
    #define SDS_TYPE_MASK 7    
    #define SDS_TYPE_BITS 3    
    
    
    
    
    
    //sds.c
    sds sdsnew(const char *init) {
        size_t initlen = (init == NULL) ? 0 : strlen(init);
        return sdsnewlen(init, initlen);
    }
    
    //根据初始字符串长度决定sds类型
    static inline char sdsReqType(size_t string_size) {
        if (string_size < 1<<5)
            return SDS_TYPE_5;    //32
        if (string_size < 1<<8)
            return SDS_TYPE_8;    //256
        if (string_size < 1<<16)
            return SDS_TYPE_16;
    #if (LONG_MAX == LLONG_MAX)
        if (string_size < 1ll<<32)
            return SDS_TYPE_32;
        return SDS_TYPE_64;
    #else
        return SDS_TYPE_32;
    #endif
    }
    
    sds sdsnewlen(const void *init, size_t initlen) {
        void *sh;
        sds s;
        char type = sdsReqType(initlen);
        //忽略掉了sds5取得的sds类型
        /* 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;
        int hdrlen = sdsHdrSize(type);
        unsigned char *fp; /* flags pointer. */
        size_t usable;
            //分配空间 1是留给 \0结束符
        sh = 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);
        s = (char*)sh+hdrlen;
        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;
    }

指令实现:预分配API——以APPEND为例

    只是使用SET命令是不会用到sds的冗余空间的,因为每次都会重新创建sds对象,在创建之初是没有额外空间的。我们以Redis拼接字符串的指令——APPEND为例,讲述空间的扩展API。

    让我们简单的看一下命令语句APPEND的方法:

    void appendCommand(client *c) {
        size_t totlen;
        robj *o, *append;
        //是否存在该key
        o = lookupKeyWrite(c->db,c->argv[1]);
        if (o == NULL) {
            /* Create the key */
            c->argv[2] = tryObjectEncoding(c->argv[2]);
            dbAdd(c->db,c->argv[1],c->argv[2]);
            incrRefCount(c->argv[2]);
            totlen = stringObjectLen(c->argv[2]);
        } else {
            /* Key exists, check type */
            if (checkType(c,o,OBJ_STRING))
                return;
            //使用sds的API
            /* "append" is an argument, so always an sds */
            append = c->argv[2];
            //总长度
            totlen = stringObjectLen(o)+sdslen(append->ptr);    
            if (checkStringLength(c,totlen) != C_OK)
                return;
    
            /* Append the value */
            o = dbUnshareStringValue(c->db,c->argv[1],o);
            //调用了sdscatlen方法  其实是在这里进行的内存预分配
            o->ptr = sdscatlen(o->ptr,append->ptr,sdslen(append->ptr));  
            totlen = sdslen(o->ptr);
        }
        signalModifiedKey(c,c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_STRING,"append",c->argv[1],c->db->id);
        server.dirty++;
        addReplyLongLong(c,totlen);
    }

    相应的方法实现:

    /* 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) {
        size_t curlen = sdslen(s);
        //在这里分配了多余的内存,事实上sds的内存预分配也都是依赖此方法,传入字符长度
        s = sdsMakeRoomFor(s,len);
        if (s == NULL) return NULL;
        memcpy(s+curlen, t, len);
        sdssetlen(s, curlen+len);
        s[curlen+len] = '\0';
        return s;
    }

预分配API实现——sdsMakeRoomFor

    #define SDS_MAX_PREALLOC (1024*1024)
    
    /* 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) {
        void *sh, *newsh;
        size_t avail = sdsavail(s);
        size_t len, newlen;
        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;
        //sds实际字符串长度
        len = sdslen(s);
        sh = (char*)s-sdsHdrSize(oldtype);
        //新字符串长度
        newlen = (len+addlen);
        //#define SDS_MAX_PREALLOC (1024*1024)
        //如果小于1MB则多分配一倍空间 多于1MB则多分配1MB
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            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;
            //数据体大小 对于常见的SDS_TYPE_8 这一数值是44
        hdrlen = sdsHdrSize(type);
        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;
    }

验证Redis中的内存预分配

    我们可以利用Redis的MEMORY USAGE指令获取Redis一个键值的空间占用,对于SDS_TYPE_8,其正常占用为44+2(\0的占用)+key的字节数+val的字节数。

    首先set一个简单的测试键,键值为test abc,不难得出其占用内存为53bytes,不计算value占用为50bytes:

    接下来我们对键值对重新赋值为abcdefg,由于进行了重分配,没有额外占用则其内存为57bytes

    接下来重新进行赋值为abc并采用append的方式进行追加字符串,可以看到内存也进行了额外的空间分配:

    新的内存占用变为66bytes,重分配内存为(3+4+1)*2=16bytes(含\0),最终分配内存为50+16=66bytes。这样同样的键值对(test : abcdefg)因为扩展分配了额外的内存空间(\0其实是后追加的,原长去掉\0为49bytes)。其实不必纠结分配了多少,只需要注意采用append等字符串操作会使Redis占用额外的内存空间,但是频繁的字符串追加可能会相对快速一些。

总结——Redis中的SDS

    Redis中几乎所有的字符串都是SDS对象,包括key、string类型的value、列表、hash类型的value等,相比原生的字符串,其应用主要有:

  1. 存储了字符串长度,相比C语言遍历获取长度,将时间复杂度由O(n)变为O(1);

  2. 当SDS每次发生修改时,会进行内存空间预分配,在字符串空间小于1MB时,每次分配实际长度2倍的空间,而在大于1MB时则是分配多1MB的空间,是在空间不足时才会触发分配。避免多次的重分配。(其实内存预分配在Redis的API中使用不多,仅在字符串修改操作例如append会用到,直接set不会进行预分配

  3. 内存空间的释放是惰性的,每次SDS缩短也不会立即释放空间;(笔者没有找到关于使用惰性释放的case,因为Redis对字符串的操作一般都是加长,鲜有缩短

  4. 由于直接存储二进制数据,所以sds是二进制安全的,不仅可以存储标准编码的字符串,也可以存储纯二进制格式的数据,诸如图片、各种文件流等。

    SDS v2相比v1不同之处在于v2根据字符串长度为结构体分配了不同大小的内存,可能牺牲了很小的性能但是其对象结构体换来了更小的内存空间。

评论区
评论
{{comment.creator}}
{{comment.createTime}} {{comment.index}}楼
评论

Redis原理-源码解析:数据结构1 字符串操作&SDS及预分配的实现验证

Redis原理-源码解析:数据结构1 字符串操作&SDS及预分配的实现验证

    所有原理实现基于Redis版本6.0.9。

SDS

    SDS(Simple Dynamic String)简单动态字符串,是Redis中字符串所采取的数据结构,SDS并不是Redis的独创,只是被Redis采纳的一种数据结构,用以替换C语言原生的字符串类型:sds仓库传送门。使用方法与原生的C语言字符串类似,并能提供很多类似的API。SDS经过了两个版本,目前的解析大都基于v1。

SDS v1 结构

    v1版本的sds数据结构很简单:

    struct sdshdr{
        //现有字符串长度,即buf的长度(不包含标识结束的字符\0)
        int len;
        //当下sds未使用的字节数
        int free;
        //字节数组,即实际的字符串
        char buf[];
    }

    比起C语言中单一的字符数组构成的字符串,sds具有以下优势:

  1. 存储了字符串长度,相比C语言遍历获取长度,将时间复杂度由O(n)变为O(1);

  2. 当SDS每次发生修改时,会为其分配冗余空间,在字符串空间小于1MB时,每次分配实际长度2倍的空间,而在大于1MB时则是分配多1MB的空间,是在空间不足时才会触发分配。避免多次的重分配。

  3. 内存空间的释放是惰性的,每次SDS缩短也不会立即释放空间;

  4. 由于直接存储二进制数据,所以sds是二进制安全的,不仅可以存储标准编码的字符串,也可以存储纯二进制格式的数据,诸如图片、各种文件流等。

    

    当然,相应地,SDS会耗费更多的内存。

SDS v2 结构

    随着SDS的优化,推出了v2版本,Redis也将其的SDS替换为v2,将SDS细分为多个类型,根据实际的字符串长度尽可能地节省内存占用:

    /* Note: sdshdr5 is never used, we just access the flags byte directly.
     * However is here to document the layout of type 5 SDS strings. */
    //sdshdr5 是预留的 没有实际使用到
    struct __attribute__((__packed__)) sdshdr5
    {
        unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
        char buf[];
    };
    struct __attribute__((__packed__)) sdshdr8
    {
        //现有字符串长度,即buf的长度(不包含标识结束的字符\0)
        uint8_t len;   
        //当前分配给sds对象的大小
        uint8_t alloc; 
        //sds的数据类型,仅用到了低3位     
        unsigned char flags; 
        //字节数组,即实际的字符串
        char buf[];
    };
    struct __attribute__((__packed__)) sdshdr16
    {
        uint16_t len;        /* used */
        uint16_t alloc;      /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__((__packed__)) sdshdr32
    {
        uint32_t len;        /* used */
        uint32_t alloc;      /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__((__packed__)) sdshdr64
    {
        uint64_t len;        /* used */
        uint64_t alloc;      /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };

Redis中的SDS

初始化

    一个简单的创建SDS函数如下:

    //sds.h
    sds sdsnew(const char *init);
    
    #define SDS_TYPE_5  0    
    #define SDS_TYPE_8  1    
    #define SDS_TYPE_16 2    
    #define SDS_TYPE_32 3    
    #define SDS_TYPE_64 4    
    #define SDS_TYPE_MASK 7    
    #define SDS_TYPE_BITS 3    
    
    
    
    
    
    //sds.c
    sds sdsnew(const char *init) {
        size_t initlen = (init == NULL) ? 0 : strlen(init);
        return sdsnewlen(init, initlen);
    }
    
    //根据初始字符串长度决定sds类型
    static inline char sdsReqType(size_t string_size) {
        if (string_size < 1<<5)
            return SDS_TYPE_5;    //32
        if (string_size < 1<<8)
            return SDS_TYPE_8;    //256
        if (string_size < 1<<16)
            return SDS_TYPE_16;
    #if (LONG_MAX == LLONG_MAX)
        if (string_size < 1ll<<32)
            return SDS_TYPE_32;
        return SDS_TYPE_64;
    #else
        return SDS_TYPE_32;
    #endif
    }
    
    sds sdsnewlen(const void *init, size_t initlen) {
        void *sh;
        sds s;
        char type = sdsReqType(initlen);
        //忽略掉了sds5取得的sds类型
        /* 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;
        int hdrlen = sdsHdrSize(type);
        unsigned char *fp; /* flags pointer. */
        size_t usable;
            //分配空间 1是留给 \0结束符
        sh = 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);
        s = (char*)sh+hdrlen;
        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;
    }

指令实现:预分配API——以APPEND为例

    只是使用SET命令是不会用到sds的冗余空间的,因为每次都会重新创建sds对象,在创建之初是没有额外空间的。我们以Redis拼接字符串的指令——APPEND为例,讲述空间的扩展API。

    让我们简单的看一下命令语句APPEND的方法:

    void appendCommand(client *c) {
        size_t totlen;
        robj *o, *append;
        //是否存在该key
        o = lookupKeyWrite(c->db,c->argv[1]);
        if (o == NULL) {
            /* Create the key */
            c->argv[2] = tryObjectEncoding(c->argv[2]);
            dbAdd(c->db,c->argv[1],c->argv[2]);
            incrRefCount(c->argv[2]);
            totlen = stringObjectLen(c->argv[2]);
        } else {
            /* Key exists, check type */
            if (checkType(c,o,OBJ_STRING))
                return;
            //使用sds的API
            /* "append" is an argument, so always an sds */
            append = c->argv[2];
            //总长度
            totlen = stringObjectLen(o)+sdslen(append->ptr);    
            if (checkStringLength(c,totlen) != C_OK)
                return;
    
            /* Append the value */
            o = dbUnshareStringValue(c->db,c->argv[1],o);
            //调用了sdscatlen方法  其实是在这里进行的内存预分配
            o->ptr = sdscatlen(o->ptr,append->ptr,sdslen(append->ptr));  
            totlen = sdslen(o->ptr);
        }
        signalModifiedKey(c,c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_STRING,"append",c->argv[1],c->db->id);
        server.dirty++;
        addReplyLongLong(c,totlen);
    }

    相应的方法实现:

    /* 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) {
        size_t curlen = sdslen(s);
        //在这里分配了多余的内存,事实上sds的内存预分配也都是依赖此方法,传入字符长度
        s = sdsMakeRoomFor(s,len);
        if (s == NULL) return NULL;
        memcpy(s+curlen, t, len);
        sdssetlen(s, curlen+len);
        s[curlen+len] = '\0';
        return s;
    }

预分配API实现——sdsMakeRoomFor

    #define SDS_MAX_PREALLOC (1024*1024)
    
    /* 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) {
        void *sh, *newsh;
        size_t avail = sdsavail(s);
        size_t len, newlen;
        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;
        //sds实际字符串长度
        len = sdslen(s);
        sh = (char*)s-sdsHdrSize(oldtype);
        //新字符串长度
        newlen = (len+addlen);
        //#define SDS_MAX_PREALLOC (1024*1024)
        //如果小于1MB则多分配一倍空间 多于1MB则多分配1MB
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;
        else
            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;
            //数据体大小 对于常见的SDS_TYPE_8 这一数值是44
        hdrlen = sdsHdrSize(type);
        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;
    }

验证Redis中的内存预分配

    我们可以利用Redis的MEMORY USAGE指令获取Redis一个键值的空间占用,对于SDS_TYPE_8,其正常占用为44+2(\0的占用)+key的字节数+val的字节数。

    首先set一个简单的测试键,键值为test abc,不难得出其占用内存为53bytes,不计算value占用为50bytes:

    接下来我们对键值对重新赋值为abcdefg,由于进行了重分配,没有额外占用则其内存为57bytes

    接下来重新进行赋值为abc并采用append的方式进行追加字符串,可以看到内存也进行了额外的空间分配:

    新的内存占用变为66bytes,重分配内存为(3+4+1)*2=16bytes(含\0),最终分配内存为50+16=66bytes。这样同样的键值对(test : abcdefg)因为扩展分配了额外的内存空间(\0其实是后追加的,原长去掉\0为49bytes)。其实不必纠结分配了多少,只需要注意采用append等字符串操作会使Redis占用额外的内存空间,但是频繁的字符串追加可能会相对快速一些。

总结——Redis中的SDS

    Redis中几乎所有的字符串都是SDS对象,包括key、string类型的value、列表、hash类型的value等,相比原生的字符串,其应用主要有:

  1. 存储了字符串长度,相比C语言遍历获取长度,将时间复杂度由O(n)变为O(1);

  2. 当SDS每次发生修改时,会进行内存空间预分配,在字符串空间小于1MB时,每次分配实际长度2倍的空间,而在大于1MB时则是分配多1MB的空间,是在空间不足时才会触发分配。避免多次的重分配。(其实内存预分配在Redis的API中使用不多,仅在字符串修改操作例如append会用到,直接set不会进行预分配

  3. 内存空间的释放是惰性的,每次SDS缩短也不会立即释放空间;(笔者没有找到关于使用惰性释放的case,因为Redis对字符串的操作一般都是加长,鲜有缩短

  4. 由于直接存储二进制数据,所以sds是二进制安全的,不仅可以存储标准编码的字符串,也可以存储纯二进制格式的数据,诸如图片、各种文件流等。

    SDS v2相比v1不同之处在于v2根据字符串长度为结构体分配了不同大小的内存,可能牺牲了很小的性能但是其对象结构体换来了更小的内存空间。


Redis原理-源码解析:数据结构1 字符串操作&SDS及预分配的实现验证2020-11-16鱼鱼

{{commentTitle}}

评论   ctrl+Enter 发送评论