redis字符串剖析

发表于 更新于 阅读次数：

说明

本篇文章介绍redis使用的字符串结构。redis很巧妙的在操作的指针前面增加header，并且会在尾部增加’\0’，兼容二进制的同时，也可以直接将指针传递给C库操作字符串的函数直接操作

实现

sds定义

简单的重定义了char*，即能兼容C库操作字符串的函数，也能跟原来的字符串有一定区分

1
typedef char *sds;

sds header

为了节约内存，sds根据实际存储的字符串长度，使用多个header进行描述

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
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; // 低三位存放type，高5位存放长度
    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[];
};

// sds类型，分别代表使用什么类型的header描述
#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
  • sdshdr*后面的数字即为该header能存放的字符串长度二进制位数，例如sdshdr8表示该结构体能容纳2^8-1长度的字符串
  • 所有header结构体，存放buf的前面一位肯定是flags，该变量存放当前header属于什么类型，使用了 __attribute__ ((__packed__))属性告诉编译器不要对齐，这样就可以使用s[-1]来简单的拿到flags，再根据flasgs，来获取header指针进行操作
  • 除了sdshdr5以外，其他header结构相似，len表示实际字符串长度，alloc表示实际分配的长度
  • sdshdr5只有一个存放len的变量，所以该结构不能预先分配内存
  • redis提供助手宏或者函数，可以更方便的操作sds
    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
    // 获取header指针
    #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)))) 
    // 用于计算SDS_TYPE_5的实际长度
    #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

    // 根据类型获取字符串长度
    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;
    }

    // 返回字符串剩余未使用的空间
    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;
    }

其他函数

知道了redis字符串结构之后，它提供的一系列操作它的函数就很容易看懂。包括一些初始化，复制，清空，free，增长，格式化等等。这里给出每个函数的声明及作用，具体细节可以查看我注释的redis源码

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 sdsnewlen(const void *init, size_t initlen);    // 根据传入的init指针，和initlen创建一个合适的sds，为了兼容c字符串函数，sds总是会以'\0'结尾
sds sdsnew(const char *init);                       // 直接根据传入的init字符串指针，创建合适的sds
sds sdsempty(void);                                 // 创建一个空的sds
sds sdsdup(const sds s);                            // 复制一个sds
void sdsfree(sds s);                                // 释放sds内存
sds sdsgrowzero(sds s, size_t len);                 // 增长s到能容纳len长度，增长的空间初始化为0，并且更新s长度为len，如果s实际已经比len长，则不进行任何操作
sds sdscatlen(sds s, const void *t, size_t len);    // 拼接函数
sds sdscat(sds s, const char *t);
sds sdscatsds(sds s, const sds t);
sds sdscpylen(sds s, const char *t, size_t len);    // 拷贝函数
sds sdscpy(sds s, const char *t);

// 格式化fmt，并拼接到s中
sds sdscatvprintf(sds s, const char *fmt, va_list ap);
#ifdef __GNUC__
sds sdscatprintf(sds s, const char *fmt, ...)
    __attribute__((format(printf, 2, 3)));
#else
sds sdscatprintf(sds s, const char *fmt, ...);
#endif

sds sdscatfmt(sds s, char const *fmt, ...);         // redis自定义的简化版格式化fmt并拼接到s，速度会比*printf快很多
sds sdstrim(sds s, const char *cset);               // 去除头尾指定的字符集合
void sdsrange(sds s, int start, int end);           // 用s的start到end重新赋值s，start和end可以为负值
void sdsupdatelen(sds s);                           // 使用strlen(s)更新s长度
void sdsclear(sds s);                               // 清空s，只设置了下长度为0，不会释放内存
int sdscmp(const sds s1, const sds s2);             // 比较两个sds
sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count);      // 分割字符串到返回的sds数组中，数组长度在count中返回。二进制安全
void sdsfreesplitres(sds *tokens, int count);       // 释放sdssplitlen和sdssplitargs返回的sds*数组
void sdstolower(sds s);                             // 转为小写
void sdstoupper(sds s);                             // 转为大写
sds sdsfromlonglong(long long value);               // 从long long类型初始化sds
sds sdscatrepr(sds s, const char *p, size_t len);   // 将p对应的字符串转义后用'"'包裹后，连接到s中
sds *sdssplitargs(const char *line, int *argc);     // 分割命令行到返回的sds数组中，数组长度在argc参数返回
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);    // 替换sds中的字符，如果s[i] = from[j] 则将s[i]替换为to[j]
sds sdsjoin(char **argv, int argc, char *sep);      // 拼接C风格字符串数组到新的sds中
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);    // 拼接sds数组到新的sds中

/* Low level functions exposed to the user API */
sds sdsMakeRoomFor(sds s, size_t addlen);           // 扩容s，使能再容纳addlen长度，只会修改alloc参数，不会改变len
void sdsIncrLen(sds s, int incr);                   // 增加s长度，需要跟sdsMakeRoomFor配合使用
sds sdsRemoveFreeSpace(sds s);                      // 移除s所有分配的预留空间
size_t sdsAllocSize(sds s);                         // s实际占用的内存大小
void *sdsAllocPtr(sds s);                           // 返回s header指针