Redis的底層數(shù)據(jù)結(jié)構(gòu)-String（IT楓斗者）
Redis的數(shù)據(jù)類型我們都知道有五個：String、List、Hhash、Set、Zset。
今天跟大家要說的是它們中string的底層數(shù)據(jù)結(jié)構(gòu)。?
一，底層數(shù)據(jù)結(jié)構(gòu)
二，必知必會的鋪墊
Redis對象，干嘛的？想象成對象頭，不管你什么類型，都必須要帶的，里面包含數(shù)據(jù)類型等等信息。
一個RedisObject占用的字節(jié)數(shù)：4+4+24+32+64=128位/8=16字節(jié)。
三、String數(shù)據(jù)結(jié)構(gòu)
sds/int/embstr/raw
1、SDS
1.1、sds概念
sds（simple dynamic string）：簡單動態(tài)字符串。SDS只是字符串類型中存儲字符串內(nèi)容的結(jié)構(gòu)，
Redis中的字符串分為兩種存儲方式，分別是embstr和raw。
sds中包含了free(當(dāng)前可用空間大小)，len(當(dāng)前存儲字符串長度)，buf[] (存儲的字符串內(nèi)容)，來看下
SDS的源碼：
1.2、sds干啥的？
比如你 set abc abcdefg ，簡單的一個set會創(chuàng)建出兩個sds，一個存key：abc，一個存value：abcdefg。比如如下：
1.3、為什么要有sds？
帶著問題看答案：C語言中也有字符串類型，為啥它不用C的，反正它都是C語言寫的，為啥要造個輪子sds？
1.3.1、優(yōu)化獲取字符串長度
C語言要想獲取字符串長度必須遍歷整個字符串的每一個字符，然后自增做累加，時間復(fù)雜度為O(n)；sds直接維護(hù)了一個len變量，時間復(fù)雜度為O(1)。
1.3.2、減少內(nèi)存分配
當(dāng)我們對一個字符串類型進(jìn)行追加的時候，可能會發(fā)生兩種情況：
當(dāng)前剩余空間(free)足夠容納追加內(nèi)容時，我們就不需要再去分配內(nèi)存空間，這樣可以減少內(nèi)存分配次數(shù)。
當(dāng)前剩余空間不足以容納追加內(nèi)容，我們需要重新為其申請內(nèi)存空間。
比如下面的sds的方式，free還有三個空余空間呢，你插入的是hi兩個字符，所以足夠，不需要調(diào)用函數(shù)重新分配，提升效率。
而C語言字符串在進(jìn)行字符串的擴(kuò)充和收縮的時候，都會面臨著內(nèi)存空間的重新分配問題。如果忘記分配或者分配大小不合理還會造成數(shù)據(jù)污染問題。那么sds的free值哪來的呢？也就是字符串?dāng)U容策略
當(dāng)給sds的值追加一個字符串，而當(dāng)前的剩余空間不夠時，就會觸發(fā)sds的擴(kuò)容機(jī)制。擴(kuò)容采用了空間預(yù)分配的優(yōu)化策略，即分配空間的時候：如果sds?值大小< 1M ,則增加一倍；反之如果>1M ,?則當(dāng)前空間加1M作為新的空間。
當(dāng)sds的字符串縮短了，sds的buf內(nèi)會多出來一些空間，這個空間并不會馬上被回收，而是暫時留著以防再用的時候進(jìn)行多余的內(nèi)存分配。這個是惰性空間釋放的策略
1.3.3、惰性釋放空間
當(dāng)我們截斷字符串時，Redis會把截斷部分置空，只保留剩余部分，且不立即釋放截斷部分的內(nèi)存空間，這樣做的好處就是當(dāng)下次再對這個字符串追加內(nèi)容的時候，如果當(dāng)前剩余空間足以容納追加內(nèi)容時，就不需要再去重新申請空間，避免了頻繁的內(nèi)存申請。暫時用不上的空間可以被Redis定時刪除或者惰性刪除。
1.3.4、防止緩沖區(qū)溢出
其實和減少內(nèi)存分配是成套的，都是因為sds預(yù)先檢查內(nèi)存自動分配來做到防止緩沖區(qū)溢出的。比如：
程序中有兩個在內(nèi)存中緊鄰著的 字符串 s1 和 s2，其中s1 保存了字符串“redis”，s2 則保存了字符串“MongoDb”：
1.3.5、二進(jìn)制安全
在C語言中通過判斷當(dāng)前字符是否為'\0'來確定字符串是否結(jié)束，而在sds結(jié)構(gòu)中，只要遍歷長度沒有達(dá)到len，即使遇到'\0'，也不會認(rèn)為字符串結(jié)束。比如下面內(nèi)存，C語言的字符串類型會丟失g123這四個字符，因為他遇到'\0'就結(jié)束了，而sds不會存在此問題。
1.3.6、與C總結(jié)
2、int
如果一個字符串內(nèi)容可轉(zhuǎn)為 long，那么該字符串會被轉(zhuǎn)化為 long 類型，redisObject的對象 ptr 指向該long，并將 encoding 設(shè)置為 int，這樣就不需要重新開辟空間，算是長整形的一個優(yōu)化。
3、embstr/raw
上面的SDS只是字符串類型中存儲字符串內(nèi)容的結(jié)構(gòu)，Redis中的字符串分為兩種存儲方式，分別是embstr和raw，當(dāng)字符串長度特別短（redis3.2之前是39字節(jié)，redis3.2之后是44字節(jié)）的時候，Redis使用embstr來存儲字符串，而當(dāng)字符串長度超過39（redis3.2之前）的時候，就需要用raw來存儲，下面是他們的字符串完整結(jié)構(gòu)的示意圖：
4、總結(jié)
redis的string底層數(shù)據(jù)結(jié)構(gòu)使用的是sds，但是sds有兩種存儲方式，一種是embstr，一種是raw。
embstr的優(yōu)勢在于和對象頭一起分配到連續(xù)空間，只需要調(diào)用函數(shù)malloc一次就行。raw需要兩次，一次是對象頭，一次是sds。釋放也一樣，embstr釋放一次，raw釋放兩次。
字符串內(nèi)容可轉(zhuǎn)為 long，采用 int 類型，否則長度<39（3.2版本前是39，3.2版本后分界線是44） 用embstr，其他用 raw。
SDS 是Redis自己構(gòu)建的一種簡單動態(tài)字符串的抽象類型，并將 SDS 作為 Redis 的默認(rèn)字符串表示。
SDS 與 C 語言字符串結(jié)構(gòu)相比，具有四大優(yōu)勢。
