《Redis设计与实现》阅读:Redis底层研究之简单动态字符串SDS-阿里云开发者社区

开发者社区> 数据库> 正文
登录阅读全文

《Redis设计与实现》阅读:Redis底层研究之简单动态字符串SDS

简介:         除仅用于字符串字面量的情况外,对于可以被修改值的字符串的表示,Redis底层并没有采用C语言传统的字符串表示,即以空字符结尾的字符数组,而是采用专门为其设计的简单动态字符串作为其默认字符串表示,其英文全称为Simple Dynamic String,简称SDS。

        除仅用于字符串字面量的情况外,对于可以被修改值的字符串的表示,Redis底层并没有采用C语言传统的字符串表示,即以空字符结尾的字符数组,而是采用专门为其设计的简单动态字符串作为其默认字符串表示,其英文全称为Simple Dynamic String,简称SDS。除了用于保存数据库中字符串值外,SDS也可以用于缓冲区buffer,比如AOF中的缓冲区、客户端输入缓冲区等。本文,我们将详细研究简单动态字符串SDS的实现及其在性能等方面的独特之处。

   

        注:内容总结于《Redis设计与实现》一书!


        SDS实现

        SDS整体结构如下:

struct sdshdr {
       
     // buf数组中已使用字节数量,即SDS所保存的字符串长度
     int len;

     // bur数组中未使用字节数量
     int free;

     // 用于保存字符串的字节数组
     char buf[];
}
        可以看到,SDS依然依靠字节数组char buf[]来保存字符串,但是,它还保存了字节数组char buf[]中已使用和未使用字节数量len、free,而len的含义即SDS所保存的字符串长度,free的含义则是SDS剩余可以容纳字符串的长度。一个简单的示例如下:


        上图所示的SDS,存储了字符串"Redis",其长度为5,同时尚有4个字节的空间未被利用。而且,你会发现,其实buf数组的大小实际为10,在字符串末尾还有一个表示空字符的'\0',为什么会这样呢?这就是SDS设计的巧妙之处,它为了能够直接重用C字符串函数库里的一些字符串常用函数,而这个空字符是SDS自动添加的,且不计算在len和free内,对用户而言是透明的。


        SDS较C字符串的优点

        SDS为什么要做以上设计呢,它对于C字符串而言,有哪些优点?

        其相比较于C字符串的优点总结如下:

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

              C字符串并不会记录字符串的长度,必须遍历整个字符串,对遇到的每个非空字符计数,直到遇到代表字符串结尾的空字符,才能计算出字符串长度,其时间复杂度为O(N),而SDS则直接获取len属性值即可获知字符串长度,其时间复杂度为O(1),而len属性是SDS相关函数自动完成的,对于用户而言是透明的。这个优点对任何一个,即使非常长的字符串反复执行STRLEN命令,也不会对系统性能产生影响,确保了获取字符串长度不会成为Redis的性能瓶颈。

        2、杜绝缓冲区溢出

              当修改或替换C字符串中的值时,C字符串由于不会记录本身长度,也不会预分配空间,会产生缓冲区溢出,甚至偷偷修改其他字符串内容的情况,如下图所示:


              如果我们想在S1现有字符串基础上追加一个Cluster,而又不对S1进行内存重分配,那么这个操作会造成缓冲区溢出,同时会偷偷修改掉S2字符串的值。而SDS的空间分配策略则会避免缓冲区溢出的情况发生,它会先检查len和free,确保要追加、修改、替换的长度能够得到满足,如不满足,则会自动进行空间再分配,从而避免缓冲区溢出。

        3、减少字符串修改内存重分配次数

              显然,Redis是使用场景决定了存储于其内的字符串会频繁的被修改,而如果是在C字符串情况下,就会发生以下两种情况:

              3.1、对于增长性字符串修改操作,程序每次都需要通过内存重分配来满足字符串空间要求,如果忘了,则会产生2中所说的缓冲区溢出;

              3.2、对于缩短性字符串修改操作,程序需要通过内存重分配来释放不再使用的空间,如果忘了,则会产生内存泄露的问题。

             而内存重分配算法比较复杂,且涉及到系统调用,通常是一种比较耗时的操作,而SDS则依靠空间预分配和惰性空间释放两种策略解决了上述两个问题,减少了频繁的空间重分配等,提供了系统性能。总结如下:

             (1)空间预分配

                      如果SDS修改后,其长度小于1M,也就是len小于1M,则程序会分配与len属性同样大小的未使用空间,即len=free,buf实际大小则还要加1,因为有上述兼容C字符串库函数所使用的空字符;如果SDS修改后其长度大于等于1M,则程序每次会分配1M的未使用空间,此时free等于1M,buf实际大小也是还要加,原因同上。

             (2)惰性空间释放

                      如果SDS字符串被缩短,未使用字节数增大,则SDS并不会使用内存重分配立即回收缩短后的未使用空间,而是记录在free属性中,等待将来使用,这样,惰性空间释放策略避免了SDS缩短字符串时所必须的内存重分配回收空间操作,为将来可能的增长操作使用,提高了Redis字符串处理的性能。同时,对于真正需要释放空间的情况,SDS则提供了专门的API,供用户使用,避免空间的持续浪费。

         4、二进制安全

               C字符串以空字符作为字符串结尾的特点,决定了其只能保存文本数据,而不能存储图片、视频、音频等二进制数据,而SDS通过len属性则避免了这一情况,使其可以存储诸如上述图片、视频、音频等任意格式的二进制数据。

        5、兼容部分C字符串函数

             buf中末尾自动追加的空字符实现了SDS可以兼容部分C字符串函数,比如对比strcasecmp、追加strcat等函数。


        SDS与C字符串对比如下:


        SDS简单总结如下:




版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
数据库
使用钉钉扫一扫加入圈子
+ 订阅

分享数据库前沿,解构实战干货,推动数据库技术变革

其他文章