共計 7173 個字符，預計需要花費 18 分鐘才能閱讀完成。

丸趣 TV 小編給大家分享一下 redis 內部數據結構之 SDS 簡單動態字符串的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

前言

reids 沒有直接使用 C 語言傳統的字符串表示（以空字符結尾的字符數組）而是構建了一種名為簡單動態字符串的抽象類型，并為 redis 的默認字符串表示，因為 C 字符串不能滿足 redis 對字符串的安全性、效率以及功能方面的需求

1、SDS 定義

在 C 語言中，字符串是以 \0 字符結尾（NULL 結束符）的字符數組來存儲的，通常表達為字符指針的形式（char *）。它不允許字節 0 出現在字符串中間，因此，它不能用來存儲任意的二進制數據。

sds 的類型定義

typedef char *sds;

每個 sds.h/sdshdr 結構表示一個 SDS 的值  
struct sdshdr{ 
// 記錄 buf 數組中已使用的字節的數量  
// 等于 sds 所保存字符串的長度  
int len; 
// 記錄 buf 中未使用的數據  
int free; 
// 字符數組，用于保存字符串  
} 

* free  屬性的值為 0, 表示這個 SDS 沒有分配任何未使用的空間  
* len  屬性長度為 5, 表示這個 SDS 保存一個五字節長的字符串  
* buf  屬性是一個 char 類型的數組, 數組的前 5 個字節分別保存了 R , e , d , i , s 五個字符, 而最后一個字節則保存了空字符串 \0

肯定有人感到困惑了，竟然 sds 就等同于 char *？

sds 和傳統的 C 語言字符串保持類型兼容，因此它們的類型定義是一樣的，都是 char *，在有些情況下，需要傳入一個 C 語言字符串的地方，也確實可以傳入一個 sds。

但是 sds 和 char * 并不等同，sds 是 Binary Safe 的，它可以存儲任意二進制數據，不能像 C 語言字符串那樣以字符 \0 來標識字符串的結束，因此它必然有個長度字段，這個字段在 header 中

sds 的 header 結構

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
 unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
 char buf[];
