Redis 数据结构 ( SDS) 实现

Redis没有直接使用 C 语言的字符串,而是自己创建了名为 SDS (simple dynamic string, SDS) 的字符串。
c 语言已经有字符串,为什么redis要重复造轮子

1、字符串的长度的处理,c 语言获取字符串需要遍历所有的字符长度 O(n), 而 redis的 sds 可以直接通过 len 来获取 O(1)。
2、内存重新分配,C 语言中涉及到修改字符串的时候会重新分配内存,修改地越频繁,内存分配也就越频繁,而 sds 使用 alloc 预分配,避免了频繁分配内存的问题。

一、二进制安全?

    C 语言中,用 “\0” 表示字符串的结束,如果字符串本身就有 “\0” 字符,字符串就会报截断,既非二进制安全,若通过某种机制,保证写字符串时不会受损坏的内容,则是二进制安全。

二、sds 5种 数据结构及类型,代码在 sds.h 和 sds.c中实现。

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    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[];
};
#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

三、加入 attribute ((__packed__)) 和默认对齐的区别 ?

默认对齐

struct  sdshdr16 {
    uint16_t len; 
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};

image.png

attribute ((__packed__))对齐

struct  __attribute__ ((__packed__) ) sdshdr16 {
    uint16_t len; 
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};

image.png

两个好处:
1、可以节省内存(比如 sds16 可以节省 1 个字节)
2、sds返回给上层的,不是结构体首地址,而是指向内容的buf指针,因此此时按1字节对齐,故 sds 创建后,无论是 sdshdr8、sdshr16 还是 sdshdr32,都能通过 (char*)sh+hrlen得到buf的指针。

四、柔性数组

  柔性数组只能被放在结构体的末尾,通过 malloc 动态分配内存。

这样做的好处是结构体和柔性数组的地址是连续的,提升了一个局部性的访问。

五、flags 作用

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 低三位存储类型 , 高5位存储 长度 */
    char buf[];
};

image.png

sds5、sds8、sds16、sds32、sds64 一共5种数据结构,而 2的2此方  为4,不能满足 存储 5种类型,所以需要 3 位(2的3次方 = 8)来存储。

其余的 5 个 bit 用来存储 长度 2的5次方-1 =  31,用来存储长度的、其他的数据结构flags高5位则忽略,因为已经有 len来表示。

可看到redis已经把字符串优化到极致。

六、通过宏 SDS_HDR_VAR 和 SDS_HDR 快速获取 sds 头部。

#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

七、gdb 断点创建字符串。

代码

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    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;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    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 = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

首先查看 sds5,也就是长度小于32位的。
1、在 sdsnewlen 打个断点。

image
2、在redis客户端 执行 set sds 1

image.png

3、在 gdb 执行 c 和 n 、p。

image.png

1、init 可以看到正好是set 执行的字符串, sds。
2、initlen 可以看到传入的长度是 3 。
3、type = 0,也就是sds5。

image.png

1、s 是指向buf的指针。
2、fp 则是 flags,可以通过 s[-1]很方便的得到。
3、\0 为了=二进制安全。

八、根据不同的长度创建sds类型。

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5) //32
        return SDS_TYPE_5;
    if (string_size < 1<<8) //256
        return SDS_TYPE_8;
    if (string_size < 1<<16) //65536
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32) //4294967296
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

sds 各种数据结构占用内存的大小:
image

总结:

1、可以看到当 key 的长度 < 32,会使用sds5,在实际的业务中,小于 32 的很常见,所以我们的key的长度接近32,那么就尽量小于32,这样可以节省内存空间。

2、学到了 attribute ((__packed__)) 和 默认对齐的区别。
3、当 sds为5的时候并且值为空的时候会强制转化为sds8。

4、sds是如何保证了二进制的安全。

其他接口可自行gdb 查看。

评论

暂无评论