详解redis数据结构之sds

详解redis数据结构之sds

字符串在redis中使用非常广泛，在redis中，所有的数据都保存在字典（Map）中，而字典的键就是字符串类型，并且对于很大一部分字典值数据也是又字符串组成的。以下是sds的具体存储结构：

从图中可以看出，sds的属性有三个：len、free和buf数组。这里len字段是用来保存sds字符串中所包含字符数目的，free字段则是用来保存buf数组中空余的部分的长度的，而buf数组则是实际用来保存字符串的。比如如下结构保存了“Hello World！”这个字符串：

这里需要注意的是，sds和c字符串一样，需要在字符串结尾加上一个“”表示该字符串的结束。这里这个sds对象的len属性保存了“Hello World!”这个字符串的长度，而free属性保存了数组中空余的位数，buf数组则实际保存了这个字符串，空字符和空余位。

redis使用sds结构而不用c字符串保存字符串的原因有如下几点：

①常数复杂度获取字符串长度

通过读取sds对象的len属性的值我们可以使用O(1)获取sds对象保存的字符串长度，而在c字符串中，我们必须对整个数组进行遍历从而获取字符串的长度，其时间复杂度为O(N)。

②杜绝缓冲区溢出

在c字符串中，比如char *strcat(char *dest, const char *class="lazy" data-src)函数将class="lazy" data-src连接到dest的末尾，但是c字符串假定dest数组中有足够的空余空间来保存class="lazy" data-src数组，如果dest数组长度不够就会造成缓冲区溢出；在sds对象中也提供了类似的函数sds sdscat(sds s, const char *t)和sds sdscatsds(sds s, const sds t)，这两个函数在调用之前会检查目标sds对象s中free属性是否能够保存要连接的字符串的长度，如果不够，就会对目标sds对象扩容，这就保证了sds对象不会造成缓冲区溢出。

③减少修改字符串时内存重分配的次数

在对sds进行修改的时候，redis可以通过“空间预分配”和“惰性空间释放”来保证后续对sds对象的频繁修改而不会造成sds对象的buf数组经常分配空间；而对于c字符串，每次对其进行修改都需要进行一次空间分配和复制操作。

④二进制安全

对于c字符串，由于其判断是否结束的标志是从字符串开始到结尾碰到的第一个“”字符，这就限制了c字符串不能保存像图片、音频、视频、压缩文件等二进制保存的内容；而对于sds对象，由于判断其是否结束的标志是其len属性，也就是说无论在len长度内，buf数组中是否包含“”都不影响redis判断其是否结束。

上面讲到了sds的空间预分配和惰性空间释放，sds通过这两种操作极大的简化了其对字符串的修改和对空间的分配工作。

空间预分配指的是当对一个sds对象进行结构性增加时，比如修改其内容使其增长或者连接另一个字符串到其末尾，sds会预先分配一定的空间以预防未来可能对其进行的修改。如下是redis进行空间预分配的主要代码：

sds sdsMakeRoomFor(sds s, size_t addlen) {

  struct sdshdr *sh, *newsh;

  // 获取 s 目前的空余空间长度
  size_t free = sdsavail(s);

  size_t len, newlen;

  // s 目前的空余空间已经足够，无须再进行扩展，直接返回
  if (free >= addlen) return s;

  // 获取 s 目前已占用空间的长度
  len = sdslen(s);
  sh = (void*) (s-(sizeof(struct sdshdr)));

  // s 最少需要的长度
  newlen = (len+addlen);

  // 根据新长度，为 s 分配新空间所需的大小
  if (newlen < SDS_MAX_PREALLOC)
    // 如果新长度小于 SDS_MAX_PREALLOC 
    // 那么为它分配两倍于所需长度的空间
    newlen *= 2;
  else
    // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
    newlen += SDS_MAX_PREALLOC;
  // T = O(N)
  newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

  // 内存不足，分配失败，返回
  if (newsh == NULL) return NULL;

  // 更新 sds 的空余长度
  newsh->free = newlen - len;

  // 返回 sds
  return newsh->buf;
}

从图中可以看出，当要添加的内容比目标sds对象的free属性要短时直接返回并将要添加的内容添加到目标sds对象的buf数组中即可；当要添加的内容比目标sds对象的free属性要长时，就会计算要添加的内容和sds对象的当前长度的和newlen，如果newlen小于SDS_MAX_PREALLOC也即1M的时候，新创建的buf数组的长度为newlen的两倍，如果newlen大于SDS_MAX_PREALLOC的时候，新创建的buf数组的长度为newlen+SDS_MAX_PREALLOC，即只多分配1M的预留空间。空间预分配保证了sds对象的空余位长度至多为扩张之后字符串长度的1倍，这也就保证了后续对sds对象的修改将尽可能少的分配空间。

惰性空间释放指的是当对一个sds对象进行缩短操作时，其不会直接将buf数组缩短为目标数组的长度，而是只改变sds对象的len属性的值，数组中多余的部分则保存在free属性中，这样就可以保证后续可能的对该sds对象的增长操作不需要重新分配空间。

最后需要进行说明的是，sds对象也和c一样使用“”作为字符串的结尾的原因是redis也是使用c语言编写的，使用“”结尾就可以直接使用部分c函数库中对字符串操作的函数。

通过上面对sds对象的说明可以发现，redis对sds对象的处理极大的减少了字符串处理中可能出现的复杂操作，并且大部分操作基本上都可以在极短的时间内完成，这就保证了redis对字符串处理的高速率。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！