Redis数据结构之简单动态字符串

发表于 | 分类于

Redis的数据结构-简单动态字符串SDS

1.SDS的定义

sds结构:

1
2
3
4
5
6
7
8
9
struct sdshdr{
 //记录buf数组中已经使用的字节数量
 //等于SDS中所保存字符串的长度
 int len;
 //记录buf数组中未使用字节的数量
 int free;
 //字节数组
 char[] buf
}

SDS遵循C字符串以空字符结尾的习惯，保存空字符的一字节空间不记录到len属性中。这样的好处是可以使用部分c语言的库函数。

2.SDS与c语言字符串的区别
2.1常数复杂度获取字符串长度

c语言不记录自身字符串长度，需要遍历一遍得到字符串的大小。而SDS维护了len变量，直接O(1)复杂度获取。

2.2杜绝缓冲区溢出

c不记录自身长度容易造成缓冲区溢出。而sds会首先检查sds的空间是否满足修改要求，不满足的话会自动实现扩容。

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

Redis作为内存数据库，经常被用于速度要求高，数据被频繁修改的场合。sds通过未使用空间解除了字符串长度和底层数组长度之间的关联。

  • 空间预分配

    当sds对sds进行修改并且sds需要扩展时，程序不仅会为sds分配修改所必须要的空间，而且还会为sds分配额外的未使用空间。

    策略为，若sds长度小于1MB，则分配与len相同大小的未使用空间。即len与free属性相同。若对sds进行修改，长度大于1MB,程序会分配1MB未使用空间。

    在扩容之前，会检测未使用空间是否足够，足够的话直接使用未使用空间而无需进行扩容。

  • 惰性空间释放

    当sds的api需要缩短时，并不立即内存重新分配，而是使用free属性来将这些字节数量记录并等待使用。

2.4二进制安全

为了确保Redis可以使用于不同场景，SDS的API都是二进制安全的，所有的SDS API都会以处理二进制的方式来处理SDS存放在buf数组中的数据，不会对其中的数据做任何限制，过滤和假设。

2.5兼容部分c字符串函数

sds遵循c字符串以空字符结尾的习惯，从而可以利用部分c的库函数