Redis-简单动态字符串(SDS)

引言：没有直接使用C语音的传统字符串表示，即：以空字符串结尾的字符数组，以下简称C字符串。而是自己构建名为SDS（simple dynamic string）的抽象类型。

`为什么Redis使用SDS而不是C字符串？`

基于对字符串的安全性、效率以及功能方面的要求，C字符串不能满足。
SDS具有以下优点：

常数复杂度获取字符串长度 - C字符串不记录自身长度
杜绝缓冲区溢出 - SDS会根据长度检查空间，自动扩容
注：上面2点，是由于C字符串不记录自身长度导致的。
减少修改字符串长度时所需的内存重分配次数
在一般程序中，每次修改字符串长度时，都会执行一次内存重新分配。SDS通过“未使用空间”，解除了字符串长度和底层数组长度的关联，并实现空间预分配和惰性空间分配释放两种优化策略。
二进制安全 - SDS API以处理二进制的方式来处理SDS存放在buf数组的数据，
兼容部分C字符串函数

SDS用途

保存数据库中字符串值
用作缓冲区：AOF模块中的AOF缓冲区以及客户端状态中的缓冲区

数据结构

在3.2版本以前SDS只有一种数据结构，到了3.2版本以后SDS根据存储的内容会选择不同的数据结构，以到达节省内存的效果！

注：attribute ((packed))这个声明就是用来告诉编译器取消内存对齐优化，按照实际的占用字节数进行对齐。
但是内存对齐怎么办呢，不能为了一点内存大大拖慢cpu的寻址效率啊？redis 通过自己在malloc等c语言内存分配函数上封装了一层zmalloc，将内存分配收敛，并解决了内存对齐的问题。

在3.2以后的版本，SDS分为了5种数据结构，分别应对不同长度的字符串需求，具体的类型选择如下。

说明：由于sdshdr5的只用来存储长度为32字节以下的字符数组，因此flags的5个bit就能满足长度记录，加上type所需的3bit，刚好为8bit一个字节，因此sdshdr5不需要单独的len记录长度，并且只有32个字节的存储空间，动态的变更内存余地较小，所以 redis 直接不存储alloc。
sdshdr8内部结构如下：

len ：记录当前字节数组的长度（不包括\0），使得获取字符串长度的时间复杂度由O(N)变为了O(1);
alloc：记录了当前字节数组总共分配的内存大小（不包括\0）;
flags：记录了当前字节数组的属性、用来标识到底是sdshdr8还是sdshdr16等;
buf：一个字节数组,保存了字符串真正的值以及末尾的一个\0;

为什么遵循\0字符结尾这一惯例？

SDS可以直接重用一部分C字符串函数库里面的函数，即：buf末尾的\0是为了复用string.h中部分字符串操作函数。

优化策略

空间预分配

SDS字符串在空间不够,重新分配内存时。采用空间预分配:

内存的预分配策略主要有两种：

拼接后的字符串长度不超过1M，分配两倍的内存
拼接够的字符串长度超过1M，多分配1M的内存
如果新的字符串长度超过了原有字符串类型的限定那么还会涉及到一个重新生成sdshdr的过程。还有一个细节需要注意，由于sdshrd5并不存储alloc值，因此无法获取sdshrd5的可用大小，如果继续采用sdshrd5进行存储，在之后的拼接过程中每次都还是要进行内存重分配。因此在发生拼接行为时，sdshrd5会被直接优化成sdshrd8。

设计思想：将原本N次字符串拼接需要N次内存重新分配的次数优化到最多需要N次，是典型的空间换时间的做法。