Redis数据结构-字符串

简单动态字符串(SDS)

Redis自己构建了一种名为简单动态字符串(simple dynamic string, SDS)的抽象类型,并将SDS用作Redis的默认字符串表示.

在Redis中,C字符串只会作为字符串字面量用在一些无需对字符串值进行修改的地方,比如打印日志:

1	redisLog(REDIS_WARNING, "Redis is now ready to exit");

当Redis需要的不仅仅是一个字符串字面量,而是一个可以被修改的字符串值时,Redis就会使用SDS来表示字符串值,比如在Redis的数据库里面,包含字符串值的键值对在底层都是由SDS实现的.

SDS除了用来保存数据库中的字符串之外,SDS还被用作缓冲区:AOF模块中的AOF缓冲区,以及客户端状态中的输入缓冲区,都是由SDS实现的

SDS的定义

struct sdshdr {

    // 记录buf数组中已使用字节的数量
    // 等于SDS所保存的字符串的长度
    int len;

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

    // 字节数组,用于保存字符串
    char buf[];
}

SDS遵循C字符串以空字符结尾的管理,保存空字符串的1字节空间不计算在SDS的len属性里面.
为空字符自动分配额外的1字节空间,以及添加空字符串到字符串末尾等操作都是由SDS函数自动完成的,所以这个空字符串对于SDS的使用者来说是完全透明的.

遵循空字符串结尾这一管理的好处是,SDS可以直接重用一部分C字符串函数库里面的函数

SDS与C字符串的区别

根据传统,C语言使用长度为N+!的字符串数组来表示长度为N的字符串,并且字符数组的最后一个元素总是空字符’\0’

C语言使用这种简单的字符串表示方式,并不能满足Redis对字符串在安全性,效率以及功能方面的要求

区别总结:

-	C字符串	SDS
获取字符串长度的复杂度	O(N)	O(1)
缓冲区安全	不安全	安全
修改字符串长度N次需要的重分配次数	N次	最多N次
保存数据	只能保存文本数据	可以保存文本或者二进制数据
可以使用<string.h>库中的函数	所有	部分

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

因为C字符串并不记录自身的长度信息,所以为了获取一个C字符串的长度,程序必须遍历整个字符串
和C字符串不同,因为SDS在len属性中记录了SDS本身的长度,所以获取一个SDS长度的复杂度近位O(1)

使用SDS确保了获取字符串长度的工作不会成为Redis的性能瓶颈

杜绝缓冲区溢出

当SDS API需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用SDS既不需要手动修改SDS空间大小,也不会出现缓冲区溢出问题

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

因为C字符串并不记录自身的长度,所以对于一个包含了N个字符串的C字符串来说,这个C字符串的底层实现总是一个N+1字符长的数组.因为字符串的长度和底层数组长度之间存在着这种关联性,所以每次增长或者缩短一个C字符串,程序都总要对保存这个C字符串的数组进行一次内存重分配操作:

如果程序执行的是增长字符串的操作,比如拼接操作(append),那么在执行这个操作之前,程序需要先通过内存重分配来扩展底层数组的空间大小,如果忘了这一步就会产生缓冲区溢出
如果程序执行的是缩短字符串的操作,比如截断操作(trim),那么在执行这个操作之后,程序需要通过对内存重分配来释放字符串不再使用的那部分空间,如果忘了这一步就会产生内存泄露

因为内存重分配设计复杂的算法,并且可能需要执行系统调用,所以它通常是一个比较耗时的操作,在一般程序中,如果修改字符串长度的情况不太常出现,那么每次修改都执行一次内存重分配是可以接受的;而对于Redis数据库,经常被用于速度要求严苛,数据频繁被修改的场合,如果每次修改字符串的长度都需要执行一次内存重分配的话,那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分,如果频繁发生更改的话,可能还会对性能造成影响

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

通过未使用空间,SDS实现了空间预分配和惰性空间释放两种优化策略

空间预分配

空间预分配用于优化SDS的字符串增长操作:当SDS的API对一个SDS进行修改,并且需要对SDS进行空间扩展的时候,程序不仅会为SDS分配修改所必须要的空间,还会为SDS分配额外的未实用空间.
其中,额外分配的未实用空间矢量由以下规则决定:

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

通过空间预分配策略,Redis可以减少连续执行字符串增长操作所需的内存重分配次数
在扩展SDS空间之前,SDSAPI会先检查未实用空间是否足够,如果足够的话,API就会直接使用未使用的空间,而无需执行内存重分配

惰性空间释放

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

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

二进制安全

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

虽然数据库一般用于保存文本数据,但使用数据库来保存二进制数据的场景也不少见,因此,为了确保Redis可以适用于各种不同的使用场景,SDS的API都是二进制安全的(binary-safe),所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据,程序不会对其中的数据做任何限制,过滤,或者假设,数据在写入时是什么样的,它被读取时就是什么样的

这也是我们将SDS的buf属性成为字节数组的原因:Redis不是用这个数组来保存字符,而是用它保存一系列二进制数据.

兼容部分C字符串函数

虽然SDS的API都是二进制安全的,但他们一样遵循C字符串以空字符结尾的惯例,这是为了让那些保存文本数据的SDS可以重用一部分库定义的函数

SDS API

函数	作用	时间复杂度
sdnew	创建一个包含给定C字符串的SDS	O(N)
sdsempty	创建一个不包含任何内容的空SDS	O(1)
sdsfree	释放给定的SDS	O(N)
sdslen	返回SDS已使用空间字节数	O(1)
sdsavail	返回SDS的未实用空间字节数	O(1)
sdsdup	创建一个给定SDS的副本	O(N)
sdsclear	清空SDS保存的字符串内容	惰性释放:O(1)
sdscat	将给定C字符串拼接到SDS字符串的末尾	O(N)
sdscatsds	将给定SDS字符串拼接到另一个SDS字符串的末尾	O(N)
sdscpy	将给定的C字符串复制到SDS里面,覆盖SDS原有的字符串	O(N)
sdsgrowzero	用空字符将SDS扩展至给定长度	O(N)
sdsrange	保留SDS给定区间内的数据,不在区间内的数据会被覆盖或清除	O(N)
sdstrim	接受一个SDS和一个C字符串作为参数,从SDS左右两端分别溢出所有在C字符串中出现过的字符	O(M*N)
sdscmp	对比两个SDS字符串是否相同	O(N)

重点回顾

Redis只会使用C字符串作为字面量,在大多数情况下,Redis使用SDS作为字符串表示
SDS具有以下优点:
- 常数复杂度获取字符串长度
- 杜绝缓冲区溢出
- 减少修改字符串长度时所需的内存重分配次数
- 二进制安全
- 兼容部分C字符串函数