Redis设计与实现之SDS

淡淡的烟草味﹌ 2023-03-01 10:51 17阅读 0赞

## 字符串存储规则 ##

> redis没有默认使用c字符串，仅在字符串字面量和使用c字符串。如果字符串为变量时，则使用SDS字符串。

## SDS定义 ##

### sds.h/sdshdr结构 ###

struct __attribute__ ((__packed__)) sdshdr8 {
        uint8_t len; /* 字符串长度 */
        uint8_t alloc; /* 分配内存大小（除去‘\0’） */
        unsigned char flags; /* 标志位（低三位表示类型，其余五位未使用） */
        char buf[]; /* 字符数组 */
    };
    struct __attribute__ ((__packed__)) sdshdr16 {
        uint8_t len; /* 字符串长度 */
        uint8_t alloc; /* 分配内存大小（除去‘\0’） */
        unsigned char flags; /* 标志位（低三位表示类型，其余五位未使用） */
        char buf[]; /* 字符数组 */
    };
    struct __attribute__ ((__packed__)) sdshdr32 {
        uint8_t len; /* 字符串长度 */
        uint8_t alloc; /* 分配内存大小（除去‘\0’） */
        unsigned char flags; /* 标志位（低三位表示类型，其余五位未使用） */
        char buf[]; /* 字符数组 */
    };
    struct __attribute__ ((__packed__)) sdshdr64 {
        uint8_t len; /* 字符串长度 */
        uint8_t alloc; /* 分配内存大小（除去‘\0’） */
        unsigned char flags; /* 标志位（低三位表示类型，其余五位未使用） */
        char buf[]; /* 字符数组 */
    };

如上代码块注释，个人认为，Redis并未完全抛弃C语言字符串，只不过是在C语言字符串的基础上，通过封装其他的属性，构造出一个更加高效的字符串的封装结构，在早些的版本中记录了其长度（实际使用了多少）、剩余空间、以及字符数组，最新的版本3.2.4中，已经对SDS做了一定的改动记录了长度、分配内存大小（除去‘\\0’）、标志位（低三位表示类型，其余五位未使用）、以及字符数组。在3.2.4版本里，redis细化了sdshdr长度值，不同长度的字符串可以选择对应位的sdshdr。

## SDS与C字符串区别 ##

*  **获取字符串长度**

1.  C字符串不记录自己的长度，当需要获取长度的时候，需要遍历整个字符数组，对遇到的所有的字符进行计数，直到遇到空字符为止，执行时间复杂度为O(N)。
2.  SDS字符串保存了自身的长度，当需要获取长度的时候，直接可以获取到，这样把时间复杂度降低到O(1)。设置和更新SDS长度是由SDS的API在执行时自动完成的，使用SDS无须手动修改len属性。

*  **杜绝缓冲区溢出**  
    C语言不记录字符串长度的另一个弊端就是容易造成缓冲区溢出。举个例子，拼接两个字符串：wy和xx

![format_png][]

假设前者为s1后者为s2，那么这里在进行字符串拼接的时候，一旦没有为s1从新分配适合的空间的话，那么拼接后的结果会溢出到s2的空间中去。

SDS在进行字符串拼接的时候，会自行检查是不是内存空间是不是 满足要求，如果不满足的话，自动进行分配，而且在进行分配空间的时候，会实行预先分配的策略。

*  **减少修改字符串时带来的内存重分配次数**  
    C语言字符串在进行字符串的扩充和收缩的时候，都会面临着内存空间的重新分配问题。

1.  字符串拼接会产生字符串的内存空间的扩充，在拼接的过程中，原来的字符串的大小很可能小于拼接后的字符串的大小，那么这样的话，就会导致一旦忘记申请分配空间，就会导致内存的溢出。
2.  字符串在进行收缩的时候，内存空间会相应的收缩，而如果在进行字符串的切割的时候，没有对内存的空间进行一个重新分配，那么这部分多出来的空间就成为了内存泄露。  
    Redis在内存空间分配的问题上进行了优化，主要分为两个过程。
3.  内存预分配  
    内存空间进行分配的时候，预先分配一块多余的空间给当前的字符串对象，使得，在下一次字符串比如拼接的时候，尽可能保证其内存空间的足够用，不需要再去分配内存，这样的话，效率将会大大的提升。  
    额外分配未使用空间数量：  
    1). 如果修改之后SDS的长度小于1MB,那么程序将会分配和当前字符串len相同的空间给该字符串对象。比如说，wy和xx进行合并，这里是4个字符，大小为4，实际的存储大小为5，但是分配的内存空间大小会采用预分配的方式，那么分配后的内存大小为4+4+1=9个字节。  
    2). 如果修改之后的SDS的长度大小大于等于1MB的话，程序分配的内存空间将会为1MB,比如说变化后的字符串对象达到了30M，当他在分配空间的时候只分配1MB空间。那么最终空间大小为30M+1MB+1B.
4.  惰性释放  
    当字符串进行缩短操作的时候，并不立即将空间释放出来，而是，将这部分空间通过free进行标识，本字符串有多少的空余的空间。这样的话，在再次使用时也可以避免分配内存造成的时间开销。  
    当然，Redis中提供了专门的API，需要的时候，会真正的释放这部分空闲的内存。

**二进制安全**  
C字符串必须符合某种编码，除了字符串的末尾外，不能包含空字符，否则会被误认为是字符串的结尾，导致最终读取的字符串是不完整的。这些限制导致了字符串不能用于存放图片、音频、视频等二进制数据，只能存放文本数据。  
但是在Redis中，不是靠空字符来判断字符串的结束的，而是通过len这个属性。那么，即便是中间出现了空字符对于SDS来说，读取该字符仍然是可以的。

![format_png 1][]

*  **C字符串和SDS字符串区别总结**

<table> 
 <thead> 
  <tr> 
   <th>C字符串</th> 
   <th>SDS字符串</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>获取字符串长度复杂度 O(N)</td> 
   <td>获取字符串长度复杂度 O(1)</td> 
  </tr> 
  <tr> 
   <td>API是不安全的，可能造成缓冲区溢出</td> 
   <td>API 安全，不会造成缓冲区溢出</td> 
  </tr> 
  <tr> 
   <td>修改字符串长度N次需要修改N次内存</td> 
   <td>修改字符串长度N次最多需要修改N次内存</td> 
  </tr> 
  <tr> 
   <td>只能保存文本数据</td> 
   <td>可以保存二进制数据</td> 
  </tr> 
  <tr> 
   <td>可以使用所有&lt;string.h&gt;库函数</td> 
   <td>可以使用部分&lt;string.h&gt;库函数</td> 
  </tr> 
 </tbody> 
</table>

[format_png]: /images/20230208/6b94990730fa4fbf99d701c8f35d72a8.png
[format_png 1]: /images/20230208/2987da746cba45b9bf34b55be8c78581.png