医院网站制作好吗,网络舆情监测与研判考试重点,微博主题WordPress,国家企业信用信息公示网查询(全国)简单动态字符串#xff08;Simple Dynamic Strings,SDS#xff09;是Redis的基本数据结构之一#xff0c;用于存储字符串和整型数据。SDS兼容C语言标准字符串处理函数#xff0c;且在此基础上保证了二进制安全。
1、数据结构
在了解SDS源码前#xff0c;我们先思考一个问…简单动态字符串Simple Dynamic Strings,SDS是Redis的基本数据结构之一用于存储字符串和整型数据。SDS兼容C语言标准字符串处理函数且在此基础上保证了二进制安全。
1、数据结构
在了解SDS源码前我们先思考一个问题如何实现一个扩容方便且二进制安全的字符串呢
注意 什么是二进制安全通俗地讲C语言中用“\0”表示字符串的结束如果字符串中本身就有“\0”字符字符串就会被截断即非二进制安全若通过某种机制保证读写字符串时不损害其内容则是二进制安全。
SDS既然是字符串那么首先需要一个字符串指针为了方便上层的接口调用该结构还需要记录一些统计信息如当前数据长度和剩余容量等例如 struct sds {int len; // buf中已占用字节数int free; // buf中剩余可用字节数char buf[]; // 数据空间};SDS结构示意如下图所示在64位系统下字段len和字段free各占4个字节紧接着存放字符串 Redis 3.2之前的SDS也是这样设计的。这样设计有以下几个优点
有单独的统计变量len和free称为头部。可以很方便地得到字符串长度。内容存放在柔性数组buf中SDS对上层暴露的指针不是指向结构体SDS的指针而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容兼容C语言处理字符串的各种函数。由于有长度统计变量len的存在读写字符串时不依赖“\0”终止符保证了二进制安全。
注意 上例中的buf[]是一个柔性数组。柔性数组成员flexible array member也叫伸缩性数组成员只能被放在结构体的末尾。包含柔性数组成员的结构体通过malloc函数为柔性数组动态分配内存。
之所以用柔性数组存放字符串是因为柔性数组的地址和结构体是连续的这样查找内存更快因为不需要额外通过指针找到字符串的位置可以很方便地通过柔性数组的首地址偏移得到结构体首地址进而能很方便地获取其余变量。
到这里我们实现了一个最基本的动态字符串但是该结构是否有改进的空间呢我们从一个简单的问题开始思考不同长度的字符串是否有必要占用相同大小的头部一个int占4字节在实际应用中存放于Redis中的字符串往往没有这么长每个字符串都用4字节存储未免太浪费空间了。我们考虑三种情况短字符串len和free的长度为1字节就够了长字符串用2字节或4字节更长的字符串用8字节。
这样确实更省内存但依然存在以下问题
问题1如何区分这3种情况问题2对于短字符串来说头部还是太长了。以长度为1字节的字符串为例len和free本身就占了2个字节能不能进一步压缩呢
对于问题1我们考虑增加一个字段flags来标识类型用最小的1字节来存储且把flags加在柔性数组buf之前这样虽然多了1字节但通过偏移柔性数组的指针即能快速定位flags区分类型也可以接受对于问题2由于len已经是最小的1字节了再压缩只能考虑用位来存储长度了。
结合两个问题5种类型长度1字节、2字节、4字节、8字节、小于1字节的SDS至少要用3位来存储类型2^38,1个字节8位剩余的5位存储长度可以满足长度小于32的短字符串。在Redis 5.0中我们用如下结构来存储长度小于32的短字符串 struct __attribute__ ((__packed__))sdshdr5 {unsigned char flags; / 低3位存储类型高5位存储长度 /char buf[]; /柔性数组存放实际内容/};sdshdr5结构下图中flags占1个字节其低3位bit表示type高5位bit表示长度能表示的长度区间为03125-1, flags后面就是字符串的内容。 而长度大于31的字符串1个字节依然存不下。我们按之前的思路将len和free单独存放。sdshdr8、sdshdr16、sdshdr32和sdshdr64的结构相同sdshdr16结构如下图所示 其中“表头”共占用了S[2(len)2(alloc)1(flags)]个字节。flags的内容与sdshdr5类似依然采用3位存储类型但剩余5位不存储长度。
在Redis的源代码中对类型的宏定义如下 #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在Redis 5.0中sdshdr8、sdshdr16、sdshdr32和sdshdr64的数据结构如下 struct __attribute__((__packed__))sdshdr8 {uint8_t len; / 已使用长度用1字节存储 /uint8_t alloc; / 总长度用1字节存储/unsigned char flags; / 低3位存储类型高5位预留 /char buf[]; /柔性数组存放实际内容/};struct __attribute__((__packed__))sdshdr16 {uint16_t len; /已使用长度用2字节存储/uint16_t alloc; / 总长度用2字节存储/unsigned char flags; / 低3位存储类型高5位预留 /char buf[]; /柔性数组存放实际内容/};struct __attribute__((__packed__))sdshdr32 {uint32_t len; /已使用长度用4字节存储/uint32_t alloc; / 总长度用4字节存储/unsigned char flags; / 低3位存储类型高5位预留 /char buf[]; /柔性数组存放实际内容/};struct __attribute__((__packed__))sdshdr64 {uint64_t len; /已使用长度用8字节存储/uint64_t alloc; / 总长度用8字节存储/unsigned char flags; / 低3位存储类型高5位预留 /char buf[]; /柔性数组存放实际内容/};可以看到这4种结构的成员变量类似唯一的区别是len和alloc的类型不同。结构体中4个字段的具体含义分别如下
len表示buf中已占用字节数。alloc表示buf中已分配字节数不同于free记录的是为buf分配的总长度。flags标识当前结构体的类型低3位用作标识位高5位预留。buf柔性数组真正存储字符串的数据空间。
2、基本操作
数据结构的基本操作不外乎增、删、改、查SDS也不例外。由于Redis 3.2后的SDS涉及多种类型修改字符串内容带来的长度变化可能会影响SDS的类型而引发扩容。
2.1、创建字符串
Redis通过sdsnewlen函数创建SDS。在函数中会根据字符串长度选择合适的类型初始化完相应的统计值后返回指向字符串内容的指针根据字符串长度选择不同的类型 sds sdsnewlen(const void init, size_t initlen) {void sh;sds s;char type sdsReqType(initlen); //根据字符串长度选择不同的类型if (type SDS_TYPE_5 initlen 0) type SDS_TYPE_8; //SDS_TYPE_5强制转化为SDS_TYPE_8int hdrlen sdsHdrSize(type); //计算不同头部所需的长度unsigned char fp; / 指向flags的指针 /sh s_malloc(hdrleninitlen1); //1是为了结束符’\0...s (char)shhdrlen; //s是指向buf的指针fp ((unsigned char)s)-1; //s是柔性数组buf的指针-1即指向flags...s[initlen] \0; //添加末尾的结束符return s;}注意 Redis 3.2后的SDS结构由1种增至5种且对于sdshdr5类型在创建空字符串时会强制转换为sdshdr8。原因可能是创建空字符串后其内容可能会频繁更新而引发扩容故创建时直接创建为sdshdr8。
创建SDS的大致流程首先计算好不同类型的头部和初始长度然后动态分配内存。需要注意以下3点
创建空字符串时SDS_TYPE_5被强制转换为SDS_TYPE_8。长度计算时有“1”操作是为了算上结束符“\0”。返回值是指向sds结构buf字段的指针。
返回值sds的类型定义如下 typedef char sds;从源码中我们可以看到其实s就是一个字符数组的指针即结构中的buf。这样设计的好处在于直接对上层提供了字符串内容指针兼容了部分C函数且通过偏移能迅速定位到SDS结构体的各处成员变量。
2.2、释放字符串
SDS提供了直接释放内存的方法——sdsfree该方法通过对s的偏移可定位到SDS结构体的首部然后调用s_free释放内存 void sdsfree(sds s) {if (s NULL) return;s_free((char)s-sdsHdrSize(s[-1])); //此处直接释放内存}为了优化性能减少申请内存的开销, SDS提供了不直接释放内存而是通过重置统计值达到清空目的的方法——sdsclear。该方法仅将SDS的len归零此处已存在的buf并没有真正被清除新的数据可以覆盖写而不用重新申请内存 void sdsclear(sds s) {sdssetlen(s, 0); //统计值len归零s[0] \0; //清空buf}2.3、拼接字符串
拼接字符串操作本身不复杂可用sdscatsds来实现代码如下 sds sdscatsds(sds s, const sds t) {return sdscatlen(s, t, sdslen(t));}sdscatsds是暴露给上层的方法其最终调用的是sdscatlen。由于其中可能涉及SDS的扩容sdscatlen中调用sdsMakeRoomFor对带拼接的字符串s容量做检查若无须扩容则直接返回s若需要扩容则返回扩容好的新字符串s。函数中的len、curlen等长度值是不含结束符的而拼接时用memcpy将两个字符串拼接在一起指定了相关长度故该过程保证了二进制安全。最后需要加上结束符。 / 将指针t的内容和指针s的内容拼接在一起该操作是二进制安全的/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(scurlen, t, len); //直接拼接保证了二进制安全sdssetlen(s, curlenlen);s[curlenlen] \0; //加上结束符return s;}下图描述了sdsMakeRoomFor的实现过程。 Redis的sds中有如下扩容策略 1若sds中剩余空闲长度avail大于新增内容的长度addlen直接在柔性数组buf末尾追加即可无须扩容。代码如下 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; //s[-1]即flagsint hdrlen;if (avail addlen) return s; //无须扩容直接返回...}2若sds中剩余空闲长度avail小于或等于新增内容的长度addlen则分情况讨论新增后总长度lenaddlen1MB的按新长度的2倍扩容新增后总长度lenaddlen1MB的按新长度加上1MB扩容。代码如下 sds sdsMakeRoomFor(sds s, size_t addlen){...newlen (lenaddlen);if (newlen SDS_MAX_PREALLOC)// SDS_MAX_PREALLOC这个宏的值是1MBnewlen 2;elsenewlen SDS_MAX_PREALLOC;...}3最后根据新长度重新选取存储类型并分配空间。此处若无须更改类型通过realloc扩大柔性数组即可否则需要重新开辟内存并将原字符串的buf内容移动到新位置。具体代码如下 sds sdsMakeRoomFor(sds s, size_t addlen){...type sdsReqType(newlen);/ type5的结构不支持扩容所以这里需要强制转成type8/if (type SDS_TYPE_5) type SDS_TYPE_8;hdrlen sdsHdrSize(type);if (oldtypetype) {/无须更改类型通过realloc扩大柔性数组即可注意这里指向buf的指针s被更新了/newsh s_realloc(sh, hdrlennewlen1);if (newsh NULL) return NULL;s (char)newshhdrlen;} else {/ 扩容后数据类型和头部长度发生了变化此时不再进行realloc操作而是直接重新开辟内存拼接完内容后释放旧指针/newsh s_malloc(hdrlennewlen1); //按新长度重新开辟内存if (newsh NULL) return NULL;memcpy((char)newshhdrlen, s, len1); //将原buf内容移动到新位置s_free(sh); //释放旧指针s (char)newshhdrlen; //偏移sds结构的起始地址得到字符串起始地址s[-1] type; //为falgs赋值sdssetlen(s, len); //为len属性赋值}sdssetalloc(s, newlen); //为alloc属性赋值return s;}2.4、其余API
下表列出了其他常用的API 学习时把握以下两点
SDS暴露给上层的是指向柔性数组buf的指针。读操作的复杂度多为O(1)直接读取成员变量涉及修改的写操作则可能会触发扩容。
