【Redis原理】Redis數據結構底層原理

一、SDS

二、IntSet（整數集合）

三、雙向鏈表

四、壓縮列表

五、字典（哈希表）

七、跳表

八、QuickList

九、RedisObject

一、SDS

Redis 是用 C語言實現的，但是它沒有直接使用C 語言的 char* 字符數組來實現字符串，而是自己封裝了-個名為簡單動態字符串(simple dynamic string，SDs) 的數據結構來表示字符串，也就是 Redis 的String 數據類型的底層數據結構是 SDS。
?

C 語言字符串的缺陷

獲取字符串長度的時間復雜度為O(N)
非二進制安全（不能存二進制數據）
不可修改
字符串操作函數不高效且不安全，比如有緩沖區溢出的風險，有可能會造成程序運行終止
?

SDS 結構

?Redis 5.0 的 SDS 的數據結構：

len：記錄了字符串長度。這樣獲取字符串長度的時候，只需要返回這個成員變量值就行，時間復雜度只需要O(1)。
alloc：分配給字符數組的空間長度。這樣在修改字符串的時候，可以通過alloc - len計算出剩余的空間大小，可以用來判斷空間是否滿足修改需求，如果不滿足的話，就會自動將SDS的空間擴展至執行修改所需的大小，然后才執行實際的修改操作，所以使用SDS既不需要手動修改SDS的空間大小，也不會出現前面所說的緩沖區溢出的問題。
flags：用來表示不同類型的SDS。一共設計了5種類型，分別是sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64。
buf[]：字節數組，用來保存實際數據。不僅可以保存字符串，也可以保存二進制數據。?總的來說，Redis的SDS結構在原本字符數組之上，增加了三個元數據：len、alloc、flags，用來解決C語言字符串的缺陷。

SDS的擴容原理：

如果所需的sds長度小于1MB，那么最后的擴容是按照翻倍擴容來執行的，即2倍的newlen。
如果所需的sds長度超過1MB，那么最后的擴容長度應該是newlen + 1MB。

在擴容SDS空間之前，SDS API會優先檢查未使用空間是否足夠，如果不夠的話，API不僅會為SDS分配修改所必須要的空間，還會給SDS分配額外的「未使用空間」。

這樣的好處是，下次在操作SDS時，如果SDS空間夠的話，API就會直接使用「未使用空間」，而無須執行內存分配，有效的減少內存分配次數。

所以，使用SDS即不需要手動修改SDS的空間大小，也不會出現緩沖區溢出的問題。

二、IntSet（整數集合）

IntSet是Redis中set集合的一種實現方式，基于整數數組來實現，并且具備長度可變、有序等特征。結構如下：

typedef struct intset {uint32_t encoding;  // 編碼方式，決定每個元素的字節大小uint32_t length;    // 集合包含的元素數量int8_t contents[];  // 保存元素的柔性數組
} intset;

其中的encoding包含三種模式，表示存儲的整數大小不同：

為了方便查找，Redis會將intset中所有的整數按照升序依次保存在contents數組中，結構如圖：

現在，數組中每個數字都在int16_t的范圍內，因此采用的編碼方式是INTSET_ENC_INT16，每部分占用的字節大小為：

encoding：4字節
length：4字節
contents：2字節 * 3 = 6字節

我們向該其中添加一個數字：50000，這個數字超出了int16_t的范圍，intset會自動升級編碼方式到合適的大小。

以當前案例來說流程如下：

升級編碼為INTSET_ENC_INT32, 每個整數占4字節，并按照新的編碼方式及元素個數擴容數組
倒序依次將數組中的元素拷貝到擴容后的正確位置
將待添加的元素放入數組末尾
最后，將inset的encoding屬性改為INTSET_ENC_INT32，將length屬性改為4

Intset可以看做是特殊的整數數組，具備一些特點：

Redis會確保Intset中的元素唯一、有序

具備類型升級機制，可以節省內存空間

底層采用二分查找方式來查詢

不支持降級操作

