目錄

1.動態字符串SDS

1.1SDS底層源碼

1.2 SDS動態擴容

1.3動態字符串SDS優點?

2.IntSet?

2.1底層結構

2.2有序性

2.3.IntSet結構擴容

2.4總結

3.Dict

3.1底層結構

3.2.Dict擴容?

3.3Dict收縮

?3.4.Dict的rehash

1.分配空間

2. 設置?rehashidx

3. 漸進式?rehash

Redis 采用漸進式?rehash?策略，避免一次性?rehash?大量鍵對服務器性能造成影響。具體步驟如下：

4. 遷移完成

4.ZipList

4.1底層結構

4.1.1 ZipList

?4.1.2 Entry

4.2.Encoding編碼

設計優勢

4.3.ZipList的連鎖更新問題

5.QuickList

5.1總結

6.SKipList

6.1底層結構源碼

?6.2總結

7.RedisObject

7.1.Redis的編碼方式

---

1.動態字符串SDS

我們都知道Redis保存的key是字符串value往往是字符串或者字符串的集合。可見字符串是redis中最常見的一種數據結構。

redis底層是c語言編寫的，不過redis并沒有直接使用c語言中的字符串，因為c語言字符串存在許多問題：

//c語言
char* s = "hello"
//本質是字符串數組：{'h','e','l','l','o','\0'}

• 獲取字符串長度需要通過運算（獲取字符串長度還需要 - 結束標識符）
• 非二進制安全（不能包含特殊字符）
• 不可修改

所以Redis構建了一種新的字符串，動態字符串簡稱SDS

1.1SDS底層源碼

flags：redis為了解決數據結構體大小受限問題創建了不同的SDS數據結構類型（比如uint8_t只能存儲大小為255個字節數組字符串），flags主要作用就是用來存儲SDS的類型信息，在redis中，不同SDS在存儲容量和內存使用效率上各有不同。借助flags字段，redis能夠依據實際需求選用合適的SDS類型，從而實現內存的高效利用

flags默認值如下

例如，一個字符串包含name的sds結構如下：

flags：1表示使用type8來存儲數據

1.2 SDS動態擴容

SDS之所以叫動態字符串，因為它具備動態擴容的能力

步驟如下：

1.redis首先會去申請新的內存空間：申請規則如下

如果我們新的字符串大小小于1M,則新空間為擴張后字符串長度兩倍+1（減少內存分配的次數減少性能開銷）

如果新字符串大小大于1M，則新空間為擴展后字符串長度+1M+1。稱為內存分配。（大于1M字符串如果再擴張為2倍非常浪費內存空間）

2.再把原數組數據賦值過來

1.3動態字符串SDS優點?

• 1.獲取字符串長度的時間復雜度為0（1）
• 2.支持動態擴容
• 3.減少內存分配次數
• 4.二進制安全

---

2.IntSet?

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

2.1底層結構

encoding其實和動態字符串SDS的flags作用一樣記錄使用哪種數據類型?，其中encoding包含三種模式，表示存儲的整數大小不同：

2.2有序性

為了方便查找，Redis會在intset中所有的整數按照升序依次保存在contens數組中，

現在每個數組中的每個數字都在int16_t范圍內，因此采用的編碼方式是INTSET_ENC_INT16

• 1.IntSet底層采用的是連續的數組來存儲元素，并且每個元素的類型相同，那么每個元素內存中所占空間大小是固定的。
• 2.intset會有尋址公式startPtr + (sizeof(int16)*index)通過這種尋址公式，intset可以高效的訪問數組中任意元素，通過將起始地址startPtr加上偏移量（sizeof(int16)*index），就能得到指定索引位置元素的內存地址。
• 3.startPtr：這是整數集合底層數組的起始地址。根據上面那幅圖就是Header包含的部分
• sizeof(int16)：sizeof是一個用于獲取數據類型所占字節數的操作符，int16表示 16 位整數，
• index：這是數組中元素的索引

2.3.IntSet結構擴容

IntSet支持動態升級能力，如果當前數據結構存儲不了要添加數據的大小就會升級編碼

舉個栗子：

