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