=================
== Time Stream ==
=================
一个小学生

Redis简单动态字符串SDS

redis

Redis中的字符串使用的是Redis自定义的抽象类型,而不是直接使用C语言的字符串表示。Redis的字符串叫做:简单动态字符串Simple Dynamic String,简称SDS。

SDS除了能保存字符串值,还能作为缓冲区buffer:AOF模块中的AOF缓冲区、客户端状态中的输入缓冲区。

SDS定义

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

SDS-1

  1. free=0,表示SDS没有分配未使用空间
  2. len=5,表示SDS保存了一个5字节长的字符串
  3. buf是一个char类型数组,前面5个保存了实际的字符,最后一个字节保存了空字符\0

SDS-2

  1. free=5,表示为buf数组分配了5字节未使用空间

SDS与C字符串的区别

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

C字符串不记录自身长度,需要遍历字符串,直到遇到结尾空字符串,时间复杂度为O(N)。SDS记录了自身长度,获取长度的时间复杂度为O(1)。

杜绝缓冲区溢出

C字符串不记录自身长度,修改字符串容易产生缓冲区溢出问题。SDS修改字符串时会先检查空间是否满足要求,不满足的话会自动将SDS空间扩充到所需大小,再执行修改,也就不会产生缓冲区溢出问题。

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

C字符串每次增长或缩短,程序都需要对这个C字符数组进行内存充分配操作:

  1. 增长C字符串时,程序先通过内存重分配来扩展底层数组空间大小,否则会产生缓冲区溢出。
  2. 缩短C字符串时,程序先通过内存充分配来释放不再使用的空间,否则会产生内存泄露。

C字符串的这种方式会对Redis产生性能影响,SDS通过未使用空间实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

SDS需要进行空间扩展的时候,先会分配必须要的空间,还会分配额外未使用空间,通过空间预分配可以减少连续执行字符串增长操作所需的内存重分配次数:

  1. SDS修改后,长度len小于1MB时,会分配一个长度也为len的未使用空间。比如修改后SDS长度len=13,则分配free=13,SDS长度实际为:len + free + 1 = 13 + 13 + 1
  2. SDS修改后,长度len大于等于1MB时,会分配一个长度为1MB的未使用空间。比如修改后SDS长度len=2MB,则分配free=1MB,SDS长度实际为:len + free + 1 = 2MB + 1MB + 1byte

惰性空间释放

SDS需要进行字符串缩短操作时,不会立即回收缩短后空闲出来的空间,而是分配给free,等待将来使用。

二进制安全

C字符串中的字符必须符合某种编码,除了末尾字符,其他字符不能是空字符。C字符串只能保存文本数据,不能保存图像、音频、视频、压缩文件等二进制数据。

SDS是二进制安全的,buf数组里的数据没有任何限制,buf数组里不保存字符,而保存二进制数据。

兼容部分C字符串函数

SDS可使用部分的C字符串函数

总结

C字符串 SDS
获取长度时间复杂度O(N) 获取长度时间复杂度O(1)
API不安全,可能造成缓冲区溢出 API安全,不会造成缓冲区溢出
修改长度N次,需要N次内存重分配 修改长度N次,最多需要N次内存重分配
只能保存文本数据 可以保存文本和二进制数据
可使用C的所有字符串函数 可使用部分C的字符串函数

参考

  • 《redis设计与实现》(第二版)