SDS(Simple Dynamic String)简单动态字符串

在Redis中可修改的字符串值都是采用的SDS数据结构, 而不可修改的都采用了C字符串

SDS的结构

有三个基本变量

  • free 纪录buf数组中未使用字节的数量
  • len 纪录buf数组中已使用字节的数量, 等于SDS所保存字符串的长度
  • buf 字节数组, 用于保存字符串(二进制)

为什么采用SDS

SDS是基于C字符串结构的缺点优化后的产物, 因为采用C字符串的方式会有以下一些问题：

  • 获取字符串长度需要遍历字符串获取, 将需要O(N)的时间复杂度
  • C字符串会有缓冲区溢出的问题
  • 一旦修改字符串操作发生就会重新分配内存, 修改N次就分配N次 所以, 基于以上问题SDS结构的优点也显而易见了, 如下:
  • 因为结构体中标记了字符串长度, 所以获取长度的时间复杂度变成了O(1)
  • SDS的API中对内存分配的机制杜绝了缓冲区溢出的问题
  • 同样, API中的操作也减少了修改字符串长度时所需的内存重分配次数
  • 二进制安全
  • 兼容部分C字符串函数

内存分配机制

  • 空间预分配 在字符串增长操作中有两种情况来预分配空间 第一种是修改后的长度(len的值)小于1MB的情况下, free的值会和len的值相同, 来做到减少内存分配次数, 预分配以后可能会使用到的空间 第二种是修改后的长度大于1MB的情况下, free的值会多修改为1MB, 也就是在原来基础上多出1MB的未使用空间
  • 惰性空间释放 在字符串缩短操作的时候, 不会将释放的空间马上回收, 而是会写入到free中, 将缩短的长度标记为未使用空间为将来可能会使用的字符串预留位置。SDS中也有相应的API, 可以在需要时真正释放这部分空间。