Redis SDS实现
介绍
Redis没有直接使用C语言传统的字符串而是自己创建了一种名为简单动态字符串SDS(simple dynamic string)的抽象类型(C语言封装的字符串类型),并将SDS用作Redis的默认字符串表示。
SDS是Redis默认的字符表示,比如包含字符串值的键值对都是由SDS实现的。
sds 有两个版本,在Redis 3.2之前使用的是第一个版本,其数据结构如下所示:
typedef char *sds; //注意,sds其实不是一个结构体类型,而是被typedef的char* struct sdshdr { unsigned int len; //buf中已经使用的长度 unsigned int free; //buf中未使用的长度 char buf[]; //柔性数组buf };
但是在Redis 3.2 版本中,对数据结构做出了修改,针对不同的长度范围定义了不同的结构,如下,这是目前的结构:
typedef char *sds; struct __attribute__ ((__packed__)) sdshdr5 { // 对应的字符串长度小于 1<<5 unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr8 { // 对应的字符串长度小于 1<<8 uint8_t len; /* used */ //目前字符创的长度 uint8_t alloc; //已经分配的总长度 unsigned char flags; //flag用3bit来标明类型,类型后续解释,其余5bit目前没有使用 char buf[]; //字符数组,以'\0'结尾 }; struct __attribute__ ((__packed__)) sdshdr16 { // 对应的字符串长度小于 1<<16 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 { // 对应的字符串长度小于 1<<32 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 { // 对应的字符串长度小于 1<<64 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[]; };
为了满足不同长度的字符串可以使用不同大小的Header,从而节省内存,可以选取不同的数据类型uint8_t或者uint16_t或者uint32_t等来表示长度、一共申请字节的大小等。
上面结构体中的__attribute__ ((__packed__)) 设置是告诉编译器取消字节对齐,则结构体的大小就是按照结构体成员实际大小相加得到的。
3.2版本之前的SDS
注意:这里的len是buf字符数组中,不包括最后的空字符的字符个数。
另外带有空闲空间的SDS字符串例子:
Redis SDS与C语言比较
1)获取字符串长度的时间复杂度
SDS获取字符串长度:O(1)。
C字符串获取字符串长度时间复杂度为O(N),需要遍历字符串,以空字符为结尾。
使用SDS可以确保获取字符串长度的操作不会成为Redis的性能瓶颈。
2)杜绝缓冲区溢出
C字符串不记录自身长度和空闲空间,容易造成缓冲区溢出,使用SDS则不会,SDS拼接字符串之前会先通过free字段检测剩余空间能否满足需求,不能满足需求的就会扩容。
3)减少修改字符串时带来的内存重分配次数
使用C字符串的话:
每次对一个C字符串进行增长或缩短操作,长度都需要对这个C字符串数组进行一次内存重分配,比如C字符串的拼接,程序要先进行内存重分配来扩展字符串数组的大小,避免缓冲区溢出,又比如C字符串的缩短操作,程序需要通过内存重分配来释放不再使用的那部分空间,避免内存泄漏,所以C语言中每次修改字符串都会造成内存重分配。
使用SDS的话:
通过SDS的len属性和free属性可以实现两种内存分配的优化策略:空间预分配和惰性空间释放。
1.针对内存分配的策略:空间预分配(SDS字符串扩容操作)
在对SDS的空间进行扩展的时候,程序不仅会为SDS分配修改所必须的空间,还会为SDS分配额外的未使用的空间
这样可以减少连续执行字符串增长操作所需的内存重分配次数,通过这种预分配的策略,SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次,这是个很大的性能提升。
额外分配未使用空间的大小由以下策略决定:
在扩展sds空间之前,sds api会检查未使用的空间是否够用,如果够用则直接使用未使用的空间,无须执行内存重分配。
如果空间不够用则执行内存重分配:
2.针对内存释放的策略:惰性空间释放(SDS字符串缩短操作)
在对SDS的字符串进行缩短操作的时候,程序并不会立刻使用内存重分配来回收缩短之后多出来的字节,而是使用free属性将这些字节的数量记录下来等待将来使用。
通过惰性空间释放策略,SDS避免了缩短字符串时所需的内存重分配次数,并且为将来可能有的增长操作提供了优化!
当然如果我们在有需要的时候,也可以通过sds api来释放未使用的空间,不用担心惰性空间释放策略会造成内存浪费。
4)二进制安全
为了确保数据库可以二进制数据(图片,视频等),SDS的API都是二进制安全的,所有的API都会以处理二进制的方式来处理存放在SDS的buf数组里面的数据,程序不会对其中的数据做任何的限制,过滤,数据存进去是什么样子,读出来就是什么样子,这也是buf数组叫做字节数组而不是叫字符数组的原因,以为它是用来保存一系列二进制数据的。
通过二进制安全的SDS,Redis不仅可以保存文本数据,还可以保存任意格式是二进制数。
而C语言字符串的字符必须符号某种编码(比如ascii),并且除了末尾的空字符,字符串其他位置不能包含空字符,所以C语言字符串只能保存文本数据,不能保存二进制数据。
5)兼容部分c语言函数
总结:
3.2版本前sds sapi源码
Redis学习之SDS源码分析
3.2版本之后的SDS
下面内容转载:Redis源码分析(sds)
此时的SDS由两个部分组成,Header与数据部分。
Header部分主要包含以下几个部分:
- len:表示字符串真正的长度,不包括空终止字符
- alloc:表示字符串的最大容量,不包含Header和最后的空终止字符
- flags:表示Header的类型
数据部分:字符数组。
由于sds的header共有五种,要想得到sds的header属性,就必须先知道header的类型,flags字段存储了header的类型。假如我们定义了sds* s,那么获取flags字段仅仅需要将s向前移动一个字节,即unsigned char flags = s[-1]。
// 五种header类型,flags取值为0~4 #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
然后通过以下宏定义来对header进行操作
#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) // 获取sdshdr5的长度
创建、扩容和销毁
接下来我们以一个例子来跟踪源码展示sds的创建、扩容和销毁等过程,这是我们的源代码:
int main(int argc, char *argv[]) { sds s = sdsnew("Hello World,"); printf("Length:%d, Type:%d\n", sdslen(s), sdsReqType(sdslen(s))); s = sdscat(s, "The length of this sentence is greater than 32 bytes"); printf("Length:%d, Type:%d\n", sdslen(s), sdsReqType(sdslen(s))); sdsfree(s); return 0; } Out> Length:12, Type:0 Length:64, Type:1
首先我们创建了一个sds名为s,初始化为”Hello World”,然后打印它的length和type分别为12和0,接着我们继续给s追加了一个字符串,使得它的长度变成了64,获取type,发现变成了1,最后free掉s,有关type的定义,位于sds.h头文件,随着长度不同,type也会发生变化。
#define SDS_TYPE_5 0 //长度小于 1<<5 即32,类型为SDS_TYPE_5 #define SDS_TYPE_8 1 // ... #define SDS_TYPE_16 2 #define SDS_TYPE_32 3 #define SDS_TYPE_64 4
下面我们从sdsnew出发,去看下它的实现:
/* Create a new sds string starting from a null terminated C string. */ sds sdsnew(const char *init) { size_t initlen = (init == NULL) ? 0 : strlen(init); return sdsnewlen(init, initlen); }
可以看到sdsnew实际上调用了sdsnewlen,帮我们计算了传进去的字符串长度,然后传给sdsnewlen,继续看sdsnewlen
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; }
函数基本流程如下所示:
char type = sdsReqType(initlen);根据我们传入的初始化字符串长度获取类型,获取代码如下:
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; #endif return SDS_TYPE_64; }
函数根据字符串大小的不同返回不同的类型。
int hdrlen = sdsHdrSize(type);根据上一步获取的type通过sdsHdrSize函数获得Header的长度,sdsHdrSize代码如下:
static inline int sdsHdrSize(char type) { switch(type&SDS_TYPE_MASK) { case SDS_TYPE_5: return sizeof(struct sdshdr5); case SDS_TYPE_8: return sizeof(struct sdshdr8); case SDS_TYPE_16: return sizeof(struct sdshdr16); case SDS_TYPE_32: return sizeof(struct sdshdr32); case SDS_TYPE_64: return sizeof(struct sdshdr64); } return 0; }
这个函数直接return了相应的结构体大小。
接下来malloc申请了hdrlen+initlen+1大小的空间,表示头部+字符串+Null,然后让s指向了字符串的首地址,fp指向了头部的最后一个字节,也就是flag。
然后我们的程序进入了switch,因为类型为SDS_TYPE_5,所以执行了*fp = type | (initlen << SDS_TYPE_BITS); 对于SDS_TYPE_5类型来说,长度信息实际上也是存在flag里面的,因为最大长度是31,占5bit,还有3bit表示type。
接着break出来后,完成了字符串的拷贝工作,然后给s结尾置’\0’,s[initlen] = '\0';,至此,sdsnew调用完毕,此时我们的sds结构如下图所示:
flag大小为1字节,中间的String长度为11字节,后面还有一个\0结尾。接着我们的代码执行输出长度和类型,然后调用了sdscat函数,如下:
s = sdscat(s, "The length of this sentence is greater than 32 bytes");
我们给原始的s继续追加了超过32个字符,其实目的是为了是它转变成SDS_TYPE_8类型,sdscat的代码如下所示:
sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t)); }
它调用了sdscatlen函数:
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); s[curlen+len] = '\0'; return s; }
size_t curlen = sdslen(s);首先获取了当前的长度curlen,接着调用了sdsMakeRoomFor函数,这个函数比较关键,它能保证s的空间足够,如果空间不足会动态分配,代码如下:
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); 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. */ if (type == SDS_TYPE_5) type = SDS_TYPE_8; hdrlen = sdsHdrSize(type); 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 */ 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; }
size_t avail = sdsavail(s);首先调用sdsavail函数获取了当前s可用空间的大小,sdsavail函数如下:
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; }
对于SDS_TYPE_5类型,直接return 0,对于其他类型,需要在Header获取alloc和len然后相减,获取Header的宏如下:
SDS_HDR_VAR(8,s); #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); //本质上就是用s的地址减去(偏移)相应头部结构体大小的地址,就到了Header的第一个字节 return sh->alloc - sh->len; //然后返回可用字节大小
if (avail >= addlen) return s; 接着判断大小,如果空间是足够的,则将s返回,函数结束。
否则我们获取到目前的长度,然后给它加上sdscat所追加的字符串长度,如果此时的新长度没有超过SDS_MAX_PREALLOC=1024*1024,我们再给新长度x2,这样做是为了避免频繁调用malloc。
type = sdsReqType(newlen); 然后我们需要根据新长度重新获取type类型。
if (oldtype==type)然后判断type是否发生了变化,来决定扩充空间还是重新申请空间。对于我们的例子,接下来需要重新分配空间,如下,走else分支:
else { /* Since the header size changes, need to move the string forward, * and can't use realloc */ newsh = s_malloc(hdrlen+newlen+1); //重新分配Header+newlen+1的空间 if (newsh == NULL) return NULL; memcpy((char*)newsh+hdrlen, s, len+1); //将String部分拷贝至新String部分 s_free(sh); //把旧的sds全部释放 s = (char*)newsh+hdrlen; s[-1] = type; //将type更新 sdssetlen(s, len); //设置大小 } sdssetalloc(s, newlen); //设置alloc大小 return s; //将新的s返回 }
当sdsMakeRoomFor函数返回后,sdscatlen函数继续执行,将需要添加的字符串拷贝至新的空间,然后设置长度和最后的\0就返回了。此时s变成了下面这样:
需要注意的是执行代码打印出来长度为64指的是已经分配的长度,也就是len的大小,图片上的128是alloc的大小,则此时可用长度还有64字节,下次如果再追加小于64字节的内容就不会重新分配了。最后我们看下free的过程,代码如下:
void sdsfree(sds s) { if (s == NULL) return; s_free((char*)s-sdsHdrSize(s[-1])); }
很简单,如果为NULL就返回,否则得到Header的首地址然后释放,sdsHdrSize(s[-1])是根据flag类型获取Header的长度,用s减去(偏移)Header长度个字节就到头部了。上面的过程基本上分析清楚了sds有关于创建和扩容以及释放的过程,这样其实已经把握了sds的大体脉络。
相关文章
- 基于redis集群实现的分布式锁,可用于秒杀,定时器。
- 用PHP+Redis实现延迟任务,实现自动取消订单
- Laravel 下配置 Redis 让缓存、Session 各自使用不同的 Redis 数据库
- Redis实战 内存淘汰机制
- Redis学习(4)-数据类型,string,hash
- Redis阻塞操作实现原理(转)
- Centos7安装Redis
- redis 简单整理——内存的优化[二十七]
- spring boot:用redis+lua实现基于ip地址的分布式流量限制(限流/简单计数器算法)(spring boot 2.2.0)
- 单点登录实现(spring session+redis完成session共享)
- redis 内存淘汰策略和内存大小限制
- Redis数据清除问题
- Atitit.redis操作总结
- 〖Python 数据库开发实战 - Python与Redis交互篇⑤〗- 利用 redis-py 实现哈希数据类型的常用指令操作
- 〖Python 数据库开发实战 - Python与Redis交互篇⑧〗- 利用 redis-py 实现缓存观众投票数据信息案例
- 深入理解 Redis Template及4种序列化方式__spring boot整合redis实现RedisTemplate三分钟快速入门
- 【架构师修炼之路】Redis 哨兵机制 ( Sentinel ) : 实现高可用Redis 哨兵机制 ( Sentinel ) : 实现高可用...
- 分布式锁tair redis zookeeper,安全性
- Java操作Redis的方式
- 为什么分布式一定要有redis?
- 借助共享缓存redis实现分布式锁
- 利用redis-lua+python实现接口限流
- RedLock算法-使用redis实现分布式锁服务
- 监控服务器配置(五)-----Redis_exporter安装配置
- 【redis】redis的 key的命名规则
- 03-Redis客户端连接Redis服务器(redis.conf 文件配置没有生效导致redis运行报错Error: Connection reset by peer)
- 【redis】Redis缓存失效、雪崩、穿透、击穿、并发等案例分析难题解决方案
- Redis_19_Redis实现消息队列