現在假設有一個IntSet，元素為{5，10，20}采用的編碼是INTSET_ENC_INT16則每個整數占2個字節

我們向該其中添加一個數字：5000,這個數字超出了int16_t的范圍，intset會自動升級編碼方式到合適的大小。
以當前案例來說流程如下：

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

---

這里你可能會有疑問為什么不正序添加元素而是采用倒序添加元素

主要是避免數據覆蓋問題：IntSet在內存中是連續存儲的，當進行編碼升級時，新元素類型的字節數會比原類型大。（要么添加到所有元素之后要么添加到所有元素之前，因為這個數要么就是負數很小，要么就是整數很大比如-5000or5000）如果正序添加元素，在將原Intset中的元素復制到新數組時，由于新元素占用空間更大，可能會覆蓋尚未處理的后續元素。

2.4總結

• 1.Redis會確保Inset中的元素唯一，有序
• 2.具備類型升級機制，可以節省內存空間
• 3.底層采用二分查找方式來查詢

---

3.Dict

Dict是dictionary也就是字典的簡稱。redis是一個鍵值型（Key-Value pair)的數據庫，我們可以根據鍵實現快速的增刪改查。而鍵與值的映射關系Dict來實現的。
Dict由三部分組成，分別是：哈希表（DictHashTable),哈希節點（DictEntry),字典（Dict)

3.1底層結構

dict（字典）

• 1.type表示字典類型（不同場景下使用不同字典類型，擴展性很強）
• 2.ht[2]表是兩個hash表，一個用于存儲數據，一個用于重新構建hash表的時候使用
• 3.rehashidx表示是否進行rehash

對于dictht（哈希表）

• 1.第一個字段 table表示指針指向存儲hash節點數組的指針
• 2.size代表hash表的大小也就是數組的大小
• 3.掩碼sizemask，用于計算鍵值對存儲的位置
• 4.used表示有多少個元素，因為會有hash沖突保存到數組同一個位置這樣就形成鏈表

DictEntry（hash節點）：就表示一個鏈表數據結構

---

當我們向dict添加鍵值對時，redis首先根據key計算出hash值（h),然后利用h&sizemask(按位與)來計算元素應該存儲到數組中的哪個索引位置。我們存儲k1=v1,假設k1的哈希值h =1,則1&3=1,因此k1=v1要存儲到數組角標1位置。

3.2.Dict擴容?

Dict中的HashTable就是數組結合單向鏈表的實現，當集合中元素較多時，必然導致哈希沖突增多，鏈表過長，則查詢，效率會大大降低。
Dict在每次新增鏈值對時都會檢查負載因子 (LoadFactor=used/size),滿足以下兩種情況時會觸發哈希表擴容：

• 哈希表的LoadFactor>=1,并且服務器沒有執行bgsave 或者bgrewriteaof等后臺進程；(因為這些后臺進程對cpu使用非常高而且大量io讀寫，這時擴容影響性能)
• 哈希表的LoadFactor>5;

底層源碼執行邏輯如下?

3.3Dict收縮

dict除了擴容以外，每次刪除元素時，也會對負載因子做檢查，當LoadFactor<0.1時，會做哈希表收縮；

實現邏輯如下

?3.4.Dict的rehash

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

實現步驟如下：

1.分配空間

• 擴展操作：為?ht[1]?分配空間，其大小是第一個大于等于?ht[0].used * 2?的 2 的冪。
• 收縮操作：為?ht[1]?分配空間，其大小是第一個大于等于?ht[0].used?的 2 的冪。
• 

2. 設置?rehashidx

把?dict?結構里的?rehashidx?設置為 0，這表明?rehash?操作正式開始。

3. 漸進式?rehash

Redis 采用漸進式?rehash?策略，避免一次性?rehash?大量鍵對服務器性能造成影響。具體步驟如下：

• 在?rehash?期間，每次對字典執行增、刪、查、改操作時，程序除了完成指定操作之外，還會順帶將?ht[0]?哈希表在?rehashidx?索引上的所有鍵值對?rehash?到?ht[1]，然后將?rehashidx?的值加 1。
• 此外，Redis 還會在定時任務里對字典進行?rehash?操作，每次處理一定數量的鍵值對。

