前言

在上一篇文章中，我和大家介紹了Redis的前世今生，Redis的誕生就是為了解決mysql中IO性能的瓶頸，這一篇就和大家一起揭秘Redis神秘的面紗，第一個(gè)我們就來(lái)聊一聊Redis數(shù)據(jù)類(lèi)型中的String！

Redis的數(shù)據(jù)結(jié)構(gòu)

Redis最常用的數(shù)據(jù)類(lèi)型有五種

• String: 字符串
• Hash: 散列
• List: 列表
• Set: 集合
• Sorted Set: 有序集合

五種其實(shí)是Redis鍵值對(duì)中值存儲(chǔ)的數(shù)據(jù)類(lèi)型，而他們的底層數(shù)據(jù)結(jié)構(gòu)一共有6種：分別是

• 簡(jiǎn)單動(dòng)態(tài)字符串
• 雙向鏈表
• 壓縮列表
• 哈希表
• 跳表
• 整數(shù)數(shù)組

數(shù)據(jù)類(lèi)型和數(shù)據(jù)結(jié)構(gòu)的對(duì)應(yīng)關(guān)系如下圖：

image.png

這張圖會(huì)在未來(lái)幾篇文章中反復(fù)出現(xiàn)，幫大家徹底了解Redis的基礎(chǔ)類(lèi)型。

今天我們就來(lái)聊一聊其中的string

Redis是用C寫(xiě)的，那為什么不用C語(yǔ)言的String?

眾所周知，Redis是用C語(yǔ)言寫(xiě)的，那Redis為什么沒(méi)有使用C原生的字符串，而是自己創(chuàng)建了一個(gè)簡(jiǎn)單動(dòng)態(tài)字符串？（SDS simple dynamic string）

• C語(yǔ)言的字符串底層是用字符數(shù)組來(lái)實(shí)現(xiàn)的，在一片連續(xù)的空間中依次存放字符，為了判斷字符的結(jié)束，他會(huì)在最后以'\0'作為識(shí)別,這樣就會(huì)帶來(lái)以下問(wèn)題

  1. 無(wú)法存放任意的字符，至少'\0'是不可以的，這就會(huì)導(dǎo)致一些如圖片，音頻等出現(xiàn)了'\0'就會(huì)出現(xiàn)問(wèn)題。
  2. 對(duì)字符串進(jìn)行追加等操作的時(shí)候，必須遍歷到'\0'才可以操作，會(huì)導(dǎo)致效率比較低，復(fù)雜度為o(n)

• C語(yǔ)言的字符串是不記錄字符串長(zhǎng)度的，一旦我們調(diào)用了拼接函數(shù)等，而沒(méi)有提前計(jì)算好內(nèi)存，就會(huì)產(chǎn)生緩沖區(qū)溢出的情況，所以為了不出問(wèn)題，會(huì)進(jìn)行內(nèi)存重分配，而這又多出了內(nèi)存重分配的性能損耗。

那么，Redis是怎么處理這些問(wèn)題的呢？

簡(jiǎn)單動(dòng)態(tài)字符串（Redis5.0版本）

Redis中的字符串?dāng)?shù)據(jù)是通過(guò)簡(jiǎn)單動(dòng)態(tài)字符串（以下簡(jiǎn)稱(chēng)SDS）來(lái)存儲(chǔ)數(shù)據(jù)的。

SDS到底是什么？

我們先來(lái)看看SDS的結(jié)構(gòu)長(zhǎng)什么樣

image.png

• len：表示buf的已用長(zhǎng)度。（sdshdr8中占1個(gè)字節(jié)）
• alloc：表示分配給buf的總長(zhǎng)度，不包括結(jié)構(gòu)體和'\0'結(jié)束字符。（sdshdr8中占1個(gè)字節(jié)）
• flags: SDS類(lèi)型。（sdshdr8中占一個(gè)字節(jié)）
• buf：字節(jié)數(shù)組，保存實(shí)際數(shù)據(jù)。為了表示字節(jié)數(shù)組的結(jié)束，Redis 會(huì)自動(dòng)在數(shù)組最后加一個(gè)“\0”，這就會(huì)額外占用 1 個(gè)字節(jié)的開(kāi)銷(xiāo)。（nycdf--> 你也才掉發(fā)是我在這里寫(xiě)的示例，代表存儲(chǔ)的某個(gè)數(shù)據(jù)）

你丫才掉發(fā)小課堂--詳解SDS類(lèi)型

SDS 結(jié)構(gòu)中的字段 flags，表示的是SDS的類(lèi)型。在Redis中SDS一共設(shè)計(jì)了5種類(lèi)型，分別是

• sdshdr5（未使用）
• sdshdr8
• sdshdr16
• sdshdr32
• sdshdr64

