Redis源码阅读笔记(1)——简单动态字符串sds实现原理

首先,sds即simple dynamic string,redis实现这个的时候使用了一个技巧,并且C99将其收录为标准,即柔性数组成员(flexible array member),参考资料见这里。柔性数组成员不占用结构体的空间,只作为一个符号地址存在,而且必须是结构体的最后一个成员。柔性数组成员不仅可以用于字符数组,还可以是元素为其它类型的数组。C99中,结构中的最后一个元素允许是未知大小的数组,这就叫做柔性数组成员,但结构中的柔性数组成员前面必须至少一个其他成员。柔性数组成员允许结构中包含一个大小可变的数组。sizeof返回的这种结构大小不包括柔性数组的内存。包含柔性数组成员的结构用malloc()函数进行内存的动态分配,并且分配的内存应该大于结构的大小,以适应柔性数组的预期大小。

Redis使用sds代替C语言中的char*,实现自定义的字符串对象,redis是K-V型DB,数据库的值可以是字符串、集合、列表多种类型,而键则总是字符串对象。Redis中的字符串分两类:二进制安全的和非二进制安全的,对于存储的值是二进制安全的,对于键是非二进制安全的。

对于二进制安全,我的理解就是把处理的字符串作为原始的、无任何特殊格式意义的数据流。

Redis中字符串类型是最基本的类型,redis自己实现的字符串对象相对char*来说,有以下两点优势:

  • char*计算字符串长度,时间O(n);
  • char*对字符串进行追加,追加N次,必定需要对字符串进行N次内存重分配;

作为值存储也是最常用的,其他诸如集合、列表也是基于字符串实现的,redis字符串类型sds在sds.h、shs.c文件中定义。

定义:

// sds 类型
typedef char *sds; // sdshdr 结构
struct sdshdr { // buf 已占用长度
int len; // buf 剩余可用长度
int free; // 实际保存字符串数据的地方
// 利用c99(C99 specification 6.7.2.1.16)中引入的 flexible array member,通过buf来引用sdshdr后面的地址,
// 详情google "flexible array member"
char buf[];
};

因为自定义类型加入了长度,每次获取字符串长度的时间复杂度就是O(1),而利用len和free属性对追加字符串进行优化,也可以降低重新分配内存的次数。但是这里也有要求就是len和free的更新要小心,不然很容易产生bug。

新建字符串对象:

sds sdsnewlen(const void *init, size_t initlen) {

    struct sdshdr *sh;

    // 有初始值
// O(N)
if (init) {
sh = zmalloc(sizeof(struct sdshdr)+initlen+);
} else {
sh = zcalloc(sizeof(struct sdshdr)+initlen+);
} // 内存不足,分配失败
if (sh == NULL) return NULL; sh->len = initlen;
sh->free = ; // 如果给定了 init 且 initlen 不为 0 的话
// 那么将 init 的内容复制至 sds buf
// O(N)
if (initlen && init)
memcpy(sh->buf, init, initlen); // 加上终结符
sh->buf[initlen] = '\0'; // 返回 buf 而不是整个 sdshdr
return (char*)sh->buf;
}

上面首先分配空间,空间大小为

sizeof(struct sdshdr)+initlen+

即sdshdr长度+字符串长度+一个结束符'\0'。

而且注意到,函数返回的是存储的字符串指针sh->buf,而不是sdshdr,那么如何得到sdshdr呢?

来举个例子:

sdsnewlen("redis", );

调用这个函数会新建一个sdshdr类型变量,其中内容如下:

len=5;

free=0;

buf="redis";

函数成功返回之后,大体是这个样子的:

-----------
|5|0|redis|
-----------
^ ^
sh sh->buf

函数返回地址sh->buf。此时如果想得到指向sh的指针可以得到吗?该怎么做呢?

答案是通过指针运算,sh->buf 减去两个int长度之后就得到了sh的地址。来看看redis源码里是怎么做的:

static inline size_t sdslen(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->len;
}

这里就是利用开头提到的flexible array member,char[]不占用结构体的空间,所以,s-(sizeof(struct sdshdr))恰好等于sh的地址。

优化追加操作:

上面提到了,redis使用sds比使用char*有两个地方有优势,下面来说说redis优化字符串追加操作的原理。

