引言

为何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中字符串操作的安全,高效提供了保障。

(1)读取 http body 部分

(2)根据 boundary 分析出分隔符特征(这个串是唯一的,不会与body内其他数据冲突)

(3)根据实际分隔符分段获取 body 内容

(4)遍历分段内容

(5)根据 Content-Disposition 特征获取其中值

(6)根据值中 filename 或 name 区分是否是包含二进制流还是表单数据的 k-v

(7)根据 filename 获取原始文件名

(8)从连续 两个 newline 字符串为起始至当前分段完毕,按照二进制流读取上传文件流信息。

完成后即有——

  • 原始文件名信息
  • 原始文件类型信息
  • 全部文件流信息

然后该干嘛干嘛,比如写文件到磁盘等。

具体怎么处理是服务器做的事儿,HTTP协议本身并没有死规定,以下说的只是解决问题的某一种思路。

有一个基本认识是,每一个请求都是一个流。而每一个用于传输文件的HTTP报文,都会有类似于这样的报头:

Content-Type: multipart/form-data; boundary=巴拉巴拉

如果报头定义了这样的东西,就可以判断客户端采用了multipart格式传递信息,同时我们也拿到了boundray。

再考虑文件如何处理。以问题中提到的报文为例,payload(你题干中的报文格式并不对,我根据题目意思做了相应修改)为:

-----------------------------14579331036932498511351460782
Content-Disposition: form-data; name="userfile1"; filename="备注说明.txt"
Content-Type: text/plain

1.±ê×¢ÒÔiPhone6s ÆÁÄ»³ß´çΪ±ê×¼£»
2.Èç¹ûÐèÒª²»Í¬³ß´çµÄicon£¬ÔÙ¸øÎÒ˵¡£
-----------------------------14579331036932498511351460782
Content-Disposition: form-data; name="hehe"

tewtw
-----------------------------14579331036932498511351460782--

1. 第一次读到定义的边界”—————————–14579331036932498511351460782″

意味着一个字段的开始;

2. 继续读入一行,发现这是个文件;再读入一行,发现定义了Content-Type,也许还会定义charset之类的信息;再读入一行发现是个 CRLF ,意味着后续的内容是文件数据,这时候可以构造一个新的临时文件对象,将后续的数据pipe到这个临时文件对象中。

3. 再一次读到边界”—————————–14579331036932498511351460782″意味着这一个字段结束,这时候可以去关闭刚刚创建的临时文件。

4. 然后开始继续下一字段解析过程。

ps:以上部分只是简单的说了解决思路,并不涉及检查、转换等工作。比如在流的pipe过程中,可能需要根据之前定义的charset进行流的转换,甚至如果发现Content-Type不是自己需要的,就压根不存而是直接pipe到黑洞中去。