三、雙向鏈表

Redis的鏈表實現優點如下：

listNode鏈表節點的結構里帶有prev和next指針，獲取某個節點的前置節點或后置節點的時間復雜度只需O(1)，而且這兩個指針都可以指向 NULL，所以鏈表是無環鏈表；
list結構因為提供了表頭指針 head 和表尾節點tail，所以獲取鏈表的表頭節點和表尾節點的時間復雜度只需O(1)；
list結構因為提供了鏈表節點數量len，所以獲取鏈表中的節點數量的時間復雜度只需O(1)；
listNode鏈表節使用void* 指針保存節點值，并且可以通過 list結構的 dup、free、match函數指針為節點設置該節點類型特定的函數，因此鏈表節點可以保存各種不同類型的值；?

鏈表的缺點：

鏈表每個節點之間的內存都是不連續的，意味著無法很好利用CPU緩存。能很好利用CPU緩存的數據結構就是數組，因為數組的內存是連續的，這樣就可以充分利用 CPU緩存來加速訪問。
還有一點，保存一個鏈表節點的值都需要一個鏈表節點結構頭的分配，內存開銷較大。

因此， Redis 3.0的List對象在數據量比較少的情況下，會采用「壓縮列表」作為底層數據結構的實現，它的優勢是節省內存空間，并且是內存緊湊型的數據結構。

不過，壓縮列表存在性能問題（具體什么問題，下面會說），所以 Redis在3.2版本設計了新的數據結構quicklist，并將List對象的底層數據結構改由 quicklist 實現。

然后在 Redis 5.0 設計了新的數據結構 listpack，沿用了壓縮列表緊湊型的內存布局，最終在最新的 Redis版本，將 Hash對象和 Zset對象的底層數據結構實現之一的壓縮列表，替換成由 listpack實現。

四、壓縮列表

ZipList 是一種特殊的“雙端鏈表” ，由一系列特殊編碼的連續內存塊組成。可以在任意一端進行壓入/彈出操作, 并且該操作的時間復雜度為 O(1)。

屬性	類型	長度	用途
zlbytes	uint32_t	4 字節	記錄整個壓縮列表占用的內存字節數
zltail	uint32_t	4 字節	記錄壓縮列表表尾節點距離壓縮列表的起始地址有多少字節，通過這個偏移量，可以確定表尾節點的地址。
zllen	uint16_t	2 字節	記錄了壓縮列表包含的節點數量。最大值為UINT16_MAX （65534），如果超過這個值，此處會記錄為65535，但節點的真實數量需要遍歷整個壓縮列表才能計算得出。
entry	列表節點	不定	壓縮列表包含的各個節點，節點的長度由節點保存的內容決定。
zlend	uint8_t	1 字節	特殊值 0xFF （十進制 255 ），用于標記壓縮列表的末端。

ZipListEntry

ZipList 中的Entry并不像普通鏈表那樣記錄前后節點的指針，因為記錄兩個指針要占用16個字節，浪費內存。而是采用了下面的結構：

previous_entry_length：前一節點的長度，占1個或5個字節。
- 如果前一節點的長度小于254字節，則采用1個字節來保存這個長度值
- 如果前一節點的長度大于254字節，則采用5個字節來保存這個長度值，第一個字節為0xfe，后四個字節才是真實長度數據
encoding：編碼屬性，記錄content的數據類型（字符串還是整數）以及長度，占用1個、2個或5個字節
contents：負責保存節點的數據，可以是字符串或整數

ZipList中所有存儲長度的數值均采用小端字節序，即低位字節在前，高位字節在后。例如：數值0x1234，采用小端字節序后實際存儲值為：0x3412

Encoding編碼

ZipListEntry中的encoding編碼分為字符串和整數兩種：字符串：如果encoding是以“00”、“01”或者“10”開頭，則證明content是字符串

