原创

Redis设计与实现-SDS


简单动态字符串(SDS)

Redis没有直接使用C语言传统的字符串标识(以空字符串结尾的字符数组),而是自己构建了一种名为简单动态字符串(SDS)的抽象类型,并将SDS用作Redis的默认字符串表示

SDS的定义
struct sdshdr{
    //记录buf数组中已使用字节的数量
    //等于SDS所保存字符串的长度
    int len;
    
    //记录buf数组中未使用字节的数量
    int free;
    
    //字节数组
    char buf[];
}

SDS遵循C字符串以空字符结尾的惯例,保存空字符的1字节不计算在SDS的len属性里面

SDS与C字符串的区别
常数复杂度获取字符串长度

因为C字符串并不记录自身的长度信息,所以为了获取一个C字符串的长度,程序必须遍历整个字符串,直到遇到代表字符串结尾的空字符为止,复杂度为O(N)

和C字符串不同,因为SDS在len属性中记录了SDS本身的长度,所以获取一个SDS长度的复杂度为O(1)

杜绝缓冲区溢出

因为C字符串不记录自身长度,所以strcat假定用户在执行这个函数时,已经为字符串分配了足够多的内存,可以容纳拼接后的所有内容,而一旦这个假定不成立,程序员粗心的忘了分配足够多的空间,那么就会产生缓冲区的溢出

与C字符串不同,SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性:当SDS API 需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需的要求,如果不满足,API会自动将SDS的空间扩展至执行修改所需的大小

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

C字符串并不记录自身的长度,所以对于一个包含了N个字符的C字符串来说,这个字符串的底层实现总是一个N+1个字符串的数组,所以每次增长或者缩短一个C字符串,程序都要对保存这个C字符串的数组进行一次内存重分配

对于SDS来说,它有两个机制会避免这种情况

1 - 空间预分配

当SDS的API对一个SDS进行修改,并且需要对SDS进行空间扩展时,程序不仅会为SDS分配修改所必须要的空间,还会为SDS分配额外的未使用的空间

如果对SDS进行修改之后,SDS的长度将小于1MB,那么程序分配和len属性相同大小的未使用空间。举个例子,如果修改之后,SDS的len将变为13字节,那么程序和额外分配13字节,SDS的buf数组的实际长度为13+13+1=27字节(额外一字节用于保存空字符串)

如果对SDS修改轴,SDS长度将大于1MB,那么程序会分配1MB的未使用空间

2 - 惰性空间释放

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

二进制安全

C字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据

SDS可以

Redis
  • 作者:刘柄岐
  • 发表时间: 2022-03-23 19:04
  • 版权声明:自由转载-非商用