阿里面試這樣問(wèn)：redis 為什么把簡(jiǎn)單的字符串設(shè)計(jì)成 SDS？

2021開(kāi)工第一天，就有小伙伴私信我，還給我分享了一道他面阿里的redis題（這家伙絕比已經(jīng)拿到年終獎(jiǎng)了），我看了以后覺(jué)得挺有意思，題目很簡(jiǎn)單，是那種典型的似懂非懂，常常容易被大家忽略的問(wèn)題。這里整理出來(lái)分享一下，順便自己鞏固一下基礎(chǔ)，希望對(duì)正在面試和想要面試的兄弟有點(diǎn)幫助。

題目大致是這樣的

面試官：了解redis的String數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)嘛?

鐵子：當(dāng)然知道，是基于SDS實(shí)現(xiàn)的

面試官：redis是用C語(yǔ)言開(kāi)發(fā)的，那為啥不直接用C的字符串，還單獨(dú)設(shè)計(jì)SDS這樣的結(jié)構(gòu)呢?

鐵子：·····

“

其實(shí)看得出面試官是想看看，鐵子是只停留在redis的使用層面，還是對(duì)底層數(shù)據(jù)結(jié)構(gòu)有過(guò)更深入的研究，面試嘛都愛(ài)這樣問(wèn)大家都懂得。

我們知道redis是用C寫(xiě)的，但它卻沒(méi)有完全直接使用C的字符串，而是自己又重新構(gòu)建了一個(gè)叫簡(jiǎn)單動(dòng)態(tài)字符串SDS（simple dynamic string）的抽象類(lèi)型。

redis也支持使用C語(yǔ)言的傳統(tǒng)字符串，只不過(guò)會(huì)用在一些不需要對(duì)字符串修改的地方，比如靜態(tài)的字符輸出。

而我們開(kāi)發(fā)中使用redis，往往會(huì)經(jīng)常性的修改字符串的值，這個(gè)時(shí)候就會(huì)用SDS來(lái)表示字符串的值了。有一點(diǎn)值得注意：在redis數(shù)據(jù)庫(kù)中，key-value鍵值對(duì)含有字符串值的，都是由SDS來(lái)實(shí)現(xiàn)的。

比如：在redis執(zhí)行一個(gè)最簡(jiǎn)單的set命令，這時(shí)redis會(huì)新建一個(gè)鍵值對(duì)。

127.0.0.1:6379>?set?xiaofu?"程序員內(nèi)點(diǎn)事"

此時(shí)鍵值對(duì)的key和value都是一個(gè)字符串對(duì)象，而對(duì)象的底層實(shí)現(xiàn)分別是兩個(gè)保存著字符串xiaofu和程序員內(nèi)點(diǎn)事的SDS結(jié)構(gòu)。

再比如：我向一個(gè)列表中壓入數(shù)據(jù)，redis 又會(huì)新建一個(gè)鍵值對(duì)。

127.0.0.1:6379>?lpush?xiaofu?"程序員內(nèi)點(diǎn)事"?"程序員小富"

這時(shí)候鍵值對(duì)的鍵和上邊一樣，還是一個(gè)由SDS實(shí)現(xiàn)的字符串對(duì)象，鍵值對(duì)的值是一個(gè)包含兩個(gè)字符串對(duì)象的列表對(duì)象了，而這兩個(gè)對(duì)象的底層也是由SDS實(shí)現(xiàn)。

SDS結(jié)構(gòu)

一個(gè)SDS值的數(shù)據(jù)結(jié)構(gòu)，主要由len、free、buf[]這三個(gè)屬性組成。

struct?sdshdr{

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

??int?len;?//?buf[]數(shù)組所保存的字符串的長(zhǎng)度

??char?buf[];?//?保存字符串的數(shù)組
}

其中buf[]為實(shí)際保存字符串的char類(lèi)型數(shù)組；free表示buf[]數(shù)組未使用字節(jié)的數(shù)量；len表示buf[]數(shù)組所保存的字符串的長(zhǎng)度。

例如上圖表示的是buf[]保存長(zhǎng)度為6個(gè)字節(jié)的字符串，未使用的字節(jié)數(shù)free為0，但是眼尖的同學(xué)會(huì)發(fā)現(xiàn)這明明是7個(gè)字符，還有一個(gè)"\0"??？

上邊提到過(guò)SDS沒(méi)有完全直接使用C的字符串，還是沿用了一些C特性的，比如遵循C的字符串以空格符結(jié)尾的規(guī)則，這樣還可以使用一部分C字符串的函數(shù)。而對(duì)于SDS來(lái)說(shuō)，空字符串占用的一字節(jié)是不計(jì)算在len屬性里的，會(huì)為他分配額外的空間。

簡(jiǎn)單了解SDS結(jié)構(gòu)后，下邊我們來(lái)看看SDS相比于C字符串有哪些優(yōu)點(diǎn)。

效率高

舉個(gè)例子：工作中使用redis，經(jīng)常會(huì)通過(guò)STRLEN命令得到一個(gè)字符串的長(zhǎng)度，在SDS結(jié)構(gòu)中len屬性記錄了字符串的長(zhǎng)度，所以我們獲取一個(gè)字符串長(zhǎng)度直接取len的值，復(fù)雜度是O(1)。

而如果用C字符串，在獲取一個(gè)字符串長(zhǎng)度時(shí)，需對(duì)整個(gè)字符串進(jìn)行遍歷，直至遍歷到空格符結(jié)束（C中遇到空格符代表一個(gè)完整字符串），此時(shí)的復(fù)雜度是O(N)。

