sds 的用途

Sds 在 Redis 中的主要作用有以下两个：

1. 实现字符串对象（StringObject）；
2. 在 Redis 程序内部用作 char* 类型的替代品；

以下两个小节分别对这两种用途进行介绍。

redis> SET book "Mastering C++ in 21 days" 
OK  
redis> GET book 
"Mastering C++ in 21 days" 

redis> SADD nosql "Redis" "MongoDB" "Neo4j" 
(integer) 3  
redis> SMEMBERS nosql 
1) "Neo4j" 
2) "Redis" 
3) "MongoDB" 

Redis 中的字符串

在 C 语言中，字符串可以用一个 \0 结尾的 char 数组来表示。

比如说， hello world 在 C 语言中就可以表示为 "hello world\0" 。

这种简单的字符串表示在大多数情况下都能满足要求，但是，它并不能高效地支持长度计算和追加（append）这两种操作：

• 每次计算字符串长度（strlen(s)）的复杂度为 θ(N) 。
• 对字符串进行 N 次追加，必定需要对字符串进行 N 次内存重分配（realloc）。

在 Redis 内部， 字符串的追加和长度计算并不少见， 而 APPEND 和 STRLEN 更是这两种操作在 Redis 命令中的直接映射， 这两个简单的操作不应该成为性能的瓶颈。

另外， Redis 除了处理 C 字符串之外， 还需要处理单纯的字节数组， 以及服务器协议等内容， 所以为了方便起见， Redis 的字符串表示还应该是二进制安全的： 程序不应对字符串里面保存的数据做任何假设， 数据可以是以 \0 结尾的 C 字符串， 也可以是单纯的字节数组， 或者其他格式的数据。

考虑到这两个原因， Redis 使用 sds 类型替换了 C 语言的默认字符串表示： sds 既可以高效地实现追加和长度计算， 并且它还是二进制安全的。

typedef char *sds; 
  
struct sdshdr {     
 // buf 已占用长度     
int len;      
// buf 剩余可用长度     
int free;      
// 实际保存字符串数据的地方     
char buf[]; 
}; 

struct sdshdr {     
len = 11;     
free = 0;    
 buf = "hello world\0";  
// buf 的实际长度为 len + 1
 }; 

优化追加操作

在前面说到过，利用 sdshdr 结构，除了可以用 θ(1) 复杂度获取字符串的长度之外，还可以减少追加(append)操作所需的内存重分配次数，以下就来详细解释这个优化的原理。

为了易于理解，我们用一个 Redis 执行实例作为例子，解释一下，当执行以下代码时， Redis 内部发生了什么：

redis> SET msg "hello world" 
OK  
redis> APPEND msg " again!" 
(integer) 18  
redis> GET msg 
"hello world again!" 

首先， SET 命令创建并保存 hello world 到一个 sdshdr 中，这个 sdshdr 的值如下：

struct sdshdr {     
len = 11;     
free = 0;     
buf = "hello world\0";
 } 

当执行 APPEND 命令时，相应的 sdshdr 被更新，字符串 " again!" 会被追加到原来的 "hello world" 之后：

struct sdshdr {     
len = 18;     
free = 18;     
buf = "hello world again!\0                  ";     
// 空白的地方为预分配空间，共 18 + 18 + 1 个字节 
} 

注意， 当调用 SET 命令创建 sdshdr 时， sdshdr 的 free 属性为 0 ， Redis 也没有为 buf 创建额外的空间 —— 而在执行 APPEND 之后， Redis 为 buf 创建了多于所需空间一倍的大小。

在这个例子中， 保存 "hello world again!" 共需要 18 + 1 个字节， 但程序却为我们分配了 18 + 18 + 1 = 37 个字节 —— 这样一来， 如果将来再次对同一个 sdshdr 进行追加操作， 只要追加内容的长度不超过 free 属性的值， 那么就不需要对 buf 进行内存重分配。

比如说， 执行以下命令并不会引起 buf 的内存重分配， 因为新追加的字符串长度小于 18 ：

redis> APPEND msg " again!" 
(integer) 25 

再次执行 APPEND 命令之后， msg 的值所对应的 sdshdr 结构可以表示如下：

struct sdshdr {     
len = 25;     
free = 11;     
buf = "hello world again! again!\0           ";     
// 空白的地方为预分配空间，共 18 + 18 + 1 个字节 
} 

sds.c/sdsMakeRoomFor 函数描述了 sdshdr 的这种内存预分配优化策略， 以下是这个函数的伪代码版本：

def sdsMakeRoomFor(sdshdr, required_len):      
# 预分配空间足够，无须再进行空间分配     
if (sdshdr.free >= required_len):         return sdshdr      
# 计算新字符串的总长度     
   newlen = sdshdr.len + required_len     
# 如果新字符串的总长度小于 SDS_MAX_PREALLOC     
# 那么为字符串分配 2 倍于所需长度的空间     
# 否则就分配所需长度加上 SDS_MAX_PREALLOC 数量的空间     
if newlen < SDS_MAX_PREALLOC:         
   newlen *= 2    
else:         
   newlen += SDS_MAX_PREALLOC      
# 分配内存     
   newsh = zrelloc(sdshdr, sizeof(struct sdshdr)+newlen+1)      
# 更新 free 属性     
   newsh.free = newlen - sdshdr.len      
# 返回     
   return newsh 

在目前版本的 Redis 中， SDS_MAX_PREALLOC 的值为 1024 * 1024 ， 也就是说， 当大小小于 1MB 的字符串执行追加操作时， sdsMakeRoomFor 就为它们分配多于所需大小一倍的空间； 当字符串的大小大于 1MB ， 那么 sdsMakeRoomFor 就为它们额外多分配 1MB 的空间。

sds 模块的 API

sds 模块基于 sds 类型和 sdshdr 结构提供了以下 API ：

sds 还有另一部分功能性函数， 比如 sdstolower 、 sdstrim 、 sdscmp ， 等等， 基本都是标准 C 字符串库函数的 sds 版本， 这里不一一列举了。

小结

• Redis 的字符串表示为 sds ，而不是 C 字符串（以 \0 结尾的 char*）。
• 对比 C 字符串， sds 有以下特性：
  • 可以高效地执行长度计算（strlen）；
  • 可以高效地执行追加操作（append）；
  • 二进制安全；
• sds 会为追加操作进行优化：加快追加操作的速度，并降低内存分配的次数，代价是多占用了一些内存，而且这些内存不会被主动释放。