struct __attribute__ ((__packed__)) sdshdr8 {
 uint8_t len; /* used */
 uint8_t alloc; /* excluding the header and null terminator */
 unsigned char flags; /* 3 lsb of type, 5 unused bits */
 char buf[];
struct __attribute__ ((__packed__)) sdshdr16 {
 uint16_t len; /* used */
 uint16_t alloc; /* excluding the header and null terminator */
 unsigned char flags; /* 3 lsb of type, 5 unused bits */
 char buf[];
struct __attribute__ ((__packed__)) sdshdr32 {
 uint32_t len; /* used */
 uint32_t alloc; /* excluding the header and null terminator */
 unsigned char flags; /* 3 lsb of type, 5 unused bits */
 char buf[];
struct __attribute__ ((__packed__)) sdshdr64 {
 uint64_t len; /* used */
 uint64_t alloc; /* excluding the header and null terminator */
 unsigned char flags; /* 3 lsb of type, 5 unused bits */
 char buf[];};

SDS 一共有 5 種類型的 header。目的是節省內存。

一個 SDS 字符串的完整結構，由在內存地址上前后相鄰的兩部分組成：

一個 header。通常包含字符串的長度 (len)、最大容量(alloc) 和 flags。sdshdr5 有所不同。

一個字符數組。這個字符數組的長度等于最大容量 +1。真正有效的字符串數據，其長度通常小于最大容量。在真正的字符串數據之后，是空余未用的字節（一般以字節 0 填充），允許在不重新分配內存的前提下讓字符串數據向后做有限的擴展。在真正的字符串數據之后，還有一個 NULL 結束符，即 ASCII 碼為 0 的 \0 字符。這是為了和傳統 C 字符串兼容。之所以字符數組的長度比最大容量多 1 個字節，就是為了在字符串長度達到最大容量時仍然有 1 個字節存放 NULL 結束符。

除了 sdshdr5 之外，其它 4 個 header 的結構都包含 3 個字段：

len: 表示字符串的真正長度（不包含 NULL 結束符在內）。

alloc: 表示字符串的最大容量（不包含最后多余的那個字節）。

flags: 總是占用一個字節。其中的最低 3 個 bit 用來表示 header 的類型。

在各個 header 的類型定義中，還有幾個需要我們注意的地方：

在各個 header 的定義中使用了__attribute__ ((packed))，是為了讓編譯器以緊湊模式來分配內存。如果沒有這個屬性，編譯器可能會為 struct 的字段做優化對齊，在其中填充空字節。那樣的話，就不能保證 header 和 sds 的數據部分緊緊前后相鄰，也不能按照固定向低地址方向偏移 1 個字節的方式來獲取 flags 字段了。

在各個 header 的定義中最后有一個 char buf[]。我們注意到這是一個沒有指明長度的字符數組，這是 C 語言中定義字符數組的一種特殊寫法，稱為柔性數組（flexible array member），只能定義在一個結構體的最后一個字段上。它在這里只是起到一個標記的作用，表示在 flags 字段后面就是一個字符數組，或者說，它指明了緊跟在 flags 字段后面的這個字符數組在結構體中的偏移位置。而程序在為 header 分配的內存的時候，它并不占用內存空間。如果計算 sizeof(struct sdshdr16)的值，那么結果是 5 個字節，其中沒有 buf 字段。

sdshdr5 與其它幾個 header 結構不同，它不包含 alloc 字段，而長度使用 flags 的高 5 位來存儲。因此，它不能為字符串分配空余空間。如果字符串需要動態增長，那么它就必然要重新分配內存才行。所以說，這種類型的 sds 字符串更適合存儲靜態的短字符串（長度小于 32）。

至此，我們非常清楚地看到了：sds 字符串的 header，其實隱藏在真正的字符串數據的前面（低地址方向）。這樣的一個定義，有如下幾個好處：

header 和數據相鄰，而不用分成兩塊內存空間來單獨分配。這有利于減少內存碎片，提高存儲效率（memory efficiency）。

雖然 header 有多個類型，但 sds 可以用統一的 char * 來表達。且它與傳統的 C 語言字符串保持類型兼容。如果一個 sds 里面存儲的是可打印字符串，那么我們可以直接把它傳給 C 函數，比如使用 strcmp 比較字符串大小，或者使用 printf 進行打印。

弄清了 sds 的數據結構，它的具體操作函數就比較好理解了。

sds 的一些基礎函數

sdslen(const sds s): 獲取 sds 字符串長度。

sdssetlen(sds s, size_t newlen): 設置 sds 字符串長度。

sdsinclen(sds s, size_t inc): 增加 sds 字符串長度。

sdsalloc(const sds s): 獲取 sds 字符串容量。

sdssetalloc(sds s, size_t newlen): 設置 sds 字符串容量。

sdsavail(const sds s): 獲取 sds 字符串空余空間（即 alloc – len）。

sdsHdrSize(char type): 根據 header 類型得到 header 大小。

sdsReqType(size_t string_size): 根據字符串數據長度計算所需要的 header 類型。

二、SDS 數組動態分配策略

header 信息中的定義這么多字段，其中一個很重要的作用就是實現對字符串的靈活操作并且盡量減少內存重新分配和回收操作。

redis 的內存分配策略如下

當 SDS 的 len 屬性長度小于 1MB 時，redis 會分配和 len 相同長度的 free 空間。至于為什么這樣分配呢，上次用了 len 長度的空間，那么下次程序可能也會用 len 長度的空間，所以 redis 就為你預分配這么多的空間。

但是當 SDS 的 len 屬性長度大于 1MB 時，程序將多分配 1M 的未使用空間。這個時候我在根據這種慣性預測來分配的話就有點得不償失了。所以 redis 是將 1MB 設為一個風險值，沒過風險值你用多少我就給你多少，過了的話那這個風險值就是我能給你臨界值

reids 的內存回收策略如下

redis 的內存回收采用惰性回收，即你把字符串變短了，那么多余的內存空間我先不還給操作系統，先留著，萬一馬上又要被使用呢。短暫的持有資源，既可以充分利用資源，也可以不浪費資源。這是一種很優秀的思想。

綜上所述，redis 實現的高性能字符串的結果就把 N 次字符串操作必會發生 N 次內存重新分配變為人品最差時最多發生 N 次重新分配。

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
 void *sh, *newsh;
 size_t avail = sdsavail(s);
 size_t len, newlen;
 char type, oldtype = s[-1]   SDS_TYPE_MASK;
 int hdrlen;
 
