SDS 基本概念

簡單動態(tài)字符串（Simple Dynamic String）SDS，用作Redis 的默認字符串。

C語言中的字符串：以空字符結(jié)尾的字符數(shù)組

SDS實現(xiàn)舉例

redis > SET msg "hello world"
OK

我們通過 SET 在 Redis 數(shù)據(jù)庫中創(chuàng)建了一個數(shù)據(jù)鍵對象為 "msg" 和 數(shù)據(jù)值對象為 "hello world" 的鍵值對，其中數(shù)據(jù)鍵和數(shù)據(jù)值對象底層的字符串實現(xiàn)都是 SDS 。同時， SDS 還被用于 AOF 緩沖區(qū)。

SDS 定義

struct sdshdr {
    # 記錄 buf 數(shù)組中已使用字節(jié)的數(shù)量，即當前字符串長度值  
    # 等于 SDS 所保存字符串的字節(jié)長度
    int len;
    # 記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量，buf空余可用的長度，append時使用  
    int free;
    # 字節(jié)char數(shù)組，用于保存字符串，實際保存字符串數(shù)據(jù)，最后一個字節(jié)保存了空字符 '\0'
    char buf[];
};

buf 屬性的字節(jié)數(shù)組中的字符串長度等于 len 屬性值加上1，因為 Redis遵循 C語言的規(guī)范，在SDS數(shù)據(jù)類型字符串的結(jié)尾加上了 空字符串，額外占用 1 個字節(jié)空間，這1個字節(jié)空間不計算在 SDS 的 len屬性里面。

由于SDS將字符串的結(jié)尾加上了 空字符串符合C語言字符串規(guī)范，Redis 字符串操作可以兼容C語言中一部分字符串庫中的函數(shù)，Redis 無需專門為 SDS在編寫一套函數(shù)。

SDS的優(yōu)點

常數(shù)復(fù)雜度獲取字符串長度

1. C字符串需要遍歷整個字符串，計數(shù)，直到碰到空字符，停止計數(shù)，復(fù)雜度為O(N)
2. SDS獲取 len 屬性值即可，復(fù)雜度為 O(1) 。所以 STRLEN 的復(fù)雜度也為 O(1)

API安全，杜絕緩沖區(qū)溢出

1. C字符串在進行字符串拼接 strcat 時，需要預(yù)先分配足夠的空間，來容納拼接的字符串，否則會造成緩沖區(qū)溢出的問題，比如臨近的空間有另外一個字符串。
2. SDS 在進行字符串拼接時，會先檢查 len 的長度是否足夠，如果不夠，會先擴展 len，再進行字符串拼接。

減少修改字符串長度時所需的內(nèi)存重分配次數(shù)

• 空間預(yù)分配
• 當對 SDS 進行空間擴展時，計算擴展之后的 len值如果小于 1mb，那么久會分配 擴展之后的 len 值給 free 屬性作為，為下次擴展時預(yù)分配的未使用空間，如果下次擴展所需字節(jié)空間小于 free 的值，那么就無需進行空間擴展，直接使用未使用空間。
• 惰性空間釋放
• 同樣，默認情況下，對 SDS 進行縮減時，縮減的空間不會立刻被這個SDS釋放，而是分配給 free ，如果之后再進行擴展時，有可能會用到。
• Redis 的 SDS 類型通過這兩種空間分配策略，減少了字符串增長縮減時所需的內(nèi)存重分配操作，為內(nèi)存分配提供了優(yōu)化。

二進制安全

Redis 通過 len屬性的值來判斷是否結(jié)束，而不是C字符串的 \0 作為結(jié)束。

兼容部分C字符串函數(shù)

上面已經(jīng)提到SDS在末尾添加了 \0 ，這樣可以兼容部分C字符串函數(shù)，可以直接使用 string.h> 函數(shù)庫。

Redis 字符串源碼原理

1、Redis的字符串結(jié)構(gòu)被設(shè)計成一個[SDS]結(jié)構(gòu)

字符串實際內(nèi)容是被存放在一個數(shù)組中，如下表

struct SDST> {
  T capacity; // 數(shù)組容量
  T len; // 數(shù)組實際長度
  byte flags; // 特殊標識位，不理睬它
  byte[] content; // 數(shù)組內(nèi)容
}

當字符串的大小超出當前分配的capacity大小時，數(shù)組將擴容，分配更大的數(shù)組，將舊的數(shù)組拷貝到新數(shù)組中，再將增加到字符串添加進去。

2、embstr 與raw

1）Redis的字符串的儲存方式分為2種，當長度特別短時，使用emb形式存儲，當長度超出44時，使用raw存儲。

2）倆者的區(qū)別：

Redis的對象頭結(jié)構(gòu)如下：

struct RedisObject {
    int4 type; // 4bits
    int4 encoding; // 4bits
    int24 lru; // 24bits
    int32 refcount; // 4bytes
    void *ptr; // 8bytes，64-bit system
} robj;

解析：不同的對象具有不同類型的type；同一個類型的type會有不同的存儲形式encoding；使用lru來記錄對象的LRU信息，每個對象都有一個引用計數(shù)，當計數(shù)為0的時候，對象就會被銷毀，內(nèi)存被回收；pre指針用來指示對象內(nèi)容具體存儲位置；上訴對象有結(jié)構(gòu)內(nèi)容加起來需要占用16字節(jié)的存儲空間。

SDS對象頭大小：實際內(nèi)容的大小(capacity) + 3byte，3是用來存儲capacity + len + flags內(nèi)容加起來的長度，而content數(shù)組初始值是16，所有SDS最小的大小是19 (16+3 )；

存儲形式如下圖：

解析：embstr將RedisObject對象頭和SDS對象連續(xù)存在一起，使用malloc方法一次分配；而raw需要倆次malloc，倆個對象頭砸死內(nèi)存地址上一般是不連續(xù)的。embstr最大能容納的字符串長度是44字節(jié)

3、擴容策略

字符串在長度小于1M之前，擴容空間采用加倍策略，即保留100%冗余空間。當長度大于1M，沒次擴容只會多分配1M的冗余空間。

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。