Redis简单动态字符串(simple dynamic string,SDS)剖析!

Redis没有直接使用C语言传统的字符串表示,而是自己构建了一种名为简单动态字符串(simple dynamic string, SDS)的抽象类型,并将SDS用作Redis的默认字符串表示。

SDS的定义

每个sds.h/sdshdr结构表示一个SDS值:

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
Struct sdshdr{
    //记录buf数组中已使用字节的数  //等于SDS所保存字符串的长度  int len;  //记录buf数组中未使用字节的数量  int free;  //字节数组,用于保存字符串  char buf[];}

free属性的值为0,表示这个SDS没有分配任何未使用空间。

len属性的值为5,表示这个SDS保存了一个五字节长的字符串。

buf属性是一个char类型的数组,数组的前五个字节分别保存了‘R’、‘e’、‘d’、‘i’、‘s’五个字符,而最后一个字节则保存了空字符‘\0’。

 

SDS遵循C字符串以空字符结尾的惯例,保存空字符的1字节空间不计算在SDS的len属性里面,并且为空字符分配额外的1字节空间,以及添加字符到字符串末尾等操作,都是由SDS函数自动完成的,所以这个空字符对于SDS的使用者来说是完全透明的。

 

遵循空字符结尾这一惯例的好处是,SDS可以直接重用一部分C字符串函数库里面的函数。

SDS与C语言字符串的区别

常数复杂度获取字符串长度

因为C语言字符串并不记录自身的长度信息,所有获取一个C字符串的长度,程序需要遍历整个字符串,对遇到的每个字符串进行计数,直到遇到代表字符串结尾的空字符为止,这个操作的复杂度为O(N)。

 

而SDS在len属性中记录了SDS本身的长度,所以获取一个SDS长度的复杂度仅为O(1)。

 

通过使用SDS而不是C语言字符串,Redis将获取字符串长度所需的复杂度从O(N)降低到了O(1),这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。

 

杜绝缓冲区溢出

除了获取字符串长度的复杂度高之外,C语言字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出(buffer overflow)。

 

与C语言字符串不同,SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性:当SDS API需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用SDS既不需要手动修改SDS的空间大小,也不会出现前面所说的缓冲溢出问题。

 

减少修改字符串时带来的内存重分配次数

C语言字符串的长度和底层数组的长度之间存在着关联性,所以每次增长或者缩短一个C语言字符串时,程序要总要对保存这个C语言字符串的数组进行一次内存重分配操作。

  • 如果程序执行的是增长字符串的操作,那么在执行这个操作之前,程序需要先通过内存重分配来扩展底层数组空间的大小,如果忘记这一步操作就会产生缓冲区溢出。

  • 如果程序执行的是缩短字符串的操作,那么在执行这个操作之后,程序需要通过内存重新分配来释放字符串不再使用的那部分空间,如果忘记这一步就会产生内存泄漏。

为了避免C语言字符串这种缺陷,SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联:在SDS中,buf数组的长度不一定就是字符串数量加1,数组里面可以包含未使用的字节,而这些字节的数量就由SDS的free属性记录。

 

通过未使用空间,SDS实现了空间预分配和惰性空间释放两种优化策略。

 

空间预分配

空间预分配用于优化SDS的字符串增长操作:当SDS的API对一个SDS进行修改,并且需要对SDS进行空间扩展的时候,程序不仅会为SDS分配修改所必需的空间,还会为SDS分配额外的未使用空间。

 

其中额外分配的未使用空间数据由以下公式决定:

  • 如果对SDS进行修改之后,SDS的长度(也就是len属性的值)将小于1M,那么程序分配和len属性同样大小的未使用空间,这时SDS len值将和free属性值相同。

  • 如果对SDS进行修改之后,SDS的长度将大于等于1M,那么程序会分配1M的未使用空间。

通过空间预分配策略,Redis可以减少连续执行字符串增加操作所需的内存重分配次数。

 

在扩展SDS空间之前,SDS API会先检查未使用空间是否足够,如果足够的话,API就会直接使用未使用空间,而无须执行内存重分配。

 

通过这种预分配策略,SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。

 

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作:当SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字符的数量记录起来,并等待将来使用。

 

通过惰性空间释放策略,SDS避免来缩短字符串时所需的内存重分配操作,并为将来可能有的增长操作提供了变化。

 

二进制安全

C语言字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符,否则最先被程序读入空字符将被误认为是字符串结尾,这些限制使得C字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

 

为了确保Redis可以适用于各种不同的使用场景,SDS的API都是二进制安全的,所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据,程序不会对其中数组做任何限制、过滤、或者假设,数据在写入时是什么样的,它被读取时就是什么样。

 

兼容部分C字符串函数

通过遵从C语言字符串以空字符结尾的惯例,SDS可以在有需要时重用<string.h>函数库,从而避免来不必要的代码重复。

 

总结

比起C语言字符串,SDS具有以下优点:

  • 常数复杂度获取字符串长度

  • 杜绝缓冲区溢出

  • 减少修改字符串时带来的内存冲分配次数

  • 二进制安全

  • 兼容部分C字符串函数

全部评论

相关推荐

04-26 14:36
已编辑
郑州信息科技职业学院 Java
由于高考成绩不是很理想,听取了张雪峰老师的建议,优先选了专业并且当时的想法就是选一个能赚钱的专业,于是最终选择了报了一个能收留我的有计算机专业的学校。当时听张雪峰老师说河南的学习氛围很好,所以就想去体验一下,事实雀食如张雪峰老师所说,大家都一股脑的铺在学习这条路上。可能是因为那边氛围导致的吧,我一开始想的也是卷学习卷绩点,所以大一的时候就一直在学习硬试教育的一些东西,学期结束了,排名出来的时候中上水平吧,据我了解保研的只有前5名可能会有机会,当时的心里就想着,我这成绩再卷也卷不到哪去了,并且保研也无望了,总结的说,一些事情只有真正做了才知道是不是自己所追求的。说了很多废话吧,剩下的关于学校的就长话短说了吧。大二很多专业课基本上要从早八上到晚上,但基本上我都是不去,不如自学现在新媒体技术这么发达,并且还可以学一下自己需要的技术栈,由于学校的课程原因对其他的技术栈不是很了解,所以,一心就投入在Java这个方向了,但是,Python也会学一下,这是因为加入实验室,实验室老师是做人工智能方向的缘故。现在回想,我大二当时还是学的太慢了,还有就是信息差太大了,出来工作之后才发现有些佬们已经大二就出来实习,并且八股就背的滚瓜烂熟了。只能说这里的学习氛围很好吧,走廊里都是背书刷题的声音,跟身边的同学和实验室的同学谈是否直接就业的事,他们要么都是说考研,要么对直接就业很含糊,可能是因为觉得自己学的还不够吧,我想说,学的不够就干中学呗,反正,我先迈出去这步再说。到了大三上还是没有找工作的打算,因为身边的人也都还没有这个意识吧,现在跟了身边的同事聊天才知道,我的信息差太大了。到了大三下刚开始,我才开始正式的踏上求职路,当时的信息差还是很大的,根本就不敢碰瓷大厂,想着有一个公司能要再说吧,并且地域也限制的很死,只想着在本地找一下,因为怕学校找事(我想这是学校一贯操作了),在本地吧,他们大多数都是接受的线下面,一开始面了一个,可能自己比较摆也很悲观,就显得我很差吧,hr面完就没后续了,最终终于有一个面,并且也展示出自己的自信和对专业的理解了,最后,我也没想着这么多背调公司呀,当个备选什么的就直接去了。也算是我的第一家正式的公司吧(之前都是线上的码农兼职),干多了就发现,这个公司压根学不到东西,并且薪资低的,因为我是第一个进来的计算机实习生,有一个同事干了两三年的吧,带着我做的时候是真能学到东西,但是,最后那个同事离职了,我就只能和学艺术的老板直接汇报项目进度,一个学艺术的来指导我这个科班出身的就很离谱的好吧。最后,我也离职了,也跟前同事聊了很久,她说我是她见过大三就能学到这程度,已经超过很多人了,并且她当时在的时候还说我是内定能转正的。并且还说我真的可以去考研。我也仔细思考了一下,我决定让自己沉淀一下再出发吧,先备考了软件设计师,然后期末考,大三暑期的时候就充实自己的简历,并且也认识了一个某东的老哥,也用了内推码,教我了怎么写好简历量化成果之类的,总之,很感谢一路走来帮助我的人吧,并且我在边充实自己的同时也在边投递简历,但当时卡的也很死,要选base地在河南附近的,不像现在全国可飞。面了很多base地在学校附近的,然后,还有一个北京的py和杭州的java,最终就这两个地方给了offer,但是都是实习转正的,不是秋招offer,因为觉得Java的太卷了,然后,面试的时候也会感觉压力很大,所以就把杭州的那个拒了,去了北京的,北京是免费住的房子(三个月这是伏笔),当时觉得环境很好,但是合租室友的作息跟自己的作息不一样就很不习惯,于是,我就想着要是三个月后我一定要找一个单间的哪怕破一点。北京这个公司吧就很像国企的感觉,早九晚五,当月发当月工资,并且干的活接触的数据量都不是很大,就是干了很多杂活,并且mentor和部门的领导都不是技术出身,所以,我能学到的东西少之又少,但是吧,学习是自己的事,而且这部门不是很忙对于实习生来说,我完全可以学自己的东西(前提是不被发现)。到最后这个部门的氛围就很微妙,我遇到不会的问他们我应该怎么做的时候,他们说让我自己想,我当时就想说,神人一个,啥都不说让我自己干,干出来又不满意,你说你让我干py的东西你不会我就不说啥了,让我干无关代码的东西,让我调研项目应该做些什么内容,现在回想都是泪呀,我就这样被欺压的过完了三个月,最后免费住的地方也到期了,伏笔来了,最后,找我谈话说你技术可以了能看出来,因为你也自己独立完成了消息通知那一块内容嘛,但是,由于我们部门干的活比较杂并且我也缺少一些电力相关的一些知识,所以,觉得不合适。(OS:其实我对每一份工作都是真心换真心的,并且这些电力知识我也知道我有一点欠缺所以我也有自己再学习,你们啥也不教我,最后把屎盆子把我头上扣)最后,回到了学校,心态也发生了变化,想着做啥都不如找一个稳定的工作重要,想着回家沉淀吧,少年终有出头日。但是,计划赶不上变化,之前那个同事,内推了我去她现在的公司,并且是做AI应用的也是我想接触的,并且还是与我上家的业务场景类似的,真的感谢那个同事,俗话说:千里马常有而伯乐不常有。并且那里的部门领导也很好,并且说我虽然不是电力相关出身的,但是能做的这样已经很不错了,所以DDDD,由于各种不可抗力因素吧,还是想找一个离家近,然后不是很像小作坊的感觉(这个公司虽然比较小,但是比之前那个大的公司的氛围和待遇一点都不差的好吧甚至更好)。最终,在学校也呆了一个月吧,也陆陆续续面了一个月有一个C厂的面答的都挺好直接就谈薪了,但是风评不好还是保命要紧,还有各种的中小厂面吧,但感觉都不是自己想要的,只是想刷刷面试经验吧(这是某东哥告诉我的,与其一直改简历不如去多面)。最后,在校期间面了一个比较合适的某鸦智能,一直推进到了HR面,但是最后被横向了,开始复盘,被横向了属实是没招了,经历了这么多大风大浪什么场面没见过。过年期间,求职路线关闭,把自己缺少的技术栈和简历中的项目业务理清楚说明白。年过完就要开始加入找工作大军中了,把节前没面完的先面了,节后一开始就是某鸟的HRG面,聊的就很憋屈的感觉,问我技术方面的,说我说的很像AI的(我心想跟你说具体的细节你又说我不想听技术的,说的比较宽泛浅显说我AI)。最后,反正体验感不是很好的结束了吧。说一个星期等通知,等了两个星期才说是通过的(我认为是排名靠前的那些人没去,顺位到我了)。那你既然这样说了,那我就接受吧。还没入职就问我要身份证信息要这要那的,最后都给过去了,说HC调整,要重新review,又又又一次被恶心到了。后面就是陆续的沉淀面试等,我当时的重心已经完全的想着私企没人要,就去试试考公和考央国企了,毕竟我的履历不看学历的话放到电网当中还是可以的。私企的话有一个外企洋里洋气的说话,问我怎么口语这么好?我说这叫智取,宝贝。虽然这个tek外企过了,但是还有一个openday要去线下,来回的衣食住行不是很方便也不是很想去所以就拒绝了没去。后来就收到了,国网网申通过的通知,说实话,我之前问了很多我们学校历年有没有考央国企之类的案例,很显然都不知道,也可以说少之又少吧,于是我就奔赴京城进京赶考,唉,时间不太合适就想着算了吧,再等等,好事多磨,宁缺毋滥吧。金三银四终于等来了面试的机会,这个岗位我只能说我不是很熟悉,但是语言这东西吧都是相通的,重要的是我要把其中的内核搞懂,梳理清楚业务逻辑。最终,来到了这家公司,目前来说是我遇到过最好的了,能有hc且不是要通过实习评估的那种,并且合同期限是三年的,并且是12%的公积金。我认为这就是我所遇到的最好的了。希望能真心换真心吧,不再把我当创口贴/路边一条了,并且也遇到了很多优秀的同事。总的来说,就是要是能重来我要选李白。我肯定会打破这些信息差,后悔知道的太晚,并且跟优秀的人聊天说话真的可以学到很多东西,之前上文提到的贵人就不说了,说说最近的,他是跟我一届,学校后缀甚至不如我的后缀,但是真正了解的才会知道真是佬👍,他跟我找工作的时间线差不多,但是他在中大厂甚至大厂都呆过,因为跟他聊了才知道我当时的信息差有多大,并且毅力也是我甚至…都没有的。并且也听说了他们学校找工作的氛围很好,不像我阿巴阿巴阿巴,只有考研等相关的一些。并且说的一些观点都是很认同的。总之,希望能在这好好的吧,我真的不想经历大起大落了。经历了,打招呼挂,简历挂,一面挂,HR面挂,offer挂的,现在的心态已经放宽了很多了,但是难过还是有的,希望这家公司诚不欺我吧。也祝大家遇到自己的梦中情厂
选择和努力,哪个更重要?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务