一、基于內(nèi)存實(shí)現(xiàn)

Redis 是基于內(nèi)存的數(shù)據(jù)庫(kù)，那不可避免的就要與磁盤數(shù)據(jù)庫(kù)做對(duì)比。

對(duì)于磁盤數(shù)據(jù)庫(kù)來(lái)說(shuō)，是需要將數(shù)據(jù)讀取到內(nèi)存里的，這個(gè)過(guò)程會(huì)受到磁盤 I/O 的限制。

而對(duì)于內(nèi)存數(shù)據(jù)庫(kù)來(lái)說(shuō)，本身數(shù)據(jù)就存在于內(nèi)存里，也就沒(méi)有了這方面的開銷。

二、高效的數(shù)據(jù)結(jié)構(gòu)

Redis 中有多種數(shù)據(jù)類型，每種數(shù)據(jù)類型的底層都由一種或多種數(shù)據(jù)結(jié)構(gòu)來(lái)支持。

正是因?yàn)橛辛诉@些數(shù)據(jù)結(jié)構(gòu)，Redis 在存儲(chǔ)與讀取上的速度才不受阻礙。

1. 簡(jiǎn)單動(dòng)態(tài)字符串（SDS）

（1）字符串長(zhǎng)度處理

用一個(gè) len 字段記錄當(dāng)前字符串的長(zhǎng)度。想要獲取長(zhǎng)度只需要獲取 len 字段即可，時(shí)間復(fù)雜度為 O(1)。

（2）內(nèi)存重新分配

修改字符串的時(shí)候會(huì)重新分配內(nèi)存。修改地越頻繁，內(nèi)存分配也就越頻繁。而內(nèi)存分配是會(huì)消耗性能的，那么性能下降在所難免。而 Redis 中會(huì)涉及到字符串頻繁的修改操作，于是 SDS 實(shí)現(xiàn)了兩種優(yōu)化策略：

• - 空間預(yù)分配

對(duì) SDS 修改及空間擴(kuò)充時(shí)，除了分配所必須的空間外，還會(huì)額外分配未使用的空間。

具體分配規(guī)則是這樣的：SDS 修改后，len 長(zhǎng)度小于 1M，那么將會(huì)額外分配與 len 相同長(zhǎng)度的未使用空間。如果修改后長(zhǎng)度大于 1M，那么將分配1M的使用空間。

• - 惰性空間釋放

當(dāng)然，有空間分配對(duì)應(yīng)的就有空間釋放。

SDS 縮短時(shí)，并不會(huì)回收多余的內(nèi)存空間，而是使用 free 字段將多出來(lái)的空間記錄下來(lái)。如果后續(xù)有變更操作，直接使用 free 中記錄的空間，減少了內(nèi)存的分配。

（3）二進(jìn)制安全

讀取字符串遇到 ‘\0’ 會(huì)結(jié)束，那 ‘\0’ 之后的數(shù)據(jù)就讀取不上了。但在 SDS 中，是根據(jù) len 長(zhǎng)度來(lái)判斷字符串結(jié)束的，二進(jìn)制安全的問(wèn)題就解決了。

2. 雙端鏈表

• - 頭尾節(jié)點(diǎn)

頭節(jié)點(diǎn)里有 head 和 tail 兩個(gè)參數(shù)，分別指向頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。這樣的設(shè)計(jì)能夠?qū)﹄p端節(jié)點(diǎn)的處理時(shí)間復(fù)雜度降至 O(1) ，對(duì)于隊(duì)列和棧來(lái)說(shuō)再適合不過(guò)。同時(shí)鏈表迭代時(shí)從兩端都可以進(jìn)行。

• - 鏈表長(zhǎng)度

頭節(jié)點(diǎn)里同時(shí)還有一個(gè)參數(shù) len，和上邊提到的 SDS 里類似，這里是用來(lái)記錄鏈表長(zhǎng)度的。因此獲取鏈表長(zhǎng)度時(shí)不用再遍歷整個(gè)鏈表，直接拿到 len 值就可以了，這個(gè)時(shí)間復(fù)雜度是 O(1)。

