大家好，我是鴨血粉絲（大家會親切的喊我 「阿粉」），是一位喜歡吃鴨血粉絲的程式員，之前給大家總結了線上 OOM 的情況，相信大家也能從中學到一些東西，身為一名有追求的程式員，阿粉我的了解是光會吃老本是不行的，是以我一直也在學習，今天大家就跟我一起來了解一下 Redis 的 SDS 吧（不是 SOS 哦~）。
01、SDS 資料結構
Redis 底層是基于 C 語言來開發的，但是它沒有采用 C 語言傳統的字元串表示方式，而是自定義了一種叫做 SDS（Sample Dynamic String，簡單動态字元串）的資料結構來表示字元串。傳統的 C 語言的字元串是采用空字元（\0）作為結尾的字元數組，SDS 的資料結構稍微複雜一點，整個結構包含三個部分，是 Redis 的基礎。（阿粉猜測這裡就是傳說中的青出于藍而勝于藍）。
1.1、資料結構
在源碼 sds.h/sdshdr 結構體中定義了 SDS 的資料結構，包括三個部分，free，len，buf[]，依次含義如下
- buf[]：位元組數組，用于存放實際的字元串；
- len：記錄 buf 數組中已經使用的位元組數量，等同于 SDS 所儲存的字元串的長度；
- free：記錄 buf 數組中未使用的位元組的數量。
image-20191015000650127
說明
上圖中的 SDS 表示一個存放了 'RED' 字元串，已經使用的長度為 3，未使用的長度為 2（這裡用空白格表示未使用），其中的 '\0' 表示的是字元串的結束，不計算在 SDS 的 len 中，并且由 SDS 底層函數自動添加，對使用者來說是透明。這裡統一采用空字元（\0）結尾是為了複用 C 語言的相關函數。這個相信大家也很能了解，畢竟有祖宗可以靠，沒必要全靠自己那麼辛苦~。
02、為什麼采用 SDS
2.1、SDS 與 C語言字元串的差別
在說明 Redis 為什麼要自定義 SDS 之前，阿粉覺得我們應該先看一下 SDS 與傳統的 C 語言的字元串有什麼差別，知道了具體的差別我們才能知道這樣實作的原因是什麼。
2.1.1、O(1) 擷取字元串的長度
傳統的 C 語言字元串如果要擷取字元串的長度，則需要周遊整個字元串，直到遇到 '\0' 字元，才知道整個字元串的長度是多少，操作複雜度是 O(n) 的。但是在 SDS 中，由于我們記錄了字元串的長度，是以在擷取字元串長度的時候是可以直接擷取的，整個操作為 O(1)。
如上面的示例，我們可以直接擷取字元串的長度是 3，而不需要周遊，另外字元串 Key 在 Redis 的底層實作就是采用 SDS 的，是以這個特性就保證了我們在計算 Key 的長度的時候不會出現任何瓶頸，對系統的性能不會有任何影響。
2.1.2、動态擴容
由于 SDS 中記錄了未使用的空間大小，是以如果出現對已有字元串進行修改或者指派時，SDS 底層函數會自動檢測剩餘空間是否能滿足此次修改，如果 free 空間足夠則直接修改；如果 free 空間不夠則會先進行動态擴容達到能滿足的空間大小，然後再執行修改動作。整個擴容的動作是 SDS 底層函數自動完成，對使用者無感。
而對于傳統的 C 語言字元串，如果在修改前忘記手動擴容則會導緻字元串後面的資料被覆寫。這裡阿粉就不得不說一句了，為了友善大衆程式員，另一些骨灰級程式員（嗯，仿佛看到了未來的阿粉）也是操碎了心啊~
2.1.3、減少記憶體配置設定次數
在傳統的 C 語言的字元串，我們每次對字元串的修改都會涉及到字元串記憶體的重新配置設定，不管是增加還是減少字元串的長度。這種情況下，如果我們多次對字元串的長度進行調整的時候就會導緻多次的記憶體重新配置設定。
而在 SDS 中我們在對一個 SDS 初始化的時候會根據實際 buf[] 字元串的長度進行預先空間配置設定，并且标記為 free。這種方式叫做空間預配置設定，在很大程度上可以減少增加字元串長度導緻記憶體重新配置設定的情況。free 的空間配置設定的政策是根據 buf[] 大小來決定的，如果 buf[] 大小小于 1MB，則 len 多大 free 就多大；如果 buf[] 大小大于 1MB，則 free 固定設定為 1MB。
上面說的是SDS 字元串的長度增加，另外如果 SDS 的字元串長度減少，那麼 SDS 會将減少的長度存放到 free 中，而不是直接回收，這樣可以友善下次如果再次使用，減少記憶體重新配置設定。這種政策叫做惰性空間釋放。
同樣的上面兩種操作對使用者是完全無感的，阿粉覺得這種方案還是很合理的，不知道“元芳”你怎麼看？
2.1.4、二進制安全
我們都知道 Redis 是可以存儲各種類型資料的，不僅是字元串也可以存儲圖檔，視訊等二進制資料流。這是由于 Redis 不依賴一 '\0' 空字元作為結束字元。C 語言之是以不支援就是因為二進制流中會攜帶 '\0' 字元，導緻無法知道字元串真實的結束位置。這就帶來了另一個 Redis 特性，就是二進制的安全性。
2.2 為什麼使用 SDS
通過上面阿粉提到的内容我們知道了 SDS 比傳統的 C 語言的字元串有很多優勢，也正是這些必不可少的優勢才促成了 SDS的存在。Redis 是一個高性能的記憶體資料庫，是以在性能方面要求特别高，這種設計方式雖然浪費了一定的空間，但是為了達到性能的要求也是值得的。有空間換時間的這種方式，在軟體設計的領域還是很多的。
2.3 SDS 常用 API
上面阿粉說的都是一些原理，下面從源碼上給大家展示一下。在 2.1 中提到有擷取長度 len 和釋放空間 free 的動作，那麼對應在 SDS 底層必定會有提供支援的 API，下面我們通過源碼來看幾個常用的 API。
- 在源碼 sds.c 檔案中 sdsfree 函數定義如下
/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
if (s == NULL) return;
s_free((char*)s-sdsHdrSize(s[-1]));
} 複制
- 在源碼 sds.h 檔案中 sdslen 函數定義如下
static inline size_t sdslen(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
} 複制
上面兩個是 SDS 底層對應的
sdsfree
和
sdslen
函數，用于釋放 SDS 空間和擷取 SDS 的長度。
- 在源碼 sds.c 檔案中建立 sds 的函數定義如下
/* Create an empty (zero length) sds string. Even in this case the string
* always has an implicit null term. */
sds sdsempty(void) {
return sdsnewlen("",0);
}
/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
size_t initlen = (init == NULL) ? 0 : strlen(init);
return sdsnewlen(init, initlen);
} 複制
上面兩個是 SDS 底層對應的
sdsempty
和
sdsnew
函數，顧名思義就是建立空的 SDS 和建立一個新的 SDS 字元串。
03、總結
這篇文章阿粉跟大家介紹了一下 Redis 的 SDS 和 SDS 底層的組成結構，并且與 C 語言傳統字元串進行的詳細的對比，闡述了 SDS 出現解決了哪些問題，最後帶大家從源碼中簡單的看了幾個底層的函數實作。
在走向骨灰級程式員的道路上，阿粉我從不懈怠，充滿鬥志，那麼你呢？是否跟阿粉一樣，對未來充滿期待！
今天是 2020 年的第一個周末，是以你想怎麼過能？歡迎加入到我們 Java 極客技術的知識星球中進行留言，我們共同進步成長。
04、參考文檔
- https://github.com/antirez/redis
- https://redis.io/
- 《Redis 設計與實作（第二版）》——黃建宏