redis字符串

文章目录
  1. 1. SDS的定义
  2. 2. SDS与C字符串的区别
    1. 2.1. 常数复杂度获取字符串长度
    2. 2.2. 杜绝缓冲区溢出
    3. 2.3. 减少修改字符串时带来的内存重分配次数
      1. 2.3.1. 空间预分配
      2. 2.3.2. 惰性空间释放
    4. 2.4. 二进制安全
    5. 2.5. 兼容部分C字符串函数
    6. 2.6. SDS API

Redis没有直接使用C语言传统的字符串表示（以空字符串结尾的字符数组），而是自己构建了一种名为动态字符串（simple dynamic string，SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。Redis的数据库里面，包含字符串值的键值对在底层都是用SDS实现的；除此之外，SDS还被用作缓冲区（buffer）：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是有SDS实现的。

SDS的定义

1
2
3
4
5
6
7
8
9
struct sdshdr {
    // 记录buf数组中已使用字节的数量
    // 等于SDS保存的字符串长度
    int len;
    // 记录buf数组中未使用字节的数量
    int free;
    // 字节数组
    char buf[];
};

SDS遵循C字符串一空字符串结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节，以及添加空字符到字符串末尾等操作都是由SDS函数自动完成。遵循空字符结尾这一惯例的好处是，SDS可以直接使用一部分C字符串函数库里的函数。

SDS与C字符串的区别

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

C字符串不记录自身的长度信息，所以为了获取一个C字符串的长度，必须遍历整个字符串，复杂度O（N).

和C字符串不同，SDS在len属性中记录了SDS本身的长度，获取长度复杂度仅为O（1）。

杜绝缓冲区溢出

除了获取长度的负责度高之外，C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出。

1
char *strcat(char *dest, const char *src);

因为不记录自身长度，所以strcat假定执行这个函数时，已经为desc分配了足够多的内存，可以容纳src的所有内容，而一旦这个假设不成立，就会产生缓冲区溢出。

与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改要求，如果不满足，API自动将SDS的空间扩展至所需大小，然后才执行实际的修改操作。所以SDS不会造成缓冲区溢出。

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

因为C字符串不记录自身长度，对一个包含了N个字符的C字符串来说，字符串底层总是一个N+1字节数组。因为C字符串的长度和底层的数组长度自检存在某种关联关系，所以每次增长一个或者缩短一个C字符串，总要对保存这个C字符串的数组进行一次内存重分配操作：

  • 如果是增长操作，需要先通过内存重分类扩展底层数组的空间大小，如果忘记了就会产生缓冲区溢出操作。
  • 如果是缩短操作，需要重新分配来释放不再使用的空间，如果忘了会产生内存泄露。

为了必满C字符串的缺陷，SDS通过未使用空间接触了字符串长度和底层数组长度的关联；通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略

空间预分配

当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会分配修改所必须要的空间，还会为SDS分配额外的未使用空间。

  • 如果修改之后，SDS的长度（len）小于1MB，程序分配和len同样大小的未使用空间。
  • 如果修改之后，SDS的长度大于等于1MB，程序会分配1MB未使用空间。

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即重新分配释放多出来的字节，而是使用free将这些字节数量记录起来，并等待将来使用。

二进制安全

字符串中包含空字符串\0时，C字符串会有问题，SDS不会，因为SDS通过len记录了字符串的长度。

兼容部分C字符串函数

SDS API

  • sdsnew：创建一个包含给定C字符串的SDS，O(N)
  • sdsempy：创建一个空SDS，O(1)
  • sdsfree：释放SDS，O(1)
  • sdslen：返回已使用空间字节数，O(1)
  • sdsavail：返回未使用空间字节数，O(1)
  • sdsdup：创建SDS副本，O(N)
  • sdsclear：清空SDS内容，O(1)
  • sdscat：拼接给定C字符串，O(N)
  • sdscatsds：拼接给定SDS，O(N)
  • sdscpy：将给定C字符串复制到SDS，覆盖原有内容，O(N)
  • sdsgrowzero：用空串扩展SDS到指定长度，O(N)
  • sdsrange：保留给定区间内容，不在区间内被覆盖，O(N)
  • sdstrim：移除SDS中给定C字符串中出现过的字符，O(N^2)
  • sdscmp：比较两个SDS是否相同，O(N)