redis 学习 – sds 字符串
Redis 设计与实现:如果想要晓得 redis 底层,这本书能够给予不少的帮忙,十分举荐每一位学习 redis 的同学去翻一翻。
sds 字符串倡议多看看源代码的实现,这篇文章根本是集体看了好几篇文章之后的笔记。
源代码文件别离是:sds.c
,sds.h
redis 的 string API 应用
首先看下 API 的简略利用,设置 str1 变量为 helloworld,而后咱们应用 debug object + 变量名
的形式看下,留神编码为embstr。
127.0.0.1:17100> set str1 helloworld
-> Redirected to slot [5416] located at 127.0.0.1:17300
OK
127.0.0.1:17300> debug object str1
Value at:0x7f2821c0e340 refcount:1 encoding:embstr serializedlength:11 lru:14294151 lru_seconds_idle:8
如果咱们将 str2 设置为 helloworldhelloworldhelloworldhelloworldhell
,字符长度为 44,再应用下debug object+ 变量名
的形式看下,留神编码为embstr。
127.0.0.1:17300> set str2 helloworldhelloworldhelloworldhelloworldhell
-> Redirected to slot [9547] located at 127.0.0.1:17100
OK
127.0.0.1:17100> get str2
"helloworldhelloworldhelloworldhelloworldhell"
127.0.0.1:17100> debug object str2
Value at:0x7fd75e422c80 refcount:1 encoding:embstr serializedlength:21 lru:14294260 lru_seconds_idle:6
然而当咱们把设置为 helloworldhelloworldhelloworldhelloworldhello
,字符长度为 45,再应用debug object+ 变量名
的形式看下,留神编码扭转了,变为raw。
127.0.0.1:17100> set str2 helloworldhelloworldhelloworldhelloworldhello
OK
127.0.0.1:17100> debug object str2
Value at:0x7fd75e430c60 refcount:1 encoding:raw serializedlength:21 lru:14294358 lru_seconds_idle:9
最初咱们将其设置为整数 100,再应用 debug object+ 变量名
的形式看下,编码的格局变为了 int。
127.0.0.1:17100> set str2 11
OK
127.0.0.1:17100> get str2
"11"
127.0.0.1:17100> debug object str2
Value at:0x7fd75e44d370 refcount:2147483647 encoding:int serializedlength:2 lru:14294440 lru_seconds_idle:9
所以 Redis 的 string 类型一共有三种存储形式:
- 当字符串长度小于等于 44,底层采纳embstr;
- 当字符串长度大于 44,底层采纳raw;
- 当设置是 整数,底层则采纳int。
至于这三者有什么区别,能够间接看书:
http://redisbook.com/preview/…
为什么 redis string 要应用 sds 字符串?
- O(1)获取长度 ,c 语言的字符串自身不记录长度,而是通过开端的
\0
作为完结标记,而 sds 自身记录了字符串的长度所以获取间接变为 O(1)的工夫复杂度、同时,长度的保护操作由 sds 的自身 api 实现 - 避免缓冲区溢出 bufferoverflow:因为 c 不记录字符串长度,相邻字符串容易产生缓存溢出。sds 在进行增加之前会查看长度是否足够,并且不足够会主动依据 api 扩容
- 缩小字符串批改的内存调配次数:应用动静扩容的机制,依据字符串的大小抉择适合的 header 类型存储并且依据理论状况动静扩大。
- 应用 空间预调配和惰性空间开释,其实就是在扩容的时候,依据大小额定扩容 2 倍或者 1M 的空间,方面字符串批改的时候进行伸缩
- 应用 二进制爱护,数据的读写不受非凡的限度,写入的时候什么样读取就是什么样
- 反对 兼容局部 的 c 字符串函数,能够缩小局部 API 的开发
SDS 字符串和 C 语言字符串库有什么区别
摘自黄健巨大神的一张表
C 字符串 | SDS |
---|---|
获取字符串长度的复杂度为 O(N)。 | 获取字符串长度的复杂度为 O(1)。 |
API 是不平安的,可能会造成缓冲区溢出。 | API 是平安的,不会造成缓冲区溢出。 |
批改字符串长度 N 次必然须要执行 N 次内存重调配。 |
批改字符串长度 N 次最多须要执行 N 次内存重调配。 |
只能保留文本数据。 | 能够保留文本或者二进制数据。 |
能够应用所有 <string.h> 库中的函数。 |
能够应用一部分 <string.h> 库中的函数。 |
redis 的 sds 是如何实现的
因为 c 语言的 string 是以 \0
结尾的 Redis 独自封装了 SDS 简略动静字符串构造,如果在字符串变量非常多的状况下,会节约非常多的内存空间,同时为了缩小 malloc 操作,redis 封装了本人的 sds 字符串。
上面是网上查找的一个 sds 字符串实现的数据结构设计图:
s1,s2 别离指向实在数据区域的头部,而要确定一个 sds 字符串的类型,则须要通过 s[-1] 来获取对应的 flags,依据 flags 分别出对应的 Header 类型,获取到 Header 类型之后,依据最低三位获取 header 的类型(这也是应用 __attribute__ ((__packed__))
关键字的起因下文会阐明):
- 因为 s1[-1] == 0x01 == SDS_TYPE_8,因而 s1 的 header 类型是 sdshdr8。
- 因为 s2[-1] == 0x02 == SDS_TYPE_16,因而 s2 的 header 类型是 sdshdr16。
上面的局部是 sds 的实现源代码:
sds 一共有 5 种类型的 header。之所以有 5 种,是为了能让不同长度的字符串能够应用不同大小的 header。这样,短字符串就能应用较小的 header,从而节俭内存。
typedef char *sds;
// 这个比拟非凡,基本上用不到
struct __attribute__ ((__packed__)) sdshdr5 {
usigned char flags;
char buf[];};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];};
//string_size < 1ll<<32
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];};
//string_size < 1ll<<32
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];};
// 定义了五种 header 类型,用于示意不同长度的 string
#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 //
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); // 获取 header 头指针
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) // 获取 header 头指针
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
下面的代码须要留神以下两个点:
__attribute__ ((__packed__))
这是 C 语言的一种关键字, 这将使这个构造体在内存中不再恪守字符串对齐规定,而是以内存紧凑的形式排列。目标时在指针寻址的时候,能够间接通过 sds[-1]找到对应 flags,有了 flags 就能够晓得头部的类型,进而获取到对应的 len,alloc 信息,而不应用内存对齐,CPU 寻址就会变慢,同时如果不对齐会造成 CPU 进行优化导致空白位不补 0 使得 header 和 data 不间断,最终无奈通过 flags 获取低 3 位的 header 类型。SDS_HDR_VAR
函数则通过构造体类型与字符串开始字节,获取到动静字符串头部的开始地位,并赋值给 sh 指针。SDS_HDR
函数则通过类型与字符串开始字节,返回动静字符串头部的指针。- 在各个 header 的定义中最初有一个 char buf[]。咱们留神到这是一个没有指明长度的字符数组,这是 C 语言中定义字符数组的一种非凡写法,称为柔性数组(flexible array member),只能定义在一个构造体的最初一个字段上。它在这里只是起到一个标记的作用,示意在 flags 字段前面就是一个字符数组,或者说,它指明了紧跟在 flags 字段前面的这个字符数组在构造体中的偏移地位。而程序在为 header 调配的内存的时候,它并不占用内存空间。如果计算 sizeof(struct sdshdr16)的值,那么后果是 5 个字节,其中没有 buf 字段。
对于柔性数组的介绍:
深入浅出 C 语言中的柔性数组
- sdshdr5与其它几个 header 构造不同,它不蕴含 alloc 字段,而长度应用 flags 的 高 5 位 来存储。因而,它不能为字符串调配空余空间。如果字符串须要动静增长,那么它就必然要从新分配内存才行。所以说,这种类型的 sds 字符串更适宜存储动态的短字符串(长度小于 32)。
同时依据下面的构造能够看到,SDS 构造分为两个局部:
-
len、alloc、flags。只是
sdshdr5
有所不同,- len: 示意字符串的真正长度(不蕴含 NULL 结束符在内)。
- alloc: 示意字符串的最大容量(不蕴含最初多余的那个字节)。
- flags: 总是占用一个字节。其中的最低 3 个 bit 用来示意 header 的类型。header 的类型共有 5 种,在 sds.h 中有常量定义。
#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
- buf[]:柔性数组,之前有提到过,其实就是具体的数据存储区域,留神这里理论存储的数据的时候开端存在
NULL
小贴士:
\#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
\# 号有什么作用?
这个的含意是让 ”#” 前面的变量依照 一般字符串 来解决
双 \# 又有什么用途呢?
双“#”号能够了解为,在单“#”号的根底上,减少了连接功能
sds 的创立和销毁
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)
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;
}
sds sdsempty(void) {return sdsnewlen("",0);
}
sds sdsnew(const char *init) {
// 如果 initlen 为 NULL, 应用 0 作为初始化数据
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
}
void sdsfree(sds s) {if (s == NULL) return;
s_free((char*)s-sdsHdrSize(s[-1]));
}
下面的源代码须要留神如下几个点:
- SDS_TYPE_5因为设计之初依照常量看待,理论状况大多数为 append 操作扩容,而 SDS_TYPE_5 扩容会造成内存的调配,所以应用SDS_TYPE_8 进行断定
- SDS 字符串的长度为:
hdrlen+initlen+1
->sds_header
的长度 + 初始化长度 + 1 (开端占位符NULL
断定字符串结尾) s[initlen] = '\0';
字符串开端会应用\0
进行完结标记:代表为NULL
- sdsfree 开释 sds 字符串须要计算出 Header 的起始地位,具体为
s_malloc
指针所指向的地位
晓得了 sds 如何创立之后,咱们能够理解一下外面调用的具体函数。比方 sdsReqType,sdsReqType 办法定义了获取类型的办法,首先依据操作系统的位数依据判断 LLONG_MAX
是否等于LONG_MAX
,依据机器确定为 32 位的状况下调配 sds32,同时在 64 位的操作系统上依据判断小于 2^32 调配 sds32,否则调配 sds64。
这里值得注意的是:string_size < 1ll<<32
这段代码在 redis3.2 中才进行了 bug 修复,在晚期版本当中这里存在调配类型的Bug
commit
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
}
再来看下 sdslen
办法,s[-1]用于向低位地址偏移一个字节,和 SDS_TYPE_MASK
按位与的操作,取得 Header 类型,
static inline size_t sdslen(const sds s) {unsigned char flags = s[-1];
// SDS_TYPE_MASK == 7
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;
}
sds 的连贯(追加)操作
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
* end of the specified sds string 's'.
*
* After the call, the passed sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {size_t curlen = sdslen(s);
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
memcpy(s+curlen, t, len);
sdssetlen(s, curlen+len);
// 留神开端须要设置占位符 \0 代表完结标记
s[curlen+len] = '\0';
return s;
}
sds sdscat(sds s, const char *t) {return sdscatlen(s, t, strlen(t));
}
sds sdscatsds(sds s, const sds t) {return sdscatlen(s, t, sdslen(t));
}
// sds 实现的一个外围代码,用于判断是否能够追加以及是否有足够的空间
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);
// 如果小于 1M,则调配他的两倍大小,否则调配 +1M
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. */
// sdsheader5 会造成内存的重新分配,应用 header8 代替
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
// 如果不须要重新分配 header,那么试着在原来的 alloc 空间分配内存
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 */
// 如果须要更换 Header,则须要进行数据的搬迁
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;
}
通过下面的函数能够理解到每次传入的都是一个旧变量,然而在返回的时候,都是 新的 sds 变量,redis 少数的数据结构都采纳这种形式解决。
同时咱们能够确认一下几个点:
- append操作的实现函数为
sdscatlen
函数 getrange
这种截取一段字符串内容的形式能够间接操作字符数组,对于局部内容操作看起来比拟容易,效率也比拟高。
sds 字符串 的空间扩容策略:
- 如果 sds 字符串批改之后,空间小于 1M,扩容和 len 等长的未调配空间。比方批改之后为 13 个字节,那么程序也会调配
13
字节的未应用空间 - 如果批改之后大于等于 1M,则调配 1M 的内存空间,比方批改之后为 30M, 则 buf 的理论长度为:30M+1M+1Byte
简略来说就是:
- 小于 1M,扩容批改后长度 2 倍
- 大于 1M,扩容 1M
结尾:
多多翻翻材料,其实很多货色不须要去钻研细节,有很多优良的人为咱们答疑解惑,所以最重要的是了解作者为什么要这样设计,学习任何货色都要学习思维,思维层面的货色才是最有价值的。
sds 曾经被许多大佬文章进行过阐明,这篇文章只是简略的演绎了一下本人看的内容,如果有谬误的中央还望斧正,谢谢
参考资料:
上面是集体学习 sds 的参考资料:
Redis 外部数据结构详解(2)——sds
http://zhangtielei.com/posts/…
解析 redis 的字符串 sds 数据结构:
https://blog.csdn.net/wuxing2…
SDS 与 C 字符串的区别
http://redisbook.com/preview/…
Redis 源码分析 – 动静字符串 SDS
https://zhuanlan.zhihu.com/p/…
C 根底 带你手写 redis sds
https://www.lagou.com/lgeduar…
redis 源码剖析系列文章
http://www.soolco.com/post/73…
Redis SDS (简略动静字符串) 源码浏览
https://chenjiayang.me/2018/0…