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 會為追加操作進行優化：加快追加操作的速度，并降低內存分配的次數，代價是多占用了一些內存，而且這些內存不會被主動釋放。