Redis的字符串是怎么實(shí)現(xiàn)的？
來(lái)源：www.cnblogs.com/wyc1994666/p/10669212.html
之前本人在找工作面試時(shí)在Redis相關(guān)問(wèn)題上可栽了跟頭。
面試官 ：?看你簡(jiǎn)歷上寫(xiě)了熟悉常用數(shù)據(jù)結(jié)構(gòu)，都有哪些說(shuō)說(shuō)
本人 ：?常用有5種，string,list,set,zset,hash（內(nèi)心很得意）
面試官 ：?那你說(shuō)說(shuō)都用過(guò)哪些數(shù)據(jù)結(jié)構(gòu)_ ?
本人 ：?用的最多的是string，通常會(huì)把json字符串存進(jìn)去_
面試官 ：?那你知道Redis內(nèi)部是怎么實(shí)現(xiàn)它的string的么？_ ?
本人 ：?呃～，我了解Redis是用C語(yǔ)言寫(xiě)的，至于具體實(shí)現(xiàn)就不清楚了～
到此一面卒～～～
有相同經(jīng)歷的朋友么？
回去后惡補(bǔ)了一下Redis有關(guān)原理性的知識(shí)點(diǎn)，恰好最近在最總結(jié)面試經(jīng)歷于是有了今天這篇文章。
本篇會(huì)講以下內(nèi)容：
Redis字符串的實(shí)現(xiàn)
Redis字符串的性能優(yōu)勢(shì)
Redis字符串的實(shí)現(xiàn)
Redis雖然是用C語(yǔ)言寫(xiě)的，但卻沒(méi)有直接用C語(yǔ)言的字符串，而是自己實(shí)現(xiàn)了一套字符串。目的就是為了提升速度，提升性能，可以看出Redis為了高性能也是煞費(fèi)苦心。
Redis構(gòu)建了一個(gè)叫做簡(jiǎn)單動(dòng)態(tài)字符串（Simple Dynamic String），簡(jiǎn)稱SDS
1.SDS 代碼結(jié)構(gòu)
struct?sdshdr{??
????//??記錄已使用長(zhǎng)度??
????int?len;??
????//?記錄空閑未使用的長(zhǎng)度??
????int?free;??
????//?字符數(shù)組??
????char[]?buf;??
};??
SDS ？什么鬼？可能對(duì)此陌生的朋友對(duì)這個(gè)名稱有疑惑。只是個(gè)名詞而已不必在意，我們要重點(diǎn)欣賞借鑒Redis的設(shè)計(jì)思路。下面畫(huà)個(gè)圖來(lái)說(shuō)明，一目了然。
Redis的字符串也會(huì)遵守C語(yǔ)言的字符串的實(shí)現(xiàn)規(guī)則，即最后一個(gè)字符為空字符。然而這個(gè)空字符不會(huì)被計(jì)算在len里頭。
2.SDS 動(dòng)態(tài)擴(kuò)展特點(diǎn)
SDS的最厲害最奇妙之處在于它的Dynamic。動(dòng)態(tài)變化長(zhǎng)度。舉個(gè)例子
如上圖所示剛開(kāi)始s1 只有5個(gè)空閑位子，后面需要追加' world' 6個(gè)字符，很明顯是不夠的。那咋辦？Redis會(huì)做以下三個(gè)操作：
計(jì)算出大小是否足夠
開(kāi)辟空間至滿足所需大小
開(kāi)辟與已使用大小len相同長(zhǎng)度的空閑free空間（如果len < 1M）開(kāi)辟1M長(zhǎng)度的空閑free空間（如果len >= 1M）
看到這兒為止有沒(méi)有朋友覺(jué)得這個(gè)實(shí)現(xiàn)跟Java的列表List實(shí)現(xiàn)有點(diǎn)類似呢？看完后面的會(huì)覺(jué)得更像了。
Redis字符串的性能優(yōu)勢(shì)
快速獲取字符串長(zhǎng)度
避免緩沖區(qū)溢出
降低空間分配次數(shù)提升內(nèi)存使用效率
1.快速獲取字符串長(zhǎng)度
再看下上面的SDS結(jié)構(gòu)體：
struct?sdshdr{??
????//??記錄已使用長(zhǎng)度??
????int?len;??
????//?記錄空閑未使用的長(zhǎng)度??
????int?free;??
????//?字符數(shù)組??
????char[]?buf;??
};??
由于在SDS里存了已使用字符長(zhǎng)度len，所以當(dāng)想獲取字符串長(zhǎng)度時(shí)直接返回len即可，時(shí)間復(fù)雜度為O(1)。如果使用C語(yǔ)言的字符串的話它的字符串長(zhǎng)度獲取函數(shù)時(shí)間復(fù)雜度為O(n),n為字符個(gè)數(shù)，因?yàn)樗菑念^到尾（到空字符'\0'）遍歷相加。
2.避免緩沖區(qū)溢出
對(duì)一個(gè)C語(yǔ)言字符串進(jìn)行strcat追加字符串的時(shí)候需要提前開(kāi)辟需要的空間，如果不開(kāi)辟空間的話可能會(huì)造成緩沖區(qū)溢出，而影響程序其他代碼。如下圖，有一個(gè)字符串s1="hello" 和 字符串s2="baby",現(xiàn)在要執(zhí)行strcat(s1,"world"),并且執(zhí)行前未給s1開(kāi)辟空間，所以造成了緩沖區(qū)溢出。
而對(duì)于Redis而言由于每次追加字符串時(shí)都會(huì)檢查空間是否夠用，所以不會(huì)存在緩沖區(qū)溢出問(wèn)題。每次追加操作前都會(huì)做如下操作：
計(jì)算出大小是否足夠
開(kāi)辟空間至滿足所需大小
3.降低空間分配次數(shù)提升內(nèi)存使用效率
字符串的追加操作會(huì)涉及到內(nèi)存分配問(wèn)題，然而內(nèi)存分配問(wèn)題會(huì)牽扯內(nèi)存劃分算法以及系統(tǒng)調(diào)用所以如果頻繁發(fā)生的話影響性能，所以對(duì)于性能至上的Redis來(lái)說(shuō)這是萬(wàn)萬(wàn)不能忍受的。
所以采取了以下兩種優(yōu)化措施
空間與分配
惰性空間回收
1. 空間預(yù)分配
對(duì)于追加操作來(lái)說(shuō)，Redis不僅會(huì)開(kāi)辟空間至夠用而且還會(huì)預(yù)分配未使用的空間(free)來(lái)用于下一次操作。至于未使用的空間(free)的大小則由修改后的字符串長(zhǎng)度決定。
當(dāng)修改后的字符串長(zhǎng)度len < 1M,則會(huì)分配與len相同長(zhǎng)度的未使用的空間(free)
當(dāng)修改后的字符串長(zhǎng)度len >= 1M,則會(huì)分配1M長(zhǎng)度的未使用的空間(free)
有了這個(gè)預(yù)分配策略之后會(huì)減少內(nèi)存分配次數(shù)，因?yàn)榉峙渲皶?huì)檢查已有的free空間是否夠，如果夠則不開(kāi)辟了～
2. 惰性空間回收
與上面情況相反，惰性空間回收適用于字符串縮減操作。比如有個(gè)字符串s1="hello world"，對(duì)s1進(jìn)行sdstrim(s1," world")操作，執(zhí)行完該操作之后Redis不會(huì)立即回收減少的部分，而是會(huì)分配給下一個(gè)需要內(nèi)存的程序。當(dāng)然，Redis也提供了回收內(nèi)存的api,可以自己手動(dòng)調(diào)用來(lái)回收縮減部分的內(nèi)存。
到此為止結(jié)束了～
下次在遇到這個(gè)問(wèn)題可以侃侃而談了，哈哈哈~
如果需要找資源的話加小編微信溝通即可，小編盡力給大家去找，去安排。
??嘿嘿，你在看呢嗎