如果當前節點的數據是整數，則encoding會使用1字節的空間進行編碼，也就是encoding長度為1字節。通過encoding確認了整數類型，就可以確認整數數據的實際大小了，比如如果encoding編碼確認了數據是int16整數，那么data的長度就是int16的大小。
如果當前節點的數據是字符串，根據字符串的長度大小，encoding會使用1字節/2字節/5字節的空間進行編碼，encoding編碼的前兩個bit表示數據的類型，后續的其他bit標識字符串數據的實際長度，即data的長度。

ZipList的每個Entry都包含previous_entry_length來記錄上一個節點的大小，長度是1個或5個字節：如果前一節點的長度小于254字節，則采用1個字節來保存這個長度值如果前一節點的長度大于等于254字節，則采用5個字節來保存這個長度值，第一個字節為0xfe，后四個字節才是真實長度數據現在，假設我們有N個連續的、長度為250~253字節之間的entry，因此entry的previous_entry_length屬性用1個字節即可表示，如圖所示：

ZipList這種特殊情況下產生的連續多次空間擴展操作稱之為連鎖更新（Cascade Update）。新增、刪除都可能導致連鎖更新的發生。

優點：

節省內存開銷
能更好地利用 CPU 緩存。

缺點：

插入/刪除效率低，修改可能觸發連鎖更新問題，會導致壓縮列表占用的內存空間要多次重新分配，這就會直接影響到壓縮列表的訪問性能。
僅適合元素少、元素小的小對象存儲。

五、字典（哈希表）

Dict由三部分組成，分別是：哈希表（DictHashTable）、哈希節點（DictEntry）、字典（Dict）

Dict結構圖：

Hash沖突

Redis 采用了「鏈式哈希」的方法來解決哈希沖突（拉鏈法），（頭插法插入節點）

Dict的擴容：

Dict中的HashTable就是數組結合單向鏈表的實現，當集合中元素較多時，必然導致哈希沖突增多，鏈表過長，則查詢效率會大大降低。

Dict在每次新增鍵值對時都會檢查負載因子（LoadFactor = used/size） ，滿足以下兩種情況時會觸發哈希表擴容（rehash）：

哈希表的 LoadFactor >= 1，并且服務器沒有執行 BGSAVE 或者 BGREWRITEAOF 等后臺進程；
哈希表的 LoadFactor > 5 ；

Dict的rehash：

不管是擴容還是收縮，必定會創建新的哈希表，導致哈希表的size和sizemask變化，而key的查詢與sizemask有關。因此必須對哈希表中的每一個key重新計算索引，插入新的哈希表，這個過程稱為rehash。過程是這樣的：

計算新hash表的realeSize，值取決于當前要做的是擴容還是收縮：
- 如果是擴容，則新size為第一個大于等于dict.ht[0].used + 1的2^n
- 如果是收縮，則新size為第一個大于等于dict.ht[0].used的2^n （不得小于4）
按照新的realeSize申請內存空間，創建dictht，并賦值給dict.ht[1]
設置dict.rehashidx = 0，標示開始rehash
將dict.ht[0]中的每一個dictEntry都rehash到dict.ht[1]
將dict.ht[1]賦值給dict.ht[0]，給dict.ht[1]初始化為空哈希表，釋放原來的dict.ht[0]的內存
將rehashidx賦值為-1，代表rehash結束
在rehash過程中，新增操作，則直接寫入ht[1]，查詢、修改和刪除則會在dict.ht[0]和dict.ht[1]依次查找并執行。這樣可以確保ht[0]的數據只減不增，隨著rehash最終為空

存在的問題：

如果「哈希表1」的數據量非常大，那么在遷移至「哈希表2」的時候，因為會涉及大量的數據拷貝，此時可能會對 Redis 造成阻塞，無法服務其他請求。

漸進式 rehash

為了避免 rehash 在數據遷移過程中，因拷貝數據的耗時，影響 Redis 性能的情況，所以 Redis 采用了漸進式 rehash，也就是將數據的遷移的工作不再是一次性遷移完成，而是分多次遷移。

漸進式 rehash 步驟如下：

