Redis 是內(nèi)存數(shù)據(jù)庫，高效使用內(nèi)存對(duì) Redis 的實(shí)現(xiàn)來說非常重要。

看一下，Redis 中針對(duì)字符串結(jié)構(gòu)針對(duì)內(nèi)存使用效率做的設(shè)計(jì)優(yōu)化，版本為Redis3.2。

?

?

?

一、SDS的結(jié)構(gòu)?

c語言沒有string類型，本質(zhì)是char[]數(shù)組；而且c語言數(shù)組創(chuàng)建時(shí)必須初始化大小，指定類型后就不能改變，并且字符數(shù)組的最后一個(gè)元素總是空字符?'\0'?。

以下展示了一個(gè)值為?"Redis"?的 C 字符串：

Redis沒有直接使用C語言的字符串方式，而是構(gòu)建了一種簡(jiǎn)單動(dòng)態(tài)字符串（Simple dynamic string， SDS）的類型，Redis中的字符串底層都是使用SDS結(jié)構(gòu)進(jìn)行存儲(chǔ)，比如包含字符串的鍵值對(duì)底層都是使用SDS結(jié)構(gòu)實(shí)現(xiàn)的。

SDS結(jié)構(gòu)定義在sds.h中

struct sdshdr{


    int len;//SDS保存的字符串長(zhǎng)度


    int free;//buf數(shù)組中未使用字節(jié)數(shù)量


    char buf[];//字符數(shù)組，保存字符串


}

最后一個(gè)字節(jié)保存了空字符'\0'，保留了C字符串的規(guī)范，使得SDS結(jié)構(gòu)的字符串，可以重用一部分C函數(shù)庫的函數(shù)。

?

二、為什么不使用C字符串

主要是因?yàn)镃字符串有以下缺點(diǎn)：

• 獲取字符串長(zhǎng)度時(shí)間復(fù)雜度為O(N)：C字符串獲取長(zhǎng)度需遍歷整個(gè)字符串，遇到'\0'空字符為止。
• 緩沖區(qū)溢出：比如在進(jìn)行字符串追加操作時(shí)，如果沒有分配足夠的內(nèi)存，就會(huì)造成內(nèi)存溢出。
• 內(nèi)存重分配：每次增長(zhǎng)或者截短字符串，程序都要對(duì)保存C字符串的數(shù)組進(jìn)行內(nèi)存重分配操作，而內(nèi)存重分配涉及復(fù)雜的算法，并可能需要執(zhí)行系統(tǒng)調(diào)用，所以它通常比較耗時(shí)。
• 空字符問題：C字符串中間不能保存空格，否則程序遍歷是會(huì)誤認(rèn)為是字符串的末尾。這一限制導(dǎo)致C字符串只能存儲(chǔ)文本數(shù)據(jù)，不能保存像圖片、音視頻、壓縮文件等二進(jìn)制數(shù)據(jù)。

?

三、怎樣解決C字符串問題?

?

1、SDS通過len屬性記錄了SDS長(zhǎng)度，所以獲取長(zhǎng)度的時(shí)間復(fù)雜度為O(1)，即strlen命令的時(shí)間復(fù)雜度是O(1)。

?

2、SDS空間分配策略避免了緩沖區(qū)溢出：當(dāng)對(duì)SDS進(jìn)行修改時(shí)，會(huì)先檢查SDS空間是否滿足修改，不滿足會(huì)自動(dòng)擴(kuò)展到所需大小，然后才執(zhí)行修改。

?

3、較少修改字符串時(shí)內(nèi)存重分配次數(shù)：SDS中的free記錄buf字節(jié)數(shù)組中未使用的字節(jié)。

redis通過free屬性實(shí)現(xiàn)空間預(yù)分配、惰性空間釋放兩種優(yōu)化策略。

?

• 空間預(yù)分配：當(dāng)對(duì)SDS進(jìn)行增長(zhǎng)操作時(shí)，程序不僅會(huì)分配修改所必須得空間，還會(huì)為SDS分配額外的未使用空間。通過預(yù)分配策略，減少了連續(xù)執(zhí)行字符串增長(zhǎng)操作時(shí)內(nèi)存重分配次數(shù)。
• 惰性空間釋放：當(dāng)對(duì)SDS進(jìn)行截短操作時(shí)，程序并不會(huì)立即回收縮短后多出來的字節(jié)所占用的內(nèi)存，而是使用free屬性記錄多出來的字節(jié)數(shù)，以供將來使用。如果將來要對(duì)這個(gè)SDS進(jìn)行增長(zhǎng)操作，未使用空間可能就派上用場(chǎng)，并且增長(zhǎng)操作也不一定會(huì)執(zhí)行內(nèi)存重分配。

?

SDS結(jié)構(gòu)中的buf字節(jié)數(shù)組，是二進(jìn)制安全的，不僅可以保存字符，也可以保存二進(jìn)制數(shù)據(jù)。

SDS保留了C字符串的慣例，將數(shù)據(jù)的末尾設(shè)置為空字符'\0'，SDS中之所以保留這一規(guī)范是可以重用C字符串函數(shù)庫的一部分函數(shù)，例如追加字符串。

?

四、對(duì)字符串的進(jìn)一步優(yōu)化

Redis string的三種編碼：

• int 存儲(chǔ)8個(gè)字節(jié)的長(zhǎng)整型(long，2^63-1 )
• embstr, embstr格式的SDS (Simple Dynamic String)
• raw, raw格式的SDS，存儲(chǔ)大于44個(gè)字節(jié)的長(zhǎng)字符串

?

int類型就是指的是數(shù)字，那么raw、embstr都代表的是字符串有什么異同嗎，下面我們分析下。

?

?

?

?

圖中展示了兩者的區(qū)別，可以看到embstr將redisObject和SDS保存在連續(xù)的64字節(jié)空間內(nèi)，這樣可以只需要一次內(nèi)存分配，而對(duì)于raw來說，SDS和redisObject分離，需要兩次內(nèi)存分配，而且占用更多的內(nèi)存空間。

?

?

?

可以看到embstr在3.2+中使用了叫sdshdr8的結(jié)構(gòu)，在該結(jié)構(gòu)下，元數(shù)據(jù)只需要3個(gè)字節(jié)，而Redis需要8個(gè)字節(jié)，所以總共64個(gè)字節(jié)，減去redisObject(16字節(jié))，再減去SDS的原信息，最后的實(shí)際內(nèi)容就變成了44字節(jié)和39字節(jié)。

?

?

?

當(dāng)字符串小于等于 44 字節(jié)時(shí)，Redis 就使用了嵌入式字符串的創(chuàng)建方法，以此減少內(nèi)存分配和內(nèi)存碎片。

下面這張圖展示了 createEmbeddedStringObject 創(chuàng)建嵌入式字符串的過程：

?

?

?

總之，只要記住，Redis 會(huì)通過設(shè)計(jì)實(shí)現(xiàn)一塊連續(xù)的內(nèi)存空間，把 redisObject 結(jié)構(gòu)體和 SDS 結(jié)構(gòu)體緊湊地放置在一起。

這樣一來，對(duì)于不超過 44 字節(jié)的字符串來說，就可以避免內(nèi)存碎片和兩次內(nèi)存分配的開銷了。

?

參考資料：

https://blog.wangjunfeng.com/post/redis-sds/#redis-32%e7%89%88%e6%9c%ac%e5%90%8e%e7%9a%84sds文章來源地址http://www.zghlxwxcb.cn/news/detail-410746.html

到了這里，關(guān)于Redis源碼之SDS簡(jiǎn)單動(dòng)態(tài)字符串的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！