面試官：Redis 為什么把簡單的字符串設(shè)計成 SDS？
最近有小伙伴分享了一道 Redis 面試題，我看了以后覺得挺有意思。題目很簡單，是那種典型的似懂非懂，常常容易被大家忽略的問題。這里整理出來分享一下，順便自己鞏固一下基礎(chǔ)，希望對正在面試和想要面試的兄弟有點(diǎn)幫助。
題目大致是這樣的：
面試官：了解redis的String數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)嘛?
鐵子：當(dāng)然知道，是基于 SDS 實(shí)現(xiàn)的。
面試官：Redis 是用 C 語言開發(fā)的，那為啥不直接用 C 的字符串，還單獨(dú)設(shè)計 SDS 這樣的結(jié)構(gòu)呢?
鐵子：·····
實(shí)看得出面試官是想看看，鐵子是只停留在 Redis 的使用層面，還是對底層數(shù)據(jù)結(jié)構(gòu)有過更深入的研究，面試嘛都愛這樣問大家都懂得。
我們知道 Redis 是用 C 寫的，但它卻沒有完全直接使用 C 的字符串，而是自己又重新構(gòu)建了一個叫簡單動態(tài)字符串 SDS（simple dynamic string）的抽象類型。
Redis 也支持使用 C 語言的傳統(tǒng)字符串，只不過會用在一些不需要對字符串修改的地方，比如靜態(tài)的字符輸出。
而我們開發(fā)中使用 Redis，往往會經(jīng)常性的修改字符串的值，這個時候就會用 SDS 來表示字符串的值了。
有一點(diǎn)值得注意：在 Redis 數(shù)據(jù)庫中，key-value 鍵值對含有字符串值的，都是由 SDS 來實(shí)現(xiàn)的。
比如，在 Redis 執(zhí)行一個最簡單的 set 命令，這時 Redis 會新建一個鍵值對。
127.0.0.1:6379> set xiaofu "程序員內(nèi)點(diǎn)事"此時鍵值對的 key 和 value 都是一個字符串對象，而對象的底層實(shí)現(xiàn)分別是兩個保存著字符串 xiaofu 和程序員內(nèi)點(diǎn)事的 SDS 結(jié)構(gòu)。
再比如：我向一個列表中壓入數(shù)據(jù)，Redis 又會新建一個鍵值對。
127.0.0.1:6379> lpush xiaofu "程序員內(nèi)點(diǎn)事" "程序員小富"這時候鍵值對的鍵和上邊一樣，還是一個由 SDS 實(shí)現(xiàn)的字符串對象，鍵值對的值是一個包含兩個字符串對象的列表對象了。而這兩個對象的底層也是由 SDS 實(shí)現(xiàn)。
SDS 結(jié)構(gòu)
一個 SDS 值的數(shù)據(jù)結(jié)構(gòu)，主要由 len、free、buf[] 這三個屬性組成。
struct sdshdr{int free; // buf[]數(shù)組未使用字節(jié)的數(shù)量int len; // buf[]數(shù)組所保存的字符串的長度char buf[]; // 保存字符串的數(shù)組}
其中，buf[] 為實(shí)際保存字符串的 char 類型數(shù)組。free 表示 buf[] 數(shù)組未使用字節(jié)的數(shù)量， len 表示 buf[] 數(shù)組所保存的字符串的長度。
例如上圖表示的是 buf[] 保存長度為 6 個字節(jié)的字符串，未使用的字節(jié)數(shù) free 為 0，但是眼尖的同學(xué)會發(fā)現(xiàn)這明明是 7 個字符，還有一個"\0"??？
上邊提到過 SDS 沒有完全直接使用 C 的字符串，還是沿用了一些 C 特性的，比如遵循 C 的字符串以空格符結(jié)尾的規(guī)則。這樣還可以使用一部分 C 字符串的函數(shù)。而對于 SDS 來說，空字符串占用的一字節(jié)是不計算在 len 屬性里的，會為他分配額外的空間。
簡單了解 SDS 結(jié)構(gòu)后，下邊我們來看看 SDS 相比于 C 字符串有哪些優(yōu)點(diǎn)。
效率高
舉個例子：
工作中使用 Redis，經(jīng)常會通過 STRLEN 命令得到一個字符串的長度，在 SDS 結(jié)構(gòu)中 len 屬性記錄了字符串的長度，所以我們獲取一個字符串長度直接取 len 的值，復(fù)雜度是 O(1)。
而如果用 C 字符串，在獲取一個字符串長度時，需對整個字符串進(jìn)行遍歷，直至遍歷到空格符結(jié)束（C 中遇到空格符代表一個完整字符串）。此時的復(fù)雜度是 O(N)。
在高并發(fā)場景下頻繁遍歷字符串，獲取字符串的長度很有可能成為 Redis 的性能瓶頸，所以 SDS 性能更好一些。
數(shù)據(jù)溢出
上邊提到 C 字符串是不記錄自身長度的，相鄰的兩個字符串存儲的方式為字符串分配了合適的內(nèi)存空間。
如下圖所示：
如果此時我想把“程序員內(nèi)點(diǎn)事”改成“程序員內(nèi)點(diǎn)事123”，可之前分配的內(nèi)存只有 6 個字節(jié)，修改后的字符串需要 9 個字節(jié)才能放下啊，怎么搞？
沒辦法只能侵占相鄰字符串的空間，自身數(shù)據(jù)溢出導(dǎo)致其他字符串的內(nèi)容被修改。
而 SDS 很好的規(guī)避了這點(diǎn)：當(dāng)我們需要修改數(shù)據(jù)時，首先會檢查當(dāng)前 SDS 空間 len 是否滿足，不滿足則自動擴(kuò)容空間至修改所需的大小，然后再執(zhí)行修改。
如下圖所示：
不過有個特殊的地方，在把“程序員內(nèi)點(diǎn)事”的 6 個字節(jié)擴(kuò)容到“程序員內(nèi)點(diǎn)事123” 9 個字節(jié)后，發(fā)現(xiàn) free 屬性的值變成了擴(kuò)容后字符串的總長度。這就涉及到下邊要說的內(nèi)存重分配策略了。
內(nèi)存重分配策略
C 字符串長度是一定的，所以每次在增長或者縮短字符串時，都要做內(nèi)存的重分配。而內(nèi)存重分配算法通常又是一個比較耗時的操作，如果程序不經(jīng)常修改字符串還是可以接受的。
但很不幸，Redis 作為一個數(shù)據(jù)庫，數(shù)據(jù)肯定會被頻繁修改。如果每次修改都要執(zhí)行一次內(nèi)存重分配，那么就會嚴(yán)重影響性能。
SDS 通過兩種內(nèi)存重分配策略，很好的解決了字符串在增長和縮短時的內(nèi)存分配問題。
1. 空間預(yù)分配
空間預(yù)分配策略用于優(yōu)化 SDS 字符串增長操作，當(dāng)修改字符串并需對SDS的空間進(jìn)行擴(kuò)展時，不僅會為 SDS 分配修改所必要的空間，還會為 SDS 分配額外的未使用空間 free，下次再修改就先檢查未使用空間 free 是否滿足，滿足則不用在擴(kuò)展空間。
通過空間預(yù)分配策略，Redis 可以有效的減少字符串連續(xù)增長操作，所產(chǎn)生的內(nèi)存重分配次數(shù)。
額外分配未使用空間 free 的規(guī)則：
如果對 SDS 字符串修改后，len 值小于 1M，那么此時額外分配未使用空間 free 的大小與 len 相等。 如果對 SDS 字符串修改后，len 值大于等于 1M，那么此時額外分配未使用空間 free 的大小為1M。
2. 惰性空間釋放
惰性空間釋放策略則用于優(yōu)化 SDS 字符串縮短操作。當(dāng)縮短 SDS 字符串后，并不會立即執(zhí)行內(nèi)存重分配來回收多余的空間，而是用 free 屬性將這些空間記錄下來。如果后續(xù)有增長操作，則可直接使用。
數(shù)據(jù)格式多樣性
C 字符串中的字符必須符合某些特定的編碼格式。而且上邊我們也提到，C 字符串以 \0 空字符結(jié)尾標(biāo)識一個字符串結(jié)束。所以，字符串里邊是不能包含 \0 的，不然就會被誤認(rèn)是多個。
由于這種限制，使得 C 字符串只能保存文本數(shù)據(jù)，像音視頻、圖片等二進(jìn)制格式的數(shù)據(jù)是無法存儲的。
Redis 會以處理二進(jìn)制的方式操作 Buf 數(shù)組中的數(shù)據(jù)，所以對存入其中的數(shù)據(jù)未做任何的限制、過濾。只要存進(jìn)來什么樣，取出來還是什么樣。
總結(jié)
上邊只是 Redis 數(shù)據(jù)結(jié)構(gòu)的一點(diǎn)基礎(chǔ)知識，沒什么難度。但以我的面試經(jīng)驗(yàn)，如果被問這類問題，不要只含糊其辭的說出底層是 SDS，有理有據(jù)的把為什么這樣實(shí)現(xiàn)也說出來。
一來可以顯得自己基本功扎實(shí)，如果表達(dá)的在條理清晰，是個很不錯的加分項(xiàng)。再一個主動打消面試官問下去的念頭，當(dāng)然就怕不按套路出牌的人！
— 【 THE END 】— 本公眾號全部博文已整理成一個目錄，請在公眾號里回復(fù)「m」獲??！ 最近面試BAT，整理一份面試資料《Java面試BATJ通關(guān)手冊》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：點(diǎn)“在看”，關(guān)注公眾號并回復(fù) PDF 領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
文章有幫助的話，在看，轉(zhuǎn)發(fā)吧。
謝謝支持喲 (*^__^*）