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

Redis没有使用C语言传统的字符串表示(以空字符\0结尾的字符数组)，而是使用简单动态字符串(Simple Dynamic String， SDS)的抽象类型作为字符串的表示。

struct sdshdr {
  //记录 buf 数组中已使用的字节数量， 即sds保存的字符串长度
  int len；
  //记录 buf 数组中未使用的字节的数量
  int free;
  //字节数组，用于存储字符串
  char buf[];
}

SDS遵循C字符串以空字符结尾惯例，保存空字符的1个字节空间不计算在SDS的len属性里边。并且为空字符分配空间等操作均由SDS函数自动完成。好处是SDS可以直接重用一部分C字符串函数库里的函数。

C语言使用长度N+1的字符数组存储长度为N的字符串，最后一个元素是空字符\0。如下图所示：

C语言使用的字符串方式比较灵活，不能满足Redis对字符串在安全性、效率以及功能方面的要求。

设置和更新SDS长度的工作由SDS的API在执行时自动完成，使用SDS时无需手动干预。

通过使用SDS而不是C字符串，Redis获取字符串长度所需的复杂度从O（N）降低到O（1），确保获取字符串长度不会成为Redis性能瓶颈。

C语言不记录自身长度的另一个问题是容易造成缓冲区溢出。例如 strcat 函数是将src字符串拼接到dest字符串的末尾

1	char strcat(char dest, char *src);

如果在拼接时，dest没有足够多的内存可用，就会造成缓冲区溢出。

SDS在空间分配策略完全杜绝了缓冲区溢出的可能性。当SDS的API需要怼SDS进行修改时，API会检查SDS的空间是否满足修改所需的要求。如果不满足的话，API会自动将SDS空间扩展至执行修改所需的大小，然后再进行实际的修改操作。

C字符串在执行修改时，每次总要对保存字符的数组进行内存重新分配。（如果执行拼接操作，则需要重新分配空间，如果没有分配则会出现溢出；如果执行缩短操作，需要释放空间，如果不释放则会产生内存泄露）。

Redis SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。

空间预分配
- 当使用API对SDS进行空间扩展时，程序不仅会为SDS分配修改所必须的空间，还会分配额外未使用的空间。如果SDS 字符串长度（len的值）小于1M，那么程序将分配同len一样大小的未使用空间（len 和 free 值相同）；当SDS进行修改后，SDS的长度大于等于1M，那么程序会分配1M的未使用空间。通过空间预分配策略，Redis可用减少连续执行字符串增长操作所需的内存分配次数。
惰性空间释放
- 惰性空间释放用于优化SDS的字符串端操作；当SDS的API需要缩短SDS字符串时，程序并不是立即使用内存重新分配来回收多余的字节。通过惰性空间释放策略，SDS避免了缩短字符串时所需的内存重新分配操作，并为将来的增长操作提供优化。SDS也会提供响应的API，在需要的时候真正的释放SDS未使用的空间，不用担心内存浪费。

C字符串中的字符必须符合某种编码，且不能出现空字符\0。这些限制使得C字符串只能存储文本数据，不能存储图片、音视频、文件等二进制数据。

Redis SDS不仅可以存储文本数据，还可以存储任意格式的二进制数据。

虽然SDS的API都是二进制安全的。但它们一样遵循C字符串以空字符结尾的惯例。这样SDS可以在有需要重用C 的 string.h 函数库，避免不必要的代码重复。