給「哈希表 2」分配空間；
在 rehash 進行期間，每次哈希表元素進行新增、刪除、查找或者更新操作時，Redis 除了會執行對應的操作之外，還會順序將「哈希表 1」中索引位置上的所有 key-value 遷移到「哈希表 2」上；
隨著處理客戶端發起的哈希表操作請求數量越多，最終在某個時間點會把「哈希表 1」的所有 key-value 遷移到「哈希表 2」，從而完成 rehash 操作。

這樣就巧妙地把一次性大量數據遷移工作的開銷，分攤到了多次處理請求的過程中，避免了一次性 rehash 的耗時操作。

在進行漸進式 rehash 的過程中，會有兩個哈希表，所以在漸進式 rehash 進行期間，哈希表元素的刪除、查找、更新等操作都會在這兩個哈希表進行。

比如，查找一個 key 的值的話，先會在「哈希表 1」里面進行查找，如果沒找到，就會繼續到哈希表 2 里面進行找到。

另外，在漸進式 rehash 進行期間，新增一個 key-value 時，會被保存到「哈希表 2」里面，而「哈希表 1」則不再進行任何添加操作，這樣保證了「哈希表 1」的 key-value 數量只會減少，隨著 rehash 操作的完成，最終「哈希表 1」就會變成空表。

七、跳表

跳表結構設計：

鏈表在查找元素的時候，因為需要逐一查找，所以查詢效率非常低，時間復雜度是O(N)，于是就出現了跳表。跳表是在鏈表基礎上改進過來的，實現了一種「多層」的有序鏈表，這樣的好處是能快速定位數據。

下圖展示了一個層級為3的跳表

圖中頭節點有 L0~L2 三個頭指針，分別指向了不同層級的節點，然后每個層級的節點都通過指針連接起來：

L0 層級共有 5 個節點，分別是節點1、2、3、4、5；
L1 層級共有 3 個節點，分別是節點 2、3、5；
L2 層級只有 1 個節點，也就是節點 3。

如果我們要在鏈表中查找節點 4 這個元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節點 4，因為可以在頭節點直接從 L2 層級跳到節點 3，然后再往前遍歷找到節點 4。

可以看到，這個查找過程就是在多個層級上跳來跳去，最后定位到元素。當數據量很大時，跳表的查找復雜度就是 O(logN)。

那跳表節點是怎么實現多層級的呢？這就需要看「跳表節點」的數據結構了，如下：

typedef struct zskiplistNode {//Zset 對象的元素值sds ele;//元素權重值double score;//后向指針struct zskiplistNode *backward;//節點的 level 數組，保存每層上的前向指針和跨度struct zskiplistLevel {struct zskiplistNode *forward;unsigned long span;} level[];
} zskiplistNode;

Zset 對象要同時保存「元素」和「元素的權重」，對應到跳表節點結構里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個跳表節點都有一個后向指針（struct zskiplistNode *backward），指向前一個節點，目的是為了方便從跳表的尾節點開始訪問節點，這樣倒序查找時很方便。

跳表是一個帶有層級關系的鏈表，而且每一層級可以包含多個節點，每一個節點通過指針連接起來，實現這一特性就是靠跳表節點結構體中的zskiplistLevel 結構體類型的 level 數組。

level 數組中的每一個元素代表跳表的一層，也就是由 zskiplistLevel 結構體表示，比如 leve 就表示第一層，leve 就表示第二層。zskiplistLevel 結構體里定義了「指向下一個跳表節點的指針」和「跨度」，跨度時用來記錄兩個節點之間的距離。

比如，下面這張圖，展示了各個節點的跨度。

跨度實際上是為了計算這個節點在跳表中的排位。

具體怎么做的呢？

因為跳表中的節點都是按序排列的，那么計算某個節點排位的時候，從頭節點到該結點的查詢路徑上，將沿途訪問過的所有層的跨度累加起來，得到的結果就是目標節點在跳表中的排位。

