网站建设网站建设平台,网站出现的问题,专业做网站照片,陕西中药材初加工平台文章目录 sds简介与特性(面试)sds结构模型数据结构苛刻的数据优化数据结构优化uintX_t对齐填充 sds优势O(1)时间复杂度获取字符串长度二进制安全杜绝缓冲区溢出自动扩容机制——sdsMakeRoomFor方法 内存重分配次数优化 sds最长是多少部分API源码解读创建sds释放sds sds简介与特… 文章目录 sds简介与特性(面试)sds结构模型数据结构苛刻的数据优化数据结构优化uintX_t对齐填充 sds优势O(1)时间复杂度获取字符串长度二进制安全杜绝缓冲区溢出自动扩容机制——sdsMakeRoomFor方法 内存重分配次数优化 sds最长是多少部分API源码解读创建sds释放sds sds简介与特性(面试) Redis 面试中大概率会提及相关的数据结构SDS 的八股文大部分人倒背如流可是没有读过源码知其然不知其所以然这可万万使不得呀
sds结构模型 本文阅读的Redis源码为最新的 Redis6.2.6 和 Redis3.0.0版本 相信各位看官在听到 Redis 中的字符串不是简简单单的C语言中的字符串是 SDSSimple Dynamic String简单动态字符串时以为是造出了啥新类型呢其实 SDS 内容的源码底层就是typedef char *sds;。
数据结构
Redis6.x 的 SDS 的数据结构定义与 Redis3.0.0 相差比较大但是核心思想不变。先从简单版本Redis3.x开始吧~
struct sdshdr {//记录buf数组中已使用字节的数量//等于SDS所保存字符串的长度unsigned int len;//记录buf数组中未使用字节的数量unsigned int free;//char数组用于保存字符串char buf[];
};如下图所示为字符串Aobing在Redis中的存储形式 len 为6表示这个 SDS 保存了一个长度为6的字符串free 为0表示这个 SDS 没有剩余空间buf 是个char类型的数组注意末尾保存了一个空字符’\0’。 buf 尾部自动追加一个’\0’字符并不会计算在 SDS 的len中这是为了遵循 C 字符串以空字符串结尾的惯例使得 SDS 可以直接使用一部分string.h库中的函数如strlen #include stdio.h
#include string.hint main()
{char buf[] {A,o,b,i,n,g,\0};printf(%s\n,buf); // Aobingprintf(%lu\n,strlen(buf)); // 6return 0;
}苛刻的数据优化
数据结构优化
目前我们似乎得到了一个结构不错的 SDS 但是我们能否继续进行优化呢
在 Redis3.x 版本中不同长度的字符串占用的头部是相同的如果某一字符串很短但是头部却占用了更多的空间这未免太浪费了。所以我们将 SDS 分为三种级别的字符串
短字符串(长度小于32)len和free的长度用1字节即可长字符串用2字节或者4字节超长字符串用8字节。 共有五种类型的SDS长度小于1字节、1字节、2字节、4字节、8字节 我们可以在 SDS 中新增一个 type 字段来标识类型但是没必要使用一个 4 字节的int类型去做可以使用 1 字节的char类型通过位运算3位即可标识2^3种类型来获取类型。
如下所示为短字符串(长度小于32)的优化形式 低三位存储类型高5位存储长度最多能标识的长度为32所以短字符串的长度必定小于32。 无需free字段了32-len即为free 接下来看看Redis6.x中是怎么做的吧
// 注意sdshdr5从未被使用Redis中只是访问flags。
struct __attribute__ ((__packed__)) sdshdr5 {unsigned char flags; /* 低3位存储类型, 高5位存储长度 */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* 已使用 */uint8_t alloc; /* 总长度用1字节存储 */unsigned char flags; /* 低3位存储类型, 高5位预留 */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len; /* 已使用 */uint16_t alloc; /* 总长度用2字节存储 */unsigned char flags; /* 低3位存储类型, 高5位预留 */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* 已使用 */uint32_t alloc; /* 总长度用4字节存储 */unsigned char flags; /* 低3位存储类型, 高5位预留 */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {uint64_t len; /* 已使用 */uint64_t alloc; /* 总长度用8字节存储 */unsigned char flags; /* 低3位存储类型, 高5位预留 */char buf[];
};数据结构和我们分析的差不多嘛也是加一个标识字段而已并且不是int类型而是1字节的char类型使用其中的3位表示具体的类型。 同时Redis 中也声明了5个常量分别表示五种类型的 SDS 与我们分析的也不谋而合。
#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4uintX_t
对比前后两版代码不难发现在 Redis6.x 中 int 类型也多出了几种uint8_t / uint16_t / uint32_t /uint64_t。乍一看以为是新增类型呢毕竟 C语言里面可没有这些类型呀查看相关源码如下
typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
typedef unsigned int uint32_t;
typedef unsigned long long uint64_t;对齐填充
在 Redis6.x 的源码中 SDS 的结构体为struct __attribute__ ((__packed__))与struct有较大的差别这其实和我们熟知的对齐填充有关。
1举个例子
考虑如下结构体
typedef struct{char c1;short s; char c2; int i;
} s;若此结构体中的成员都是紧凑排列的假设c1的起始地址为0则s的地址为1c2的地址为3i的地址为4。下面用代码论证一下我们的假设。
#include stdio.htypedef struct
{char c1;short s;char c2;int i;
} s;int main()
{s a;printf(c1 - %d, s - %d, c2 - %d, i - %d\n,(unsigned int)(void *)a.c1 - (unsigned int)(void *)a,(unsigned int)(void *)a.s - (unsigned int)(void *)a,(unsigned int)(void *)a.c2 - (unsigned int)(void *)a,(unsigned int)(void *)a.i - (unsigned int)(void *)a);return 0;
}
// 结果为c1 - 0, s - 2, c2 - 4, i - 8尴尬了和假设差的不是一星半点呀这就是对齐填充搞的鬼这啥啥啥呀~
2什么是字节对齐
现代计算机中内存空间按照字节划分理论上可以从任何起始地址访问任意类型的变量。但实际中在访问特定类型变量时经常在特定的内存地址访问这就需要各种类型数据按照一定的规则在空间上排列而不是顺序一个接一个地存放这就是对齐。
3对齐原因
为什么需要对齐填充是由于各个硬件平台对存储空间的处理上有很大的不同。一些平台对某些特定类型的数据只能从某些特定地址开始存取。
最常见的是如果不按照适合其平台的要求对数据存放进行对齐会在存取效率上带来损失。
比如有些平台每次读都是从偶地址开始如果一个int型假设为 32位存放在偶地址开始的地方那么一个读周期就可以读出而如果存放在奇地址开始的地方就可能会需要2个读周期并对两次读出的结果的高低字节进行拼凑才能得到该int数据导致在读取效率上下降很多。
4更改对齐方式 注意我们写程序的时候不需要考虑对齐问题。编译器会替我们选择适合目标平台的对齐策略。 如果我们一定要手动更改对齐方式一般可以通过下面的方法来改变缺省的对界条件 使用伪指令#pragma pack(n)C编译器将按照n个字节对齐 使用伪指令#pragma pack() 取消自定义字节对齐方式。
另外还有如下的一种方式(GCC特有语法) __attribute((aligned (n))) 让所作用的结构成员对齐在n字节自然边界上。如果结构体中有成员的长度大于n则按照最大成员的长度来对齐。 attribute ((packed)) 取消结构在编译过程中的优化对齐按照实际占用字节数进行对齐。
将上述示例代码的结构体更改如下(取消对齐)再次执行可以发现取消对齐后和我们的假设就一致了。
typedef struct __attribute__ ((__packed__))
{char c1;short s;char c2;int i;
} s;
// 再次执行c1 - 0, s - 1, c2 - 3, i - 45redis为什么不对齐呢
综上所述我们知道了对齐填充可以提高 CPU 的数据读取效率作为 IO 频繁的 Redis 为什么选择不对齐呢
我们再次回顾 Redis6.x 中的 SDS 结构 有个细节各位需要知道即 SDS 的指针并不是指向 SDS 的起始位置len位置而是直接指向buf[]使得 SDS 可以直接使用 C 语言string.h库中的某些函数做到了兼容十分nice~。 如果不进行对齐填充那么在获取当前 SDS 的类型时则只需要后退一步即可flagsPointer ((unsigned char*)s)-1
相反若进行对齐填充由于 Padding 的存在我们在不同的系统中不知道退多少才能获得flags并且我们也不能将 sds 的指针指向flags这样就无法兼容 C 语言的函数了也不知道前进多少才能得到 buf[]。
sds优势
O(1)时间复杂度获取字符串长度
由于C字符串不记录自身的长度所以为了获取一个字符串的长度程序必须遍历这个字符串直至遇到’0’为止整个操作的时间复杂度为O(N)。而我们使用SDS封装字符串则直接获取len属性值即可时间复杂度为O(1)。 二进制安全 什么是二进制安全 通俗地讲C语言中用’0’表示字符串的结束如果字符串本身就有’0’字符字符串就会被截断即非二进制安全若通过某种机制保证读写字符串时不损害其内容则是二进制安全。 C字符串中的字符除了末尾字符为’\0’外其他字符不能为空字符否则会被认为是字符串结尾(即使实际上不是)。这限制了C字符串只能保存文本数据而不能保存二进制数据。而SDS使用len属性的值判断字符串是否结束所以不会受’\0’的影响。
杜绝缓冲区溢出
字符串的拼接操作是使用十分频繁的在C语言开发中使用char *strcat(char *dest,const char *src)方法将src字符串中的内容拼接到dest字符串的末尾。
由于C字符串不记录自身的长度所有strcat方法已经认为用户在执行此函数时已经为dest分配了足够多的内存足以容纳src字符串中的所有内容而一旦这个条件不成立就会产生缓冲区溢出会把其他数据覆盖掉Dangerous~。
// strcat 源码
char * __cdecl strcat (char * dst, const char * src)
{char * cp dst;while( *cp )cp; /* 找到 dst 的结尾 */while( *cp *src ) ; /* 无脑将 src 复制到 dst 中 */return( dst ); /* 返回 dst */
} 如下图所示为一次缓冲区溢出 与C字符串不同SDS 的自动扩容机制完全杜绝了发生缓冲区溢出的可能性当SDS API需要对SDS进行修改时API会先检查 SDS 的空间是否满足修改所需的要求如果不满足API会自动将SDS的空间扩展至执行修改所需的大小然后才执行实际的修改操作所以使用 SDS 既不需要手动修改SDS的空间大小也不会出现缓冲区溢出问题。
SDS 的sds sdscat(sds s, const char *t)方法在字符串拼接时会进行扩容相关操作。
sds sdscatsds(sds s, const sds t) {return sdscatlen(s, t, sdslen(t));
}/* s: 源字符串* t: 待拼接字符串* len: 待拼接字符串长度*/
sds sdscatlen(sds s, const void *t, size_t len) {// 获取源字符串长度size_t curlen sdslen(s);// SDS 分配空间自动扩容机制s sdsMakeRoomFor(s,len);if (s NULL) return NULL;// 将目标字符串拷贝至源字符串末尾memcpy(scurlen, t, len);// 更新 SDS 长度sdssetlen(s, curlenlen);// 追加结束符s[curlenlen] \0;return s;
}自动扩容机制——sdsMakeRoomFor方法
strcatlen中调用sdsMakeRoomFor完成字符串的容量检查及扩容操作重点分析此方法
/* s: 源字符串* addlen: 新增长度*/
sds sdsMakeRoomFor(sds s, size_t addlen) {void *sh, *newsh;// sdsavail: s-alloc - s-len, 获取 SDS 的剩余长度size_t avail sdsavail(s);size_t len, newlen, reqlen;// 根据 flags 获取 SDS 的类型 oldtypechar type, oldtype s[-1] SDS_TYPE_MASK;int hdrlen;size_t usable;/* Return ASAP if there is enough space left. */// 剩余空间大于等于新增空间无需扩容直接返回源字符串if (avail addlen) return s;// 获取当前长度len sdslen(s);// sh (char*)s-sdsHdrSize(oldtype);// 新长度reqlen newlen (lenaddlen);// 断言新长度比原长度长否则终止执行assert(newlen len); /* 防止数据溢出 */// SDS_MAX_PREALLOC 1024*1024, 即1MBif (newlen SDS_MAX_PREALLOC)// 新增后长度小于 1MB 则按新长度的两倍扩容newlen * 2;else// 新增后长度大于 1MB 则按新长度加上 1MB 扩容newlen SDS_MAX_PREALLOC;// 重新计算 SDS 的类型type sdsReqType(newlen);/* Dont 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. */// 不使用 sdshdr5 if (type SDS_TYPE_5) type SDS_TYPE_8;// 获取新的 header 大小hdrlen sdsHdrSize(type);assert(hdrlen newlen 1 reqlen); /* Catch size_t overflow */if (oldtypetype) {// 类型没变// 调用 s_realloc_usable 重新分配可用内存返回新 SDS 的头部指针// usable 会被设置为当前分配的大小newsh s_realloc_usable(sh, hdrlennewlen1, usable);if (newsh NULL) return NULL; // 分配失败直接返回NULL// 获取指向 buf 的指针s (char*)newshhdrlen;} else {// 类型变化导致 header 的大小也变化需要向前移动字符串不能使用 reallocnewsh s_malloc_usable(hdrlennewlen1, usable);if (newsh NULL) return NULL;// 将原字符串copy至新空间中memcpy((char*)newshhdrlen, s, len1);// 释放原字符串内存s_free(sh);s (char*)newshhdrlen;// 更新 SDS 类型s[-1] type;// 设置长度sdssetlen(s, len);}// 获取 buf 总长度(待定)usable usable-hdrlen-1;if (usable sdsTypeMaxSize(type))// 若可用空间大于当前类型支持的最大长度则截断usable sdsTypeMaxSize(type);// 设置 buf 总长度sdssetalloc(s, usable);return s;
}自动扩容机制总结
扩容阶段
若 SDS 中剩余空闲空间 avail 大于新增内容的长度 addlen则无需扩容若 SDS 中剩余空闲空间 avail 小于或等于新增内容的长度 addlen 若新增后总长度 lenaddlen 1MB则按新长度的两倍扩容若新增后总长度 lenaddlen 1MB则按新长度加上 1MB 扩容。
内存分配阶段
根据扩容后的长度选择对应的 SDS 类型 若类型不变则只需通过 s_realloc_usable(即realloc函数)扩大 buf 数组即可若类型变化则需要为整个 SDS 重新分配内存并将原来的 SDS 内容拷贝至新位置。
自动扩容流程图如下所示 扩容后的 SDS 不会恰好容纳下新增的字符而是多分配了一些空间(预分配策略)这减少了修改字符串时带来的内存重分配次数 内存重分配次数优化
1空间预分配策略
因为 SDS 的空间预分配策略 SDS 字符串在增长过程中不会频繁的进行空间分配。通过这种分配策略SDS 将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。
2惰性空间释放机制
空间预分配策略用于优化 SDS 增长时频繁进行空间分配而惰性空间释放机制则用于优化 SDS 字符串缩短时并不立即使用内存重分配来回收缩短后多出来的空间而仅仅更新 SDS 的len属性多出来的空间供将来使用。
SDS 中调用sdstrim方法来缩短字符串
/* sdstrim 方法删除字符串首尾中在 cset 中出现过的字符* 比如:* s sdsnew(AA...AA.a.aa.aHelloWorld :::);* s sdstrim(s,Aa. :);* printf(%s\n, s);** SDS 变成了 HelloWorld*/
sds sdstrim(sds s, const char *cset) {char *start, *end, *sp, *ep;size_t len;sp start s;ep end ssdslen(s)-1;// strchr()函数用于查找给定字符串中某一个特定字符while(sp end strchr(cset, *sp)) sp;while(ep sp strchr(cset, *ep)) ep--;len (sp ep) ? 0 : ((ep-sp)1);if (s ! sp) memmove(s, sp, len);s[len] \0;// 仅仅更新了lensdssetlen(s,len);return s;
}勘误 在《Redis的设计与实现》一书中针对 sdstrim方法的讲解为删除字符串中 cset 出现的所有字符而不是首尾。 比如调用sdstrim(“XYXaYYbcXyY”,“XY”)后移除了所有的’X’和’Y’。这是错误❌的~ SDS 并没有释放多出来的5字节空间仅仅将 len 设置成了7剩余空间为5。如果后续字符串增长时则可以派上用场可能不需要再分配内存。
也许各位看官又会有疑问了这没真正释放空间是否会导致内存泄漏呢放心SDS为我们提供了真正释放SDS未使用空间的方法sdsRemoveFreeSpace。
sds sdsRemoveFreeSpace(sds s) {void *sh, *newsh;// 获取类型char type, oldtype s[-1] SDS_TYPE_MASK;// 获取 header 大小int hdrlen, oldhdrlen sdsHdrSize(oldtype);// 获取原字符串长度size_t len sdslen(s);// 获取可用长度size_t avail sdsavail(s);// 获取指向头部的指针sh (char*)s-oldhdrlen;/* Return ASAP if there is no space left. */if (avail 0) return s;// 查找适合这个字符串长度的最优 SDS 类型type sdsReqType(len);hdrlen sdsHdrSize(type);/* 如果类型相同或者至少仍然需要一个足够大的类型我们只需 realloc buf即可* 否则说明变化很大则手动重新分配字符串以使用不同的头文件类型。*/if (oldtypetype || type SDS_TYPE_8) {newsh s_realloc(sh, oldhdrlenlen1);if (newsh NULL) return NULL;s (char*)newsholdhdrlen;} else {newsh s_malloc(hdrlenlen1);if (newsh NULL) return NULL;memcpy((char*)newshhdrlen, s, len1);// 释放内存s_free(sh);s (char*)newshhdrlen;s[-1] type;sdssetlen(s, len);}// 重新设置总长度为lensdssetalloc(s, len);return s;
}sds最长是多少
Redis 官方给出了最大的字符串容量为 512MB。这是为什么呢 在 Reids3.x 版本中len是使用int修饰的这就会导致 buf 最长就是2147483647无形中限制了字符串的最大长度。
任何细节在源码中都能发现在_sdsnewlen方法创建 SDS 中都会调用sdsTypeMaxSize方法获取每种类型所能创建的最大buf长度不难发现此方法最大的返回值为2147483647即512MB。
static inline size_t sdsTypeMaxSize(char type) {if (type SDS_TYPE_5)return (15) - 1;if (type SDS_TYPE_8)return (18) - 1;if (type SDS_TYPE_16)return (116) - 1;
#if (LONG_MAX LLONG_MAX)if (type SDS_TYPE_32)return (1ll32) - 1; // 不管方法啥意思最大返回2147483647。OVER~
#endifreturn -1; /* this is equivalent to the max SDS_TYPE_64 or SDS_TYPE_32 */
}此方法在 Redis3.0.0中是不存在的 部分API源码解读
创建sds
Redis 通过sdsnewlen方法创建 SDS。在方法中会根据字符串初始化长度选择合适的类型。
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {void *sh;sds s;// 根据初始化长度判断 SDS 的类型char type sdsReqType(initlen);// SDS_TYPE_5 强制转换为 SDS_TYPE_8// 这样侧面验证了 sdshdr5 从未被使用创建这一步就GG了 ੯ੁૂ‧̀͡u\if (type SDS_TYPE_5 initlen 0) type SDS_TYPE_8;// 获取头部大学int hdrlen sdsHdrSize(type);// 指向 flags 的指针unsigned char *fp; /* flags pointer. */// 分配的空间size_t usable;// 防止溢出assert(initlen hdrlen 1 initlen); /* Catch size_t overflow */// 分配空间// s_trymalloc_usable: 尝试分配内存失败则返回NULL// s_malloc_usable: 分配内存或者抛异常[不友好]sh trymalloc?s_trymalloc_usable(hdrleninitlen1, usable) :s_malloc_usable(hdrleninitlen1, usable);if (sh NULL) return NULL;if (initSDS_NOINIT)init NULL;else if (!init)memset(sh, 0, hdrleninitlen1);// s 此时指向bufs (char*)shhdrlen;// 指向flagsfp ((unsigned char*)s)-1;usable usable-hdrlen-1;// 对不同类型的 SDS 可分配空间进行截断if (usable sdsTypeMaxSize(type))usable sdsTypeMaxSize(type);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 usable;*fp type;break;}// ... 省略}if (initlen init)memcpy(s, init, initlen);// 末尾添加\0s[initlen] \0;return s;
}通过sdsnewlen方法我们可以获得以下信息
SDS_TYPE_5 会被强制转换为 SDS_TYPE_8 类型创建时默认会在末尾加\0返回值是指向 SDS 结构中 buf 的指针返回值是char *sds类型可以兼容部分C函数。
释放sds
为了优化性能SDS 提供了不直接释放内存而是通过重置len达到清空 SDS 目的的方法——sdsclear。改方法仅仅将 SDS 的len归零而buf的空间并为真正被清空新的数据可以复写而不用重新申请内存。
void sdsclear(sds s) {sdssetlen(s, 0);// 设置len为0s[0] \0;//“清空”buf
}若真正想清空 SDS 则可以调用sdsfree方法底层通过调用s_free释放内存。
void sdsfree(sds s) {if (s NULL) return;s_free((char*)s-sdsHdrSize(s[-1]));
}
