介绍 SDS，Redis 为什么要使用 SDS 而不是 C 字符串

Question

@[toc] SDS 的定义 int len ：buf 中已使用空间的长度 int free ： buf 中剩余可用空间的长度 （这个字段可以说是 SDS 的灵魂所在） char buf[] ：数据空间（SDS 遵循 C 字符串以空字符结尾的惯例） Redis 为什么要使用 SDS 而不是 C 字符

Accepted Answer

@[toc] SDS 的定义 int len ：buf 中已使用空间的长度 int free ： buf 中剩余可用空间的长度（这个字段可以说是 SDS 的灵魂所在） char buf[] ：数据空间（SDS 遵循 C 字符串以空字符结尾的惯例） Redis 为什么要使用 SDS 而不是 C 字符串？主要有 5 点： 1） O(1) 时间复杂度获取字符串长度 C 字符串：获取一个 C 字符串的长度的时间复杂度是 O(N) SDS：SDS 在 len 属性中记录了 SDS 本身的长度，所以获取一个 SDS 长度的复杂度仅为O(1) 2）杜绝缓冲区溢出（buffer flow） C 字符串：举个例子，C 语言中的 strcat 函数可以将 src 字符串中的内容拼接到 dest 字符串的末尾：strcat(dest, src)。因为 C 字符串不记录自身的长度，所以 strcat 假定用户在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立时，就会产生缓冲区溢出假设程序里有两个在内存中紧邻着的C字符串s1和s2，其中 s1 保存了字符串 "Redis"，而 s2 则保存了字符串 "MongoDB" 如果一个程序员执行：strcat(s1, " Cluster"); 却忘了在执行 strcat之前为 s1 分配足够的空间，那么在 strcat 函数执行之后，s1 的数据将溢出到 s2 所在的空间中，导致 s2 保存的内容被意外地修改 SDS：SDS 的【空间预分配策略】完全杜绝了发生缓冲区溢出的可能性（详细解释见下文） 3）减少修改字符串时带来的内存重分配次数 C 字符串：因为 C 字符串并不记录自身的长度，所以对于一个包含了 N 个字符的 C 字符串来说，这个 C 字符串的底层实现总是一个 N+1 个字符长的数组（额外的一个字符空间用于保存空字符）。所以每次增长或者缩短一个C字符串，程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作【缓冲区溢出】：如果程序执行的是增长字符串的操作，比如拼接操作（append），那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小——如果忘了这一步就会产生缓冲区溢出【内存泄漏】：如果程序执行的是缩短字符串的操作，比如截断操作（trim），那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间——如果忘了这一步就会产生内存泄漏内存重分配涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作在一般程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重分配是可以接受的但是 Redis 作为缓存，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的话，会对性能造成影响 SDS：SDS 通过未使用空间（free）解除了字符串长度和底层数组长度之间的关联【空间预分配】：用于优化 SDS 的字符串增长操作，防止缓冲区溢出，并减少字符串增长时的空间重分配的次数当 SDS 的 API 对一个 SDS 进行修改，并且需要对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间 free 如果对 SDS 进行修改之后，SDS 的长度（也即是 len 的值）将 < 1MB，那么程序分配和 len 属性同样大小的未使用空间，这时 SDS.len = free 如果对 SDS 进行修改之后，SDS 的长度将 = 1MB，那么程序会分配 1MB 的未使用空间【惰性空间释放】防止内存泄漏：用于优化 SDS 的字符串缩短操作，防止内存泄露，并减少字符串缩短时的空间重分配的次数