August's Box

Redis设计与实现笔记-章2.简单动态字符串

Redis实现了一种简单动态字符串(simple dynamic string, SDS)来作为默认的字符串表示,代替了C语言里传统的字符串。C语言里传统的字符串仅仅作为const string使用,如打印日志时使用的message。

SDS的定义

sds.h/sdshdrlink
1
2
3
4
5
struct sdshdr {
int len; //记录buf已使用数量
int free; //未使用数量
char buf[];
}

根据SDS的定义我们知道,相比于传统的字符串,sdshdr额外存储了len和free两个字段。why?

  • get len in O(1)
  • avoid buffer overflow,避免缓冲区溢出,SDS修改之前会check,不够时会扩展buf的空间
  • 减少修改字符串带来的内存重分配,SDS会通过空间预分配和惰性空间释放来优化字符串的修改
    1. 空间预分配(sdsMakeRoomFor, then sdsIncrLen),如果空余空间足够的话不予分配;所需长度(addlen+len)小于SDS_MAX_PREALLOC(1M)时,分配长度为所需长度double;所需长度大于等于SDS_MAX_PREALLOC时,分配长度为所需长度+SDS_MAX_PREALLOC。通过预分配可以减少分配次数。
      sds.clink
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      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);
      I
      // 内存不足,分配失败,返回
      if (newsh == NULL) return NULL;
      // 更新 sds 的空余长度
      newsh->free = newlen - len;
      // 返回 sds
      return newsh->buf;
      }
    2. 惰性空间释放,优化SDS字符串缩短操作,不会真的释放空间,而是通过更新free和len字段记录空间使用情况。另外,SDS还提供API真正释放未使用的空间(sdsRemoveFreeSpace),不用担心内存浪费。
  • 二进制安全,C里面字符串里面不能包含空格,对于空格会认为是字符串的结束。SDS里面API读取数据是以二进制的形式来处理的,字符长度是通过len来获取而不是通过结束字符,所以SDR可以保存任意格式的二进制数据,图片,音频,压缩文件等。
  • 兼容C字符串函数,work on buf字段 using string.h

    总结

C字符串 SDS
获取字符串长度的复杂度为 O(N) 。 获取字符串长度的复杂度为 O(1) 。
API 是不安全的,可能会造成缓冲区溢出。 API 是安全的,不会造成缓冲区溢出。
修改字符串长度 N 次必然需要执行 N 次内存重分配。 修改字符串长度 N 次最多需要执行 N 次内存重分配。
只能保存文本数据。 可以保存文本或者二进制数据。
可以使用所有 库中的函数。 可以使用一部分 库中的函数。

SDS 主要操作API

函数 作用 时间复杂度
sdsnew 创建包含给定字符串的SDS O(N),N为字符串长度
sdsempty 创建空字符串的SDS O(1)
sdsfree 释放给定的SDS O(N),N为释放SDS字符串长度
sdslen 返回给定SDS已使用空间字节数 O(1),直接读len字段
sdsavail 返回给定SDS可用空间字节数 O(1),直接读free字段
sdsdup 创建给定SDS的副本,copy O(N),N为给定SDS长度
sdsclear 清空SDS内容 O(1),惰性释放
sdscat 拼接给定字符串到SDS末尾 O(N),N为给定字符串长度
sdscatsds 拼接给定SDS到SDS末尾 O(N),N为给定SDS长度
sdscpy 将给定字符串复制到SDS里面,覆盖 O(N),N为字符串长度
sdsgrowzero 用空字符串扩充SDS到指定长度 O(N),N为新增长度
sdsrange 保留SDS给定区间的数据,清除区间外的数据 O(N),N为保留区间长度
sdstrim 去除SDS两端出现在给定字符串内的字符 O(M*N),M为SDS长度,N为字符串长度
sdscmp 对比两个SDS是否相同 O(N),N为两个SDS中较短的一个