目录
SDS是什么?
SDS结构示例
概述
空间预分配
惰性空间释放
C字符串跟SDS的区别?为什么用SDS?
SDS是什么?
Redis 底层的程序语言是由 C 语言编写的,C 语言默认字符串则是以空字符结尾的字符数组(简称 C 字符串)。但 Redis 默认的字符串并非 C 字符串,而是名为 SDS ( Simple Dynamic String )简单动态字符串的抽象结构。
- 在 Redis 里面, C 字符串只会作为字符串字面量(string literal), 用在一些无须对字符串值进行修改的地方, 比如打印日志。
- 当 Redis 需要的不仅仅是一个字符串字面量, 而是一个可以被修改的字符串值时, Redis 就会使用 SDS 来表示字符串值: 比如在 Redis 的数据库里面, 包含字符串值的键值对在底层都是由 SDS 实现的。
SDS结构示例
概述
Redis 采用一段连续的内存空间来存储 SDS 结构,具体结构如下图所示,free 代表指这个字符串剩余可用空间的长度,而 len 代表这个字符串已占用空间的长度,buf [] 就是字符数组。
struct sdshdr {// 记录 buf 数组中已使用字节的数量// 等于 SDS 所保存字符串的长度int len;// 记录 buf 数组中未使用字节的数量int free;// 字节数组,用于保存字符串char buf[];};
一个字符串为 'Redis' 在 SDS 结构中的存储例子:
图中 SDS 保留了 C 字符串以空字符结尾的传统,但这个空字符的长度1字节空间并不会计算在 SDS 的 len 属性里面,而是为这个空字符分配额外的1字节空间,每次由 SDS 相关函数默认添加到字符串末尾,Redis 这样设计的好处是 SDS 可以直接重用一部分 C 字符串相关函数。
这个 SDS 结构为字符串 'Redis' 分配了5字节的已使用长度,也为其分配了5字节的可用空间长度。
空间预分配
SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联: 在 SDS 中, buf
数组的长度不一定就是字符数量加一, 数组里面可以包含未使用的字节, 而这些字节的数量就由 SDS 的 free
属性记录。
空间预分配用于优化 SDS 的字符串增长操作: 当 SDS 的 API 对一个 SDS 进行修改, 并且需要对 SDS 进行空间扩展的时候, 程序不仅会为 SDS 分配修改所必须要的空间, 还会为 SDS 分配额外的未使用空间。通过空间预分配策略, Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。
- 如果对SDS进行修改之后,SDS的长度(也即是len属性的值)将小于1MB,那么程序分配和len属性同样大小的未使用空间,这时SDS len属性的值将和free属性的值相同。
进行修改之后, SDS 的
len
将变成14
字节, 那么程序也会分配14
字节的未使用空间, SDS 的buf
数组的实际长度将变成14
+ 14
+ 1 = 28
字节(额外的一字节用于保存空字符)。
- 如果对SDS进行修改之后,SDS的长度(也即是len属性的值)将大于等于1MB,那么程序会分配1MB的未使用空间。
进行修改之后, SDS 的
len
将变成30 MB
, 那么程序会分配1 MB
的未使用空间, SDS 的buf
数组的实际长度将为30 MB + 1 MB + 1 byte
。
在扩展 SDS 空间之前, SDS API 会先检查未使用空间是否足够, 如果足够的话, API 就会直接使用未使用空间, 而无须执行内存重分配。
通过这种预分配策略, SDS 将连续增长 N
次字符串所需的内存重分配次数从必定 N
次降低为最多 N
次。
惰性空间释放
惰性空间释放用于优化 SDS 的字符串缩短操作: 当 SDS 的 API 需要缩短 SDS 保存的字符串时, 程序并不立即使用内存重分配来回收缩短后多出来的字节, 而是使用 free
属性将这些字节的数量记录起来, 并等待将来使用。
通过惰性空间释放策略, SDS 避免了缩短字符串时所需的内存重分配操作, 并为将来可能有的增长操作提供了优化。
C字符串跟SDS的区别?为什么用SDS?
C字符串 | SDS | |
字符串长度处理 len | 需要从头开始遍历,直到遇到“/0'为止时间复杂度O(N) | 记录当前字符串的长度,直接读取即可,时间复杂度 O(1) |
内存重新分配alloc | 分配内存空间超过后,会导致数组下标越级或者内存分配溢出 | 空间预分配 惰性空间释放 有空间分配对应的就有空间释放。SDS 缩短时并不会回收多余的内存空间,而是使用 free 字段将多出来的空间记录下来。如果后续有变更操作,直接使用 free 中记录的空间,减少了内存的分配。 |
二进制安全buf | 二进制数据并不是规则的字符串格式可能会包含一些特殊的字符,比如“\0"等。C中字符串遇到“0会结束,那"\0"之后的数据就读取不上 | 根据 len 长度来判断字符串结束的,二进制安全的问题就解决了 |