Redis没有使用C语言传统的字符串表示(以空字符\0结尾的字符数组),而是使用简单动态字符串(Simple Dynamic String, SDS)的抽象类型作为字符串的表示。

SDS的定义

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

  • free 值为0,表示这个SDS没有分配为使用的空间
  • len 值为5,表示这个SDS保存了一个5字节长的字符串。
  • buf 是一个char数组,存储了Redis字符串,最后以空字符\0结尾。

SDS遵循C字符串以空字符结尾惯例,保存空字符的1个字节空间不计算在SDS的len属性里边。并且为空字符分配空间等操作均由SDS函数自动完成。好处是SDS可以直接重用一部分C字符串函数库里的函数

SDS与C字符串的区别

C语言使用长度N+1的字符数组存储长度为N的字符串,最后一个元素是空字符\0。如下图所示:

C语言使用的字符串方式比较灵活,不能满足Redis对字符串在安全性、效率以及功能方面的要求。

字符串长度

  • C字符串并不记录自身长度,获取字符串长度时需要遍历整个字符数组,直到遇到空字符\0操作复杂度为O(N)

  • SDS的len属性中记录的本身就是存储字符串的长度,所以获取一个SDS长度的复杂度仅为O(1)

设置和更新SDS长度的工作由SDS的API在执行时自动完成,使用SDS时无需手动干预。

通过使用SDS而不是C字符串,Redis获取字符串长度所需的复杂度从O(N)降低到O(1),确保获取字符串长度不会成为Redis性能瓶颈。

缓冲区溢出

C语言不记录自身长度的另一个问题是容易造成缓冲区溢出。例如 strcat 函数是将src字符串拼接到dest字符串的末尾

1
char *strcat(char *dest, char *src);

如果在拼接时,dest没有足够多的内存可用,就会造成缓冲区溢出。

SDS在空间分配策略完全杜绝了缓冲区溢出的可能性。当SDS的API需要怼SDS进行修改时,API会检查SDS的空间是否满足修改所需的要求。如果不满足的话,API会自动将SDS空间扩展至执行修改所需的大小,然后再进行实际的修改操作。

修改字符串时的内存分配

C字符串在执行修改时,每次总要对保存字符的数组进行内存重新分配。(如果执行拼接操作,则需要重新分配空间,如果没有分配则会出现溢出;如果执行缩短操作,需要释放空间,如果不释放则会产生内存泄露)。

Redis SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。

  • 空间预分配
    • 当使用API对SDS进行空间扩展时,程序不仅会为SDS分配修改所必须的空间,还会分配额外未使用的空间。如果SDS 字符串长度(len的值)小于1M,那么程序将分配同len一样大小的未使用空间(len 和 free 值相同);当SDS进行修改后,SDS的长度大于等于1M,那么程序会分配1M的未使用空间。通过空间预分配策略,Redis可用减少连续执行字符串增长操作所需的内存分配次数。
  • 惰性空间释放
    • 惰性空间释放用于优化SDS的字符串端操作;当SDS的API需要缩短SDS字符串时,程序并不是立即使用内存重新分配来回收多余的字节。通过惰性空间释放策略,SDS避免了缩短字符串时所需的内存重新分配操作,并为将来的增长操作提供优化。SDS也会提供响应的API,在需要的时候真正的释放SDS未使用的空间,不用担心内存浪费。

二进制安全

C字符串中的字符必须符合某种编码,且不能出现空字符\0。这些限制使得C字符串只能存储文本数据,不能存储图片、音视频、文件等二进制数据。

Redis SDS不仅可以存储文本数据,还可以存储任意格式的二进制数据。

兼容部分C字符串函数

虽然SDS的API都是二进制安全的。但它们一样遵循C字符串以空字符结尾的惯例。这样SDS可以在有需要重用C 的 string.h 函数库,避免不必要的代码重复。

总结

C 字符串 SDS
获取字符串长度复杂度O(N) 获取字符串长度复杂度O(1)
API不安全,可能造成内存溢出 API安全,不会造成内存溢出
对字符串长度调整需要执行内存重新分配 修改字符串长度,不一定需要执行内存分配
只能保存文本数据 可保存文本和二进制数据
可以使用所有的<string.h>库中的函数 可以使用部分的<string.h>库中的函数