SDS 基本概念

簡(jiǎn)單動(dòng)態(tài)字符串（Simple Dynamic String）SDS，用作Redis 的默認(rèn)字符串。

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

SDS實(shí)現(xiàn)舉例

redis > SET msg "hello world"
OK

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

SDS 定義

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

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

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

SDS的優(yōu)點(diǎn)

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

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

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

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

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

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

二進(jìn)制安全

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

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

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

Redis 字符串源碼原理

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

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

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

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

2、embstr 與raw

1）Redis的字符串的儲(chǔ)存方式分為2種，當(dāng)長(zhǎng)度特別短時(shí)，使用emb形式存儲(chǔ)，當(dāng)長(zhǎng)度超出44時(shí)，使用raw存儲(chǔ)。

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

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

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

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

SDS對(duì)象頭大?。簩?shí)際內(nèi)容的大小(capacity) + 3byte，3是用來(lái)存儲(chǔ)capacity + len + flags內(nèi)容加起來(lái)的長(zhǎng)度，而content數(shù)組初始值是16，所有SDS最小的大小是19 (16+3 )；

存儲(chǔ)形式如下圖：

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

3、擴(kuò)容策略

字符串在長(zhǎng)度小于1M之前，擴(kuò)容空間采用加倍策略，即保留100%冗余空間。當(dāng)長(zhǎng)度大于1M，沒(méi)次擴(kuò)容只會(huì)多分配1M的冗余空間。

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