redis数据结构(二) 字符串对象

对于Redis中的字符串等其他数据结构与对象探讨,实际都是分为两个方面。第一是上一篇文章所提到的redisObjectptr指针指向的底层数据结构的探讨,第二是不同编码方式导致使用不同数据结构的探讨。

简单动态字符串

Redis是用c语言实现的,那么Redis中的键和值如果是字符串对象的话,是不是也是直接用的c语言中的字符串呢?即形如"abc\0"这种带有终止字符的c字符串呢?

答案是no,Redis对c字符串进行了一层简单的封装,新的字符串结构叫做简单动态字符串(Simple Dynamic String,SDS)

在Redis中,C字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方,比如打印日志。

源码分析

在最新Redis源码中SDS定义如下(以下代码都在sds.h和sds.c中可以找到):

/* 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[];
};

相比较设计与实现一书中的代码,已经大大不同。新版代码将sdshdr结构分成了5种,第一种已经never used,我们跳过。剩下四种除结构中成员变量的类型不同外都是一致的。

alloc表示分配的总长度,len表示已经使用的长度,alloc - len则代表以前的free属性,即未使用的长度。flags代表当前的sdshdr是四种中的哪种类型,buf[]代表实际数据存储位置。

新版代码中提高了SDS对内存的利用率,如果SDS的长度可以用1字节(8bit)来表示,那么就用uint8,没必要统统都用到uint32。同时,SDS却对上层使用保持一致的借口,隐藏底层结构体差异性的细节。如下:

typedef char *sds; // 将char定义成*sds,指向sdshdrxx中的buf数组

我们看看具体是如何做到统一的,就拿sdsavail这个求sds中还有多少剩余空间的函数为例:

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]取得flags的值,为什么可以这么取呢?因为sds类型的s对象,对应的正是sdshdr中的buf数组,而结构体中的内存排布是连续的,buf[0]代表第一个char元素,buf[1]自然就代表排列的前面的也是char类型的flags变量了。

接着,通过flags&SDS_TYPE_MASK既根据不同的flags来走不同的sdshdr分支了。

#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

可以通过与操作来做是因为,flags的取值范围如上,是0~4,只需要3bit就可以表示,因此掩码mask为7。

在上述函数中还有最后一步,一个关键的宏SDS_HDR_VAR,用来创建指定类型的sdshdr。定义如下:

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

在下对c语言并不是很了解,但是观察这行代码大概可以知道,这个函数通过传入T和s的值,其中##T就代表创建多少bit的sh指针,该指针指示的地址是s减去对应结构的大小,即结构体最开始的地址处。

总而言之,Redis就是通过上述操作,实现sds指针的屏蔽底层结构细节,达到内存优化的目的的。

SDS的优点及内存分配

  • 降低获取字符串长度的时间复杂度。普通c字符串获取长度需要遍历,复杂度为O(n),sds直接维护一个len变量,复杂度为O(1)。也算经典空间换时间了。
  • 杜绝缓冲区溢出。字符串拼接时,普通字符串如果没分配足够空间,会导致缓冲区溢出。而sds存在内存分配策略不会溢出。最新版代码中,如果拼接后总长度小于1024*1024,即1MB,则空间alloc乘以2,否则长度加上1024*1024。这与设计与实现中的len,free两者的关系其实是一致的。内存分配具体见sdsMakeRoomFor函数。代码关键处如下:
    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC) // SDS_MAX_PREALLOC = 1024*1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
  • 减少修改字符串时带来的内存重分配次数。c字符串每次修改都要内存重分配,而有内存分配策略的sds并不是。
  • 二进制安全。
  • 兼容部分c字符串函数。

string类型的redisObject

上面我们知道字符串对象(下面我们统一将xx对象理解成redisObject对象)底层的基础实现sds的一些细节。接下来我们具体看看sds是怎么和redisObject相关联的。

在第一章中我们知道字符串对象的编码可以是int、raw或者embstr。int中并没有用到sds,只有raw和embstr用了。

如果一个字符串对象保存的是整数值,并且这个整数值可以用long类型来表示,那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面(将void*转换成long),并将字符串对象的编码设置成int。

而对于raw和embstr来说,在最新版代码中(定义在object.c中),如果字符串长度小于等于44,则选择embstr,否则选择raw。

/* Create a string object with EMBSTR encoding if it is smaller than
 * OBJ_ENCODING_EMBSTR_SIZE_LIMIT, otherwise the RAW encoding is
 * used.
 *
 * The current limit of 44 is chosen so that the biggest string object
 * we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc. */
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
        return createEmbeddedStringObject(ptr,len);
    else
        return createRawStringObject(ptr,len);
}

embstr适用于短字符串而raw适用用于长字符串,其区别在于小内存可以一次分配完,好处是充分利用内存连续性,节省多次分配和释放的开销。而大内存一次分配太慢,因此raw是两次,分别创建redisObject和sds所需要的空间的。

编码的转换

int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下,会被转换为raw编码的字符串对象。

对于int编码的对象来说,如果我们向对象执行了一些命令,使得这个对象保存的不再是整数值,而是一个字符串值,那么字符串对象的编码将从int变为raw。

对于embstr编码的对象来说,因为Reids没有为embstr编码的字符串对象编写任何相应的修改程序,所以embstr编码的字符串对象实际上是只读的。当我们对embstr编码的字符串对象执行任何修改命令时,会进行转化。

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号