SDS(redis 表示字符串的默认方式)

结构：

1
2
3
4
5
6
7
8
9
struct sdshdr{
 //记录buf数组中已使用字节的数量，等于SDS所保存字符串的长度
 int len;
 //记录buf数组中未使用的字节长度
 int free;
 //字节数组，用于保存字符串
 char buf[]
 
}

SDS最后会以空格字符’\0’结尾,该字符不计算在总长度只内

就像C语言会使用长度为N+1的字符数组表示长度为N的字符串

Redis使用SDS表示字符串而不使用C语言中的字符串有以下优点

简化计算字符串长度计算复杂度

在c语言中要计算一个字符串长度需要遍历该字符串，直到遇到’\0’空格字符，计算复杂度为 O(N)

在SDS中因为其自身结构就带有字符串长度信息，所以对于redis而言，字符串长度并不会给其带来性能瓶颈，其计算长度的计算复杂度为O(1)

不会有缓冲区溢出问题

在 C 语言中，如果 S1字符串修改为更长，就会覆盖掉 S2的内容，所以需要开发人员先计算出长度然后重新分配内存，如果忘记分配而又内存不足就会覆盖掉。

在 SDS 中，SDS api会自动根据长度len去判断是否足够，如果会覆盖掉api会重新分配内存，不会有覆盖掉的风险

减少内存重分配次数

由于redis是数据库，所以数据会频繁发生变化，redis中为了实现减少内存重分配次数，采用了两种优化策略

  1. 空间预分配

也就是会分配空余空间，额外分配的未使用空间由以下公式决定:

  • 如果SDS进行修改之后，SDS的长度(也就是len属性的值)将小于1MB,那么程序分配贺len属性同样大小的未使用空间，这时 SDS len属性的值将和free属性的值相同。举个例子，如果进行修改之后,SDS的len将变成13字节，那么程序也会分配13字节未使用空间，SDS的buf数组实际长度将变成 13+13+1=27字节(额外的一字节用于保存空字符)
  • 如果SDS进行修改之后，SDS的长度将大于等于1MB,那么程序会分配1MB的未使用空间。举个例子，如果进行修改之后，SDS的len将变成30M,那么程序会分配1MB的未使用空间，SDS的buf实际长度将为30MB+1MB+1byte

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

  1. 惰性空间释放

空间预分配是在字符串长度增加时，预分配更多空间以达减少空间重分配次数。

惰性空间释放是在字符串长度减少是，不会立马释放空间，而是依然使用free来维持。以预防长度增加时需要再分配空间。达到减少空间重分配次数。

兼容部分C字符串函数

SDS 遵循了C语言的字符数组以’\0’空格结尾的惯例，所以可以重用部分 C 语言的函数