4. 遷移完成

當?ht[0]?中的所有鍵值對都被?rehash?到?ht[1]?之后，釋放?ht[0]，將?ht[1]?設置為?ht[0]，并創建一個新的空白哈希表作為?ht[1]，同時將?rehashidx?設置為 -1，表明?rehash?操作結束。

---

4.ZipList

ziplist是一種特殊的"雙端鏈表",由一系列特殊編碼的連續內存塊組成。可以在任意一端進行壓入/彈出操作，并且"該操作的時間復雜度為0(1)。當列表或哈希元素數量較少且值較小時會采用這種結構。

4.1底層結構

4.1.1 ZipList

?4.1.2 Entry

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

previous_entry_length:前一節點的長度，占1個或5個字節。

• 如果前一節點的長度小于254字節，則采用1個字節來保存這個長度值
• 如果前一節點的長度大于254字書，則采用5個字節來保存這個長廢值，第一個字節為oxfe,后四個字節才是真實長度數據

encoding:編碼屬性，記錄contentent的數據類型（字符串還是整數）以及長度，占用1個，2個或5個字節

content:負責保存節點的數據，可以是字符串或整數

---

ZipList的Entry這樣設計不僅在節省內存空間的同時，保證數據的高效存儲和訪問，并且支持正向和反向遍歷等操作。

1.記錄前置節點長度（previous_entry_length）和當前節點長度（encoding）的字段，會根據實際長度動態調整。

2.反向遍歷：借助記錄前一個 Entry 的長度（previous_entry_length），能夠從后往前反向遍歷 ZipList。在某些場景下，反向遍歷是必要的，比如實現棧的操作時，就需要從后往前訪問元素。

4.2.Encoding編碼

ZipListEntry中的encoding編碼分為字符串和整數兩種

整數編碼：當?entry?存儲整數時，encoding?用 1 字節表示 。通過?encoding?可確定整數類型及實際大小

常見整數編碼如下：

• ZIP_INT_8B?：對應二進制?11111110?，表示 8 位整數，content（數據部分）占 1 字節?
• ZIP_INT_16B?：對應二進制?1100 0000?，表示 16 位整數，content?占 2 字節 。
• ZIP_INT_24B?：對應二進制?1111 0000?，表示 24 位整數，content?占 3 字節 。
• ZIP_INT_32B?：對應二進制?1110 0000?，表示 32 位整數，content?占 4 字節 。
• ZIP_INT_64B?：對應二進制?1101 0000?，表示 64 位整數，content?占 8 字節 。
• ZIP_INT_2C?：對應二進制?11111101?，表示 2 位有符號整數，實際取值范圍有限 。

字節數組（字符串）編碼：當?entry?存儲字符串時，根據字符串長度不同，encoding?有 3 種編碼方式，編碼的第一個字節前 2 位表示數據類型，后續位標識字符串實際長度：

總結：

1.判斷數據類型：encoding?第一個字節的前 2 位用于確定數據類型，二進制?11?開頭表示整數 ；非?11?開頭則是字節數組（字符串）。

2.解析字節數組長度：對于字節數組編碼，確定是字節數組類型后，根據前 2 位具體值判斷是哪種字符串編碼，再依據對應規則解析出字符串長度。

設計優勢

• 節省內存：根據數據實際類型和長度選擇合適編碼，避免固定長度存儲造成的內存浪費。如存儲小整數或短字符串時，使用較少字節數編碼。
• 快速解析：通過?encoding?編碼，可快速確定數據類型和長度，在讀取?entry?數據時提高解析效率 。

4.3.ZipList的連鎖更新問題

ZipList 的每個節點（Entry）包含一個記錄前一個節點長度的屬性?previous_entry_length?，該屬性占用 1 個或 5 個字節：

?

• 若前一節點長度小于 254 字節，用 1 字節保存長度值。
• 若前一節點長度大于等于 254 字節，用 5 字節保存長度值，第一個字節固定為?0xfe?，后 4 字節是真實長度數據。
• 

?