• - 每個(gè)節(jié)點(diǎn)

鏈表里每個(gè)節(jié)點(diǎn)都帶有兩個(gè)指針，prev 指向前節(jié)點(diǎn)，next 指向后節(jié)點(diǎn)。這樣在時(shí)間復(fù)雜度為 O(1) 內(nèi)就能獲取到前后節(jié)點(diǎn)。

• - 鏈表結(jié)構(gòu)

3. 壓縮列表

如果在一個(gè)鏈表節(jié)點(diǎn)中存儲(chǔ)一個(gè)小數(shù)據(jù)，比如一個(gè)字節(jié)。那么對(duì)應(yīng)的就要保存頭節(jié)點(diǎn)，前后指針等額外的數(shù)據(jù)。

這樣就浪費(fèi)了空間，同時(shí)由于反復(fù)申請(qǐng)與釋放也容易導(dǎo)致內(nèi)存碎片化。這樣內(nèi)存的使用效率就太低了。Redis為了節(jié)約內(nèi)存開發(fā)了壓縮列表。

壓縮列表結(jié)構(gòu)

參數(shù)說(shuō)明：

• zlbytes：記錄整個(gè)壓縮列表占用的內(nèi)存字節(jié)數(shù)。
• zltail：記錄壓縮列表表尾節(jié)點(diǎn)距離壓縮列表起始地址有多少字節(jié)。
• zllen：記錄了壓縮列表包含的節(jié)點(diǎn)數(shù)量。
• entryN：壓縮列表的節(jié)點(diǎn)，節(jié)點(diǎn)長(zhǎng)度由節(jié)點(diǎn)保存的內(nèi)容決定。
• zlend：特殊值0xFF（十進(jìn)制255），用于標(biāo)記壓縮列表的末端。

4. 字典

dict結(jié)構(gòu)體是字典中最頂層的結(jié)構(gòu)體，用于指向兩個(gè)哈希表，兩個(gè)哈希表是為了在擴(kuò)容時(shí)使用

hash擴(kuò)容：

• 1 創(chuàng)建ht[1]，長(zhǎng)度= len(ht[0]) * 2
• 2 將ht[0]上的數(shù)據(jù)rehash到ht[1]上，即重新計(jì)算哈希地址
• 3 釋放ht[0]，將ht[1]設(shè)置為ht[0]，然后創(chuàng)建新的ht[1]

5. 跳躍表

調(diào)表的結(jié)構(gòu)：

由多層鏈表構(gòu)成，每層之間部分節(jié)點(diǎn)相連，且每層鏈表的數(shù)據(jù)都是有序的

最底層的鏈表是雙向的，且包含所有元素，可實(shí)現(xiàn)類似二分查找，

在調(diào)表中的查找次數(shù)接近層數(shù)，時(shí)間復(fù)雜度為O(logn)

用隨機(jī)化來(lái)決定哪些節(jié)點(diǎn)需要上浮

跳表中的查找：

類似二分查找，從最頂層開始查找，大數(shù)向右查找，小數(shù)向左查找

如查找17，查找路徑為 13 -> 46 -> 22 -> 17

因?yàn)?7>13(L3)，就在L3中往后走，發(fā)現(xiàn)17<46(L3)，

就通過(guò)13(L3)到達(dá)了13(L2)，然后往后走發(fā)現(xiàn)17<22(L2)，

就通過(guò)13(L2)往下達(dá)到了13(L1)，然后往后走就遇到了17

查找35 13 -> 46 -> 22 -> 46 -> 35

查找 54 13 -> 46 -> 54

跳表中的插入：

1 先在最底層鏈表中找到合適的位置，并插入

2 然后用拋硬幣的方式?jīng)Q定它是需要上浮的次數(shù)

