← 返回学习路线

SYSTEM

字符串

Java基础字符串system
src/content/notes/system/字符串.md

数据结构

字符串

SDS

Redis 构建了简单动态字符串(SDS)的数据类型,作为 Redis 的默认字符串表示,包含字符串的键值对在底层都是由 SDS 实现

struct sdshdr {
    // 记录buf数组中已使用字节的数量,等于 SDS 所保存字符串的长度
    int len;
    
	// 记录buf数组中未使用字节的数量
    int free;
    
    // 【字节】数组,用于保存字符串(不是字符数组)
    char buf[];
};

SDS 遵循 C 字符串以空字符结尾的惯例,保存空字符的 1 字节不计算在 len 属性,SDS 会自动为空字符分配额外的 1 字节空间和添加空字符到字符串末尾,所以空字符对于 SDS 的使用者来说是完全透明的


对比

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

  • C 字符串不记录自身的长度,获取时需要遍历整个字符串,遇到空字符串为止,时间复杂度为 O(N)
  • SDS 获取字符串长度的时间复杂度为 O(1),设置和更新 SDS 长度由函数底层自动完成

杜绝缓冲区溢出:

  • C 字符串调用 strcat 函数拼接字符串时,如果字符串内存不够容纳目标字符串,就会造成缓冲区溢出(Buffer Overflow)

    s1 和 s2 是内存中相邻的字符串,执行 strcat(s1, " Cluster")(有空格):

  • SDS 空间分配策略:当对 SDS 进行修改时,首先检查 SDS 的空间是否满足修改所需的要求, 如果不满足会自动将 SDS 的空间扩展至执行修改所需的大小,然后执行实际的修改操作, 避免了缓冲区溢出的问题

二进制安全:

  • C 字符串中的字符必须符合某种编码(比如 ASCII)方式,除了字符串末尾以外其他位置不能包含空字符,否则会被误认为是字符串的结尾,所以只能保存文本数据
  • SDS 的 API 都是二进制安全的,使用字节数组 buf 保存一系列的二进制数据,使用 len 属性来判断数据的结尾,所以可以保存图片、视频、压缩文件等二进制数据

兼容 C 字符串的函数:SDS 会在为 buf 数组分配空间时多分配一个字节来保存空字符,所以可以重用一部分 C 字符串函数库的函数


内存

C 字符串每次增长或者缩短都会进行一次内存重分配,拼接操作通过重分配扩展底层数组空间,截断操作通过重分配释放不使用的内存空间,防止出现内存泄露

SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联,在 SDS 中 buf 数组的长度不一定就是字符数量加一, 数组里面可以包含未使用的字节,字节的数量由 free 属性记录

内存重分配涉及复杂的算法,需要执行系统调用,是一个比较耗时的操作,SDS 的两种优化策略:

  • 空间预分配:当 SDS 需要进行空间扩展时,程序不仅会为 SDS 分配修改所必需的空间, 还会为 SDS 分配额外的未使用空间

    • 对 SDS 修改之后,SDS 的长度(len 属性)小于 1MB,程序分配和 len 属性同样大小的未使用空间,此时 len 和 free 相等

      s 为 Redis,执行 sdscat(s, " Cluster") 后,len 变为 13 字节,所以也分配了 13 字节的 free 空间,总长度变为 27 字节(额外的一字节保存空字符,13 + 13 + 1 = 27)

    • 对 SDS 修改之后,SDS 的长度大于等于 1MB,程序会分配 1MB 的未使用空间

    在扩展 SDS 空间前,API 会先检查 free 空间是否足够,如果足够就无需执行内存重分配,所以通过预分配策略,SDS 将连续增长 N 次字符串所需内存的重分配次数从必定 N 次降低为最多 N 次

  • 惰性空间释放:当 SDS 缩短字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用 free 属性将这些字节的数量记录起来,并等待将来复用

    SDS 提供了相应的 API 来真正释放 SDS 的未使用空间,所以不用担心空间惰性释放策略造成的内存浪费问题