我要评论实验的环境
- redis 6.0
- vscode 1.88.1
什么是sds?
sds：simple dynamic string，翻译为简单动态字符串。
sds是一种用于存储二进制数据的数据结构，具有动态扩容的特点，代码位于src/sds.h和src/sds.c
sds的总体数据结构大致如图：在源码里sds包括几个部分，len、alloc、flags、buf，其中 sdshdr是头部，buf是真实存储数据的地方，在存储的数据后面会跟一个\0，所以数据加上\0就是所谓的buf
- len：保存了sds字符串的长度
- buf[]：保存数据的地方
- alloc：分别以uint8, uint16, uint32, uint64表示整个sds
- flags：始终为一字节, 以低三位标示着头部的类型, 高5位未使用
查看源码sds.h，可以看到sds里面有几种不同的头部，其中sdshdr5实际并未使用到，所以实际上有四种不同的头部
/* note: sdshdr5 is never used, we just access the flags byte directly.
* however is here to document the layout of type 5 sds strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};为什么要使用sds？
redis是用c语言写的，为什么不直接就用c语言里的char来定义字符串？
获取字符串长度
由于有len属性，所以获取sds字符串的长度只需要读取len属性，所以时间复杂度为o(1)。
如果直接使用c语言中的字符串来实现，获取字符串的长度需要遍历计数，时间复杂度为o(n)。
避免缓存区溢出
在c语言中，如果使用strcat函数来进行两个字符串的拼接，如果没有分配足够长度的内存空间，就会造成缓存区溢出。
而对于sds数据类型，在进行字符串修改的时候，会根据记录的len属性检查内存空间是否满足需求，如果不满足，会进行相应空间的扩展，所以不会出现缓存区溢出
减少字符串内存重新分配次数
在c语言中字符串，是不会记录字符串的长度的，所以一旦修改了字符串，就需要重新分配内存，因为如果没有重新分配，字符串长度增大时会造成内存溢出区溢出，长度减小时会造成内存泄漏。
而对于sds来说，因为有长度熟悉len和alloc属性的存在，sds实现了空间预分配和惰性空间释放两种策略来减少重新分配内存
- 空间预分配：sds对空间进行扩展的时候，扩展的内存比实际需要的多，这样可以减少字符串增长操作所需的内存重新分配次数
- 惰性空间释放：sds对字符串进行缩短操作时，不会立即进行内存重新分配，来回收缩短后多余的内存空间，而是使用
alloc将这些字节数量记录下来，等待后续使用
二进制安全
在c语言中，是以空字符串作为字符串结束的标识，但是一些特殊的字符串，可能就包括空字符串的，所以容易丢失数据，不能正确存取。
而sds是根据len属性，以处理二进制的方式来处理buf里的数据，所以保存数据更加安全
兼容部分c字符串函数
sds可以重用c语言库<string.h>中的一部分函数
c字符串和sds对比
| c字符串 | sds |
|---|---|
| 获取字符串长度时间复杂度为o(n) | 获取字符串的长度时间复杂度为o(1) |
| 不安全，可能会造成缓冲区溢出 | 安全，不会造成缓冲区溢出 |
| 修改字符串n次就需要进行n次内存分配 | 修改字符串长度n次，最多需要n次内存分配 |
| 只能保存文本数据 | 可以保存文本数据或者二进制数据 |
| 可以使用所有<string.h>库中的函数 | 可以使用一部分<string.h>库中的函数 |
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。
发表评论