在高并發(fā)場(chǎng)景下頻繁遍歷字符串，獲取字符串的長(zhǎng)度很有可能成為redis的性能瓶頸，所以SDS性能更好一些。

數(shù)據(jù)溢出

上邊提到C字符串是不記錄自身長(zhǎng)度的，相鄰的兩個(gè)字符串存儲(chǔ)的方式可能如下圖，為字符串分配了合適的內(nèi)存空間。

如果此時(shí)我想把“程序員內(nèi)點(diǎn)事”改成“程序員內(nèi)點(diǎn)事123”，可之前分配的內(nèi)存只有6個(gè)字節(jié)，修改后的字符串需要9個(gè)字節(jié)才能放下啊，怎么搞？

沒(méi)辦法只能侵占相鄰字符串的空間，自身數(shù)據(jù)溢出導(dǎo)致其他字符串的內(nèi)容被修改。

而SDS很好的規(guī)避了這點(diǎn)，當(dāng)我們需要修改數(shù)據(jù)時(shí)，首先會(huì)檢查當(dāng)前SDS空間len是否滿(mǎn)足，不滿(mǎn)足則自動(dòng)擴(kuò)容空間至修改所需的大小，然后再執(zhí)行修改,如下圖所示。

不過(guò)有個(gè)特殊的地方，在把“程序員內(nèi)點(diǎn)事”的6個(gè)字節(jié)擴(kuò)容到“程序員內(nèi)點(diǎn)事123”9個(gè)字節(jié)后，發(fā)現(xiàn)free屬性的值變成了擴(kuò)容后字符串的總長(zhǎng)度，這就涉及到下邊要說(shuō)的內(nèi)存重分配策略了。

內(nèi)存重分配策略

C字符串長(zhǎng)度是一定的，所以每次在增長(zhǎng)或者縮短字符串時(shí)，都要做內(nèi)存的重分配，而內(nèi)存重分配算法通常又是一個(gè)比較耗時(shí)的操作，如果程序不經(jīng)常修改字符串還是可以接受的。

但很不幸，redis作為一個(gè)數(shù)據(jù)庫(kù)，數(shù)據(jù)肯定會(huì)被頻繁修改，如果每次修改都要執(zhí)行一次內(nèi)存重分配，那么就會(huì)嚴(yán)重影響性能。

SDS通過(guò)兩種內(nèi)存重分配策略，很好的解決了字符串在增長(zhǎng)和縮短時(shí)的內(nèi)存分配問(wèn)題。

1.空間預(yù)分配

空間預(yù)分配策略用于優(yōu)化SDS字符串增長(zhǎng)操作，當(dāng)修改字符串并需對(duì)SDS的空間進(jìn)行擴(kuò)展時(shí)，不僅會(huì)為SDS分配修改所必要的空間，還會(huì)為SDS分配額外的未使用空間free，下次再修改就先檢查未使用空間free是否滿(mǎn)足，滿(mǎn)足則不用在擴(kuò)展空間。

通過(guò)空間預(yù)分配策略，redis可以有效的減少字符串連續(xù)增長(zhǎng)操作，所產(chǎn)生的內(nèi)存重分配次數(shù)。

額外分配未使用空間free的規(guī)則：

• 如果對(duì) SDS 字符串修改后，len 值小于 1M，那么此時(shí)額外分配未使用空間 free 的大小與len相等。
• 如果對(duì) SDS 字符串修改后，len 值大于等于 1M，那么此時(shí)額外分配未使用空間 free 的大小為1M。

2.惰性空間釋放

惰性空間釋放策略則用于優(yōu)化SDS字符串縮短操作，當(dāng)縮短SDS字符串后，并不會(huì)立即執(zhí)行內(nèi)存重分配來(lái)回收多余的空間，而是用free屬性將這些空間記錄下來(lái)，如果后續(xù)有增長(zhǎng)操作，則可直接使用。

數(shù)據(jù)格式多樣性

C字符串中的字符必須符合某些特定的編碼格式，而且上邊我們也提到，C字符串以\0空字符結(jié)尾標(biāo)識(shí)一個(gè)字符串結(jié)束，所以字符串里邊是不能包含\0的，不然就會(huì)被誤認(rèn)是多個(gè)。

由于這種限制，使得C字符串只能保存文本數(shù)據(jù)，像音視頻、圖片等二進(jìn)制格式的數(shù)據(jù)是無(wú)法存儲(chǔ)的。

redis 會(huì)以處理二進(jìn)制的方式操作Buf數(shù)組中的數(shù)據(jù)，所以對(duì)存入其中的數(shù)據(jù)未做任何的限制、過(guò)濾，只要存進(jìn)來(lái)什么樣，取出來(lái)還是什么樣。

總結(jié)

上邊只是 redis 數(shù)據(jù)結(jié)構(gòu)的一點(diǎn)基礎(chǔ)知識(shí)，沒(méi)什么難度，但以我的面試經(jīng)驗(yàn)，如果被問(wèn)這類(lèi)問(wèn)題,不要只含糊其辭的說(shuō)出底層是SDS，有理有據(jù)的把為什么這樣實(shí)現(xiàn)也說(shuō)出來(lái)。

一來(lái)可以顯得自己基本功扎實(shí)，如果表達(dá)的在條理清晰，是個(gè)很不錯(cuò)的加分項(xiàng)；在一個(gè)主動(dòng)打消面試官問(wèn)下去的念頭，當(dāng)然就怕不按套路出牌的人！