Redis简单动态字符串(Simple Dynamic Strings)学习笔记

柔性数组成员与简单动态字符串sds

柔性数组成员

  • 柔性数组成员(flexible array member)也叫伸缩性数组成员。在C99标准中,结构中的最后一个元素允许是未知大小的数组,这就叫做柔性数组成员,但结构中的柔性数组成员前面必须至少一个其他成员。对一个包含柔性数组成员的结构体执行sizeof运算,返回的大小不包括柔性数组占用的内存。在sds的定义中,结构体成员buf即为柔性数组成员。

简单动态字符串sds

  • Redis内部构建了名为简单动态字符串(sds)的抽象类型,该类型替代了传统的C字符串作为Redis内部的默认字符串表示。其结构体定义如下:
    1
    2
    3
    4
    5
    struct sdshdr {
    int len; // buf已占用长度
    int free; // buf可使用长度
    char buf[]; // 字节数组,表示实际数据
    };

sds与C字符串的对比

sds的劣势

  • sds占用更多空间
    • sds使用两个int成员记录字节数组已占用的长度和可使用的长度
    • 由于内存预分配和缓回收策略,可能有部分空间实际未被数据占用

sds的优势

  • sds头部成员len记录了实际数据的长度,获取字节数组长度的时间复杂度仅为O(1),而获取C字符串的函数strlen的时间复杂度为O(n),对于经常需要获取字节数组长度的场景,sds显然效率更高
  • sds能彻底杜绝C字符串存在的缓冲区溢出问题,当调用方通过api对sds进行修改时,api会先检查sds的空间并根据需要进行空间扩展
  • sds能减少数据变更时引起的内存重分配次数,对于字符串增长操作,api会根据实际情况使用空闲的空间或执行预分配策略,而对于字符串截断操作,api仅更新中止符与结构体成员,并不会立即释放空间
  • sds是二进制安全的,它的buf成员称为字节数组,每个数组元素存储的数据没有任何限制,sds使用len成员记录字节数组的有效长度,而不是依赖空字符来判断字符串是否结束

sds内存分配与回收策略

  • buf成员初始化时,允许指定是否预留数据空间,同时它需要额外1个字节存放空字符(‘\0’)
  • 每次sds执行增长操作的时候,api会预先计算修改之后的长度(即成员len的值)
    • 若len小于1024字节,则预分配和len属性同样大小的未使用空间,这时成员len和成员free的值是相同的
    • 若len大于等于1024字节,则预分配1024字节的未使用空间,这时成员free的值是1024
  • 每次sds执行缩短操作的时候,api不立即回收多出来的字节,仅更新成员len和成员free的值,以待后续使用,调用方可以在需要时调用api真正释放sds的未使用空间

sds主要API

  • sdsnew 创建一个包含给定的C字符串的sds
  • sdsempty 创建一个不包含任何内容的空sds
  • sdsfree 释放给定的sds
  • sdslen 获取sds的已使用长度
  • sdsavail 获取sds的未使用长度
  • sdsdup 创建一个给定sds的副本
  • sdsclear 清空sds保存的字符串内容
  • sdscat 将给定的C字符串拼接至sds的末尾
  • sdscatsds 将给定的sds拼接到另一个sds的末尾
  • sdscpy 将给定的C字符串复制到sds里面,覆盖sds原有的数据
  • sdsgrowzero 用空字符串将sds扩展至指定长度
  • sdsrange 保留sds给定区间内的数据,不在区间内的数据会被覆盖或清除
  • sdstrim 从sds两端分别移除所有在C字符串中出现的字符
  • sdscmp 比较两个sds的字节数组

参考资料