 /* Return ASAP if there is enough space left. */
 if (avail  = addlen) return s;
 
 len = sdslen(s);
 sh = (char*)s-sdsHdrSize(oldtype);
 newlen = (len+addlen);
 if (newlen   SDS_MAX_PREALLOC)
 newlen *= 2;
 else
 newlen += SDS_MAX_PREALLOC;
 
 type = sdsReqType(newlen);
 
 /* Don t use type 5: the user is appending to the string and type 5 is
 * not able to remember empty space, so sdsMakeRoomFor() must be called
 * at every appending operation. */
 if (type == SDS_TYPE_5) type = SDS_TYPE_8;
 
 hdrlen = sdsHdrSize(type);
 if (oldtype==type) { newsh = s_realloc(sh, hdrlen+newlen+1);
 if (newsh == NULL) return NULL;
 s = (char*)newsh+hdrlen;
 } else {
 /* Since the header size changes, need to move the string forward,
 * and can t use realloc */
 newsh = s_malloc(hdrlen+newlen+1);
 if (newsh == NULL) return NULL;
 memcpy((char*)newsh+hdrlen, s, len+1);
 s_free(sh);
 s = (char*)newsh+hdrlen;
 s[-1] = type;
 sdssetlen(s, len);
 }
 sdssetalloc(s, newlen);
 return s;
 
/* Reallocate the sds string so that it has no free space at the end. The
 * contained string remains not altered, but next concatenation operations
 * will require a reallocation.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdsRemoveFreeSpace(sds s) {
 void *sh, *newsh;
 char type, oldtype = s[-1]   SDS_TYPE_MASK;
 int hdrlen;
 size_t len = sdslen(s);
 sh = (char*)s-sdsHdrSize(oldtype);
 
 type = sdsReqType(len);
 hdrlen = sdsHdrSize(type);
 if (oldtype==type) { newsh = s_realloc(sh, hdrlen+len+1);
 if (newsh == NULL) return NULL;
 s = (char*)newsh+hdrlen;
 } else { newsh = s_malloc(hdrlen+len+1);
 if (newsh == NULL) return NULL;
 memcpy((char*)newsh+hdrlen, s, len+1);
 s_free(sh);
 s = (char*)newsh+hdrlen;
 s[-1] = type;
 sdssetlen(s, len);
 }
 sdssetalloc(s, len);
 return s;
}

三、SDS 的特點

sds 正是在 Redis 中被廣泛使用的字符串結構，它的全稱是 Simple Dynamic String。與其它語言環境中出現的字符串相比，它具有如下顯著的特點：

可動態擴展內存。SDS 表示的字符串其內容可以修改，也可以追加。在很多語言中字符串會分為 mutable 和 immutable 兩種，SDS 屬于 mutable 類型的。

二進制安全（Binary Safe）。sds 能存儲任意二進制數據。

與傳統的 C 語言字符串類型兼容。

預分配空間，可以懶惰釋放，在內存緊張的時候也可以縮減不需要的內存

常數復雜度獲取字符串長度

杜絕緩沖區溢出，邊界檢查

四、淺談 SDS 與 string 的關系

127.0.0.1:6379  set test test
127.0.0.1:6379  append test   test 
(integer) 9
127.0.0.1:6379  get test
 test test 
127.0.0.1:6379  setbit test 36 1
(integer) 0
127.0.0.1:6379  get test
 test(test 
127.0.0.1:6379  getrange test -5 -1
 (test

append 操作使用 SDS 的 sdscatlen 來實現。

setbit 和 getrange 都是先根據 key 取到整個 sds 字符串，然后再從字符串選取或修改指定的部分。由于 SDS 就是一個字符數組，所以對它的某一部分進行操作似乎都比較簡單。

但是，string 除了支持這些操作之外，當它存儲的值是個數字的時候，它還支持 incr、decr 等操作。它的內部存儲不是 SDS，這種情況下，setbit 和 getrange 的實現也會有所不同。

以上是“redis 內部數據結構之 SDS 簡單動態字符串的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注丸趣 TV 行業資訊頻道！