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

作者：佚名 2021-02-23 09:35:33

數(shù)據(jù)庫(kù) 其他數(shù)據(jù)庫(kù) Redis

2021開工第一天，就有小伙伴私信我，還給我分享了一道他面阿里的redis題，題目很簡(jiǎn)單，是那種典型的似懂非懂，這里整理出來分享一下，順便自己鞏固一下基礎(chǔ)，希望對(duì)正在面試和想要面試的兄弟有點(diǎn)幫助。

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

題目大致是這樣的

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

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

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

鐵子：·····

[[383116]]

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

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

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

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

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

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

效率高

舉個(gè)例子：工作中使用redis，經(jīng)常會(huì)通過STRLEN命令得到一個(gè)字符串的長(zhǎng)度，在SDS結(jié)構(gòu)中l(wèi)en屬性記錄了字符串的長(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é)才能放下啊，怎么搞？

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

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

不過有個(gè)特殊的地方，在把“程序員內(nèi)點(diǎn)事”的6個(gè)字節(jié)擴(kuò)容到“程序員內(nèi)點(diǎn)事123”9個(gè)字節(jié)后，發(fā)現(xiàn)free屬性的值變成了擴(kuò)容后字符串的總長(zhǎng)度，這就涉及到下邊要說的內(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通過兩種內(nèi)存重分配策略，很好的解決了字符串在增長(zhǎng)和縮短時(shí)的內(nèi)存分配問題。

1.空間預(yù)分配

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

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