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

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

對于磁盤數(shù)據(jù)庫來說，是需要將數(shù)據(jù)讀取到內(nèi)存里的，這個過程會受到磁盤 I/O 的限制。

而對于內(nèi)存數(shù)據(jù)庫來說，本身數(shù)據(jù)就存在于內(nèi)存里，也就沒有了這方面的開銷。

二、高效的數(shù)據(jù)結構

Redis 中有多種數(shù)據(jù)類型，每種數(shù)據(jù)類型的底層都由一種或多種數(shù)據(jù)結構來支持。

正是因為有了這些數(shù)據(jù)結構，Redis 在存儲與讀取上的速度才不受阻礙。

1. 簡單動態(tài)字符串（SDS）

（1）字符串長度處理

用一個 len 字段記錄當前字符串的長度。想要獲取長度只需要獲取 len 字段即可，時間復雜度為 O(1)。

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

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

• - 空間預分配

對 SDS 修改及空間擴充時，除了分配所必須的空間外，還會額外分配未使用的空間。

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

• - 惰性空間釋放

當然，有空間分配對應的就有空間釋放。

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

（3）二進制安全

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

2. 雙端鏈表

• - 頭尾節(jié)點

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

• - 鏈表長度

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

• - 每個節(jié)點

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

• - 鏈表結構

3. 壓縮列表

如果在一個鏈表節(jié)點中存儲一個小數(shù)據(jù)，比如一個字節(jié)。那么對應的就要保存頭節(jié)點，前后指針等額外的數(shù)據(jù)。

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

壓縮列表結構

參數(shù)說明：

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

4. 字典

dict結構體是字典中最頂層的結構體，用于指向兩個哈希表，兩個哈希表是為了在擴容時使用

hash擴容：

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

5. 跳躍表

調(diào)表的結構：

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

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

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

用隨機化來決定哪些節(jié)點需要上浮

跳表中的查找：

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

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

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

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

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

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

查找 54 13 -> 46 -> 54

跳表中的插入：

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

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

假如此時鏈表共3層，需要拋兩次硬幣，來決定它上浮幾次

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

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

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

2 在做范圍查找的時候，平衡樹比skiplist操作要復雜。

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

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

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

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

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

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

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

5 查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)，大體相當；

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

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

從算法實現(xiàn)難度上來比較，skiplist比平衡樹要簡單得多。

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

對于每一種數(shù)據(jù)類型來說，底層的支持可能是多種數(shù)據(jù)結構，什么時候使用哪種數(shù)據(jù)結構，這就涉及到了編碼轉(zhuǎn)化的問題。

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

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

五、合適的線程模型

1. I/O多路復用模型

2. 避免上下文切換

3. 單線程模型

總結

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

最新評論