Simple Dynamic String

引言

为何redis中大量使用的是SDS,而不是传统的C语言字符串表示法存储字符串?到底什么是SDS?为什么要使用SDS?其相对于传统的C语言字符串有何优点?本文会针对以上几点做一个详细的分析,帮助大家以及自己更好的理解redis中的简单动态字符串

介绍SDS之前先简单介绍一下C语言中的传统字符串表示法

C语言字符串(C字符串)

始终以空字符结尾的字符数组,c语言为其封装了大量的函数库操作API

C字符串特点
  • 字符数组存储
  • 以空字符结尾,除了末尾之外,字符串里面不可以包含空字符
  • 由于采用字符数组,导致所存储的字符必须符合某种编码(如ASCII)
  • 获取C字符串长度必须遍历整个字符串,并对遇到的每个字符计数,直到遇到空字符为止,时间复杂度为O(N)

那么基于以上特点,C字符串是否能够满足我们Redis高效,安全的需求呢?显然是不能的,单是一个获取字符串长度就需要遍历整个字符串数组了,必须重新定义一种新的结构以支持Redis中对于频繁高效操作字符串的要求。


SDS 简单动态字符串

基于以上C字符串的缺陷,Redis自己构建了一种名为简单动态字符串的抽象类型,简称SDS。

SDS结构
struct sdshdr {

    // buf数组已经使用字节数量,即SDS字符串长度
    int len;

    // 记录buf数组中未使用字节的数量
    int free;

    // 字节数组,用于保存二进制数据
    char buf[];
}

可以看出,SDS定义的结构中,增加了一个int类型的len属性用于记录SDS所保存的字符串长度,一个free属性用于记录数组中未使用的字节数量。

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

Redis中利用SDS字符串的len属性可以直接获取到所保存的字符串的长
度,直接将获取字符串长度所需的复杂度从C字符串的O(N)降低到了O(1)。


  • 减少修改字符串时导致的内存重新分配次数

基于前面介绍的C字符串的特性,我们知道对于一个包含了N个字符的C字符串来说,其底层实现总是N+1个字符长的数组(额外一个空字符结尾),那么如果这个时候需要对字符串进行修改,程序就需要提前对这个C字符串数组进行一次内存重分配(可能是扩展或者释放),而内存重分配就意味着是一个耗时的操作。

Redis巧妙的使用了SDS避免了C字符串的缺陷,在SDS中,buf数组的长度不一定就是字符串的字符数量加一,buf数组里面可以包含未使用的字节,而这些未使用的字节由free属性记录。

SDS采用了空间预分配策略避免C字符串每一次修改时都需要进行内存重分配的耗时操作,将内存重分配从原来的每修改N次就分配N次降低到了修改N次最多分配N次。

字符串扩展:

首先检查SDS未使用空间即free属性是否够用,如果够用,则会直接使用未使用空间,而无须进行内存重分配

空间预分配

所谓预分配就是额外多分配一部分空间给SDS,并不是仅仅只分配刚好够字符串扩展修改后的空间。

分配策略:

  1. 若SDS修改后,其长度(len的属性)小于1MB,那么程序会分配和修改后的len属性同样大小的未使用空间
  2. 若修改后,其长度大于1MB,那么程序只会分配固定1MB的未使用空间,不会再多分配了,考虑内存的成本因素

字符串缩短:

针对SDS字符串的缩短场景,SDS并不会立即释放多余出来的内存空间,而是将这部分内存空间记录再其free属性中,当SDS字符串进行扩展时,这部分未使用的内存空间就能直接用,而不需要进行内存重分配,这就是SDS的惰性空间释放


  • 杜绝缓冲区溢出

在C字符串的拼接操作过程中,例如某程序员操作S1拼接S2,由于程序员忘记了给需要拼接的字符串S1分配足够的内存空间(到底需要分配多少内存呢?哈哈,当然需要遍历S2的字符数组才能知道S2的长度是多少,因为C字符串不记录自身的长度),那么拼接的时候就会导致缓冲区溢出的可能性。

针对以上情况,SDS的空间分配策略可以完全杜绝这种情况,因为当SDS 的API对SDS进行修改时,API会首先检查SDS的未使用空间是否足够,不够的化会进行内存重分配以扩展空间至足够修改所需的大小,然后再执行实际的修改操作,这样就可以达到杜绝缓冲区溢出的可能。


  • 让Redis保存更多类型的数据成为可能

由于C字符串中保存的字符必须符合某种编码格式(如ASCII),这就限制了C字符串只能保存文本数据,而不能保存箱视频,音频,压缩文件这种的二进制数据。

另一个限制是C字符串中间不能包含空字符,否则中间的空字符会被认为是整个字符串的结尾,而导致后面的部分字符被忽略掉。

SDS的API被设计成了二进制安全的,以处理二进制的方式来处理SDS中存放再buf数组中的数据,原样存取,这就是为什么在SDS的结构中采用的是字节数组,而不是C字符串中的字符数组

这样的二进制安全的SDS,使得Redis不仅可以保存文本,还可以保存任意格式的二进制数据。


  • 兼容部分C字符串API

由于C字符串本身具有大量操作API,SDS如果可以利用一部分C字符串的API那样就不用重复发明轮子了,所以Redis中的SDS遵循C字符串以空字符结尾的惯例,在SDS的API中,总会将SDS保存的数据末尾设置未空字符,在分配buf数组时也总会多分配一个字节来保存这个空字符,这样SDS就可以重用一部分C字符串库的API。


C字符串与SDS对比

对比点C字符串SDS
获取字符串长度时间复杂度O(N)O(1)
API安全性不安全,可能造成缓冲区溢出安全,不会造成溢出
字符串修改N次需要几次内存重分配N次至多N次
能够保存数据类型只能保存文本文本或二进制
对于C语言中字符串API的使用范围所有一部分

总结

Redis中采用SDS替代C语言中传统字符串表示法,提升了获取字符串长度的效率,扩大了能够保存数据的类型范围,以及降低了每次修改字符串时候的内存重分配次数,甚至规避了在操作C字符串中可能出现的缓冲区内存溢出的可能性,从而为Redis中字符串操作的安全,高效提供了保障。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注