Redis八股文精講：字符串
寫在前面
小牛之前出了八股文背誦版系列，不少朋友問我，能不能搞個(gè)八股文精講，把面試問題講講透，于是系列就這樣誕生了。咱們第一期先聊聊Redis。
字符串
Redis底層是C語言實(shí)現(xiàn)的。于是不少朋友想當(dāng)然的以為，Redis的字符串和C語言字符串實(shí)現(xiàn)方式一致。
但事實(shí)上，Redis自己定義了一套字符串的實(shí)現(xiàn)，名曰SDS(simple dynamic string)。
不少同學(xué)在面試時(shí)，面試官輕描淡學(xué)來一句，來講一講Redis的SDS吧。大家一臉懵逼，半天答不上來。最后搞半天，其實(shí)面試官就是問的Redis字符串呀。
首先回答一個(gè)問題：為什么Redis不采用C語言的字符串直接做具體實(shí)現(xiàn)?
這當(dāng)然是因?yàn)檫@種數(shù)據(jù)結(jié)構(gòu)有固有缺陷啦。主要有如下幾個(gè)
缺點(diǎn)1：O(n)復(fù)雜度獲取長(zhǎng)度
我們知道，C語言如何判斷一個(gè)字符串已經(jīng)結(jié)束，當(dāng)然是通過標(biāo)志位'\0'。
C語言Str
所以，對(duì)于我們想獲得字符串長(zhǎng)度，我們需要從頭開始遍歷，直至遍歷到\0，時(shí)間復(fù)雜度變成了O(n)。
缺點(diǎn)2：沒有較好的擴(kuò)容機(jī)制
對(duì)于C語言，想要搞個(gè)字符串?dāng)?shù)組，肯定需要預(yù)先確定好字符串長(zhǎng)度。如果這個(gè)字符串經(jīng)常需要修改，修改前后長(zhǎng)度一致還好說，如果不一致，那程序?qū)用婢托枰匦律暾?qǐng)一段新內(nèi)存，并把字符一個(gè)個(gè)拷貝到新的地方。
缺點(diǎn)3：特殊字符無法處理
引用《Redis源碼剖析與實(shí)戰(zhàn)》的例子 如果我們想存儲(chǔ)字符串"redis\0"
- char *a = "redis\0";
到原始C語言，它編譯器看到\0，以為還是字符結(jié)束的標(biāo)志呢，如果把它打印下來，它只打出redis。所以特別是對(duì)于二進(jìn)制數(shù)據(jù)，這種奇奇怪怪的case特別多，因此C語言的字符數(shù)組就處理不了這塊存儲(chǔ)二進(jìn)制字符的需求了。
為了解決C語言字符數(shù)組的不足，redis提出了新的方法。我們先來看看3.0及之前版本的實(shí)現(xiàn)。
- struct sdshdr {
- unsigned int len;
- unsigned int free;
- char buf[];
- }
來解釋一下這些字段吧。
len：數(shù)組字符串已使用長(zhǎng)度
free: 數(shù)組未使用的字符串長(zhǎng)度
buf：存儲(chǔ)字符串
在之后的版本，Redis對(duì)SDS進(jìn)行了改進(jìn)，但大體思想不變
- struct sdshdr {
- unsigned int len;
- unsigned int alloc;
- unsigned char flags;
- char buf[];
- }
來解釋一下這些字段吧。
len：數(shù)組字符串已使用長(zhǎng)度
alloc: 數(shù)組分配的長(zhǎng)度
flags: 表示SDS類型
buf：存儲(chǔ)字符串
對(duì)于SDS類型，我也稍微多啰嗦兩句。在新版本redis中，有4種SDS類型(sdshrd5 never used)。其中 sdshrd8 sdshrd16 sdshrd32 sdshrd64 的區(qū)別僅僅就在len和alloc上有所區(qū)別。
對(duì)于sdshrd8 該定義為
- struct sdshdr8 {
- uint8_t len;
- uint8_t alloc;
- unsigned char flags;
- char buf[];
- }
以此類推，sdshrd16就是
- struct sdshdr16 {
- uint16_t len;
- uint16_t alloc;
- unsigned char flags;
- char buf[];
- }
那為啥新版Redis搞這么多結(jié)構(gòu)體?一個(gè)結(jié)構(gòu)體不是一法通萬法就夠了嘛。
當(dāng)然，事實(shí)確實(shí)如此，按實(shí)現(xiàn)角度看。如果只采用sdshrd64，肯定也夠了。
但按摳門角度看呢?如果我們機(jī)子很菜，內(nèi)存很小，想摳摳索索能省一點(diǎn)，是一點(diǎn)，這樣做就有好處辣。
好處在哪里?當(dāng)然是uint8_t、uint16_t、uint32_t、uint64_t占的空間不一樣，對(duì)于小字符串，用小頭sdshdr8，這樣len 和alloc占用字段也能省一點(diǎn)，就是這么回事。
所以可以看到，SDS本質(zhì)上是C語言的字符數(shù)組，加上了一點(diǎn)別的標(biāo)識(shí)屬性的結(jié)構(gòu)體而已。小伙伴們下次碰見面試官問SDS，就不用慌啦!
最后多啰嗦兩句SDS擴(kuò)容：
- 對(duì)于字符串增加了，如果原始的剩余空間足夠，直接返回
- 如果空間不足夠，重新申請(qǐng)兩倍最小需要長(zhǎng)度的空間，再進(jìn)行挨個(gè)賦值。
最后總結(jié)一下：Redis提出動(dòng)態(tài)字符串這一數(shù)據(jù)結(jié)構(gòu)，改進(jìn)了C語言字符數(shù)組的不足。該動(dòng)態(tài)字符串有如下好處：
- 字符串長(zhǎng)度獲取時(shí)間復(fù)雜度從O(n)->O(1)
- 減少字符串?dāng)U容引起的數(shù)據(jù)搬運(yùn)次數(shù)。
- 可以存儲(chǔ)更加復(fù)雜的二進(jìn)制數(shù)據(jù)
參考
《Redis源碼剖析與實(shí)戰(zhàn)》
https://blog.csdn.net/weixin_39744512/article/details/111170924
https://blog.csdn.net/wolf2s/article/details/107945242
《Redis的設(shè)計(jì)與實(shí)現(xiàn)》
