定义

简单动态字符串（SDS）

1
2
3
4
5
6
7
8
struct sdshdr {
    // buf 中已占用空间的长度
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[];
};

用SDS表示 “Redis” 字符串，其中：

  • free：值为0，表示该SDS没有任何未分配的空间
  • len：值为5，表示该SDS保存了一个五字节长的字符串
  • buf：是 char 类型的数组，表示存储的字符串，其中最后一个子节保存了空字符 \0

SDS与C字符串

获取字符串长度

由于C字符串并不记录自己的长度信息，所以为了获取一个C字符串的长度，程序必须遍历这个字符串，直到遇到空字符 \0 为止，这个操作的时间复杂度为 O(n)

与C字符串不同，SDS在新增或者更新的时候就会改变 len 的值来记录当前字符串的长度，获取字符串长度直接读取 len 即可，因此复杂度为 O(1)，保证了 STRLEN 的性能

杜绝缓冲区溢出

在函数库<string.h> 中的 strcat 函数可以将字符串 src 中的内容拼接到另一个字符串 dest 的末尾 char *strcat(char *dest, const char *src);

假设有两个字符串 S1="Redis" 和字符串 S2="MongoDB"，并且S1和S2在内存中的地址是相邻的

此时调用 strcat(s1,"Cluster");，想在S1后追加字符串”Cluster”，但是没有为S1分配组够的空间，就会导致S1的数据溢出到S2中，导致S2的数据意外被修改，如图

而SDS的空间分配策略则杜绝了这种缓冲区溢出的情况：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出问题。

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

1. 空间预分配

对于一个长度为N的字符串，C串会为其分配N+1长度字符数组，因此每次字符串需要增长或者缩短时，程序总要为C串重新分配内存。倘若要频繁的操作C串，可能就会导致出现频繁的内存分配操作，对于程序的性能会有一定的影响

Redis是一个对性能要求十分高的一个中间件。对此，当字符空间不足时，SDS会额外的分配未使用空间，而不需要每次增长字符串长度的时候都重新分配空间。相当于使用部分额外的空间来换取内存分配的时间

字符修改后，对于额外空间的数量有下列公式计算

  • 如果 len < 1M，则程序会分配同样大小的额外空间，此时len == free

  • 如果 len >= 1M，则程序会分配 1M 的额外空间

通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

2. 惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作：当SDS需要缩短保存的字符串的时候，程序并不会立即使用内存重分配来回收多余的字节，而是使用 free 属性来记录多余的字节，以用来之后可能会出现的增长字符串的操作提供一定的空间。

与此同时，SDS也提供了相应的API，让我们可以在有需要时，真正地释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

二进制安全

C串中的字符必须要符合某种编码（比如ASCII），并且除了字符末尾外字符中不能包含空字符\0，否则空字符会被程序误认为是字符串结尾。如图，假设图中是一个连续的字符串，而在读取的时候只能读取到 “Redis” 而无法读取到 “Cluster”

而在SDS结构中，读取字符串不是按照空字符\0来做判断，而是依据 len 属性来决定字符的长度，因此不会出现上述的问题

不仅能够存储文本数据，SDS也能够保证安全的存储二进制数据，为了确保Redis可以适用于不同的场景，SDS的API都是二进制安全的，所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。

通过使用二进制安全的SDS，而不是C字符串，使得Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。

总结

C串 SDS
获取字符串长度的复杂度为O(n) 获取字符串长度的复杂度为O(1)
API是不安全的，可能会造成缓冲区溢出 API是安全的，不会造成缓冲区溢出
修改字符串长度必然需要重新分配内存 修改字符串长度不一定要重新分配内存
只能保存文本数据 可以保存文本或者二进制数据

参考 《Redis设计与实现》