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

绝地灬酷狼 2022-10-23 14:27 190阅读 0赞

#  一：简单动态字符串的结构 #

## 1：SDS结构体 ##

struct sdshdr {
      //buf已占用的空间长度
      //等于SDS所保存的字符串长度
      int len;
      //buf中剩余的空间长度   
      int free; 
      //字符数组，用于保存字符串
      char but[];  
    }

## 2：SDS数据式例 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

*  free属性值为5，表示这个SDS还有5个字节的未使用空间。
 *  len属性值为5，表示这个SDS保存了一个五字节长的字符串。
 *  buf属性是一个char类型的数组，数组的前五个字节分别保存了‘R’、‘e’、‘d’、‘i’、‘s’五个字符，而最后一个字节则保存了空字符串'\\0'。

# 二：简单动态字符串的优点 #

## 1：常数复杂度获取字符串的长度 ##

相比较与C字符串遍历获取长度，而SDS获取长度只需获取结构体中的len属性即可，将原来获取字符串长度的复杂度从O(N)降低到了O(1)

## 2：杜绝缓冲区溢出 ##

C字符串执行strcat函数的时候，如果忘记在执行之前检查剩余的空间是否足够，则很有可能造成数据溢出到其他位置，导致其他字符串被修改掉了。

如果有两个在内存中紧邻着的C字符串S1和S2，其中S1保存了字符串‘Redis’，S2保存了字符串'MongoDB'，如下图所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1][]

如果有程序员执行strcat(1, "Cluster")，则S1的数据会溢出到S2的内存上，将S2字符串给篡改了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2][]

SDS执行字符串拼接的时候就不会存在这个问题，它在执行之前会先检查剩余空间是否充足，如果不充足则会将空间扩展到执行所需要的大小，然后再执行C语言中的字符串连接函数，这样就不会出现缓冲区溢出的现象

## 3：减少字符串修改时内存重新分配的次数 ##

*  C字符串在执行append拼接函数的时候，则需要进行内存重新分配，避免内存不足造成的缓冲区溢出问题。
 *  C字符串在执行trim截断函数的时候，则需要进行内存重新分配来释放不在使用的内存空间，如果这步忘记操作会造成内存泄漏。

对于SDS而言，设计者利用了空间预分配和惰性释放空间来解决频繁进行内存重新分配的问题。

##   3.1：空间预分配 ##

当执行拼接函数的时候发现内存不空不足，则会进行内存空间预分配，分配的规则如下

*  如果对SDS进行修改之后的长度小于1M，则会分配和len属性值相同的内存空间给free，如S1字符串修改之后的长度为13个字节吗，则free也会分配13个字节的内存空间，而buf数组的实际长度为13+13+1=27字节的长度（1是用来保存空字符串的）
 *  如果对SDS进行修改之后的长度大于等于1M，则程序会分配给free1MB的未使用内存空间，如果SDS修改之后的len属性值为2MB，则free为1MB，而buf数组的实际长度为2MB+1MB+1byte

##   3.2：惰性空间释放 ##

对于SDS执行sdstrim函数的时候，会将释放的内存计入到free中去，等到下次执行sdscat函数的时候这些释放的空间可以派上用场，这样就避免了内存的频繁重新分配。

同时SDS也有对应的函数让我们在有需要的时候去释放SDS的未使用空间，所以不用担心内存浪费的问题。

空间预分配和惰性空间释放都可以很好的避免频繁进行内存重新分配问题。

## 4：二进制安全 ##

C字符串必须符合某种编码（如ASCII），并且除了字符串末尾之外，字符串里面不能包含空字符串，否则会被认为是字符串结尾，这些就限定了C字符串必须是文本，而不能保存想图片，音频，视频，压缩文件这样的二进制数据。

而SDS保存数据是通过二进制进行保存数据的，而且是通过len属性值而不是空字符判断字符串是否结束。这样就可以保证Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。

## 5：兼容部分C字符串函数 ##

SDS中的数据末尾会设置成空字符串，这样就可以使用一部分<string.h>的函数，如strcasecmp()函数，这样就避免了不必要的代码重复。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221023/ecb74b21ad7f4223bd62140c211af998.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1]: /images/20221023/279e270798994a1ebbfe13cb7b0773df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2]: /images/20221023/ab2fcf5952454d9b93421b33c9c6786f.png