面試題解-Redis的String是如何實(shí)現(xiàn)的？

第44題: Redis 的String 是怎么實(shí)現(xiàn)的？為什么不直接用c的字符串？

Redis 沒有直接使用C 語(yǔ)言的字符串表示，而是自己構(gòu)建一種簡(jiǎn)單動(dòng)態(tài)字符串（SDS: simple dynamic string）。

Redis 中的String 都是SDS，例如我們執(zhí)行這樣一條命令:

redis> SET blog angela

那么Redis 在內(nèi)存中創(chuàng)建了一個(gè)鍵值對(duì)，

• 鍵：鍵是一個(gè)字符串對(duì)象，對(duì)應(yīng)底層實(shí)現(xiàn)是一個(gè)保存字符串“blog” 的SDS;
• 值：值也是一個(gè)字符串對(duì)象，對(duì)應(yīng)底層實(shí)現(xiàn)是一個(gè)保存字符串是“angela”的SDS。

如果執(zhí)行

redis> RPUSH blog "angela" "de" "blog"

那么Redis 將在內(nèi)存中創(chuàng)建一個(gè)鍵值對(duì)，鍵還是一個(gè)SDS，存放“blog”，值是一個(gè)列表，存放三個(gè)SDS，“angela”、“de”、“blog”

SDS如何實(shí)現(xiàn)的呢？

首先SDS被定義為這樣一個(gè)結(jié)構(gòu)體:

struct sdshdr {
   char buf[];//字節(jié)數(shù)組,用于保存字符串
   int len;//記錄buf數(shù)組中已使用字節(jié)的數(shù)量
   int free;//記錄buf數(shù)組中未使用字節(jié)的數(shù)量
}

舉個(gè)例子:

現(xiàn)有執(zhí)行redis> SET blog angela 命令后，value值在redis 中存放如下圖所示，buf存放字節(jié)數(shù)組(真實(shí)數(shù)據(jù))，len表示存放字符串的長(zhǎng)度（不包括結(jié)束符號(hào)'\0'）,free表示剩余空間，可以看到還剩5個(gè)字節(jié)。

SDS遵循了C語(yǔ)言字符串以空字符結(jié)尾的慣例，保存空字符的1個(gè)字節(jié)空間不在SDS 的len屬性里面。這樣做有個(gè)好處是我們直接可以復(fù)用C 提供的庫(kù)函數(shù)，比如打印字符串，直接用C 提供的printf("%s", s->buf);

那又是為什么不直接用C語(yǔ)言提供的字符串呢？

在C語(yǔ)言中，表示一個(gè)“angela” 的字符串如下圖所示，結(jié)束也是通過(guò)空字符表示：

C語(yǔ)言的字符串和SDS的區(qū)別如下：

• 長(zhǎng)度獲取效率：C語(yǔ)言如果需要獲取字符串長(zhǎng)度，需要從頭開始遍歷，時(shí)間復(fù)雜度O(n)，SDS提供len屬性，訪問(wèn)時(shí)間復(fù)雜度O(1), Redis的strlen 獲取字符串長(zhǎng)度函數(shù)性能毫無(wú)壓力；

• 杜絕溢出：C字符串不記錄自身長(zhǎng)度的另一個(gè)問(wèn)題是容易造成緩沖區(qū)溢出，比如要做字符串拼接，char *strcat(char *dest, const char *src), 講src 字符串拼到desc字符串，如果desc忘記提前擴(kuò)容，就會(huì)溢出，而恰好desc后面正好有數(shù)據(jù)，則會(huì)被覆蓋；

• 減少內(nèi)存重分配：對(duì)于Redis這種內(nèi)存數(shù)據(jù)庫(kù)，很多場(chǎng)景會(huì)頻繁更新value的值，那如果采用C字符串，value長(zhǎng)度有變化，就需要頻繁分配內(nèi)存，SDS做了內(nèi)存的預(yù)分配和惰性釋放，能有效減少內(nèi)存分配次數(shù)，內(nèi)存的重分配代價(jià)還是很高昂的，對(duì)于Redis這種對(duì)性能要求非常高的緩存產(chǎn)品，這種性能損耗是不能接受的；

• 二進(jìn)制安全：C字符串必須符合某種編碼（比如ASCII），除了空字符結(jié)尾，字符串中間是不能包含空字符的，否則會(huì)被誤以為是字符串結(jié)尾。這就限定了C字符串不能用來(lái)存儲(chǔ)類型圖片、音頻、視頻、壓縮文件這種二進(jìn)制書數(shù)據(jù)，但是SDS可以，SDS設(shè)計(jì)的API都是二進(jìn)制安全的。

-End-

最近有一些小伙伴，讓我?guī)兔φ乙恍?nbsp;面試題 資料，于是我翻遍了收藏的 5T 資料后，匯總整理出來(lái)，可以說(shuō)是程序員面試必備！所有資料都整理到網(wǎng)盤了，歡迎下載！