小技术君     个人站点纯粹分享有意思或者在看的东西~

redis 基础-数据结构-简单动态字符串

2020-07-28

简单动态字符串定义:

每个sds.h/sdshdr结构表示一个SDS值

SDS示例:

SDS和C字符一样保留空字符结尾,但是不会计算在len属性里,自动分配1字节空间和末尾添加空字符都是sds函数自动完成的。

SDS与C字符串的区别:

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

C字符串本身的长度不记录,所以获取对应的长度是O(n)复杂度。

因为SDS在len属性中记录了SDS本身的长度,所以获取一个SDS长度的复杂度仅为O(1).

这个结构确保了获取字符串长度的工作不会成为Redis的性能瓶颈。

  • 杜绝缓冲区溢出

C字符串除了O(n)复杂度之外,还会存在缓冲区溢出(buffer overflow)

使用sds api对 sds修改的时候,会先检查其对应空间是否满足,不满足会自动拓展,在执行修改。

举个例子,SDS的API里面也有一个用于执行拼接操作的sdscat函数,它可以将一个C字符串拼接到给定SDS所保存的字符串的后面,

但是在执行拼接操作之前,sdscat会先检查给定SDS的空间是否足够,如果不够的话,sdscat就会先扩展SDS的空间,然后才执行拼接操作

拼接操作之前:

sdscat(s," Cluster");

拼接操作之后:

  • 减少修改字符串时带来的内存重分配次数

每次增长或者缩短一个C字符串,程序都总要对保存这个C字符串的数组进行一次内存重分配操作:

比如拼接操作(append),截断操作(trim)。

因为内存重分配涉及复杂的算法,并且可能需要执行系统调用,所以它通常是一个比较耗时的操作。

为了避免C字符串的这种缺陷,SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联:在SDS中,buf数组的长度不一定就是字符数量加一,数组里面可以包含未使用的字节,而这些字节的数量就由SDS的free属性记录

SDS实现了空间预分配和惰性空间释放两种优化策略:

  • 1.空间预分配

    • 如果对SDS进行修改之后,SDS的长度(也即是len属性的值)将小于1MB,那么程序分配和len属性同样大小的未使用空间,这时SDS len属性的值将和free属性的值相同

    • 如果对SDS进行修改之后,SDS的长度将大于等于1MB,那么程序会分配1MB的未使用空间

执行sdscat之前:

执行sdscat之后:

再次执行sdscat:

过这种预分配策略,SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次

  • 2.惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作:当SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录起来,并等待将来使用。

执行sdstrim之前:

执行sdstrim之后:

再次执行sdscat之后:

当然SDS也提供了相应的API,让我们可以在有需要时,真正地释放SDS的未使用空间,所以不用担心惰性空间释放策略会造成内存浪费。

  • 二进制安全

C字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符,否则最先被程序读入的空字符将被误认为是字符串结尾,这些限制使得C字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据

为了确保Redis可以适用于各种不同的使用场景,SDS的API都是二进制安全的(binary-safe),所有SDSAPI都会以处理二进制的方式来处理SDS存放在buf数组里的数据也是我们将SDS的buf属性称为字节数组的原因。

通过使用二进制安全的SDS,而不是C字符串,使得Redis不仅可以保存文本数据,还可以保存任意格式的二进制数据

  • C字符串和SDS之间的区别

SDS API

总结

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

2)杜绝缓冲区溢出。

3)减少修改字符串长度时所需的内存重分配次数。

4)二进制安全。

5)兼容部分C字符串函数。


Similar Posts


欢迎关注我的公众号

Comments