Redis数据结构学习-SDS(一)

SDS 简单动态字符串

SDS 定义

每个sds.h/sdshdr 结构表示一个SDS值

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

image-SDS.png

• free属性值为0, 表示 SDS 未分配 未使用空间
• len 属性为5, 表示 SDS 保存了一个5字节长的字符串
• buf 属性是一个char类型的数组, 数组的前5个字节保存了 R, e,d,i, s, 五个字符, 最后一个字节保存了空字符串\0

为什么不使用C原生字符串呢 ?

1. C字符串获取长度需要遍历, SDS则记录了自身长度(len), 将获取字符串长度的时间复杂度从O(N)降低到了O(1), 即使反复执行strlen, 也不会对系统造成任何影响
2. C字符串不记录自身长度, 容易造成缓冲区溢出, eg. strcat可以将字符串拼接, 执行这一操作时, 系统假定用户已分配了足够长度的内存, 假设不成立时, 就会造成缓冲区溢出(覆盖后边的字符)
3. C的实现是一个N+1字符长的数组, 每次增长或缩短一个C字符串, 都会重新分配内存
   • 若增长, eg. append、需要先扩容, 否则会产生内存溢出
   • 若缩容, eg. trim、需要先缩容, 否则会造成内存泄露
4. 为避免C字符串的缺陷, SDS通过未使用空间分配, 实现了空间预分配和惰性空间释放来优化.
   • 空间预分配: 当字符串扩展时, 不仅分配必须空间, 还会分配额外空间(len<1M时, free=len, len>=1M时, free=1M), 来减少连续执行字符串增长需要的内存分配次数, 将字符串连续增长N次需要的内存重分配次数从必定N次, 降低到最多N次
   • 惰性释放: 用free来标记被释放的空间, 而不真正操作内存, 也提供了API, 在需要时释放free空间, 不必担心惰性释放造成的空间浪费
5. C字符串用\0标记字符串结尾, 字符串本身不能包含空字符, 使得C字符串只能保存文本数据, 而不能保存图片、音频、视频、压缩文件等二进制数据. 而redis SDS字符靠len属性来判断字符串结尾, 是二进制安全的.
6. 兼容部分C字符. SDS总在结尾多分配一个字符\0 是为了保证C函数可以正常使用, 避免不必要的代码重复

总结

C字符串	SDS字符串
获取字符串长度时间复杂度 O(N)	获取字符串长度时间复杂度 O(1)
API非安全, 可能造成缓冲区溢出	API安全, 不会操作缓冲区溢出
修改字符串会造成NN次内存分配	修改字符串最多N次内存分配
只保存文本数据	可以保存文本及二进制数据
可以使用 <string.h> 库中的函数	可以使用部分 <string.h> 库中的函数