簡單動態(tài)字符串(simple dynamic string,SDS)

1. 簡單動態(tài)字符串

Redis 沒有直接使用 C 語言傳統(tǒng)的字符串表示（以空字符結(jié)尾的字符數(shù)組，以下簡稱 C 字符串）。

Redis 構(gòu)建了一種名為簡單動態(tài)字符串（simple dynamic string,SDS）的抽象類型，并將其作為Redis的默認(rèn)字符串表示。

SDS定義:

struct?sdshdr{
????//記錄?buf?數(shù)組中已使用字節(jié)的數(shù)量
????//等于?SDS?所保存字符串的長度
????int?len;

????//記錄?buf?數(shù)組中未使用字節(jié)的數(shù)量
????int?free;

????//字節(jié)數(shù)組，用于保存字符串
????char?buf[];
}

SDS遵循C字符串以空字符結(jié)尾的慣例，保存空字符的1字節(jié)空間不計(jì)算在SDS的len屬性中，空字符額外占1字節(jié)空間，添加空字符到字符串末尾等操作，都是由SDS函數(shù)自動完成。

2. SDS 與 C 字符串區(qū)別

2.1 獲取字符串長度的復(fù)雜度

在C語言中，其字符串并不記錄自身的長度信息，獲取一個(gè)C字符串長度需要遍歷整串，復(fù)雜度為O(N)?。

SDS的len屬性中直接就記錄了其本身的長度，故獲取其長度的復(fù)雜度為O(1)。

在Redis中，通過使用SDS將獲取字符串長度的復(fù)雜度從O(N)降到O(1)，這確保了獲取字符串長度的工作不會成為Redis的性能瓶頸。例如，Redis 的字符串鍵在底層上也是通過SDS實(shí)現(xiàn)的，即使對一個(gè)非常長的字符串鍵反復(fù)執(zhí)行STRLEN命令，也不會影響 Redis 性能。

2.2 杜絕緩沖區(qū)溢出

因?yàn)?/span>C字符串不記錄自身長度，當(dāng)一個(gè)字符串str2拼接到字符串str1時(shí)，很可能因?yàn)?/span>str1自身空間分配不足造成緩沖區(qū)溢出。

SDS的空間分配策略完全杜絕了發(fā)生緩沖區(qū)溢出的可能性：當(dāng)SDS的API需要對其進(jìn)行修改時(shí)，API會先檢查其空間是否滿足修改需求，若不滿足，則API會自動將SDS的空間擴(kuò)展到執(zhí)行修改所需的大小，然后采取執(zhí)行真正的修改操作。

舉個(gè)例子，<string.h>/strcat 是一個(gè)具有拼接字符串功能的函數(shù)，現(xiàn)有字符串str1保存了一個(gè)字符串"Redis"，字符串str2保存了"SpringBoot"，且它倆在內(nèi)存中的位置是相鄰的。

當(dāng)執(zhí)行 strcat(str1," Mysql"); 操作時(shí)，str1并沒有足夠的空間，那么 strcat 函數(shù)執(zhí)行后，str1的數(shù)據(jù)將會溢出到str2所在空間，str2之前所保存的內(nèi)容會被修改。

2.3 減少修改字符串帶來的內(nèi)存重新分配次數(shù)

C字符串并不記錄自身長度，其每次增長或縮短，程序都總要對保存這個(gè)C字符串的數(shù)組進(jìn)行一次內(nèi)存重新分配操作，而這通常是耗時(shí)操作。

SDS通過未使用空間(free)解除了字符串長度和底層數(shù)組長度之間的關(guān)聯(lián)，且通過未使用空間，實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化策略。

空間預(yù)分配：?空間預(yù)分配用于優(yōu)化SDS的字符串增長操作，當(dāng)SDS進(jìn)行空間擴(kuò)展時(shí)，程序不僅會為其分配修改所必須的空間，還會為其分配額外未使用的空間。

• ??如果對SDS進(jìn)行修改后，SDS的長度（也即是len屬性的值）將小于1MB，那么程序?qū)⒎峙浜?/span>len?屬性同樣大小的未使用空間。

• ??如果對SDS進(jìn)行修改后，SDS的長度將大于等于1MB，那么程序?qū)⒎峙?/span>1MB的未使用空間。

惰性空間釋放：?惰性空間釋放用于優(yōu)化SDS的字符串縮短操作：當(dāng)SDS進(jìn)行空間收縮時(shí)，程序不會立即使用空間分配來回收縮短后多出來的字節(jié)，而是使用free屬性將這些字節(jié)數(shù)量記錄起來，并等待將來使用

SDS也提供了相應(yīng)的API，在有需要時(shí)可以真正的釋放SDS未使用的空間，所以不用擔(dān)心惰性空間釋放策略會造成內(nèi)存浪費(fèi)。

2.4 二進(jìn)制安全

C字符串中不能包含空格，否則最先被程序讀入的空字符將被誤認(rèn)為是字符串結(jié)尾，使得C字符串只能保存文本數(shù)據(jù)，而不能保存如圖片、音頻、視頻等二進(jìn)制數(shù)據(jù)。

SDS的API會以處理二進(jìn)制的方式處理存放在buf數(shù)組中的數(shù)據(jù)，程序不會對其中的數(shù)據(jù)做任何的限制、過濾，數(shù)據(jù)在寫入時(shí)是什么樣的，它被讀取時(shí)就是什么樣。

2.5 對比總結(jié)

參考：[1]黃健宏. Redis設(shè)計(jì)與實(shí)現(xiàn)[M]. 機(jī)械工業(yè)出版社, 2014.