這5種類(lèi)型的主要區(qū)別就在于，它們數(shù)據(jù)結(jié)構(gòu)中的len和alloc，這兩個(gè)字段占據(jù)的大小不同，也就是這個(gè)結(jié)構(gòu)體能存儲(chǔ)的長(zhǎng)度不同。下面他們是結(jié)構(gòu)體的源碼：

image.png

從源碼我們可以看出來(lái)，其實(shí)最大的不同就是len和alloc所代表的字節(jié)數(shù)不同，那么比如sdshdr8中這2個(gè)字段的類(lèi)型uint8_t,也就是這個(gè)類(lèi)型結(jié)構(gòu)最大存儲(chǔ)的字符長(zhǎng)度為256（2的8次方），其他的以此類(lèi)推。

這樣的設(shè)計(jì)目的:Redis是基于內(nèi)存的，而內(nèi)存永遠(yuǎn)都是珍貴的資源，每一個(gè)字節(jié)都很重要，所以針對(duì)不同大小的字符串使用不同的結(jié)構(gòu)，也是為了節(jié)省內(nèi)存資源。

在SDS中，除了上面解釋過(guò)的flags，對(duì)比于C傳統(tǒng)的char[],SDS新增了2個(gè)參數(shù)，實(shí)際占用長(zhǎng)度len 和總分配長(zhǎng)度alloc。

SDS解決了什么問(wèn)題呢？

1. 獲取字符串長(zhǎng)度的復(fù)雜度問(wèn)題

上面我們說(shuō)過(guò)，c語(yǔ)言遍歷一下字符串的復(fù)雜度是o(n)。

對(duì)于SDS來(lái)說(shuō)，我們有了長(zhǎng)度的參數(shù)，那么我們的復(fù)雜度就是o(1)，這樣在進(jìn)行拼接等操作的時(shí)候不需要再次遍歷了。

2. 存儲(chǔ)二進(jìn)制數(shù)據(jù)

C字符串不能存儲(chǔ)二進(jìn)制數(shù)據(jù)的原因是只能根據(jù)'\0'來(lái)判斷數(shù)據(jù)是否結(jié)束，不能保證其完整性，但因?yàn)镾DS的len屬性，無(wú)論你數(shù)據(jù)里有多少'\0'都沒(méi)關(guān)系，我是根據(jù) len 屬性值來(lái)判斷數(shù)據(jù)長(zhǎng)度的，必定是完整的，所以SDS可以安全地存儲(chǔ)二進(jìn)制數(shù)據(jù)，這樣圖片音頻等二進(jìn)制數(shù)據(jù)也可以存儲(chǔ)。

你丫才掉發(fā)小課堂

Q:SDS你都有l(wèi)en了，那為啥還要跟C字符串一樣在字符串后面加'\0'，是不是多此一舉了？

A:SDS如果保持和C字符串一樣的特性，就不用專(zhuān)門(mén)編寫(xiě)多余的函數(shù)了，在一定的情況下可以直接用C語(yǔ)言的函數(shù)，避免了不必要的重寫(xiě)。

3. 分配內(nèi)存空間問(wèn)題

上面還在存在一個(gè)問(wèn)題是在使用拼接等操作的時(shí)候C語(yǔ)言是需要重分配空間的，而這個(gè)又是非常的消耗資源。SDS提供的2個(gè)特性就是空間預(yù)分配 和 惰性空間釋放

空間預(yù)分配

image.png

空間預(yù)分配源碼

在真正執(zhí)行拼接等操作之前，會(huì)先計(jì)算下空間是否滿(mǎn)足

1. 如果計(jì)算后的SDS的長(zhǎng)度(源碼中的newLen)小于1MB，那么就會(huì)分配和len屬性同樣大的未使用空間，相當(dāng)于將原數(shù)組長(zhǎng)度乘以二。

image.png

2. 如果計(jì)算后的SDS的長(zhǎng)度(源碼中的newLen)大于或等于1MB，那么就會(huì)分配固定的1MB未使用空間。

image.png

所以當(dāng)有N次拼接操作時(shí)候，一定需要N次的內(nèi)存重分配操作，現(xiàn)在最多只需要N次。

比如你第一次拼接后，剩余的長(zhǎng)度（alloc - len）就大于后續(xù)要拼接的字符串長(zhǎng)度之和了，那其實(shí)就只有1次內(nèi)存重分配操作，就可以進(jìn)行至少2次拼接操作，所以說(shuō)最多N次,這也就可以省下很多分配空間的消耗。

惰性空間釋放

當(dāng)有縮短SDS字符串操作時(shí)，程序并不立即把空閑出來(lái)的字節(jié)釋放掉，而是留給到惰性刪除策略等機(jī)制釋放。

具體的表現(xiàn)就是：

在做刪除操作的時(shí)候，當(dāng)刪掉N個(gè)字符后，alloc-len（也就是剩余空間）就增加N，換個(gè)說(shuō)法，就是你刪除的字符并沒(méi)有立即被系統(tǒng)回收，這樣當(dāng)你短時(shí)間內(nèi)再次拼接的時(shí)候，就不會(huì)申請(qǐng)空間分配了。

