Redis 数据结构之SDS
简单动态字符串
为了实现对于字符串的高效操作,Redis 自己构建的一种名为简单动态字符串(SDS)的抽象数据结构。
1、SDS 数据结构
struct sdshdr{
// 记录buf数组中已使用的字节数量,等于sds 保存字符串的长度
int len;
// 记录buf 中未使用的字节数量
int free;
// 字节数据
char buf[];
}
2、SDS 与 C字符串的优缺点
-
常数复杂度获取字符串长度;
SDS 字符串长度的复杂度为O(1),而C字符串长度需要遍历,复杂度为O(n);
-
避免缓冲区溢出;
当对SDS进行修改时,API会检查SDS 的空间是否满足修改所需的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作;
-
减少修改字符串时带来的内存分配次数
对于C字符串来说,如果修改字符串的长度,都需要重新执行内存分配操作;但是对于Redis数据库来说,如果频繁执行内存分配/释放操作,必然会对性能产生一定影响。为了避免C字符串的缺陷,SDS采用了空间预分配和惰性空间释放两种优化策略。
-
空间预分配
它主要解决字符串增长的操作,即通过API对增加SDS的长度时,它不仅会分配实际所需的长度,除此之还会额外分配一块未使用的内存,以便下次直接使用,无需重新分配内存,对于分配的额外内存有一下两种策略:
- 如果对SDS修改后,它的长度小于1MB,那么程序会分配相同大小(和len长度一致)的空间来作为未使用的空间(完成之后len=free,此时总大小为2*len);
- 如果对于SDS修改后大于1MB,那么程序只会分配1MB的内存给未使用的空间(此时SDS总长度为len+1MB);
通过上述优化,对于N次SDS的修改,分配内存的操作由N次变为至多N次。
-
惰性空间释放
主要解决字符串的缩短操作,即当SDS的API缩短字符串时,缩小的空间不会立刻释放,而是暂时作为未使用区,以便后续增长时再次使用。同时,SDS提供了相应的API,以便我们在真正使用内存时,通过API真正的释放SDS的未使用空间。
基于SDS上面的两个特性,我们可以得出如下结论:SDS在分配/释放空间方面的优化也提升了Redis的速度,但与此同时,如果有频繁操作比较大的字符串时,会对Redis的内存空间有一定浪费,同时在分配/释放内存的性能上也会有所损失。
-
-
二进制安全
对于C字符串来说,字符串中不能包含空字符,否则最先被程序读入的空字符串被误认为是字符串结尾,这使得C字符串只能保存文本数据,而不能保存图片、音视频等二进制文件。对于SDS来说,所有SDS都会以处理二进制的方式来处理SDS保存在buf数组中的内容,程序不会对里面的内容做任何限制。
-
兼容部分C字符串函数
SDS末尾设置空字符的操作使得它可以和部分C字符串函数兼容。
网友评论