Redis之字符串

SDS

Redis底层并没有使用C语言的传统字符串(以空字符结尾的字符数组),而是自定义了一种简单的动态字符串类型(SDS)

在Redis里,C字符串只会作为字符串字面量用在一些无需对字符串值进行修改的地方,比如打印日志。其余地方使用的都是SDS

比如

set msg "hello world"

Redis将在数据库中创建一个键值对

  • 键是一个“msg”的SDS
  • 值是一个“hello world”的SDS

SDS结构

struct sdshdr{
  //记录buf数组中已使用的字节的数量 ,不包含'\0'
  int len;
  //记录buf数组中未使用的字节的数量
  int free;
  //字节数组,用于保存字符串
  char buf[];
}

Redis之字符串

SDS遵循C字符串以空字符结尾的惯例,保存空字符'\0'的1字节空间不计算在len长度中,并且添加空字符到末尾的操作都是由SDS函数自动完成的,这个空字符对用户来说是完全透明的,可以当不存在。

为什么要以空字符结尾?

主要是为了复用c语言中关于字符串的一些函数。

SDS的优势

  • 常数时间复杂度获取字符串的长度

    C字符串不记录字符串长度,获取长度需要遍历整个字符串,时间复杂度O(N),而SDS的时间复杂度为O(1)

  • 杜绝缓冲区溢出

    C字符串容易造成缓冲区溢出,假设我们现在想在字符串s1后面拼接一个字符串,如果没有给字符串s1分配足够的内存,就会造成缓冲区溢出的情况。而SDS由于存储了字符串的长度和空闲空间的大小,因此很容易检查有没有足够的空间用来拼接字符串,如果没有则会自动扩展空间。

  • 减少修改字符串带来的内存重分配

    由于C字符串不存储字符串的长度信息,因此C字符串的底层实现总是N+1个字符长度的数组。在我们每次增长或者缩短字符串时,都要对底层数组进行内存重分配。在Redis中修改字符串是一件特别频繁的事情,因此Redis通过未使用空间free采用了两种优化策略

    • 空间预分配。

      当对一个SDS进行空间扩展时,不仅为SDS分配需要的空间还会额外分配未使用的空间。(如果对SDS修改后,len小于1MB,则额外分配len大小的未使用空间,如果len>1MB则分配1MB的未使用空间)

    • 惰性空间释放

      当缩短一个SDS时,并不立即回收空间,而是使用free记录起来

  • 二进制安全

    C语言智能保存文本数据,且不能含有空格,因为会自动将空格当成字符串结束的标志。而SDS可以处理文本或者二进制数据,也能记录空格,通过len判断字符串结束

上一篇:Redis 数据结构(一)—— 简单动态字符串(SDS 和 C字符串的区别)


下一篇:Android TextView自动换行文字排字参差不齐的原因及处理