Redis - SDS 簡單動態字串

語言: CN / TW / HK

定義解釋

Redis 沒有直接使用C語言傳統的字串表示(以空字元 \0  結尾的字元陣列,以下簡稱 C字串),而是自己構建了一種名為簡單動態字串(simple dynamic string,SDS)的抽象型別,並將 SDS 作為預設字串表示。

Redis 客戶端傳入伺服器的協議內容、 aof 快取、 返回給客戶端的回覆等等, 這些重要的內容都是由 sds 型別來儲存的。只有在字串不需要修改的時候採用 C字串,其餘情況都採用 SDS。

不直接使用 C字串的原因大致下面幾種:

1)C語言的字串不記錄自身長度,想要知道一個字串的長度就必須遍歷一遍字串,複雜度為 O(N),而Redis的字元串同樣使用命令 STRLEN 的時候,複雜度為 O(1)。

2)二進位制安全,可以儲存非文字資料的,包括影片,音訊,圖片等。SDS並不是像傳統的C字串(字元陣列)一樣,而SDS常被稱作位元組陣列,採用以位元組為單位的形式儲存資料,而最後的 \0 也是一個位元組,這樣資料怎麼樣存入的,取出來的時候還是怎麼樣的,因此是二進位制安全的。 因為在結構中定義了 len 屬性,所以及時在字串中間出現 \0 也是可以完整儲存而不會被截斷。

3)可以高效地執行追加操作(append),加快追加操作的速度,並降低記憶體分配的次數,代價是多佔用了一些記憶體,而且這些記憶體不會被主動釋放。

原始碼解讀

對於 SDS ,Redis 有五種實現方式 SDS_TYPE_5、SDS_TYPE_8、SDS_TYPE_16、SDS_TYPE_32、SDS_TYPE_64。根據初始化的長度決定使用哪種型別,從而減少記憶體的使用。

資料結構

位於 sds.h 標頭檔案

``` struct attribute ((packed)) sdshdr8 {

uint8_t len;         // 已經使用的位元組數     uint8_t alloc;       // 總共可用的字元空間大小,應該是實際buf的大小減1 (因為c字串末尾必須是 \0, 不計算在內)。     unsigned char flags; // 標誌位,主要是識別這是sdshdr幾,目前只用了3位,還有5位空餘     char buf[];          // 實際儲存字串的地方 其實就是 C 原生字串+部分空餘空間

}; ```

但是當初始化為空和 SDS_TYPE_5 較為特殊,在原始碼中會強制轉換為 SDS_TYPE_8。理解是因這種情況下,很大可能後續會追加資料。故給一個比較合適的等級。

位於 sds.c 

``` sds sdsnewlen(const void *init, size_t initlen) {

...

if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;      ...

} ```

有意思的是對於 Key 和 Value 都很小,只有 Value 會被強轉,我理解是 Key 不怎麼會更新。故給最小的值即可。

```

sds sdsnewlen(const void *init, size_t initlen) {      ...     s[initlen] = '\0';     return s; } ```

sdsnewlen() 返回的 SDS 指標並不是直接指向 sdshdr 的地址,而是直接指向了 sdshdr 中 buf 的地址。因為這樣可以相容c原生字串, buf 其實就是 C 原生字串 + 部分空餘空間,中間是特殊符號’\0’隔開,‘\0’是標識C字串末尾的符號,這樣就實現了和C原生字串的相容,部分C字串的API也就可以直接使。

擴容操作

若新申請的記憶體加已使用記憶體沒有超過 SDS_MAX_PREALLOC(1024*1024) 則按 * 2 倍申請。反之按 SDS_MAX_PREALLOC 遞增。

```

// 擴大sds的實際可用空間,以便後續能拼接更多字串。 // 這裡實際不會改變sds的長度,只是增加了更多可用的空間(buf) sds sdsMakeRoomFor(sds s, size_t addlen) { ...

len = sdslen(s);     sh = (char*)s-sdsHdrSize(oldtype);     newlen = (len+addlen);

// 在未超出SDS_MAX_PREALLOC前,擴容都是按2倍的方式擴容,超出後只能遞增     if (newlen < SDS_MAX_PREALLOC)  // SDS_MAX_PREALLOC = 10241024         newlen = 2;     else         newlen += SDS_MAX_PREALLOC; ...     sdssetalloc(s, newlen);     return s; } ```

String 型別實現

上面提到 String 型別不僅僅只能儲存字串型別資料,所以對於賦予不同的資料型別時候,string 是會區別對待。

1)當儲存的資料是整數型別時候,String 型別會使用 int 編碼方式來儲存。具體為使用一個 8位元組的 Long 型別來實現。

2)當儲存的資料中包含字串時候,String 型別會使用 SDS 結構體來儲存。

結構如下

``` struct {

flags; // 佔 8 個位元組,標誌位,主要是識別這是sdshdr幾,目前只用了3位,還有5位空餘
len ; // 佔 4 個位元組,表示 buf 的已用長度。
alloc; // 佔 4 個位元組,表示 buf 的實際分配長度,一般大於 len。 buf ; // 位元組陣列,儲存實際資料。為了表示位元組陣列的結束,Redis 會自動在陣列最後加一個“\0”,這就會額外佔用 1 個位元組的開銷。

} ```

除了記錄實際資料,String 型別還需要額外的記憶體空間記錄資料長度、空間使用、最後一次訪問的時間、被引用的次數等元資料,所以,Redis 會用一個 RedisObject 結構體來統一記錄這些元資料,同時指向實際資料。

一個 RedisObject 包含了 8 位元組的元資料和一個 8 位元組指標,這個指標再進一步指向具體資料型別的實際資料所在或者為真實值。

​編輯

為了節省記憶體使用,對 Long 和 SDS 做了不同的處理:

1)當儲存的是 Long 型別整數時,RedisObject 中的指標就直接賦值為整數資料了,這樣就不用額外的指標再指向整數了,節省了指標的空間開銷。

2)當儲存的是字串資料,並且字串小於等於 44 位元組時,RedisObject 中的元資料、指標和 SDS 是一塊連續的記憶體區域,這樣就可以避免記憶體碎片。這種佈局方式也被稱為 embstr 編碼方式。

3)當儲存的是字串資料,並且字串大於 44 位元組時,SDS 的資料量就開始變多了,Redis 就不再把 SDS 和 RedisObject 佈局在一起了,而是會給 SDS 分配獨立的空間,並用指標指向 SDS 結構。這種佈局方式被稱為 raw 編碼模式。

總結

SDS 最為 Redis 最常用的資料機構,總結有下面幾種原因。

1)常數複雜度獲取字串長度:O(1)。

2)避免緩衝區溢位。

3)減少修改字串時帶來的記憶體重分配次數。

4)二進位制安全。

SDS 雖好,但是也不能亂用。可以繼續看這篇文章:Redis 請慎用String型別