舉個例子，查找圖中節點3在跳表中的排位，從頭節點開始查找節點3，查找的過程只經過了一個層（L2），并且層的跨度是3，所以節點3在跳表中的排位是3。

另外，圖中的頭節點其實也是zskiplistNode跳表節點，只不過頭節點的后向指針、權重、元素值都沒有用到，所以圖中省略了這部分。

問題來了，由誰定義哪個跳表節點是頭節點呢？這就介紹「跳表」結構體了，如下所示：

typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;int level;
} zskiplist;

跳表結構里包含了：

跳表的頭尾節點，便于在O(1)時間復雜度內訪問跳表的頭節點和尾節點；
跳表的長度，便于在O(1)時間復雜度獲取跳表節點的數量；
跳表的最大層數，便于在O(1)時間復雜度獲取跳表中層高最大的那個節點的層數量；

跳表節點查詢過程

查找一個跳表節點的過程時，跳表會從頭節點的最高層開始，逐一遍歷每一層。在遍歷某一層的跳表節點時，會用跳表節點中的 SDS 類型的元素和元素的權重來進行判斷，共有兩個判斷條件：

如果當前節點的權重『小于』要查找的權重時，跳表就會訪問該層上的下一個節點。
如果當前節點的權重『等于』要查找的權重時，并且當前節點的 SDS 類型數據『小于』要查找的數據時，跳表就會訪問該層上的下一個節點。

如果上面兩個條件都不滿足，或者下一個節點為空時，跳表就會使用目前遍歷到的節點的 level 數組里的下一層指針，然后沿著下一層指針繼續查找，這就相當于跳到了下一層接著查找。

舉個例子，下圖有個 3 層級的跳表。

如果要查找『元素：abcd，權重：4』的節點，查找的過程是這樣的：

先從頭節點的最高層開始，L2 指向了『元素：abc，權重：3』節點，這個節點的權重比要查找節點的小，所以要訪問該層上的下一個節點；
但是該層的下一個節點是空節點（leve指向的是空節點），于是就會跳到『元素：abc，權重：3』節點的下一層去找，也就是 leve;
『元素：abc，權重：3』節點的 leve 的下一個指針指向了『元素：abcde，權重：4』的節點，然后將其和要查找的節點比較。雖然『元素：abcde，權重：4』的節點的權重和要查找的權重相同，但是當前節點的 SDS 類型數據『大于』要查找的數據，所以會繼續跳到『元素：abc，權重：3』節點的下一層去找，也就是 leve;
『元素：abc，權重：3』節點的 leve 的下一個指針指向了『元素：abcd，權重：4』的節點，該節點正是要查找的節點，查詢結束。

跳表節點層數設置

跳表的相鄰兩層的節點數量的比例會影響跳表的查詢性能、舉個例子，下圖的跳表，第二層的節點數量只有1個，而第一層的節點數量有6個

這時，如果想要查詢節點 6，那基本就跟鏈表的查詢復雜度一樣，就需要在第一層的節點中依次順序查找，復雜度就是 O(N) 了。所以，為了降低查詢復雜度，我們就需要維持相鄰層結點數間的關系。

跳表的相鄰兩層的節點數量最理想的比例是 2:1，查找復雜度可以降低到 O(logN)。

下圖的跳表就是，相鄰兩層的節點數量的比例是 2:1。

那怎樣才能維持相鄰兩層的節點數量的比例為 2 : 1 呢?

如果采用新增節點或者刪除節點時，來調整跳表節點以維持比例的方法的話，會帶來額外的開銷。

Redis 則采用一種巧妙的方法是，跳表在創建節點的時候，隨機生成每個節點的層數，并沒有嚴格維持相鄰兩層的節點數量比例為 2 : 1 的情況。

具體的做法是，跳表在創建節點時候，會生成范圍為[0-1]的一個隨機數，如果這個隨機數小于 0.25（相當于概率 25%），那么層數就增加 1 層，然后繼續生成下一個隨機數，直到隨機數的結果大于 0.25 結束，最終確定該節點的層數。

