详解redis数据结构之sds
详解redis数据结构之sds
字符串在redis中使用非常广泛,在redis中,所有的数据都保存在字典(Map)中,而字典的键就是字符串类型,并且对于很大一部分字典值数据也是又字符串组成的。以下是sds的具体存储结构:
从图中可以看出,sds的属性有三个:len、free和buf数组。这里len字段是用来保存sds字符串中所包含字符数目的,free字段则是用来保存buf数组中空余的部分的长度的,而buf数组则是实际用来保存字符串的。比如如下结构保存了“Hello World!”这个字符串:
这里需要注意的是,sds和c字符串一样,需要在字符串结尾加上一个“\0”表示该字符串的结束。这里这个sds对象的len属性保存了“Hello World!”这个字符串的长度,而free属性保存了数组中空余的位数,buf数组则实际保存了这个字符串,空字符和空余位。
redis使用sds结构而不用c字符串保存字符串的原因有如下几点:
①常数复杂度获取字符串长度
通过读取sds对象的len属性的值我们可以使用O(1)获取sds对象保存的字符串长度,而在c字符串中,我们必须对整个数组进行遍历从而获取字符串的长度,其时间复杂度为O(N)。
②杜绝缓冲区溢出
在c字符串中,比如char *strcat(char *dest, const char *src)函数将src连接到dest的末尾,但是c字符串假定dest数组中有足够的空余空间来保存src数组,如果dest数组长度不够就会造成缓冲区溢出;在sds对象中也提供了类似的函数sds sdscat(sds s, const char *t)和sds sdscatsds(sds s, const sds t),这两个函数在调用之前会检查目标sds对象s中free属性是否能够保存要连接的字符串的长度,如果不够,就会对目标sds对象扩容,这就保证了sds对象不会造成缓冲区溢出。
③减少修改字符串时内存重分配的次数
在对sds进行修改的时候,redis可以通过“空间预分配”和“惰性空间释放”来保证后续对sds对象的频繁修改而不会造成sds对象的buf数组经常分配空间;而对于c字符串,每次对其进行修改都需要进行一次空间分配和复制操作。
④二进制安全
对于c字符串,由于其判断是否结束的标志是从字符串开始到结尾碰到的第一个“\0”字符,这就限制了c字符串不能保存像图片、音频、视频、压缩文件等二进制保存的内容;而对于sds对象,由于判断其是否结束的标志是其len属性,也就是说无论在len长度内,buf数组中是否包含“\0”都不影响redis判断其是否结束。
上面讲到了sds的空间预分配和惰性空间释放,sds通过这两种操作极大的简化了其对字符串的修改和对空间的分配工作。
空间预分配指的是当对一个sds对象进行结构性增加时,比如修改其内容使其增长或者连接另一个字符串到其末尾,sds会预先分配一定的空间以预防未来可能对其进行的修改。如下是redis进行空间预分配的主要代码:
sds sdsMakeRoomFor(sds s, size_t addlen) { struct sdshdr *sh, *newsh; // 获取 s 目前的空余空间长度 size_t free = sdsavail(s); size_t len, newlen; // s 目前的空余空间已经足够,无须再进行扩展,直接返回 if (free = addlen) return s; // 获取 s 目前已占用空间的长度 len = sdslen(s); sh = (void*) (s-(sizeof(struct sdshdr))); // s 最少需要的长度 newlen = (len+addlen); // 根据新长度,为 s 分配新空间所需的大小 if (newlen SDS_MAX_PREALLOC) // 如果新长度小于 SDS_MAX_PREALLOC // 那么为它分配两倍于所需长度的空间 newlen *= 2; else // 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC newlen += SDS_MAX_PREALLOC; // T = O(N) newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1); // 内存不足,分配失败,返回 if (newsh == NULL) return NULL; // 更新 sds 的空余长度 newsh- free = newlen - len; // 返回 sds return newsh-
从图中可以看出,当要添加的内容比目标sds对象的free属性要短时直接返回并将要添加的内容添加到目标sds对象的buf数组中即可;当要添加的内容比目标sds对象的free属性要长时,就会计算要添加的内容和sds对象的当前长度的和newlen,如果newlen小于SDS_MAX_PREALLOC也即1M的时候,新创建的buf数组的长度为newlen的两倍,如果newlen大于SDS_MAX_PREALLOC的时候,新创建的buf数组的长度为newlen+SDS_MAX_PREALLOC,即只多分配1M的预留空间。空间预分配保证了sds对象的空余位长度至多为扩张之后字符串长度的1倍,这也就保证了后续对sds对象的修改将尽可能少的分配空间。
惰性空间释放指的是当对一个sds对象进行缩短操作时,其不会直接将buf数组缩短为目标数组的长度,而是只改变sds对象的len属性的值,数组中多余的部分则保存在free属性中,这样就可以保证后续可能的对该sds对象的增长操作不需要重新分配空间。
最后需要进行说明的是,sds对象也和c一样使用“\0”作为字符串的结尾的原因是redis也是使用c语言编写的,使用“\0”结尾就可以直接使用部分c函数库中对字符串操作的函数。
通过上面对sds对象的说明可以发现,redis对sds对象的处理极大的减少了字符串处理中可能出现的复杂操作,并且大部分操作基本上都可以在极短的时间内完成,这就保证了redis对字符串处理的高速率。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
我想要获取技术服务或软件
服务范围:MySQL、ORACLE、SQLSERVER、MongoDB、PostgreSQL 、程序问题
服务方式:远程服务、电话支持、现场服务,沟通指定方式服务
技术标签:数据恢复、安装配置、数据迁移、集群容灾、异常处理、其它问题
本站部分文章参考或来源于网络,如有侵权请联系站长。
数据库远程运维 详解redis数据结构之sds
相关文章
- Redis底层数据结构之dict、ziplist、quicklist详解
- Go-连接Redis-学习go-redis包详解编程语言
- 连接阿里云Redis: 一步一步操作指南(阿里云redis怎么连接)
- 如何使用Redis查看所有集合数据(redis查看所有集合)
- 深入了解:Redis数据库的数据结构(redis数据库结构)
- set数据结构 探索Redis中Sort Set的魅力(redis中sort)
- 探究Redis揭秘这种被广泛使用的数据结构(怎么看redis内容)
- 张冬洪极速开启 Redis 之旅(张冬洪 redis)
- 实例开启多个Redis实例之道实现丰富的缓存功能(开启多个redis)
- 比较直接内存与Redis的优势和劣势(直接内存还是redis)
- 测试Redis性能探索极速体验(测试redis的性能)
- Vue框架下的Redis调用实战(vue调用redis)
- 学习Redis前备知识网络编程和数据结构(学redis之前要学什么)
- 提升效率多线程读取Redis队列(多线程读取redis队列)
- 深入理解Redis数据结构之旅(什么是redis数据结构)
- 高效安全基于Redis的交易系统实现(基于redis的交易系统)
- 图解Redis数据结构实现原理(图解redis数据结构)
- 使用Redis实现高并发计数器(redis高并发 计数器)
- 脚本Redis集群构建使用Lua脚本实现优化(redis集群执行lua)
- 崩溃恢复Redis集群从节点崩溃到恢复(redis 集群 从节点)
- Redis队列轮询启动危机宕机漩涡(redis队列轮询崩溃)
- Redis连接池配置深度剖析(redis连接池配置详解)
- Redis连接池技术实现解析(redis连接池详解)
- 使用Redis实现域名连接及其利弊(redis连接域名)
- Redis架构实现高效可靠的独立连接(redis连接互不影响)
- Redis缓存实现过期策略的指南(redis过期教程)
- Redis评论灵活的数据结构(redis评论什么结构)
- 自动化管理Redis实现自动序列号(redis自动序列号)
- Redis革新性的设计精髓(redis设计详解)