暂无图片
暂无图片
1
暂无图片
暂无图片
暂无图片

面试:你知道Redis的字符串是怎么实现的吗?

IT大咖说 2020-03-07
523

之前本人在找工作面试时在Redis相关问题上可栽了跟头。在面试前按常规套路准备了一下,比如 Redis 的常用5种数据结构,Redis持久化策略,Redis实现分布式锁,简单发布订阅等等都准备了,当时不知天高地厚以为十拿九稳了,可是万万没想到我终究还是在Redis的被问的第一个问题上翻船了~~

面试官 :看你简历上写了熟悉常用数据结构,都有哪些说说
本人 :常用有5种,string,list,set,zset,hash(内心很得意)

面试官 :那你说说都用过哪些数据结构
本人 :用的最多的是string,通常会把json字符串存进去

面试官 :那你知道Redis内部是怎么实现它的string的么?
本人 :呃~,我了解Redis是用C语言写的,至于具体实现就不清楚了~

到此一面卒~~~

有相同经历的朋友么?


回去后恶补了一下Redis有关原理性的知识点,恰好最近在最总结面试经历于是有了今天这篇文章。

本篇会讲以下内容:

  • Redis字符串的实现

  • Redis字符串的性能优势

Redis字符串的实现

Redis虽然是用C语言写的,但却没有直接用C语言的字符串,而是自己实现了一套字符串。目的就是为了提升速度,提升性能,可以看出Redis为了高性能也是煞费苦心。

Redis构建了一个叫做简单动态字符串(Simple Dynamic String),简称SDS

1.SDS 代码结构

struct sdshdr{
记录已使用长度
int len;
// 记录空闲未使用的长度
int free;
// 字符数组
char[] buf;
};

SDS ?什么鬼?可能对此陌生的朋友对这个名称有疑惑。只是个名词而已不必在意,我们要重点欣赏借鉴Redis的设计思路。下面画个图来说明,一目了然。

Redis的字符串也会遵守C语言的字符串的实现规则,即最后一个字符为空字符。然而这个空字符不会被计算在len里头。

2.SDS 动态扩展特点

SDS的最厉害最奇妙之处在于它的Dynamic。动态变化长度。举个例子

如上图所示刚开始s1 只有5个空闲位子,后面需要追加' world' 6个字符,很明显是不够的。那咋办?Redis会做以下三个操作:

  1. 计算出大小是否足够

  2. 开辟空间至满足所需大小

  3. 开辟与已使用大小len相同长度的空闲free空间(如果len < 1M)开辟1M长度的空闲free空间(如果len >= 1M)

看到这儿为止有没有朋友觉得这个实现跟Java的列表List实现有点类似呢?看完后面的会觉得更像了。

Redis字符串的性能优势

  • 快速获取字符串长度

  • 避免缓冲区溢出

  • 降低空间分配次数提升内存使用效率

1.快速获取字符串长度

再看下上面的SDS结构体:

struct sdshdr{
// 记录已使用长度
int len;
// 记录空闲未使用的长度
int free;
// 字符数组
char[] buf;
};

由于在SDS里存了已使用字符长度len,所以当想获取字符串长度时直接返回len即可,时间复杂度为O(1)。如果使用C语言的字符串的话它的字符串长度获取函数时间复杂度为O(n),n为字符个数,因为他是从头到尾(到空字符'\0')遍历相加。

2.避免缓冲区溢出

对一个C语言字符串进行strcat追加字符串的时候需要提前开辟需要的空间,如果不开辟空间的话可能会造成缓冲区溢出,而影响程序其他代码。如下图,有一个字符串s1="hello" 和 字符串s2="baby",现在要执行strcat(s1,"world"),并且执行前未给s1开辟空间,所以造成了缓冲区溢出。

而对于Redis而言由于每次追加字符串时都会检查空间是否够用,所以不会存在缓冲区溢出问题。每次追加操作前都会做如下操作:

  1. 计算出大小是否足够

  2. 开辟空间至满足所需大小

3.降低空间分配次数提升内存使用效率

字符串的追加操作会涉及到内存分配问题,然而内存分配问题会牵扯内存划分算法以及系统调用所以如果频繁发生的话影响性能,所以对于性能至上的Redis来说这是万万不能忍受的。所以采取了以下两种优化措施

  • 空间与分配

  • 惰性空间回收

1. 空间预分配

对于追加操作来说,Redis不仅会开辟空间至够用而且还会预分配未使用的空间(free)来用于下一次操作。至于未使用的空间(free)的大小则由修改后的字符串长度决定。

当修改后的字符串长度len < 1M,则会分配与len相同长度的未使用的空间(free)

当修改后的字符串长度len >= 1M,则会分配1M长度的未使用的空间(free)

