# 簡單動態字符串
[TOC=2,3]
Sds (Simple Dynamic String,簡單動態字符串)是 Redis 底層所使用的字符串表示,幾乎所有的 Redis 模塊中都用了 sds。
本章將對 sds 的實現、性能和功能等方面進行介紹,并說明 Redis 使用 sds 而不是傳統 C 字符串的原因。
### sds 的用途
Sds 在 Redis 中的主要作用有以下兩個:
1. 實現字符串對象(StringObject);
1. 在 Redis 程序內部用作 `char*` 類型的替代品;
以下兩個小節分別對這兩種用途進行介紹。
### 實現字符串對象
Redis 是一個鍵值對數據庫(key-value DB),數據庫的值可以是字符串、集合、列表等多種類型的對象,而數據庫的鍵則總是字符串對象。
對于那些包含字符串值的字符串對象來說,每個字符串對象都包含一個 sds 值。
Note
“包含字符串值的字符串對象”,這種說法初聽上去可能會有點奇怪,但是在 Redis 中,一個字符串對象除了可以保存字符串值之外,還可以保存 `long` 類型的值,所以為了嚴謹起見,這里需要強調一下:當字符串對象保存的是字符串時,它包含的才是 sds 值,否則的話,它就是一個 `long` 類型的值。
舉個例子,以下命令創建了一個新的數據庫鍵值對,這個鍵值對的鍵和值都是字符串對象,它們都包含一個 sds 值:
~~~
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"
~~~
### 用 sds 取代 C 默認的 char* 類型
因為 `char*` 類型的功能單一,抽象層次低,并且不能高效地支持一些 Redis 常用的操作(比如追加操作和長度計算操作),所以在 Redis 程序內部,絕大部分情況下都會使用 sds 而不是 `char*` 來表示字符串。
性能問題在稍后介紹 sds 定義的時候就會說到,因為我們還沒有了解過 Redis 的其他功能模塊,所以也沒辦法詳細地舉例說那里用到了 sds ,不過在后面的章節中,我們會經常看到其他模塊(幾乎每一個)都用到了 sds 類型值。
目前來說,只要記住這個事實即可:在 Redis 中,客戶端傳入服務器的協議內容、aof 緩存、返回給客戶端的回復,等等,這些重要的內容都是由 sds 類型來保存的。
### Redis 中的字符串
在 C 語言中,字符串可以用一個 `\0` 結尾的 `char` 數組來表示。
比如說, `hello world` 在 C 語言中就可以表示為 `"hello world\0"` 。
這種簡單的字符串表示,在大多數情況下都能滿足要求,但是,它并不能高效地支持長度計算和追加(append)這兩種操作:
- 每次計算字符串長度(`strlen(s)`)的復雜度為 \(\theta(N)\) 。
- 對字符串進行 N 次追加,必定需要對字符串進行 N 次內存重分配(`realloc`)。
在 Redis 內部,字符串的追加和長度計算很常見,而 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 和 [STRLEN](http://redis.readthedocs.org/en/latest/string/strlen.html#strlen "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/strlen.html#strlen] 更是這兩種操作,在 Redis 命令中的直接映射,這兩個簡單的操作不應該成為性能的瓶頸。
另外,Redis 除了處理 C 字符串之外,還需要處理單純的字節數組,以及服務器協議等內容,所以為了方便起見,Redis 的字符串表示還應該是[二進制安全的](http://en.wikipedia.org/wiki/Binary-safe) [http://en.wikipedia.org/wiki/Binary-safe]:程序不應對字符串里面保存的數據做任何假設,數據可以是以 `\0` 結尾的 C 字符串,也可以是單純的字節數組,或者其他格式的數據。
考慮到這兩個原因,Redis 使用 sds 類型替換了 C 語言的默認字符串表示:sds 既可高效地實現追加和長度計算,同時是二進制安全的。
### sds 的實現
在前面的內容中,我們一直將 sds 作為一種抽象數據結構來說明,實際上,它的實現由以下兩部分組成:
~~~
typedef char *sds;
struct sdshdr {
// buf 已占用長度
int len;
// buf 剩余可用長度
int free;
// 實際保存字符串數據的地方
char buf[];
};
~~~
其中,類型 `sds` 是 `char *` 的別名(alias),而結構 `sdshdr` 則保存了 `len` 、 `free` 和 `buf` 三個屬性。
作為例子,以下是新創建的,同樣保存 `hello world` 字符串的 `sdshdr` 結構:
~~~
struct sdshdr {
len = 11;
free = 0;
buf = "hello world\0"; // buf 的實際長度為 len + 1
};
~~~
通過 `len` 屬性, `sdshdr` 可以實現復雜度為 \(\theta(1)\) 的長度計算操作。
另一方面,通過對 `buf` 分配一些額外的空間,并使用 `free` 記錄未使用空間的大小,`sdshdr` 可以讓執行追加操作所需的內存重分配次數大大減少,下一節我們就會來詳細討論這一點。
當然,sds 也對操作的正確實現提出了要求 —— 所有處理 `sdshdr` 的函數,都必須正確地更新 `len` 和 `free` 屬性,否則就會造成 bug 。
### 優化追加操作
在前面說到過,利用 `sdshdr` 結構,除了可以用 \(\theta(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](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#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](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 之后,Redis 為 `buf` 創建了多于所需空間一倍的大小。
在這個例子中,保存 `"hello world again!"` 共需要 `18 + 1` 個字節,但程序卻為我們分配了 `18 + 18 + 1 = 37` 個字節 ——這樣一來,如果將來再次對同一個 `sdshdr` 進行追加操作,只要追加內容的長度不超過 `free` 屬性的值,那么就不需要對 `buf` 進行內存重分配。
比如說,執行以下命令并不會引起 `buf` 的內存重分配,因為新追加的字符串長度小于 `18` :
~~~
redis> APPEND msg " again!"
(integer) 25
~~~
再次執行 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#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` 的空間。
Note
這種分配策略會浪費內存嗎?
執行過 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令的字符串會帶有額外的預分配空間,這些預分配空間不會被釋放,除非該字符串所對應的鍵被刪除,或者等到關閉 Redis 之后,再次啟動時重新載入的字符串對象將不會有預分配空間。
因為執行 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令的字符串鍵數量通常并不多,占用內存的體積通常也不大,所以這一般并不算什么問題。
另一方面,如果執行 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 操作的鍵很多,而字符串的體積又很大的話,那可能就需要修改 Redis 服務器,讓它定時釋放一些字符串鍵的預分配空間,從而更有效地使用內存。
### sds 模塊的 API
sds 模塊基于 `sds` 類型和 `sdshdr` 結構提供了以下 API :
| 函數 | 作用 | 算法復雜度 |
|-----|-----|-----|
| `sdsnewlen` | 創建一個指定長度的 `sds` ,接受一個 C 字符串作為初始化值 | \(O(N)\) |
| `sdsempty` | 創建一個只包含空白字符串 `""` 的 `sds` | \(O(1)\) |
| `sdsnew` | 根據給定 C 字符串,創建一個相應的 `sds` | \(O(N)\) |
| `sdsdup` | 復制給定 `sds` | \(O(N)\) |
| `sdsfree` | 釋放給定 `sds` | \(O(N)\) |
| `sdsupdatelen` | 更新給定 `sds` 所對應 `sdshdr` 結構的 `free` 和 `len` | \(O(N)\) |
| `sdsclear` | 清除給定 `sds` 的內容,將它初始化為 `""` | \(O(1)\) |
| `sdsMakeRoomFor` | 對 `sds` 所對應 `sdshdr` 結構的 `buf` 進行擴展 | \(O(N)\) |
| `sdsRemoveFreeSpace` | 在不改動 `buf` 的情況下,將 `buf` 內多余的空間釋放出去 | \(O(N)\) |
| `sdsAllocSize` | 計算給定 `sds` 的 `buf` 所占用的內存總數 | \(O(1)\) |
| `sdsIncrLen` | 對 `sds` 的 `buf` 的右端進行擴展(expand)或修剪(trim) | \(O(1)\) |
| `sdsgrowzero` | 將給定 `sds` 的 `buf` 擴展至指定長度,無內容的部分用 `\0` 來填充 | \(O(N)\) |
| `sdscatlen` | 按給定長度對 `sds` 進行擴展,并將一個 C 字符串追加到 `sds` 的末尾 | \(O(N)\) |
| `sdscat` | 將一個 C 字符串追加到 `sds` 末尾 | \(O(N)\) |
| `sdscatsds` | 將一個 `sds` 追加到另一個 `sds` 末尾 | \(O(N)\) |
| `sdscpylen` | 將一個 C 字符串的部分內容復制到另一個 `sds` 中,需要時對 `sds` 進行擴展 | \(O(N)\) |
| `sdscpy` | 將一個 C 字符串復制到 `sds` | \(O(N)\) |
`sds` 還有另一部分功能性函數,比如 `sdstolower` 、 `sdstrim` 、 `sdscmp` ,等等,基本都是標準 C 字符串庫函數的 `sds` 版本,這里不一一列舉了。
### 小結
- Redis 的字符串表示為 `sds` ,而不是 C 字符串(以 `\0` 結尾的 `char*`)。
- 對比 C 字符串, `sds` 有以下特性:
- 可以高效地執行長度計算(`strlen`);
- 可以高效地執行追加操作(`append`);
- 二進制安全;
- `sds` 會為追加操作進行優化:加快追加操作的速度,并降低內存分配的次數,代價是多占用了一些內存,而且這些內存不會被主動釋放。