簡單動態字符串 · Redis 設計與實現（第一版）

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