Redis中的動態字符串學習教程

sds 的用途
Sds 在 Redis 中的主要作用有以下兩個：

實現字符串對象（StringObject）；
在 Redis 程序內部用作 char* 類型的替代品；
以下兩個小節分別對這兩種用途進行介紹。

實現字符串對象

Redis 是一個鍵值對數據庫（key-value DB），數據庫的值可以是字符串、集合、列表等多種類型的對象，而數據庫的鍵則總是字符串對象。

對于那些包含字符串值的字符串對象來說，每個字符串對象都包含一個 sds 值。

“包含字符串值的字符串對象”，這種說法初聽上去可能會有點奇怪，但是在 Redis 中，一個字符串對象除了可以保存字符串值之外，還可以保存 long 類型的值，所以為了嚴謹起見，這里需要強調一下：當字符串對象保存的是字符串時，它包含的才是 sds 值，否則的話，它就是一個 long 類型的值。
舉個例子，以下命令創建了一個新的數據庫鍵值對，這個鍵值對的鍵和值都是字符串對象，它們都包含一個 sds 值：

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

以下命令創建了另一個鍵值對，它的鍵是字符串對象，而值則是一個集合對象：

redis> SADD nosql "Redis" "MongoDB" "Neo4j"(integer) 3redis> SMEMBERS nosql1) "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 。

數據類型定義
與sds實現有關的數據類型有兩個，一個是 sds：

  // 字符串類型的別名   typedef char *sds;

另一個是 sdshdr：

  // 持有sds的結構   struct sdshdr {     // buf中已經被使用的字符串空間數量     int len;     // buf中預留字符串的空間數量     int free;     // 實際存儲字符串的地方     char buf[];   };

其中，sds只是字符串數組類型char*的別名，而sdshdr用于持有和保存sds的信息

比如，sdshdr.len可以用于在O（1）的復雜度下獲取sdshdr.buf中存儲的字符串的實際長度，而sdshdr.free則用于保存sdshdr.buf中還有多少預留空間

（這里sdshdr應該是sds handler的縮寫）

將sdshdr用作sds
sds模塊對sdshdr結構使用了一點小技巧：通過指針運算，它使得sdshdr結構可以像sds類型一樣被傳值和處理，并在需要的時候恢復成sdshdr類型

通過下面的函數定義來理解這個技巧

sdsnewlen 函數返回一個新的sds值，實際上，它創建的卻是一個sdshdr結構：

  sds sdsnewlen(const void *init, size_t initlen)   {     struct sdshdr *sh;        if (init) {       // 創建       sh = malloc(sizeof(struct sdshdr) + initlen + 1);     } else {       // 重分配       sh = calloc(1, sizeof(struct sdshdr) + initlen + 1);     }        if (sh == NULL) return NULL;        sh->len = initlen;     sh->free = 0;  // 剛開始free為0        if (initlen && init) {       memcpy(sh->buf, init, initlen);     }     sh->buf[initlen] = '/0';        // 只返回sh->buf這個字符串部分     return (char *)sh->buf;   }

通過使用變量持有一個sds的值，在遇到那些只處理sds值本身的函數時，可以直接將sds傳給它們。比如說，sdstoupper 函數就是其中的一個例子：

  static inline size_t sdslen(const sds s)   {     // 從sds中計算出相應的sdshdr結構     struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));        return sh->len;   }         void sdstoupper(sds s)   {     int len = sdslen(s), j;        for (j = 0; j < len; j ++)       s[j] = toupper(s[j]);   }

這里有一個技巧，通過指針運算，可以從sds值中計算出相應的sdshdr結構：

sds雖然是指向char *的buf（ps：并且空數組不占用內存空間，數組名即為內存地址），但是分配的時候是分配sizeof(struct sdshdr) + initlen + 1的，通過sds - sizeof(struct sdshdr)可以計算出struct sdshdr的首地址，從而可以得到len和free的信息

sdsavail 函數就是使用這中技巧的一個例子：

  static inline size_t sdsavail(const sds s)   {     struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr)));        return sh->free;   }

內存分配函數實現
和Reids 的實現決策相關的函數是 sdsMakeRoomFor ：

  sds sdsMakeRoomFor(sds s, size_t addlen)   {     struct sdshdr *sh, *newsh;     size_t free = sdsavail(s);     size_t len, newlen;        // 預留空間可以滿足本地拼接      if (free >= addlen) return s;        len = sdslen(s);     sh = (void *)(s - (sizeof(struct sdshdr)));        // 設置新sds的字符串長度     // 這個長度比完成本次拼接實際所需的長度要大     // 通過預留空間優化下次拼接操作     newlen = (len + addlen);     if (newlen < 1024 * 1024)       newlen *= 2;     else       newlen += 1024;        // 重新分配sdshdr     newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1);     if (newsh == NULL) return NULL;        newsh->free = newlen - len;        // 只返回字符串部分     return newsh->buf;   }

這種內存分配策略表明，在對sds 值進行擴展（expand）時，總會預留額外的空間，通過花費更多的內存，減少了對內存進行重分配(reallocate)的次數，并優化下次擴展操作的處理速度

再把redis的如果實現對sds字符串擴展的方法貼一下，很不錯的思路：

  /**    * 按長度len擴展sds，并將t拼接到sds的末尾    */   sds sdscatlen(sds s, const void *t, size_t len)   {     struct sdshdr *sh;        size_t curlen = sdslen(s);        // O(N)     s = sdsMakeRoomFor(s, len);     if (s == NULL) return NULL;        // 復制     memcpy(s + curlen, t, len);        // 更新len和free屬性     sh = (void *)(s - (sizeof(struct sdshdr)));     sh->len = curlen + len;     sh->free = sh->free - len;        // 終結符     s[curlen + len] = '/0';        return s;   }      /**    * 將一個char數組拼接到sds 末尾    */   sds sdscat(sds s, const char *t)   {     return sdscatlen(s, t, strlen(t));   }