redis底层结构之-SDS

redis没有直接使用C语言传统的字符串,而是自己构建了一种名为简单动态字符串(SDS)的结构,并将SDS用作redis的默认字符串表示。

  • C语言传统字符串:以空字符结尾的字符数组;使用长度N+1的字符数组来表示长度为N的字符串

SDS

1
2
3
4
5
6
7
8
9
10
11
struct sdshdr{
// 记录buf数组中已使用字节的数量
// 等于SDS所保存字符后的长度
int len;

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

// 字节数组,用于保存字符串
char buf[];
};
  • 可以明显看出 buf数组的长度 = len(已使用长度) + free(未使用长度)

举例说明

  • free值为5,表示这个SDS有5字节的空间未使用
  • len值为5,保存了一个五字节长的字符串
  • buf是一个字节数组,保存了 ‘R’,’e’,’d’,’i’,’s’,五个已使用字符,还有一个空字符 ‘\0’,不算len的长度,还有5个字节的空间未使用

相当于buf的长度为 buf.length = len + free + 1。但是真实情况下,这个1字节的空间不会算在len属性里面

SDS这样设计的好处

  1. 获取字符串的长度 时间为O(1)
  2. 杜绝缓冲区溢出
  3. 减少修改字符串时带来的内存重分配次数
  4. 二进制安全(可以保存文本或二进制数据)
    • c字符串只能保存文本数据,不能保存图片、音频、视频等二进制数据
    • buf称为字节数组的原因–并不是用这个数组保存的字符,而是保存的二进制数据
  5. 兼容部分C字符串函数

好处一—获取长度时间为O(1)

  • C 语言中,获取字符串的长度需要用指针遍历字符串,时间复杂度为 O(n),而 SDS 的长度,直接从len 获取复杂度为 O(1)。
  • 对一个非常长的字符串键反复执行strlen命令,不会对系统性能造成任何影响

好处二—杜绝缓冲区溢出

c语言中,假设此时正在做字符串的拼接操作

char strcat(char dest, const char *src);将src的内容拼接到dest的后面

假设已经为dest分配了足够多的内存,可以容纳src字符串中的所有内容。但是假设不成立,就会造成缓冲区溢出

  • 缓冲区溢出的理解:假设内存中紧邻着两个字符后S1,S2。S1保存了redis,S2保存了MongoDb,如果执行strcat(s1,” Cluster”);将s1的内容修改为“Redis Cluster”,但是却忘记了在strcat之前为s1分配足够多的空间,就会将s1的数据溢出到s2所在的空间中,导致s2保存的内容被修改

SDS的空间分配策略就杜绝了发生缓冲区溢出的可能性,它需要先验证 free的长度,如果free 不够就会扩容整个 buf,防止溢出。

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

c字符串每次增长或者缩短一个字符串时,都会对这个字符串数组进行一次内存重分配操作

  • 如果程序执行的是增长字符串的操作, 比如拼接操作(append), 那么在执行这个操作之前, 程序需要先通过内存重分配来扩展底层数组的空间大小一如果忘了这步就会产生缓冲区溢出。

  • 如果程序执行的是缩短字符串的操作,比如截断操作(trim), 那么在执行这个操作之后,程序需要通过内存重分配来释放字符串不再使用的那部分空间——如果忘了这一步就会产生内存泄漏。

redis 作为高性能的内存数据库,需要较高的相应速度。字符串也很大概率的频繁修改。

SDS 通过未使用空间这个参数,将字符串的长度和底层buf的长度之间的额关系解除了。

buf的长度也不是字符串的长度。基于这个分设计 SDS 实现了空间的··预分配··和··惰性释放··。

空间预分配

空间预分配用于优化SDS的字符串增长操作。

  • 如果对SDS进行修改之后,len小于1MB,free = len(目前小于1MB的大小),buf的实际长度 = len + free + 1byte = len * 2 + 1byte(额外的1字节用于保存空字符)

  • 如果对SDS进行修改之后,len大于等于1MB,free = 1MB,len = 目前现在的大小,buf的实际长度 = len + 1MB + 1byte

通过空间预分配策略,redis可以减少连续执行字符串增长操作所需要的内存重分配次数。因为每次增长字符串之后,实际的Buf长度变长了,用于下次你的长度变更。

补充小知识:

我们可能会想 字符串增长是个什么操作?

1
2
3
4
5
6
redis> set str "hello"
OK
redis> append str " world"
(integer) 11
redis> get str
"hello world"
  • append命令

惰性释放

惰性空间释放用于优化SDS的字符串缩短操作

  • 如果缩短 SDS 的字符串长度,redis并不是马上减少 SDS 所占内存。只是增加 free 的长度。同时向外提供 API 。真正需要释放的时候,才去重新缩小 SDS 所占的内存

二进制安全

  • C 语言中的字符串是以 ”\0“ 作为字符串的结束标记。而 SDS 是使用 len 的长度来标记字符串的结束。所以SDS 可以存储字符串之外的任意二进制流。因为有可能有的二进制流在流中就包含了”\0“造成字符串提前结束。也就是说 SDS 不依赖 “\0” 作为结束的依据。