Redis 数据结构之SDS

简单动态字符串

为了实现对于字符串的高效操作，Redis 自己构建的一种名为简单动态字符串（SDS）的抽象数据结构。

1、SDS 数据结构

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

2、SDS 与 C字符串的优缺点

• 常数复杂度获取字符串长度；

  SDS 字符串长度的复杂度为O(1)，而C字符串长度需要遍历，复杂度为O(n);

• 避免缓冲区溢出；

  当对SDS进行修改时，API会检查SDS 的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作；

• 减少修改字符串时带来的内存分配次数

  对于C字符串来说，如果修改字符串的长度，都需要重新执行内存分配操作；但是对于Redis数据库来说，如果频繁执行内存分配/释放操作，必然会对性能产生一定影响。为了避免C字符串的缺陷，SDS采用了空间预分配和惰性空间释放两种优化策略。

  • 空间预分配

    它主要解决字符串增长的操作，即通过API对增加SDS的长度时，它不仅会分配实际所需的长度，除此之还会额外分配一块未使用的内存，以便下次直接使用，无需重新分配内存，对于分配的额外内存有一下两种策略：

    • 如果对SDS修改后，它的长度小于1MB，那么程序会分配相同大小（和len长度一致）的空间来作为未使用的空间（完成之后len=free，此时总大小为2*len）；
    • 如果对于SDS修改后大于1MB，那么程序只会分配1MB的内存给未使用的空间（此时SDS总长度为len+1MB）；

    通过上述优化，对于N次SDS的修改，分配内存的操作由N次变为至多N次。

  • 惰性空间释放

    主要解决字符串的缩短操作，即当SDS的API缩短字符串时，缩小的空间不会立刻释放，而是暂时作为未使用区，以便后续增长时再次使用。同时，SDS提供了相应的API，以便我们在真正使用内存时，通过API真正的释放SDS的未使用空间。

  基于SDS上面的两个特性，我们可以得出如下结论：SDS在分配/释放空间方面的优化也提升了Redis的速度，但与此同时，如果有频繁操作比较大的字符串时，会对Redis的内存空间有一定浪费，同时在分配/释放内存的性能上也会有所损失。

• 二进制安全

  对于C字符串来说，字符串中不能包含空字符，否则最先被程序读入的空字符串被误认为是字符串结尾，这使得C字符串只能保存文本数据，而不能保存图片、音视频等二进制文件。对于SDS来说，所有SDS都会以处理二进制的方式来处理SDS保存在buf数组中的内容，程序不会对里面的内容做任何限制。

• 兼容部分C字符串函数

  SDS末尾设置空字符的操作使得它可以和部分C字符串函数兼容。