假如此時(shí)鏈表共3層，需要拋兩次硬幣，來(lái)決定它上浮幾次

跳表與平衡樹、哈希表的比較

1 skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。

因此，在哈希表上只能做單個(gè)key的查找，不適宜做范圍查找。所謂范圍查找，指的是查找那些大小在指定的兩個(gè)值之間的所有節(jié)點(diǎn)。

2 在做范圍查找的時(shí)候，平衡樹比skiplist操作要復(fù)雜。

在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續(xù)尋找其它不超過(guò)大值的節(jié)點(diǎn)。

如果不對(duì)平衡樹進(jìn)行一定的改造，這里的中序遍歷并不容易實(shí)現(xiàn)。

而在skiplist上進(jìn)行范圍查找就非常簡(jiǎn)單，只需要在找到小值之后，對(duì)第1層鏈表進(jìn)行若干步的遍歷就可以實(shí)現(xiàn)。

3 平衡樹的插入和刪除操作可能引發(fā)子樹的調(diào)整，邏輯復(fù)雜，

而skiplist的插入和刪除只需要修改相鄰節(jié)點(diǎn)的指針，操作簡(jiǎn)單又快速。

4 從內(nèi)存占用上來(lái)說(shuō)，skiplist比平衡樹更靈活一些。

一般來(lái)說(shuō)，平衡樹每個(gè)節(jié)點(diǎn)包含2個(gè)指針（分別指向左右子樹），而skiplist每個(gè)節(jié)點(diǎn)包含的指針數(shù)目平均為1/(1-p)，具體取決于參數(shù)p的大小。如果像Redis里的實(shí)現(xiàn)一樣，取p=1/4，那么平均每個(gè)節(jié)點(diǎn)包含1.33個(gè)指針，比平衡樹更有優(yōu)勢(shì)。

5 查找單個(gè)key，skiplist和平衡樹的時(shí)間復(fù)雜度都為O(log n)，大體相當(dāng)；

而哈希表在保持較低的哈希值沖突概率的前提下，查找時(shí)間復(fù)雜度接近O(1)，性能更高一些。

所以我們平常使用的各種Map或dictionary結(jié)構(gòu)，大都是基于哈希表實(shí)現(xiàn)的。

從算法實(shí)現(xiàn)難度上來(lái)比較，skiplist比平衡樹要簡(jiǎn)單得多。

四、合理的數(shù)據(jù)編碼

對(duì)于每一種數(shù)據(jù)類型來(lái)說(shuō)，底層的支持可能是多種數(shù)據(jù)結(jié)構(gòu)，什么時(shí)候使用哪種數(shù)據(jù)結(jié)構(gòu)，這就涉及到了編碼轉(zhuǎn)化的問(wèn)題。

那我們就來(lái)看看，不同的數(shù)據(jù)類型是如何進(jìn)行編碼轉(zhuǎn)化的：

• String：存儲(chǔ)數(shù)字的話，采用int類型的編碼，如果是非數(shù)字的話，采用 raw 編碼；
• List：字符串長(zhǎng)度及元素個(gè)數(shù)小于一定范圍使用 ziplist 編碼，任意條件不滿足，則轉(zhuǎn)化為 linkedlist 編碼；
• Hash：hash 對(duì)象保存的鍵值對(duì)內(nèi)的鍵和值字符串長(zhǎng)度小于一定值及鍵值對(duì)；
• Set：保存元素為整數(shù)及元素個(gè)數(shù)小于一定范圍使用 intset 編碼，任意條件不滿足，則使用 hashtable 編碼；
• Zset：zset 對(duì)象中保存的元素個(gè)數(shù)小于及成員長(zhǎng)度小于一定值使用 ziplist 編碼，任意條件不滿足，則使用 skiplist 編碼。

五、合適的線程模型

1. I/O多路復(fù)用模型

2. 避免上下文切換

3. 單線程模型

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論