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