假設存在 N 個連續的、長度在 250 - 253 字節之間的 Entry ，此時每個 Entry 的?previous_entry_length?都僅需 1 字節表示。若在隊首插入一個 254 字節的數據：

?

1. 第二個 Entry 的?previous_entry_length?就得從 1 字節擴展為 5 字節 ，這使第二個 Entry 長度變為 254 字節。
2. 第二個 Entry 長度變化后，第三個 Entry 的?previous_entry_length?也需從 1 字節變為 5 字節 ，依此類推，后續所有 Entry 都會因前一個長度的改變而改變 。

?

這種特殊情況下產生的連續多次空間擴展操作，就是連鎖更新（Cascade Update） 。不僅插入操作，刪除操作也可能引發連鎖更新。比如刪除一個節點后，相鄰節點記錄的前置節點長度發生變化，若涉及長度從小于 254 字節變為大于等于 254 字節（或反之），就可能引發連鎖更新。

---

5.QuickList

ZipList雖然節省內存，但申請內存必須是連續空間，如果內存占用過多，申請內存效率很低。所以當我們要存儲大量數據，超出ZipList最佳上限那么可以創建多個ZipList來分片存儲數據。

Redis3.2版本引入了新的數據結構QuickList，它是一個雙端鏈表，只不過鏈表中的每個節點都是ZipList

1.為了避免QuickList中的每個ZipList中entry過多，Redis提供了一個配置項：list-max-ziplist-size來限制。

• 如果值為正，則代表ziplist的允許的entry個數的最大值
• 如果值為負，則代表ziplist的最大內存大小，分5種情況：

1:每個ziplist的內存占用不能超過4kb

-2:每個ziplist的內存占用不能超過8kb

-3:每個ziplist的內存占用不能超過16kb

-4:每個ziplist的內存占用不能超過32kb

-5:每個ziplist的內存占用不能超過64kb

其默認值為-2:

2.除了控制ziplist的大小，quicklist-comprest還可以對節點的ZipList做壓縮。通過配置項ist-compress-depth來控制。因為鏈表一般都是從首尾訪問較多，所以首尾是不壓縮的。這個參數是控制首尾不壓縮的節點個數：

• 0:特殊值，代表不壓縮
• 1:標示quicklist的首尾各有1個節點不壓縮，中間節點壓縮
• 2:標示quicklist的首尾各有2個節點不壓縮，中間節點壓縮

以此類推

默認值：

QuickList整體結構圖如下?

5.1總結

1. quickList是一個節點為ZipList的雙端鏈表
2. 節點采用ZipList，解決了傳統鏈表的內存占用問題
3. 控制了ZipList大小，解決連續內存空間申請效率問題
4. 中間節點可以壓縮，進一步節省了內存

---

6.SKipList

SkipList（跳表）是一種用于實現有序集合的數據結構。首先是鏈表，但與傳統鏈表相比有幾點差異：

• 元素按照升序排列存儲
• 節點可能包含多個指針，指針跨度不同。

6.1底層結構源碼

score:分值是用于排序的依據

ele:實際存儲的數據

backward:后退指針用于從尾向頭遍歷跳躍表

zskiplistLevel:層數組則用于實現多層索引結構，每個元素包含一個前進指針（forward）和跨度（span）。跨度表示從當前節點到下一個節點之間的元素數量

調表結構圖：

?6.2總結

1. 調表是一個雙向鏈表，每個節點都包含score和ele值
2. 節點按照score值排序，score值一樣按照ele字典排序
3. 每個節點都可以包含多層指針，層數是1到32之間的隨機數
4. 不同層指針到下一個節點的跨度不同，層級越高，跨度越大
5. 增刪改查效率與紅黑樹基本一致，實現卻更簡單

---

7.RedisObject

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

RedisObject是 Redis 實現多數據類型支持的關鍵結構。借助?type?和?encoding?字段，Redis 能夠靈活存儲和處理不同類型的數據，同時利用引用計數和 LRU/LFU 機制管理內存。

7.1.Redis的編碼方式

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

String，List，Set，Zset，Hash每一種數據類型對應幾種不同編碼：