阿里面試這樣問：redis 為什么把簡單的字符串設計成 SDS？
面試官：了解redis的String數(shù)據(jù)結構底層實現(xiàn)嘛?
鐵子：當然知道，是基于SDS實現(xiàn)的
面試官：redis是用C語言開發(fā)的，那為啥不直接用C的字符串，還單獨設計SDS這樣的結構呢?
鐵子：·····
“其實看得出面試官是想看看，鐵子是只停留在redis的使用層面，還是對底層數(shù)據(jù)結構有過更深入的研究，面試嘛都愛這樣問大家都懂得。
redis是用C寫的，但它卻沒有完全直接使用C的字符串，而是自己又重新構建了一個叫簡單動態(tài)字符串SDS（simple dynamic string）的抽象類型。redis也支持使用C語言的傳統(tǒng)字符串，只不過會用在一些不需要對字符串修改的地方，比如靜態(tài)的字符輸出。redis，往往會經(jīng)常性的修改字符串的值，這個時候就會用SDS來表示字符串的值了。有一點值得注意：在redis數(shù)據(jù)庫中，key-value鍵值對含有字符串值的，都是由SDS來實現(xiàn)的。redis執(zhí)行一個最簡單的set命令，這時redis會新建一個鍵值對。127.0.0.1:6379> set xiaofu "AAA"
key和value都是一個字符串對象，而對象的底層實現(xiàn)分別是兩個保存著字符串xiaofu和AAA的SDS結構。127.0.0.1:6379> lpush xiaofu "AAA" "BBB"
SDS結構
len、free、buf[]這三個屬性組成。struct sdshdr{
int free; // buf[]數(shù)組未使用字節(jié)的數(shù)量
int len; // buf[]數(shù)組所保存的字符串的長度
char buf[]; // 保存字符串的數(shù)組
}
buf[]為實際保存字符串的char類型數(shù)組；free表示buf[]數(shù)組未使用字節(jié)的數(shù)量；len表示buf[]數(shù)組所保存的字符串的長度。
buf[]保存長度為6個字節(jié)的字符串，未使用的字節(jié)數(shù)free為0，但是眼尖的同學會發(fā)現(xiàn)這明明是7個字符，還有一個"\0"?。?/span>SDS沒有完全直接使用C的字符串，還是沿用了一些C特性的，比如遵循C的字符串以空格符結尾的規(guī)則，這樣還可以使用一部分C字符串的函數(shù)。而對于SDS來說，空字符串占用的一字節(jié)是不計算在len屬性里的，會為他分配額外的空間。效率高
redis，經(jīng)常會通過STRLEN命令得到一個字符串的長度，在SDS結構中len屬性記錄了字符串的長度，所以我們獲取一個字符串長度直接取len的值，復雜度是O(1)。
redis的性能瓶頸，所以SDS性能更好一些。數(shù)據(jù)溢出
“AAA”改成“AAA123”，可之前分配的內(nèi)存只有6個字節(jié)，修改后的字符串需要9個字節(jié)才能放下啊，怎么搞？
侵占相鄰字符串的空間，自身數(shù)據(jù)溢出導致其他字符串的內(nèi)容被修改。len是否滿足，不滿足則自動擴容空間至修改所需的大小，然后再執(zhí)行修改,如下圖所示。
“AAA”的6個字節(jié)擴容到“AAA123”9個字節(jié)后，發(fā)現(xiàn)free屬性的值變成了擴容后字符串的總長度，這就涉及到下邊要說的內(nèi)存重分配策略了。內(nèi)存重分配策略
redis作為一個數(shù)據(jù)庫，數(shù)據(jù)肯定會被頻繁修改，如果每次修改都要執(zhí)行一次內(nèi)存重分配，那么就會嚴重影響性能。1.空間預分配
free，下次再修改就先檢查未使用空間free是否滿足，滿足則不用在擴展空間。redis可以有效的減少字符串連續(xù)增長操作，所產(chǎn)生的內(nèi)存重分配次數(shù)。
free的規(guī)則：如果對 SDS 字符串修改后， len值小于1M，那么此時額外分配未使用空間free的大小與len相等。如果對 SDS 字符串修改后， len值大于等于1M，那么此時額外分配未使用空間free的大小為1M。
2.惰性空間釋放
free屬性將這些空間記錄下來，如果后續(xù)有增長操作，則可直接使用。
數(shù)據(jù)格式多樣性
\0空字符結尾標識一個字符串結束，所以字符串里邊是不能包含\0的，不然就會被誤認是多個。Buf數(shù)組中的數(shù)據(jù)，所以對存入其中的數(shù)據(jù)未做任何的限制、過濾，只要存進來什么樣，取出來還是什么樣。總結
有道無術，術可成；有術無道，止于術
歡迎大家關注Java之道公眾號
好文章，我在看??
評論
圖片
表情