建站
咨詢
售后
建站咨詢
新聞中心
面試官：了解redis的String數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)嘛?
鐵子：當(dāng)然知道，是基于SDS實(shí)現(xiàn)的
面試官：redis是用C語言開發(fā)的，那為啥不直接用C的字符串，還單獨(dú)設(shè)計(jì)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 "AAA"
此時鍵值對的key和value都是一個字符串對象，而對象的底層實(shí)現(xiàn)分別是兩個保存著字符串xiaofu和AAA的SDS結(jié)構(gòu)。
再比如：我向一個列表中壓入數(shù)據(jù)，redis 又會新建一個鍵值對。
127.0.0.1:6379> lpush xiaofu "AAA" "BBB"
這時候鍵值對的鍵和上邊一樣，還是一個由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é)是不計(jì)算在len屬性里的，會為他分配額外的空間。
簡單了解SDS結(jié)構(gòu)后，下邊我們來看看SDS相比于C字符串有哪些優(yōu)點(diǎn)。
效率高
舉個例子：工作中使用redis，經(jīng)常會通過STRLEN命令得到一個字符串的長度，在SDS結(jié)構(gòu)中l(wèi)en屬性記錄了字符串的長度，所以我們獲取一個字符串長度直接取len的值，復(fù)雜度是O(1)。
???
而如果用C字符串，在獲取一個字符串長度時，需對整個字符串進(jìn)行遍歷，直至遍歷到空格符結(jié)束（C中遇到空格符代表一個完整字符串），此時的復(fù)雜度是O(N)。
在高并發(fā)場景下頻繁遍歷字符串，獲取字符串的長度很有可能成為redis的性能瓶頸，所以SDS性能更好一些。
數(shù)據(jù)溢出
上邊提到C字符串是不記錄自身長度的，相鄰的兩個字符串存儲的方式可能如下圖，為字符串分配了合適的內(nèi)存空間。
???
如果此時我想把“AAA”改成“AAA123”，可之前分配的內(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í)行修改,如下圖所示。
???
不過有個特殊的地方，在把“AAA”的6個字節(jié)擴(kuò)容到“AAA123”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)然就怕不按套路出牌的人！
分享文章：阿里面試這樣問：Redis為什么把簡單的字符串設(shè)計(jì)成SDS？
分享網(wǎng)址：http://www.5511xx.com/article/djsesop.html
