1_1_Redis设计与实现读书记-SDS
发布于 2022年 01月 20日 20:31
简单动态字符串（SDS）
Redis是使用C语言实现的，没有使用C语言传统的字符串表示，而是使用自己构建的一种简单动态字符串（simple dynamic string， SDS）的抽象类型，并用作Redis的默认字符串表示。依然遵守了C语言中以'\0'结尾的惯例。
除了保存字符串值之外，还被作用缓冲区（buffer）：AOF模块中的AOF缓冲区一级客户端状态中的输入缓冲区，都是由SDS实现。
1. SDS的结构：
**注：**在保存空字符（'\0'字符）空间不计算在SDS的len属性中，为空字符分配额外的1字节空间。对于空字符到字符串末尾等操作，均由SDS函数自动完成。遵循这一惯例，好处是SDS可以直接重用一部分C字符创函数库中的函数。
SDS与C字符串的区别
1. 常数复杂度获取字符串长度
C字符串不记录自身长度信息，为了获取一个C字符串的长度，必须遍历整个字符串，整个操作的复杂度为O(N)。
SDS在len属性中记录了SDS字符串本身的长度，获取长度的操作复杂度仅为O(1)。SDS的长度操作由API自动完成，无须进行任何手动修改长度的工作。
2. 杜绝缓冲区溢出
C字符串容易造成缓冲区溢出（buffer overflow）。例如：在C字符串进行拼接时，源字符串长度未分配足够多的内存，就会产生缓冲区溢出的问题。
SDS在字符串拼接之前则会先判断源字符串的内存是否足够。不够则分配足够的空间，从而杜绝了发生缓冲区溢出的肯能性。
3. 减少修改字符串时带来的内存重分配次数
C字符串底层实现总是一个N+1长度的数组(额外的一个字符空间用于保存空字符)。若进行拼接操作，在执行这个操作前，需要通过内存重分配来扩展底层数组的空间大小，否则会产生缓冲区溢出。若进行截断操作，需要通过内存重分配来释放字符串不再使用的空间，否则会产生内存泄漏。
SDS中buf数组的长度 不一定就是字符数量加一，数组中可以包含未使用的字节，数量则保存在free属性中。
3.1 空间预分配
用于优化SDS的字符串增长操作：当SDS进行空间扩展时，程序不仅会为SDS分配必须的空间，还会分配额外的未使用空间。
1. 如果SDS的长度(len的属性值)小于1MB,则会分配和len同样大小的未使用free空间。此时实际长度为：len + free + 1 字节
2. 如果SDS的长度大于等于1MB，则会分配1MB的未使用空间。
通过空间的预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。
3.2 惰性空间释放
用户优化SDS的字符串的缩短操作：当SDS进行空间缩短时，程序不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将多余的字节记录起来，等待将来使用。
惰性释放的策略，SDS避免了缩短字符串时需要的内存重分配操作，并为将来的增长提供了优化。也可以真正地释放未使用空间，不必担心会造成的内存浪费。
4. 二进制安全
避免了C字符串中，读取到空字符('\0')结束读取的问题。SDS结构中的buf数组，都会以二进制的方式进行处理，它保存的是一些列的二进制数据。SDS中使用len属性值判断字符串是否结束。Redis不仅可以存文本数据，还能保存任意格式的二进制数据。
5. 兼容部分C字符函数
遵循C字符的要求，可以复用C中的一些函数，避免了不必要的代码重复。