Posted on 2013-04-05 17:54
鑫龍 閱讀(1138)
評論(0) 編輯 收藏 引用 所屬分類:
redis
轉自：http://www.redisbook.com
簡單動態字符串
Sds （Simple Dynamic String，簡單動態字符串）是 Redis 底層所使用的字符串表示， 它被用在幾乎所有的 Redis 模塊中。
本章將對 sds 的實現、性能和功能等方面進行介紹， 并說明 Redis 使用 sds 而不是傳統 C 字符串的原因。
sds 的用途
Sds 在 Redis 中的主要作用有以下兩個：
- 實現字符串對象（StringObject）；
- 在 Redis 程序內部用作 char* 類型的替代品；
以下兩個小節分別對這兩種用途進行介紹。
實現字符串對象
Redis 是一個鍵值對數據庫（key-value DB）， 數據庫的值可以是字符串、集合、列表等多種類型的對象， 而數據庫的鍵則總是字符串對象。
對于那些包含字符串值的字符串對象來說， 每個字符串對象都包含一個 sds 值。
“包含字符串值的字符串對象”，這種說法初聽上去可能會有點奇怪， 但是在 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)）的復雜度為 θ(N) 。
- 對字符串進行 N 次追加，必定需要對字符串進行 N 次內存重分配（realloc）。
在 Redis 內部， 字符串的追加和長度計算并不少見， 而 APPEND 和 STRLEN 更是這兩種操作在 Redis 命令中的直接映射， 這兩個簡單的操作不應該成為性能的瓶頸。
另外， Redis 除了處理 C 字符串之外， 還需要處理單純的字節數組， 以及服務器協議等內容， 所以為了方便起見， Redis 的字符串表示還應該是二進制安全的： 程序不應對字符串里面保存的數據做任何假設， 數據可以是以 \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 可以實現復雜度為 θ(1) 的長度計算操作。
另一方面， 通過對 buf 分配一些額外的空間， 并使用 free 記錄未使用空間的大小， sdshdr 可以讓執行追加操作所需的內存重分配次數大大減少， 下一節我們就會來詳細討論這一點。
當然， sds 也對操作的正確實現提出了要求 —— 所有處理 sdshdr 的函數，都必須正確地更新 len 和 free 屬性，否則就會造成 bug 。
優化追加操作
在前面說到過，利用 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 的空間。
這種分配策略會浪費內存嗎？
執行過 APPEND 命令的字符串會帶有額外的預分配空間， 這些預分配空間不會被釋放， 除非該字符串所對應的鍵被刪除， 或者等到關閉 Redis 之后， 再次啟動時重新載入的字符串對象將不會有預分配空間。
因為執行 APPEND 命令的字符串鍵數量通常并不多， 占用內存的體積通常也不大， 所以這一般并不算什么問題。
另一方面， 如果執行 APPEND 操作的鍵很多， 而字符串的體積又很大的話， 那可能就需要修改 Redis 服務器， 讓它定時釋放一些字符串鍵的預分配空間， 從而更有效地使用內存。
sds 模塊的 API
sds 模塊基于 sds 類型和 sdshdr 結構提供了以下 API ：
| 函數 | 作用 | 算法復雜度 |
|---|
| sdsnewlen | 創建一個指定長度的 sds ，接受一個 C 字符串作為初始化值 | O(N) |
| sdsempty | 創建一個只包含空白字符串 "" 的 sds | O(N) |
| sdsnew | 根據給定 C 字符串，創建一個相應的 sds | O(N) |
| sdsdup | 復制給定 sds | O(N) |
| sdsfree | 釋放給定 sds | O(N) |
| sdsupdatelen | 更新給定 sds 所對應 sdshdr 結構的 free 和 len | O(1) |
| 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 會為追加操作進行優化：加快追加操作的速度，并降低內存分配的次數，代價是多占用了一些內存，而且這些內存不會被主動釋放。