Redis

SDS其实就是C字符串，redis利用一些技巧，使其更快更好。

那么SDS是怎么从char* 到SDS的，其实很巧妙：

通过下面这三个步骤，一个void * sh，就变成了 指定类型的 SDS

1.先声明几种SDS结构体的 类型，成员变量。

2.通过宏定义，将sh 转变为 SDShdr 结构体的指针，并设置指针的头指向SDS结构体的头。

3.在新建SDS的时候，使用结构体给sh指向的空间赋值。

上面是SDS的结构图，可以看到 每个SDS字符串的前面都存储了len 和alloc这两个值，这在大量对SDS进行调整和扩容的时候还是非常有用的。这种情况下获取SDS长度只需要O(1)的时间复杂度。

字符串的拼接操作是使用十分频繁的，在C语言开发中使用strcat方法拼接字符串到末尾。但由于C字符串不记录自身的长度，所似strcat方法会认为用户已经提前分配好足够的内存，而这个条件不成立，就会产生缓冲区溢出，会把其他数据覆盖掉。

解决方案：SDS与C字符串不同，它的自动扩容机制杜绝了缓冲区溢出的可能：当SDS修改时，会先检查 SDS 的空间是否满足修改所需的要求，不满足，则自动扩展空间至所需大小，然后执行修改操作。不需要用户手动操作。

1. 空间预分配策略

   因为 SDS 的空间预分配策略， SDS 字符串在增长过程中不会频繁的进行空间分配。

   SDS被分配的空间，往往是大于他实际占用的空间的，于是在增加SDS长度的时候，并不一定必须对他进行扩容。

   且在对SDS进行扩容的时候，还会对他多分配一些空间。

2. 自动扩容机制总结：

   扩容阶段：
   1、若 SDS 中剩余空闲空间 avail >新增内容的长度 addlen，则无需扩容；
   2、若 SDS 中剩余空闲空间 avail <=新增内容的长度 addlen：
   1)、若新增后总长度 len+addlen < 1MB，则按新长度的两倍扩容；
   2)、若新增后总长度 len+addlen > 1MB，则按新长度加上 1MB 扩容。

   内存分配阶段，需根据扩容后的长度选择对应的 SDS 类型：
   1、若类型不变/或者新类型，则只需通过 s_realloc_usable扩大 buf 数组即可；
   2、若类型变化，则需要为整个 SDS 重新分配内存，并将原来的 SDS 内容拷贝至新位置。

2、惰性空间释放机制
当SDS 字符串缩短时，并不会立即使用内存重分配来回收缩短后多出来的空间，而仅仅更新 SDS 的len属性，多出来的空间供将来使用。

3、释放SDS（类似惰性空间释放）
为了优化性能，SDS 提供了不直接释放内存，而是通过重置len达到清空 SDS 目的的方法SDSclear。将 SDS 的len归零，而buf的空间并未真正被清空，新的数据可以复写，而不用重新申请内存。

//普通的SDSclear（）实际上是将SDS的len设为0，将buf的第一个字符设为空字符。

//真正的释放内存需要调用

C字符串以空字符“”作为结束符号，而SDS实际则是以len判断结束位置。

问题：什么是二进制安全？
回答：通俗地讲，C语言中，用’0’表示字符串的结束，如果字符串本身就有’0’字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则是二进制安全。

另外：C字符串中的字符除了末尾字符为’’外其他字符不能为空字符，否则会被认为是字符串结尾。这限制了C字符串只能保存文本数据，而不能保存二进制数据。而SDS使用len属性的值判断字符串是否结束，所以不会受’’的影响。所以SDS可以方便的保存二进制数据，如图片，视频，压缩文件。

buf的尾部自动追加一个‘’，且不会计算在SDS的len中，这是延续C字符串以空字符串结尾的惯例，方便SDS可以使用string.h库中的函数，如strlen。

（二进制安全与兼容 部分C字符串函数并不矛盾，当SDS存储的是普通的字符串，仍旧可以使用这些函数）

问题：在Redis3.x版本中，不同长度的字符串占用头部是相同的，但如果一字符串很短，则头部会占用更多空间，造成浪费。
解决思路：区分不同长度字符串，优化短字符串的数据结构。
方案：
把字符串区分为三种：
短字符串(长度小于32byte)，len和flag的长度共用1字节即可 低三位为type 高五位为len；
长字符串，用2字节或者4字节表示len 和alloc；
超长字符串，用8字节，表示len和alloc。
用一个type字段为类型标识，但由于只有5种类型，所以用1byte的char类型即可（实际只用到了低三位）。