今天来聊个关于redis的话题,redis的数据结构,我之前的一篇文章,专门写过Redis的数据类型,及其简单的应用场景。今天这篇文章来专门聊一下Redis的数据结构,它的底层是如何存储的。
Redis的string类型
String概述
Coding的哔哔叨叨
String结构可以存储字符串或者各种类型的二进制数据。
能表达3种类型:字符串、整数和浮点数。根据场景相互间自动转型,并且根据需要选取底层的承载方式。
value内部以int、sds(简单动态字符串sample dynamic string)作为结构存储,sds是可以动态修改的字符串,类似于java中的ArrayList,采取预分配冗余空间的方式来减少内存的频繁分配。int存放整型数据,sds存放字节/字符串和浮点型数据
Redis 底层是用C语言编写的,可是在字符存储上,并未使用C原生的String类型,而是定义了自己的字符串结构 Simple Dynamic Stirng,简称SDS。
SDS内部结构
Coding的哔哔叨叨
struct sdshdr {int len; // 记录buf数组中已使用字节的数量,等于SDS所保存字符串的长度 int free; // 记录buf数组中未使用字节的数量 char buf[];// 字节数组,用于保存字符串 };
sds用buf数组存储字符串的内容,但数组的长度会大于所存储内容的长度。会有一格专门存放”\0”(C标准库)作为结尾,还有预留多几个空的(即free区域),当append字符串的长度小于free区域,则sds不会重新申请内存,直接使用free区域。
为符合c语言的规范会用"\0"来表示结尾,且字符串的长度len不包含结尾标识符"\n"。
SDS优势
Coding的哔哔叨叨
1、 O(1)时间复杂复杂度获取字符串长度。
sds内部维护这字符串长度的len变量,可以直接读取,时间复杂度为O(1)。对于传统c的字符串需要遍历整个字符串,知道遇到结尾标识符"\0",时间复杂度为O(N)。
2、缓冲区溢出规避
所谓缓冲区溢出即所需要的内存超出了实际的内存。因此对于C字符串来说,要特别注意内存分配,回收使用问题。比如,向一个现有字符串内添加特定字符时,需要保证当前已经分配了这足够的内存。
与C不同的是,redis自定义字符串,使用预分配内存空间来规避缓冲区溢出发生。
当需要对SDS进行操作时,首先会检查自己当前free空间够不够,不够的话会进行扩容,内存检查相对于C变成了内部预置操作。关于扩容我们下文会进行详述,大家接着往下看。
3、减少内存重分配次数
在C中,对字符串进行操作前都需要进行内存分配,同时,操作完成后需要进行内存回收,一次操作至少涉及一次内存分配操作。
大家应该都知道分配内存是一个复杂且精细的操作,耗时耗资源,针对此缺陷,Redis采用了空间预分配+惰性删除相结合来的策略。
空间预分配
空间预分配用于优化Redis字符扩展操作。所谓预分配,就是说在一次扩展操作中,分配的内存空间会大于实际需要的内存空间。
预分配空间的大小基于以下规则计算:
SDS len<1M:分配len长度空间作为预分配空间;SDS len>=1M:分配1M空间作为预分配空间;
这样在下次进行字符串操作的时候,如果需要的空间小于当前SDS free空间,就不在执行内存扩展重新分配操作。
SDS的空间预分配机制,使得一次扩展操作所需要的内存重分配次数变为<=1。
惰性删除
所谓惰性删除,即调整删除SDS部分数据时,不会立刻执行内存回收操作,而是会保留空出来的内存,并更新free属性值,以备将来字符扩展需要时,可以直接使用。
当然Redis也提供了主动释放未使用内存的方法。
4、二进制安全
C字符串由于特殊的编码要求只能保存文本数据。
SDS相关的功能方法会以二进制的形式来操作SDS存储的数据,没有任何中间操作,存储最原始的数据,因此不会有字符层面的因素影响。
SDS可以保存任何源的二进制数据,字符、图片、文件或者序列化的对象等等。
String的最大长度
Coding的哔哔叨叨
Redis中String是最常见的数据类型,包括redis的key使用的数据结构都是这个string类型(redis的不同类型的数据结构,仅体现在value的结构不一样),而redis中规定了string的最大长度为512M。
/** 检查容量大小的方法*/static int checkStringLength(client *c, long long size) {// 超出了512M,就直接报错 if (size > 512*1024*1024) {addReplyError(c,"string exceeds maximum allowed size (512MB)"); return C_ERR; } return C_OK;}
Redis的存储:ReidsObject
Coding的哔哔叨叨
redis对象内部存储形态。
type:数据类型、例如sting、hash、list、set、zset等,值类型查看命令【type】。
encoding:值存储内部实现的数据结构。
lru:最后一次被访问时间,辅助回收,可以通过object idletime {key} 在不更新lru属性情况下查看key的空闲时间。
refcount:当前对象被引用次数,辅助回收,可以通过 object refcount {key} 查看引用数,当对象为整数且值在范围在[0-9999]时,redis可以通过共享对象的方式来节省内存。目前共享对象池只对整数设置了0~9999个共享对象,一方面整数对象池复用率最大,同时等值判断上时间复杂度为O(1)。
*ptr:数据本身或者指向数据的指针,redis3.0之后,长度在39以内的字符串数据,内部编码为embstr,内存创建时,字符串和redisObject一起分配,减少一次内存分配。
value对象通常具有两个内存部分:redisObject部分和redisObject的*ptr指向的sds部分。创建value对象时,通常需要为redisObject和sds申请两次内存。但对于短小的字符串,可以把两者连续存放,所以可以一次性把两者的内存一起申请了。
Redis 的字符串共有两种存储方式,在长度特别短时,使用 emb 形式存储 (embedded),当长度超过44时,使用raw形式存储。
embstr存储形式是这样一种存储形式,它将RedisObject 对象头和 SDS 对象连续存在一起,使用 malloc 方法一次分配。而raw存储形式不一样,它需要两次 malloc,两个对象头在内存地址上一般是不连续的。在字符串比较小时,SDS 对象头的大小是capacity+3——SDS结构体的内存大小至少是 3。意味着分配一个字符串的最小空间占用为 19 字节 (16+3)。如果总体超出了 64 字节,Redis 认为它是一个大字符串,不再使用 emdstr 形式存储,而该用 raw 形式。而64-19-结尾的\0,所以empstr只能容纳44字节。
不积跬步,无以至千里。
文章有帮助的话,点个转发、在看呗。
谢谢支持哟 (*^__^*)
END
?