有了这个预分配策略之后会减少内存分配次数,因为分配之前会检查已有的free空间是否够,如果够则不开辟了~

2. 惰性空间回收

与上面情况相反,惰性空间回收适用于字符串缩减操作。比如有个字符串s1="hello world",对s1进行sdstrim(s1," world")操作,执行完该操作之后Redis不会立即回收减少的部分,而是会分配给下一个需要内存的程序。当然,Redis也提供了回收内存的api,可以自己手动调用来回收缩减部分的内存。

到此为止结束了~

下次在遇到这个问题可以侃侃而谈了,哈哈哈

来源:juejin.im/post/5ca9d8ae6fb9a05e5c05c4e8



来都来了,走啥走,留个言呗~




 IT大咖说  |  关于版权 

由“IT大咖说(ID:itdakashuo)”原创的文章,转载时请注明作者、出处及微信公众号。投稿、约稿、转载请加微信:ITDKS10(备注:投稿),茉莉小姐姐会及时与您联系!

感谢您对IT大咖说的热心支持!



相关推荐


推荐文章

  • HTTP客户端连接,选择HttpClient还是OkHttp?

  • 如何通过nginx反向代理来调试代码?

  • 手把手带你编写一个可复用的SpringBoot应用运维脚本

最近活动

  • MAD |亚马逊、VMware、新大陆大咖与你共话新物联

  • 腾讯大数据星火计划--Angel技术沙龙 对外报名正式启动!

  • 阿里云在线直播课程



点击【阅读原文】更多IT技术


redis
文章转载自 IT大咖说,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

评论

天下网标王丹东品牌网站设计哪家好芜湖网站搭建价格济南建设网站哪家好大浪百度关键词包年推广推荐龙岩网页制作报价衡水网站建设公司吉祥英文网站建设哪家好塘坑百度网站优化排名报价德宏seo排名甘孜企业网站改版推荐济南网站建设设计哪家好韶关百度标王推荐仙桃网站改版价格宜春营销网站哪家好永湖关键词排名价格巢湖设计网站多少钱乌海营销网站报价开封百度网站优化价格沧州网站优化按天收费定西企业网站制作公司深圳SEO按效果付费价格爱联建设网站报价湖州seo优化公司济南百度竞价推荐黄山品牌网站设计多少钱襄阳网站优化推广百色百度竞价哪家好盐田seo思茅网站seo优化报价成都关键词按天收费多少钱香港通过《维护国家安全条例》两大学生合买彩票中奖一人不认账让美丽中国“从细节出发”19岁小伙救下5人后溺亡 多方发声卫健委通报少年有偿捐血浆16次猝死汪小菲曝离婚始末何赛飞追着代拍打雅江山火三名扑火人员牺牲系谣言男子被猫抓伤后确诊“猫抓病”周杰伦一审败诉网易中国拥有亿元资产的家庭达13.3万户315晚会后胖东来又人满为患了高校汽车撞人致3死16伤 司机系学生张家界的山上“长”满了韩国人?张立群任西安交通大学校长手机成瘾是影响睡眠质量重要因素网友洛杉矶偶遇贾玲“重生之我在北大当嫡校长”单亲妈妈陷入热恋 14岁儿子报警倪萍分享减重40斤方法杨倩无缘巴黎奥运考生莫言也上北大硕士复试名单了许家印被限制高消费奥巴马现身唐宁街 黑色着装引猜测专访95后高颜值猪保姆男孩8年未见母亲被告知被遗忘七年后宇文玥被薅头发捞上岸郑州一火锅店爆改成麻辣烫店西双版纳热带植物园回应蜉蝣大爆发沉迷短剧的人就像掉进了杀猪盘当地回应沈阳致3死车祸车主疑毒驾开除党籍5年后 原水城县长再被查凯特王妃现身!外出购物视频曝光初中生遭15人围殴自卫刺伤3人判无罪事业单位女子向同事水杯投不明物质男子被流浪猫绊倒 投喂者赔24万外国人感慨凌晨的中国很安全路边卖淀粉肠阿姨主动出示声明书胖东来员工每周单休无小长假王树国卸任西安交大校长 师生送别小米汽车超级工厂正式揭幕黑马情侣提车了妈妈回应孩子在校撞护栏坠楼校方回应护栏损坏小学生课间坠楼房客欠租失踪 房东直发愁专家建议不必谈骨泥色变老人退休金被冒领16年 金额超20万西藏招商引资投资者子女可当地高考特朗普无法缴纳4.54亿美元罚金浙江一高校内汽车冲撞行人 多人受伤

天下网标王 XML地图 TXT地图 虚拟主机 SEO 网站制作 网站优化