/*
* 将一个 char 数组的前 len 个字节复制至 sds
* 如果 sds 的 buf 不足以容纳要复制的内容,
* 那么扩展 buf 的长度,让 buf 的长度大于等于 len 。
*
* T = O(N)
*/
sds sdscpylen(sds s, const char *t, size_t len) { struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr))); // 是否需要扩展 buf ?
size_t totlen = sh->free+sh->len;
if (totlen < len) {
// 扩展 buf 长度,让它的长度大于等于 len
// 具体的大小请参考 sdsMakeRoomFor 的注释
// T = O(N)
s = sdsMakeRoomFor(s,len-sh->len);
if (s == NULL) return NULL;
sh = (void*) (s-(sizeof(struct sdshdr)));
totlen = sh->free+sh->len;
} // O(N)
memcpy(s, t, len);
s[len] = '\0'; sh->len = len;
sh->free = totlen-len; return s;
}

上面代码功能就是把一个字符串拷贝到sds,如果sds空间不够,则调用sdsMakeRoomFor来扩容;

再来看看append代码:

/*
* 按长度 len 扩展 sds ,并将 t 拼接到 sds 的末尾
*
* T = O(N)
*/
sds sdscatlen(sds s, const void *t, size_t len) { struct sdshdr *sh; size_t curlen = sdslen(s); // O(N)
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL; // 复制
// O(N)
memcpy(s+curlen, t, len); // 更新 len 和 free 属性
// O(1)
sh = (void*) (s-(sizeof(struct sdshdr)));
sh->len = curlen+len;
sh->free = sh->free-len; // 终结符
// O(1)
s[curlen+len] = '\0'; return s;
}

追加操作也是调用的sdsMakeRoomFor来扩展空间,追加字符串到源字符串最后。

那么sdsMakeRoomFor是怎么实现扩容的呢,具体扩容方案是什么呢?下面就是redis的源码:

/*
* 对 sds 的 buf 进行扩展,扩展的长度不少于 addlen 。
*
* T = O(N)
*/
sds sdsMakeRoomFor(
sds s,
size_t addlen // 需要增加的空间长度
)
{
struct sdshdr *sh, *newsh;
size_t free = sdsavail(s);
size_t len, newlen; // 剩余空间可以满足需求,无须扩展
if (free >= addlen) return s; sh = (void*) (s-(sizeof(struct sdshdr))); // 目前 buf 长度
len = sdslen(s);
// 新 buf 长度
newlen = (len+addlen);
// 如果新 buf 长度小于 SDS_MAX_PREALLOC 长度
// 那么将 buf 的长度设为新 buf 长度的两倍
if (newlen < SDS_MAX_PREALLOC)
newlen *= ;
else
newlen += SDS_MAX_PREALLOC; // 扩展长度
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+); if (newsh == NULL) return NULL; newsh->free = newlen - len; return newsh->buf;
}

可以看到,如果新字符串长度比SDS_MAX_PREALLOC小,则将其长度double,如果大于SDS_MAX_PREALLOC则再给SDS_MAX_PREALLOC空间。这个值redis定义的是1024*1024,即1MB。

这样一来,扩容一次多给一倍请求的空间,可以减少分配内存的次数,当然稍微有点浪费,但append操作一般情况不会太多,如果场景append很多还要优化redis的代码。

小结:

  1. Redis的字符串表示为sds,不是char*;
  2. 对比原生char*,sds有以下优势:
    • 长度计算只需O(1)时间复杂度;
    • 字符串追加更高效;
    • 二进制安全;
  3. sds对追加操作有优化,加快追加速度,降低内存重新分配次数,代价是浪费一些内存,并且不会主动释放。

参考资料:

  1. Redis String类型实现原理,http://blog.nosqlfan.com/html/2853.html
  2. c99之 柔性数组成员(flexible array member),http://blog.csdn.net/sunlylorn/article/details/7544301
  3. Binary-safe,http://en.wikipedia.org/wiki/Binary-safe
  4. https://github.com/huangz1990/annotated_redis_source
上一篇:.netcore跨平台 之 windows上编译,ubuntu上运行


下一篇:spring.net (3)依赖注入基础2