[[312201]]

大家好，我是鴨血粉絲(大家會親切的喊我 「阿粉」)，是一位喜歡吃鴨血粉絲的程序員，之前給大家總結(jié)了線上 OOM 的情況，相信大家也能從中學(xué)到一些東西，身為一名有追求的程序員，阿粉我的理解是光會吃老本是不行的，所以我一直也在學(xué)習(xí)，今天大家就跟我一起來了解一下 Redis 的 SDS 吧(不是 SOS 哦~)。

01、SDS 數(shù)據(jù)結(jié)構(gòu)

Redis 底層是基于 C 語言來開發(fā)的，但是它沒有采用 C 語言傳統(tǒng)的字符串表示方式，而是自定義了一種叫做 SDS(Sample Dynamic String，簡單動態(tài)字符串)的數(shù)據(jù)結(jié)構(gòu)來表示字符串。傳統(tǒng)的 C 語言的字符串是采用空字符(\0)作為結(jié)尾的字符數(shù)組，SDS 的數(shù)據(jù)結(jié)構(gòu)稍微復(fù)雜一點，整個結(jié)構(gòu)包含三個部分，是 Redis 的基礎(chǔ)。(阿粉猜測這里就是傳說中的青出于藍(lán)而勝于藍(lán))。

1.1、數(shù)據(jù)結(jié)構(gòu)

在源碼 sds.h/sdshdr 結(jié)構(gòu)體中定義了 SDS 的數(shù)據(jù)結(jié)構(gòu)，包括三個部分，free，len，buf[]，依次含義如下

1. buf[]：字節(jié)數(shù)組，用于存放實際的字符串;
2. len：記錄 buf 數(shù)組中已經(jīng)使用的字節(jié)數(shù)量，等同于 SDS 所保存的字符串的長度;
3. free：記錄 buf 數(shù)組中未使用的字節(jié)的數(shù)量。

說明

上圖中的 SDS 表示一個存放了 'RED' 字符串，已經(jīng)使用的長度為 3，未使用的長度為 2(這里用空白格表示未使用)，其中的 '\0' 表示的是字符串的結(jié)束，不計算在 SDS 的 len 中，并且由 SDS 底層函數(shù)自動添加，對使用者來說是透明。這里統(tǒng)一采用空字符(\0)結(jié)尾是為了復(fù)用 C 語言的相關(guān)函數(shù)。這個相信大家也很能理解，畢竟有祖宗可以靠，沒必要全靠自己那么辛苦~。

02、為什么采用 SDS

2.1、SDS 與 C語言字符串的區(qū)別

在說明 Redis 為什么要自定義 SDS 之前，阿粉覺得我們應(yīng)該先看一下 SDS 與傳統(tǒng)的 C 語言的字符串有什么區(qū)別，知道了具體的區(qū)別我們才能知道這樣實現(xiàn)的原因是什么。

2.1.1、O(1) 獲取字符串的長度

傳統(tǒng)的 C 語言字符串如果要獲取字符串的長度，則需要遍歷整個字符串，直到遇到 '\0' 字符，才知道整個字符串的長度是多少，操作復(fù)雜度是 O(n) 的。但是在 SDS 中，由于我們記錄了字符串的長度，所以在獲取字符串長度的時候是可以直接獲取的，整個操作為 O(1)。

如上面的示例，我們可以直接獲取字符串的長度是 3，而不需要遍歷，另外字符串 Key 在 Redis 的底層實現(xiàn)就是采用 SDS 的，所以這個特性就保證了我們在計算 Key 的長度的時候不會出現(xiàn)任何瓶頸，對系統(tǒng)的性能不會有任何影響。

2.1.2、動態(tài)擴容

由于 SDS 中記錄了未使用的空間大小，所以如果出現(xiàn)對已有字符串進行修改或者賦值時，SDS 底層函數(shù)會自動檢測剩余空間是否能滿足此次修改，如果 free 空間足夠則直接修改;如果 free 空間不夠則會先進行動態(tài)擴容達到能滿足的空間大小，然后再執(zhí)行修改動作。整個擴容的動作是 SDS 底層函數(shù)自動完成，對使用者無感。

而對于傳統(tǒng)的 C 語言字符串，如果在修改前忘記手動擴容則會導(dǎo)致字符串后面的數(shù)據(jù)被覆蓋。這里阿粉就不得不說一句了，為了方便大眾程序員，另一些骨灰級程序員(嗯，仿佛看到了未來的阿粉)也是操碎了心啊~