這樣的做法，相當于每增加一層的概率不超過 25%，層數越高，概率越低，層高最大限制是 64。

雖然我前面講解跳表的時候，圖中的跳表的「頭節點」都是 3 層高，但是其實如果層高最大限制是 64，那么在創建跳表「頭節點」的時候，就會直接創建 64 層高的頭節點。

八、QuickList

其實 quicklist 就是「雙向鏈表+壓縮列表」組合，因為一個 quicklist 就是一個鏈表，而鏈表中的每個元素又是一個壓縮列表。

雖然壓縮列表是通過緊湊型的內存布局節省了內存開銷，但是因為它的結構設計，如果保存的元素數量增加，或者元素變大了，壓縮列表會有「連鎖更新」的風險，一旦發生，會造成性能下降。

quicklist 解決辦法，通過控制每個鏈表節點中的壓縮列表的大小或者元素個數，來規避連鎖更新的問題,因為壓縮列表元素越少或越小，連鎖更新帶來的影響就越小，從而提供了更好的訪問性能。
?

quicklist 結構設計

在向 quicklist 添加一個元素的時候，不會像普通的鏈表那樣，直接新建一個鏈表節點。而是會檢查插入位置的壓縮列表是否能容納該元素，如果能容納就直接保存到 quicklistNode 結構里的壓縮列表，如果不能容納，才會新建一個新的 quicklistNode 結構。

quicklist 會控制 quicklistNode 結構里的壓縮列表的大小或者元素個數，來規避潛在的連鎖更新的風險，但是這并沒有完全解決連鎖更新的問題。

QuickList的特點：

是一個節點為ZipList的雙端鏈表

節點采用ZipList，解決了傳統鏈表的內存占用問題

控制了ZipList大小，解決連續內存空間申請效率問題

中間節點可以壓縮，進一步節省了內存

九、RedisObject

Redis中的任意數據類型的鍵和值都會被封裝為一個RedisObject，也叫做Redis對象

從Redis的使用者的角度來看，?個Redis節點包含多個database（非cluster模式下默認是16個，cluster模式下只能是1個），而一個database維護了從key space到object space的映射關系。這個映射關系的key是string類型，?value可以是多種數據類型，比如： string, list, hash、set、sorted set等。

我們可以看到，key的類型固定是string，而value可能的類型是多個。

?從Redis內部實現的?度來看，database內的這個映射關系是用?個dict來維護的。dict的key固定用?種數據結構來表達就夠了，這就是動態字符串sds。而value則比較復雜，為了在同?個dict內能夠存儲不同類型的value，這就需要?個通?的數據結構，這個通用的數據結構就是robj，全名是redisObject。

Redis的編碼方式

Redis中會根據存儲的數據類型不同，選擇不同的編碼方式，共包含11種不同類型：

編號	編碼方式	說明
0	OBJ_ENCODING_RAW	raw編碼動態字符串
1	OBJ_ENCODING_INT	long類型的整數的字符串
2	OBJ_ENCODING_HT	hash表（字典dict）
3	OBJ_ENCODING_ZIPMAP	已廢棄
4	OBJ_ENCODING_LINKEDLIST	雙端鏈表
5	OBJ_ENCODING_ZIPLIST	壓縮列表
6	OBJ_ENCODING_INTSET	整數集合
7	OBJ_ENCODING_SKIPLIST	跳表
8	OBJ_ENCODING_EMBSTR	embstr的動態字符串
9	OBJ_ENCODING_QUICKLIST	快速列表
10	OBJ_ENCODING_STREAM	Stream流

五種數據結構

Redis中會根據存儲的數據類型不同，選擇不同的編碼方式。每種數據類型的使用的編碼方式如下：

數據類型	編碼方式
OBJ_STRING	int、embstr、raw
OBJ_LIST	LinkedList和ZipList(3.2以前)、QuickList（3.2以后）
OBJ_SET	intset、HT
OBJ_ZSET	ZipList、HT、SkipList
OBJ_HASH	ZipList、HT