Redis源码阅读:Redis里的动态字符串SDS

Redis源码阅读:Redis里的动态字符串SDS

version : 5.0rc3

SDS作用

C语言中的字符串以'\0'做结尾,不记录自身使用参数,同时不具有动态扩展的特性,在释放内存、频繁扩展字符串的场景中不适用,SDS(simple dynamic string)作为redis中最基本的数据结构,用最简单的方式实现了动态字符串的功能,并记录了自身的大小,便于扩展与释放操作;同时为不同大小的字符串设置了不同的字符串数据类型,尽可能的减少内存的分配。本文主要分析的是sds.h/c两个文件。

基本数据结构定义

新的字符串的结构最好拥有几个基本的功能:
- 常数时间内获取当前字符串的长度
- 能够动态的扩展字符串
- 二进制安全,可以存放'\0'
- 尽可能的节约内存空间

打开sds,h,除了一些预定义和函数,可以看到几个struct的定义

/* 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五种数据结构,除了sdshdr5,其他都含有四个数据成员,他们的作用也很显而易见:
- len : 当前使用的字符串长度
- alloc : 当前数据结构被分配的总长度
- flags : 一个字节,使用其中的第三位用于标识当前数据类型的型别
- buf[] : buf存放以'\0'结尾的传统c字符串
根据注释,可以知道,sdshdr5基本不被使用,只是用来访问flags;接下来可以看到和flags相关的宏定义

#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

不同的数据结构内部数据成员的大小也不一样,故几种不同的sdshdr主要用于不同大小的字符串选择使用不同的类型进行存储;短字符串用小的数据结构,尽可能的减少空闲空间的分配;
留意到,在定义struct的时候,有关键字

__attribute__  ((__packed__))

这两个关键字的作用是在gcc编译器编译程序的过程中,以紧凑模式来分配内存,避免内存对齐;
基本的数据结构定义基本就是如上所示,还有几个相关的宏定义:

#define SDS_MAX_PREALLOC (1024*1024)

#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))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

SDS_MAX_PREALLOC大小为1Mb,在扩展字符串的过程中,如果字符串的大小小于这一值,则扩展一倍的空间,也就是扩展后已使用空间等于空闲空间,如果已经大于这一值,则线性扩展,在原有基础上,增加多出的空间。
'##'在C语言的宏定义中表示衔接两段宏,sdshdr##8,预处理之后即为‘sdshdr8’,我们可以把这几种数据结构看作是一个header模块和一个buf的结合,那么SDS_HDR_VAR(T,s)与SDS_HDR(T,s)两个宏可以根据buf的地址得到header的地址,这也得益于C语言直接面向内存的优势,操作内存地址非常灵活。

内存申请与释放

/* Export the allocator used by SDS to the program using SDS.
 * Sometimes the program SDS is linked to, may use a different set of
 * allocators, but may want to allocate or free things that SDS will
 * respectively free or allocate. */
void *sds_malloc(size_t size);
void *sds_realloc(void *ptr, size_t size);
void sds_free(void *ptr);

sds_malloc、sds_realloc、sds_free定义如下

void *sds_malloc(size_t size) { return s_malloc(size); }
void *sds_realloc(void *ptr, size_t size) { return s_realloc(ptr,size); }
void sds_free(void *ptr) { s_free(ptr); }

这几个函数通过"sdsalloc.h"中的宏定义指向文件"zmalloc.h"中的具体实现:

#include "zmalloc.h"
#define s_malloc zmalloc
#define s_realloc zrealloc
#define s_free zfree

这里需要注意,realloc是在原有的位置上,向后申请空间,而malloc是直接申请一片空白内存。

基本操作函数

sds实现了一套与原生字符串操作函数相近的操作函数,所进行的操作看函数定义的名称基本就可以了解,这里就不分析具体实现了,每一个的实现都不是很复杂

sds sdsnewlen(const void *init, size_t initlen);
sds sdsnew(const char *init);
sds sdsempty(void);
sds sdsdup(const sds s);
void sdsfree(sds s);
sds sdsgrowzero(sds s, size_t 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);

sds sdscatfmt(sds s, char const *fmt, ...);
sds sdstrim(sds s, const char *cset);
void sdsrange(sds s, ssize_t start, ssize_t end);
void sdsupdatelen(sds s);
void sdsclear(sds s);
int sdscmp(const sds s1, const sds s2);
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s);
void sdstoupper(sds s);
sds sdsfromlonglong(long long value);
sds sdscatrepr(sds s, const char *p, size_t len);
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep);
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);

总结

Redis自己实现了一个二进制安全、具有动态扩展、常数时间获取字符串参数的字符类型,通过多类型SDS的分配,尽可能节约内存,合理分配空间,同时也对字符的增长方式进行了限定,避免单一字符串增长过快而消耗不必要的内存。SDS还与C语言的原生字符串实现了兼容,本质上可以看作是heder+buf的组合,一定条件下相同类型的SDS可以直接用原生字符串的比较函数进行比较。
但是Redis中的string并不等同于sds,如果存放的值是数字的时候,需要支持incr、decr等操作,这部分由其他类型的数据结构来完成。

Comments are closed.