2.1.3、減少內(nèi)存分配次數(shù)

在傳統(tǒng)的 C 語言的字符串，我們每次對字符串的修改都會涉及到字符串內(nèi)存的重新分配，不管是增加還是減少字符串的長度。這種情況下，如果我們多次對字符串的長度進行調(diào)整的時候就會導(dǎo)致多次的內(nèi)存重新分配。

而在 SDS 中我們在對一個 SDS 初始化的時候會根據(jù)實際 buf[] 字符串的長度進行預(yù)先空間分配，并且標(biāo)記為 free。這種方式叫做空間預(yù)分配，在很大程度上可以減少增加字符串長度導(dǎo)致內(nèi)存重新分配的情況。free 的空間分配的策略是根據(jù) buf[] 大小來決定的，如果 buf[] 大小小于 1MB，則 len 多大 free 就多大;如果 buf[] 大小大于 1MB，則 free 固定設(shè)置為 1MB。

上面說的是SDS 字符串的長度增加，另外如果 SDS 的字符串長度減少，那么 SDS 會將減少的長度存放到 free 中，而不是直接回收，這樣可以方便下次如果再次使用，減少內(nèi)存重新分配。這種策略叫做惰性空間釋放。

同樣的上面兩種操作對使用者是完全無感的，阿粉覺得這種方案還是很合理的，不知道“元芳”你怎么看?

2.1.4、二進制安全

我們都知道 Redis 是可以存儲各種類型數(shù)據(jù)的，不僅是字符串也可以存儲圖片，視頻等二進制數(shù)據(jù)流。這是由于 Redis 不依賴一 '\0' 空字符作為結(jié)束字符。C 語言之所以不支持就是因為二進制流中會攜帶 '\0' 字符，導(dǎo)致無法知道字符串真實的結(jié)束位置。這就帶來了另一個 Redis 特性，就是二進制的安全性。

2.2 為什么使用 SDS

通過上面阿粉提到的內(nèi)容我們知道了 SDS 比傳統(tǒng)的 C 語言的字符串有很多優(yōu)勢，也正是這些必不可少的優(yōu)勢才促成了 SDS的存在。Redis 是一個高性能的內(nèi)存數(shù)據(jù)庫，所以在性能方面要求特別高，這種設(shè)計方式雖然浪費了一定的空間，但是為了達到性能的要求也是值得的。有空間換時間的這種方式，在軟件設(shè)計的領(lǐng)域還是很多的。

2.3 SDS 常用 API

上面阿粉說的都是一些原理，下面從源碼上給大家展示一下。在 2.1 中提到有獲取長度 len 和釋放空間 free 的動作，那么對應(yīng)在 SDS 底層必定會有提供支持的 API，下面我們通過源碼來看幾個常用的 API。

1.源碼 sds.c 文件中 sdsfree 函數(shù)定義如下：

/* 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])); 
} 

2.在源碼 sds.h 文件中 sdslen 函數(shù)定義如下：

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 底層對應(yīng)的 sdsfree 和 sdslen 函數(shù)，用于釋放 SDS 空間和獲取 SDS 的長度。

3.在源碼 sds.c 文件中創(chuàng)建 sds 的函數(shù)定義如下：

/* 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 底層對應(yīng)的 sdsempty 和 sdsnew 函數(shù)，顧名思義就是創(chuàng)建空的 SDS 和創(chuàng)建一個新的 SDS 字符串。

03、總結(jié)

這篇文章阿粉跟大家介紹了一下 Redis 的 SDS 和 SDS 底層的組成結(jié)構(gòu)，并且與 C 語言傳統(tǒng)字符串進行的詳細(xì)的對比，闡述了 SDS 出現(xiàn)解決了哪些問題，最后帶大家從源碼中簡單的看了幾個底層的函數(shù)實現(xiàn)。

在走向骨灰級程序員的道路上，阿粉我從不懈怠，充滿斗志，那么你呢?是否跟阿粉一樣，對未來充滿期待!

今天是 2020 年的第一個周末，所以你想怎么過能?歡迎加入到我們 Java 極客技術(shù)的知識星球中進行留言，我們共同進步成長。

04、參考文檔

https://github.com/antirez/redis

https://redis.io/

《Redis 設(shè)計與實現(xiàn)(第二版)》——黃建宏