image.png

只有到了對(duì)應(yīng)策略或者手動(dòng)去刪除的時(shí)候才會(huì)執(zhí)行以下的代碼：

image.png

代碼的邏輯就是刪除多余的空間直到?jīng)]有浪費(fèi)為止。

有了SDS,就萬(wàn)事大吉了么？

前面我們聊完了SDS，已經(jīng)大概的知道了SDS是什么樣的，解決了什么問(wèn)題，這里給大家提出一些更深層的問(wèn)題:

1. 如果我的string是數(shù)字，Redis也按照字符串存儲(chǔ)么？
2. string在Redis中就是只有SDS就可以落地了么,有沒(méi)有別的結(jié)構(gòu)支撐？
3. SDS最大支持存儲(chǔ)長(zhǎng)度為2的64次方的數(shù)組，這些超長(zhǎng)的字符串他們是怎么存儲(chǔ)的？

初識(shí)RedisObject

在我們真實(shí)使用Redis中string的時(shí)候，除了SDS的存儲(chǔ)空間，還存在一個(gè)Redis本身的結(jié)構(gòu)體，也就是RedisObject。

RedisObject存儲(chǔ)空間

image.png

以上是RedisObject源碼，

• type:redisObject的數(shù)據(jù)類(lèi)型，4個(gè)bits
• encoding:redisObject的編碼類(lèi)型，4個(gè)bits
• lru:LRU_BITS:redisObject的LRU時(shí)間，LRU_BITS為24個(gè)bits
• refcount:redisObject的引用計(jì)數(shù)，4個(gè)字節(jié)
• *ptr:指向值的指針，8個(gè)字節(jié)

為了形象的展示占據(jù)的大小：

image.png

RedisObject和String

這里暫時(shí)不對(duì)RedisObject展開(kāi)講，我們來(lái)看看當(dāng)RedisObject和SDS在一起的時(shí)候大概是個(gè)什么樣子？

image.png

上圖表示的就是普通情況下RedisObject和SDS的關(guān)系。

作為Redis最常用的結(jié)構(gòu)之一,針對(duì)String也做了很多的優(yōu)化

1. 數(shù)字類(lèi)型的字符串

對(duì)于數(shù)字類(lèi)型的字符串，Redis在RedisObjec中的指針就直接賦值為整數(shù)數(shù)據(jù)了，這么指針的開(kāi)銷(xiāo)就省去了。

image.png

2. embstr編碼方式（embed:嵌入式）

在保存的是字符串?dāng)?shù)據(jù)，如果字符串小于等于44字節(jié)時(shí)（為什么是44呢？讀到這里可以思考一下），Redis就會(huì)將RedisObjec和SDS構(gòu)建成一塊連續(xù)的內(nèi)存區(qū)域，既可以提升查詢(xún)的速度（少了一次指針的跳轉(zhuǎn)），也可以防止內(nèi)存碎片的產(chǎn)生。

image.png

image.png

• 當(dāng)字節(jié)數(shù)小于44，調(diào)用createEmbeddedStringObject
• 當(dāng)字節(jié)數(shù)大于44，調(diào)用createRawStringObject

這里我們來(lái)看下createEmbeddedStringObject的部分源碼

image.png

這里做的事情核心

1. 先分配一段連續(xù)的內(nèi)存空間（RedisObject+SDS+1的長(zhǎng)度，這里的1是為了字符串最后的`'\0'），并創(chuàng)建RedisObject和SDS的機(jī)構(gòu)。
2. 將RedisObject的ptr指針指向字符數(shù)組的開(kāi)始。（細(xì)節(jié)！?。。。?/strong>
3. 拷貝字符串到SDS的buf[]中。

這個(gè)時(shí)候內(nèi)存塊包含如下幾部分：

• 16個(gè)字節(jié)的robj結(jié)構(gòu)。
• 3個(gè)字節(jié)的sdshdr8頭。
• 最多44個(gè)字節(jié)的sds字符數(shù)組。
• 1個(gè)'\0'結(jié)束符。

3. raw編碼模式

在保存的是字符串?dāng)?shù)據(jù)，字符串大于44字節(jié)時(shí)，Redis就不像embstr編碼方式一樣把RedisObject和SDS存放在一起，這時(shí)RedisObject中的*ptr就會(huì)發(fā)揮真正的作用，Redis在內(nèi)存中重新分配一塊空間給SDS，并用*ptr指向這個(gè)SDS。

image.png

這里我們來(lái)看下createRawStringObject的部分源碼

image.png

這里就比較簡(jiǎn)單了，一共做了這2件事：

1. 先使用sdsnewlen返回SDS結(jié)構(gòu)的指針
2. 將SDS指針賦值給RedisObject中的指針

最后再給大家把所有的編碼格式放一起匯總一下：??

image.png