前言

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

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

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

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

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

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

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

image.png

這張圖會在未來幾篇文章中反復出現(xiàn)武翎，幫大家徹底了解Redis的基礎(chǔ)類型。

今天我們就來聊一聊其中的string

Redis是用C寫的肉拓，那為什么不用C語言的String?

眾所周知后频，Redis是用C語言寫的，那Redis為什么沒有使用C原生的字符串暖途，而是自己創(chuàng)建了一個簡單動態(tài)字符串卑惜？（SDS simple dynamic string）

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

  1. 無法存放任意的字符，至少'\0'是不可以的欺栗，這就會導致一些如圖片毫痕，音頻等出現(xiàn)了'\0'就會出現(xiàn)問題。
  2. 對字符串進行追加等操作的時候迟几，必須遍歷到'\0'才可以操作消请，會導致效率比較低，復雜度為o(n)

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

那么需频，Redis是怎么處理這些問題的呢？

簡單動態(tài)字符串（Redis5.0版本）

Redis中的字符串數(shù)據(jù)是通過簡單動態(tài)字符串（以下簡稱SDS）來存儲數(shù)據(jù)的筷凤。

SDS到底是什么昭殉？

我們先來看看SDS的結(jié)構(gòu)長什么樣

image.png

• len：表示buf的已用長度。（sdshdr8中占1個字節(jié)）
• alloc：表示分配給buf的總長度，不包括結(jié)構(gòu)體和'\0'結(jié)束字符饲化。（sdshdr8中占1個字節(jié)）
• flags: SDS類型莽鸭。（sdshdr8中占一個字節(jié)）
• buf：字節(jié)數(shù)組，保存實際數(shù)據(jù)吃靠。為了表示字節(jié)數(shù)組的結(jié)束硫眨，Redis 會自動在數(shù)組最后加一個“\0”，這就會額外占用 1 個字節(jié)的開銷巢块。（nycdf--> 你也才掉發(fā)是我在這里寫的示例礁阁，代表存儲的某個數(shù)據(jù)）

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

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

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

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

image.png

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

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

在SDS中护锤，除了上面解釋過的flags官地，對比于C傳統(tǒng)的char[],SDS新增了2個參數(shù)，實際占用長度len 和總分配長度alloc烙懦。

SDS解決了什么問題呢驱入？

1. 獲取字符串長度的復雜度問題

上面我們說過，c語言遍歷一下字符串的復雜度是o(n)修陡。

對于SDS來說，我們有了長度的參數(shù)可霎，那么我們的復雜度就是o(1)魄鸦，這樣在進行拼接等操作的時候不需要再次遍歷了。

2. 存儲二進制數(shù)據(jù)

C字符串不能存儲二進制數(shù)據(jù)的原因是只能根據(jù)'\0'來判斷數(shù)據(jù)是否結(jié)束癣朗，不能保證其完整性拾因，但因為SDS的len屬性，無論你數(shù)據(jù)里有多少'\0'都沒關(guān)系，我是根據(jù) len 屬性值來判斷數(shù)據(jù)長度的绢记，必定是完整的扁达，所以SDS可以安全地存儲二進制數(shù)據(jù)，這樣圖片音頻等二進制數(shù)據(jù)也可以存儲蠢熄。

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

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

A:SDS如果保持和C字符串一樣的特性叉讥，就不用專門編寫多余的函數(shù)了，在一定的情況下可以直接用C語言的函數(shù)饥追，避免了不必要的重寫图仓。

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

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

空間預分配

image.png

空間預分配源碼

在真正執(zhí)行拼接等操作之前救崔，會先計算下空間是否滿足

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

image.png

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

image.png

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

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

惰性空間釋放

當有縮短SDS字符串操作時岖赋，程序并不立即把空閑出來的字節(jié)釋放掉檬果，而是留給到惰性刪除策略等機制釋放。

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

在做刪除操作的時候唐断，當刪掉N個字符后选脊，alloc-len（也就是剩余空間）就增加N，換個說法脸甘，就是你刪除的字符并沒有立即被系統(tǒng)回收恳啥，這樣當你短時間內(nèi)再次拼接的時候，就不會申請空間分配了丹诀。

image.png

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

image.png

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

有了SDS,就萬事大吉了么翁垂？

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

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

初識RedisObject

在我們真實使用Redis中string的時候疟游，除了SDS的存儲空間，還存在一個Redis本身的結(jié)構(gòu)體痕支，也就是RedisObject颁虐。

RedisObject存儲空間

image.png

以上是RedisObject源碼，

• type:redisObject的數(shù)據(jù)類型卧须，4個bits
• encoding:redisObject的編碼類型另绩，4個bits
• lru:LRU_BITS:redisObject的LRU時間，LRU_BITS為24個bits
• refcount:redisObject的引用計數(shù)花嘶，4個字節(jié)
• *ptr:指向值的指針笋籽，8個字節(jié)

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

image.png

RedisObject和String

這里暫時不對RedisObject展開講椭员，我們來看看當RedisObject和SDS在一起的時候大概是個什么樣子车海？

image.png

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

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

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

對于數(shù)字類型的字符串隘击，Redis在RedisObjec中的指針就直接賦值為整數(shù)數(shù)據(jù)了侍芝，這么指針的開銷就省去了。

image.png

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

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

image.png

image.png

• 當字節(jié)數(shù)小于44虱肄，調(diào)用createEmbeddedStringObject
• 當字節(jié)數(shù)大于44致板，調(diào)用createRawStringObject

這里我們來看下createEmbeddedStringObject的部分源碼

image.png

這里做的事情核心

1. 先分配一段連續(xù)的內(nèi)存空間（RedisObject+SDS+1的長度，這里的1是為了字符串最后的`'\0'）咏窿，并創(chuàng)建RedisObject和SDS的機構(gòu)斟或。
2. 將RedisObject的ptr指針指向字符數(shù)組的開始。（細節(jié)：苍帧Ｂ拼狻Ｄ虿t。挨队。?/strong>
3. 拷貝字符串到SDS的buf[]中。

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

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

3. raw編碼模式

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

image.png

這里我們來看下createRawStringObject的部分源碼

image.png

這里就比較簡單了应役，一共做了這2件事：

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

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

image.png