Redis数据库------字符串与SDS

发表于 | 分类于

简介

字符串类型是其余四种数据类型的基础，也是Redis数据库的最基本数据类型，对字符串进行不同形式的组织可以产生不同的数据类型，一个字符串类型的值能存储的最大容量为512M。

SDS

描述

redis是用c语言写的，但是它并没有直接使用c中的字符串来进行字符串的实现，而是建立了一个简单动态字符串SDS来实现字符串的实现。c中的String实际上是以字符数组为核心，以‘\0’来区分每个字符串，SDS改进了许多，使用sdshdr来实现。

  1. 使用len表示字符串长度，避免了在长度获取时的循环来提高性能。
  2. 之前使用的是free来标记已申请的字符数组的空余空间，新版本使用alloc表示目前申请的字符数组的总空间。并且采用动态的空间申请与惰性释放的方式来管理数据空间，避免了许多的内存操作来提升性能。
  3. 同时保持了字符数组的相关使用，使用buf来实际存储数据，可以调用c中的相关的字符串处理函数，减轻了开发与使用的学习成本。
  4. 保证了二进制的存储安全，由于之前的字符串数组是完全使用’\0’来区分字符串，并且才有一定的编码形式比如ascii，导致无法对图片文件等二进制文件进行存储，而使用alloc与len来区分字符串，进行边界检测，使得二进制存储的安全性得到保证。

    sdshdr

    笔者获得的最新稳定版中的定义是这样的：（sds.h）
    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
    26
    27
    28
    29
    30
    /* Note: sdshdr5 is never used, we just access the flags byte directly.
     * However is here to document the layout of type 5 SDS strings. */
    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[];
    };

实现的种类有五种，sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64。这里有一个标志flags，使用了unsigned char类型（保证八个数据位都可以使用），三位表示结构体的类型（5<8），剩下得五位只在sdshdr5中被使用用于表示字符串长度。于是我们得到了它们的长度范围，sdshdr5长为2的5次方，sdshdr8为2的8次方以此类推，buf用于存储实际的字符串数据。
顺带一提使用attribute ((packed))关键字可以使相应的结构体在内存中紧凑排列，而不需要字节对齐。uint8_t等理解如下。

1
2
3
4
5
typedef unsigned char           uint8_t;  
typedef unsigned short int      uint16_t;  
typedef unsigned int            uint32_t;  
typedef unsigned long int       uint64_t;  //字长为64位
typedef unsigned long long int  uint64_t;  //字长为32位

SDS中的sds

sds.h中有这样一个变量。

1
typedef char *sds;

只是一个字符指针的重命名,为啥这么用，我们从其创建的过程来看,创建的函数是sdsnewlen。传入的函数是一个字符指针包含需要初始化的字符数据和创建的字符串的长度。

sdsnewlen

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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;
}

我们一点一点来看，首先我们需要根据传入的长度选取合适的sdshdr，通过sdsReqType函数来实现。

sdsReqType

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    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
}

很简单的实现，根据传入的size_t的大小选取合适的sdshdr，这里的size_t是c中的一个数据类型，可以理解为size of int，就是一个整数， 使用左位移来表示数据大小。这里的LONG_MAX 与LLONG_MAX对应是long int与long long int所占的内存空间，根据此来判断一个字的大小是32位还是64位，1ll是long long int的表示。#if ，#else是为了预编译方便处理。

1
typedef unsigned int size_t;

之后，由于设计的考虑如果字符串为空（长度为0），则将sdshdr5的使用换成了sdshdr8。之后通过sdsHdrSize函数获得sdshdr的内存占用长度。

sdsHdrSize

sds.h中定义了

1
2
3
4
5
6
#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

sds.c中的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static inline int sdsHdrSize(char type) {
    switch(type&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return sizeof(struct sdshdr5);
        case SDS_TYPE_8:
            return sizeof(struct sdshdr8);
        case SDS_TYPE_16:
            return sizeof(struct sdshdr16);
        case SDS_TYPE_32:
            return sizeof(struct sdshdr32);
        case SDS_TYPE_64:
            return sizeof(struct sdshdr64);
    }
    return 0;
}

也是很简单的代码，sizeof是获取对应数据结构所占内存大小，这玩意不是函数！！！！返回的是size_t也就是个整型。之后调用s_malloc函数完成了内存的分配工作，内存的计算是sdshdr的长度（hdrlen），加上字符内容的长度（initlen），加一（字符串结尾的’\0’，保持和c的一致）。这里的s_malloc实际上是调用的zmalloc函数，在zmalloc.c中实现。

zmalloc

