redis中的数据结构—SDS简单动态字符串

Posted by CHuiL on March 19, 2019

SDS底层实现

 struct __attribute__ ((__packed__)) sdshdr5 { //从未使用过
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    /* 第三位表示类型,高5位表示长度*/
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* 除去头部(即sds结构体)和空字符串,表示已申请的空间 */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    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[];
};

根据字符串大小申请对应的type,区别在于len 和 alloc的指针;对内存进行优化; 申请内存时会先根据字符串申请对应长度的type,申请的空间如下图(黄色部分即为首部)
image

空间预分配:(因为使用c字符需要经常进行内存重分配,效率低)

扩展的时候根据扩展后的新长度进行判断是否扩容,扩容操作就是新开辟一片内存空间,将值复制进去,只是新开辟的大小有这样的规定:如果新的长度大小小于1Mb,那么申请的空间为新的长度的两倍,大于1MB则为新长度的基础上+1MB;

惰性空间释放:

释放内存时不会将已分配的内存立即Free,只是清掉了删除的字符,长度值减少而已;

二进制安全:

buf又可以称为字节数组,因为redis不用这个数组来保存字符,而是二进制数据;所以写入是什么数据,读出来的就是什么数据