1
2
3
4
5
6
7
8
9
10
11
12
void *zmalloc(size_t size) {
    void *ptr = malloc(size+PREFIX_SIZE);
    if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_alloc(zmalloc_size(ptr));
    return ptr;
#else
    *((size_t*)ptr) = size;
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)ptr+PREFIX_SIZE;
#endif
}

所以实际上获取的大小是size+PREFIX_SIZE，这个PREFIX_SIZE是这么定义的：

1
#define PREFIX_SIZE (sizeof(size_t))

我们多要了一个size_t大小的空间，玄机在((size_t)ptr) = size;一句，多的这个size_t用于存储我们传入的size的值。这样内存的分配就结束了。
之后我们根据传入的init指针来对其进行初始化，其中如果值为SDS_NOINIT则将init置为NULL。

1
const char *SDS_NOINIT = "SDS_NOINIT";

紧接着对划分的内存进行初始化，使用memset函数对其进行初始化赋初值为0，并判断是否分配成功，若分配失败则直接返回NULL。
接下来我们就可以看到sds具体的指向了

1
s = (char*)sh+hdrlen;

指向的是sdshdr之后实际的字符内容的地方，也就是说实际在存储时还是使用字符数组来进行存储，只不过对这个数组进行了加工，加上了sdshdr，并使用一个专门的指针指向字符内容（sds）。并且对应设置了fp指向sdshdr中的flags，根据设置的sdshdr类型来对flags设置，默认将type的类型赋给flags，对于特殊的sdshdr5将type放在flags低三位，高五位放置字符串的长度，剩下的alloc与len则是将传入的初始化长度赋给它们。

SDS_HDR_VAR

这里还有一个宏SDS_HDR_VAR在sds.h中定义的。

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

是通过sds的地址位置获取sdshdr的地址存到sh中，其中的##起到了连接的作用。
最后是根据传入的数据对其进行数据设置，使用memcpy将传入的init（字符串指针）内容赋到上面的sds s中，长度就是传入的initlen。（memcpy是将源地址（第二个参数）出的给定长度（第三个参数）的内存赋给目的地址（第一个参数））。
结尾将这个内存中最后一个地址设置为’\0’，返回sds，创建完成。

空间扩展

redis中对字符串的空间扩展是通过sdsMakeRoomFor实现的。

sdsMakeRoomFor

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    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;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        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(hdrlen+newlen+1);
        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);
    }
    sdssetalloc(s, newlen);
    return s;
}

首先是用avail存储已扩展的空间中有多少可用空间，使用sdsavail来实现。

sdsavail

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
static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

s[-1]中的-1是指上一个内存单元，s[-1]是获取s上一个内存单元中的内容即flags。根据给的类型来确定可用的大小，很简单的将总的大小（alloc）减去已使用的大小（len）剩下的是可用的大小。特别的sdshdr5直接返回0。
oldtype获取的是之前的type类型。判断剩余可用的是否足够，如果足够就返回原来的sds。如果不够就进行扩展处理，首先获取已经使用的长度len。

sdslen

sds.h中的函数，很简单的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

对于非sdshdr5类型的直接用SDS_HDR宏来获取指针进而由指针来指向结构体中的len，对于sdshdr5就使用SDS_TYPE_5_LEN宏来实现。

1
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

之后直接获取sdshdr结构体指针sh,计算新的字符串需要的大小。

1
2
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);

内存分配策略

重点来了！！！！！！

1
2
3
4
if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;

新计算需要的内存空间是newlen，如果这个值在最大阈值之内就将其空间扩大一倍，如果超过了阈值就将其内存再扩大一个阈值的大小，这个阈值定义为1M（2的20次方）

1
#define SDS_MAX_PREALLOC (1024*1024)

之后对新设定的内存大小进行相关设置，确定对应的sdshdr类型（还是没有使用sdshdr5，而是sdshdr8代替），根据新产生的类型分配内存，当与原来的类型一样时：

1
2
3
4
5
if (oldtype==type) {
	newsh = s_realloc(sh, hdrlen+newlen+1);//重新划分内存大小
    if (newsh == NULL) return NULL;//划分失败直接返回NULL
   	s = (char*)newsh+hdrlen;//设置sds s的位置。
}

zrealloc

s_realloc实际上是在zmalloc中实现的zrealloc函数。

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
26
27
28
void *zrealloc(void *ptr, size_t size) {
#ifndef HAVE_MALLOC_SIZE
    void *realptr;
#endif
    size_t oldsize;
    void *newptr;

    if (ptr == NULL) return zmalloc(size);
#ifdef HAVE_MALLOC_SIZE
    oldsize = zmalloc_size(ptr);
    newptr = realloc(ptr,size);
    if (!newptr) zmalloc_oom_handler(size);

    update_zmalloc_stat_free(oldsize);
    update_zmalloc_stat_alloc(zmalloc_size(newptr));
    return newptr;
#else
    realptr = (char*)ptr-PREFIX_SIZE;
    oldsize = *((size_t*)realptr);
    newptr = realloc(realptr,size+PREFIX_SIZE);
    if (!newptr) zmalloc_oom_handler(size);

    *((size_t*)newptr) = size;
    update_zmalloc_stat_free(oldsize+PREFIX_SIZE);
    update_zmalloc_stat_alloc(size+PREFIX_SIZE);
    return (char*)newptr+PREFIX_SIZE;
#endif
}

主要的作用是重新分配原有的内存，使其调节至相应的大小。
与原来类型不同时：

1
2
3
4
5
6
7
8
9
10
11
12
else {
    /* Since the header size changes, need to move the string forward,
     * and can't use realloc */
    /*由于sdshdr的变化导致字符串的移动，所以无法使用realloc函数*/
    newsh = s_malloc(hdrlen+newlen+1);//重新划分的内存
    if (newsh == NULL) return NULL;//划分失败直接返回NULL
    memcpy((char*)newsh+hdrlen, s, len+1);//将原有的字符串复制到新划分的内存位置上，len+1是包括字符结尾的'\0'.
    s_free(sh);//释放原有的内存
    s = (char*)newsh+hdrlen;//重新设置sds的位置
    s[-1] = type;//重新设置flags
	sdssetlen(s, len);
}

zfree

s_free实际上是使用在zmalloc中实现的zfree函数，对内存进行的释放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void zfree(void *ptr) {
#ifndef HAVE_MALLOC_SIZE
    void *realptr;
    size_t oldsize;
#endif

    if (ptr == NULL) return;
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_free(zmalloc_size(ptr));
    free(ptr);
#else
    realptr = (char*)ptr-PREFIX_SIZE;
    oldsize = *((size_t*)realptr);
    update_zmalloc_stat_free(oldsize+PREFIX_SIZE);
    free(realptr);
#endif
}

sdssetlen

目的是设置sdshdr中的len参数，实现也很简单，相关函数详见上文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
}

sdssetalloc

设置sdshdr中的alloc参数，更新设置后的内存总量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

内存扩展完成返回最终的sds。

空间释放

redis中对字符串的空间释放是通过sdsRemoveFreeSpace实现的，这里只是描述释放的过程，并没有描述释放的策略。

sdsRemoveFreeSpace

相关函数参见上文。

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
26
27
28
29
30
31
32
sds sdsRemoveFreeSpace(sds s) {
    void *sh, *newsh;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;//获取sdshdr的类型
    int hdrlen, oldhdrlen = sdsHdrSize(oldtype);//获取sdshdr的大小
    size_t len = sdslen(s);//获取sdshdr中记录的已使用的大小
    sh = (char*)s-oldhdrlen;//获取sdshdr指针

    /* Check what would be the minimum SDS header that is just good enough to
     * fit this string. */
    type = sdsReqType(len);//检测对应字符串大小的sdshdr是否符合。
    hdrlen = sdsHdrSize(type);//根据检测后的结果获取sdshdr的大小

    /* If the type is the same, or at least a large enough type is still
     * required, we just realloc(), letting the allocator to do the copy
     * only if really needed. Otherwise if the change is huge, we manually
     * reallocate the string to use the different header type. */
    if (oldtype==type || type > SDS_TYPE_8) {//如果类型没有改变，或者还有大空间的需求
        newsh = s_realloc(sh, oldhdrlen+len+1);//调节内存
        if (newsh == NULL) return NULL;//失败就返回NULL
        s = (char*)newsh+oldhdrlen;//重新设置sds的位置
    } else {//类型发生改变或者使用SDS_TYPE_8小空间的
        newsh = s_malloc(hdrlen+len+1);//重新分配内存
        if (newsh == NULL) return NULL;//失败就返回NULL
        memcpy((char*)newsh+hdrlen, s, len+1);//将原有的值复制过去包含'\0'
        s_free(sh);//释放原有空间
        s = (char*)newsh+hdrlen;//设置sds
        s[-1] = type;//设置flags
        sdssetlen(s, len);//重新设置sdshdr中的len
    }
    sdssetalloc(s, len);//重新设置sdshdr中的alloc
    return s;
}

可见内存的释放与扩展在函数操作上是很相似的。

小结

作为redis中最为重要的数据类型，字符串的sds结构实现过程大致就是如此了，感觉设计的很巧妙，在源码中还有许多的api函数，可以实现许多的需求，了解基本的sds数据结构将有利于我们的理解与运用。