深入探討Redis數據結構
1. Redis數據結構-動態字符串
Redis中保存的Key是字符串，value是字符串或者字符串的集合。可見字符串是Redis中最常用的一種數據結構。
Redis沒有直接使用C語言中的字符串，因為C語言字符串存在很多問題：
- 獲取字符串長度的需要通過運算
- 非二進制安全
- 不可修改Redis構建了一種新的字符串結構，稱為簡單動態字符串（Simple Dynamic String），簡稱SDS。例如，我們執行命令：
圖片
那么Redis將在底層創建兩個SDS，其中一個是包含“name”的SDS，另一個是包含“虎哥”的SDS。
Redis是C語言實現的，其中SDS是一個結構體，源碼如下：
圖片
例如，一個包含字符串“name”的sds結構如下：
圖片
SDS之所以叫做動態字符串，是因為它具備動態擴容的能力，例如一個內容為“hi”的SDS：
圖片
假如我們要給SDS追加一段字符串“,Amy”，這里首先會申請新內存空間：
- 如果新字符串小于1M，則新空間為擴展后字符串長度的兩倍+1；
- 如果新字符串大于1M，則新空間為擴展后字符串長度+1M+1。稱為內存預分配。
圖片
2. Redis數據結構-intset
IntSet是Redis中set集合的一種實現方式，基于整數數組來實現，并且具備長度可變、有序等特征。結構如下：
圖片
其中的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中的元素唯一、有序
- 具備類型升級機制，可以節省內存空間
- 底層采用二分查找方式來查詢
1.3. Redis數據結構-Dict
我們知道Redis是一個鍵值型（Key-Value Pair）的數據庫，我們可以根據鍵實現快速的增刪改查。而鍵與值的映射關系正是通過Dict來實現的
Dict由三部分組成:
- 哈希表（DictHashTable）
- 哈希節點（DictEntry）
- 字典（Dict）
圖片
當我們向Dict添加鍵值對時，Redis首先根據key計算出hash值（h），然后利用 h & sizemask來計算元素應該存儲到數組中的哪個索引位置。我們存儲k1=v1，假設k1的哈希值h =1，則1&3 =1，因此k1=v1要存儲到數組角標1位置。
圖片
Dict由三部分組成，分別是：哈希表（DictHashTable）、哈希節點（DictEntry）、字典（Dict）
圖片
圖片
Dict的擴容
Dict中的HashTable就是數組結合單向鏈表的實現，當集合中元素較多時，必然導致哈希沖突增多，鏈表過長，則查詢效率會大大降低。Dict在每次新增鍵值對時都會檢查負載因子（LoadFactor = used/size） ，滿足以下兩種情況時會觸發哈希表擴容：
- 哈希表的 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最終為空
整個過程可以描述成：
圖片
小總結：
Dict的結構：
- 類似java的HashTable，底層是數組加鏈表來解決哈希沖突
- Dict包含兩個哈希表，ht[0]平常用，ht[1]用來rehash
Dict的伸縮：
- 當LoadFactor大于5或者LoadFactor大于1并且沒有子進程任務時，Dict擴容
- 當LoadFactor小于0.1時，Dict收縮
- 擴容大小為第一個大于等于used + 1的2^n
- 收縮大小為第一個大于等于used 的2^n
- Dict采用漸進式rehash，每次訪問Dict時執行一次rehash
- rehash時ht[0]只減不增，新增操作只在ht[1]執行，其它操作在兩個哈希表
4. Redis數據結構-ZipList
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是字符串
編碼 | 編碼長度 | 字符串大小 |
|00pppppp| | 1 bytes | <= 63 bytes |
|01pppppp|qqqqqqqq| | 2 bytes | <= 16383 bytes |
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| | 5 bytes | <= 4294967295 bytes |
例如，我們要保存字符串：“ab”和 “bc”
圖片
ZipListEntry中的encoding編碼分為字符串和整數兩種：
- 整數：如果encoding是以“11”開始，則證明content是整數，且encoding固定只占用1個字節
編碼 | 編碼長度 | 整數類型 |
11000000 | 1 | int16_t（2 bytes） |
11010000 | 1 | int32_t（4 bytes） |
11100000 | 1 | int64_t（8 bytes） |
11110000 | 1 | 24位有符整數(3 bytes) |
11111110 | 1 | 8位有符整數(1 bytes) |
1111xxxx | 1 | 直接在xxxx位置保存數值，范圍從0001~1101，減1后結果為實際值 |
圖片
圖片
5. Redis數據結構-ZipList的連鎖更新問題
ZipList的每個Entry都包含previous_entry_length來記錄上一個節點的大小，長度是1個或5個字節：如果前一節點的長度小于254字節，則采用1個字節來保存這個長度值 如果前一節點的長度大于等于254字節，則采用5個字節來保存這個長度值，第一個字節為0xfe，后四個字節才是真實長度數據 現在，假設我們有N個連續的、長度為250~253字節之間的entry，因此entry的previous_entry_length屬性用1個字節即可表示，如圖所示：
圖片
ZipList這種特殊情況下產生的連續多次空間擴展操作稱之為連鎖更新（Cascade Update）。新增、刪除都可能導致連鎖更新的發生。
小總結：
ZipList特性：
- 壓縮列表的可以看做一種連續內存空間的"雙向鏈表"
- 列表的節點之間不是通過指針連接，而是記錄上一節點和本節點長度來尋址，內存占用較低
- 如果列表數據過多，導致鏈表過長，可能影響查詢性能
- 增或刪較大數據時有可能發生連續更新問題
6. Redis數據結構-QuickList
問題1：ZipList雖然節省內存，但申請內存必須是連續空間，如果內存占用較多，申請內存效率很低。怎么辦？
答：為了緩解這個問題，我們必須限制ZipList的長度和entry大小。
問題2：但是我們要存儲大量數據，超出了ZipList最佳的上限該怎么辦？
答：我們可以創建多個ZipList來分片存儲數據。
問題3：數據拆分后比較分散，不方便管理和查找，這多個ZipList如何建立聯系？
答：Redis在3.2版本引入了新的數據結構QuickList，它是一個雙端鏈表，只不過鏈表中的每個節點都是一個ZipList。
圖片
為了避免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：
圖片
以下是QuickList的和QuickListNode的結構源碼：
圖片
我們接下來用一段流程圖來描述當前的這個結構
圖片
總結：
QuickList的特點：
- 是一個節點為ZipList的雙端鏈表
- 節點采用ZipList，解決了傳統鏈表的內存占用問題
- 控制了ZipList大小，解決連續內存空間申請效率問題
- 中間節點可以壓縮，進一步節省了內存
7. Redis數據結構-SkipList
SkipList（跳表）首先是鏈表，但與傳統鏈表相比有幾點差異：
- 元素按照升序排列存儲
- 節點可能包含多個指針，指針跨度不同。
圖片
SkipList（跳表）首先是鏈表，但與傳統鏈表相比有幾點差異：元素按照升序排列存儲 節點可能包含多個指針，指針跨度不同。
圖片
SkipList（跳表）首先是鏈表，但與傳統鏈表相比有幾點差異：元素按照升序排列存儲 節點可能包含多個指針，指針跨度不同。
圖片
小總結：
SkipList的特點：
- 跳躍表是一個雙向鏈表，每個節點都包含score和ele值
- 節點按照score值排序，score值一樣則按照ele字典排序
- 每個節點都可以包含多層指針，層數是1到32之間的隨機數
- 不同層指針到下一個節點的跨度不同，層級越高，跨度越大
- 增刪改查效率與紅黑樹基本一致，實現卻更簡單
8. Redis數據結構-RedisObject
Redis中的任意數據類型的鍵和值都會被封裝為一個RedisObject，也叫做Redis對象，源碼如下：
1、什么是redisObject：從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 |
9. Redis數據結構-String
String是Redis中最常見的數據存儲類型：
其基本編碼方式是RAW，基于簡單動態字符串（SDS）實現，存儲上限為512mb。
如果存儲的SDS長度小于44字節，則會采用EMBSTR編碼，此時object head與SDS是一段連續空間。申請內存時
只需要調用一次內存分配函數，效率更高。
- 底層實現?式：動態字符串sds 或者 long
String的內部存儲結構?般是sds（Simple Dynamic String，可以動態擴展內存），但是如果?個String類型的value的值是數字，那么Redis內部會把它轉成long類型來存儲，從?減少內存的使用。
圖片
如果存儲的字符串是整數值，并且大小在LONG_MAX范圍內，則會采用INT編碼：直接將數據保存在RedisObject的ptr指針位置（剛好8字節），不再需要SDS了
圖片
圖片
圖片
確切地說，String在Redis中是??個robj來表示
用來表示String的robj可能編碼成3種內部表?：
- OBJ_ENCODING_RAW
- OBJ_ENCODING_EMBSTR
- OBJ_ENCODING_INT
其中前兩種編碼使?的是sds來存儲，最后?種OBJ_ENCODING_INT編碼直接把string存成了long型。在對string進行incr, decr等操作的時候，如果它內部是OBJ_ENCODING_INT編碼，那么可以直接行加減操作；如果它內部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR編碼，那么Redis會先試圖把sds存儲的字符串轉成long型，如果能轉成功，再進行加減操作。對?個內部表示成long型的string執行append, setbit, getrange這些命令，針對的仍然是string的值（即?進制表示的字符串），而不是針對內部表?的long型進?操作。比如字符串”32”，如果按照字符數組來解釋，它包含兩個字符，它們的ASCII碼分別是0x33和0x32。當我們執行命令setbit key 7 0的時候，相當于把字符0x33變成了0x32，這樣字符串的值就變成了”22”。?如果將字符串”32”按照內部的64位long型來解釋，那么它是0x0000000000000020，在這個基礎上執?setbit位操作，結果就完全不對了。因此，在這些命令的實現中，會把long型先轉成字符串再進行相應的操作。
10. Redis數據結構-List
Redis的List類型可以從首、尾操作列表中的元素：
圖片
哪一個數據結構能滿足上述特征？
- LinkedList ：普通鏈表，可以從雙端訪問，內存占用較高，內存碎片較多
- ZipList ：壓縮列表，可以從雙端訪問，內存占用低，存儲上限低
- QuickList：LinkedList + ZipList，可以從雙端訪問，內存占用較低，包含多個ZipList，存儲上限高
Redis的List結構類似一個雙端鏈表，可以從首、尾操作列表中的元素：
在3.2版本之前，Redis采用ZipList和LinkedList來實現List，當元素數量小于512并且元素大小小于64字節時采用ZipList編碼，超過則采用LinkedList編碼。
在3.2版本之后，Redis統一采用QuickList來實現List：
圖片
10.1 Redis數據結構-Set結構
Set是Redis中的單列集合，滿足下列特點：
- 不保證有序性
- 保證元素唯一
- 求交集、并集、差集
圖片
可以看出，Set對查詢元素的效率要求非常高
思考一下，什么樣的數據結構可以滿足？
HashTable，也就是Redis中的Dict，不過Dict是雙列集合（可以存鍵、值對）
Set是Redis中的集合，不一定確保元素有序，可以滿足元素唯一、查詢效率要求極高。為了查詢效率和唯一性，set采用HT編碼（Dict）。Dict中的key用來存儲元素，value統一為null。當存儲的所有數據都是整數，并且元素數量不超過set-max-intset-entries時，Set會采用IntSet編碼，以節省內存
圖片
結構如下：
圖片
10.2 Redis數據結構-ZSET
ZSet也就是SortedSet，其中每一個元素都需要指定一個score值和member值：
- 可以根據score值排序后
- member必須唯一
- 可以根據member查詢分數
圖片
因此，zset底層數據結構必須滿足鍵值存儲、鍵必須唯一、可排序這幾個需求。之前學習的哪種編碼結構可以滿足？
- SkipList：可以排序，并且可以同時存儲score和ele值（member）
- HT（Dict）：可以鍵值存儲，并且可以根據key找value
圖片
圖片
當元素數量不多時，HT和SkipList的優勢不明顯，而且更耗內存。因此zset還會采用ZipList結構來節省內存，不過需要同時滿足兩個條件：
- 元素數量小于zset_max_ziplist_entries，默認值128
- 每個元素都小于zset_max_ziplist_value字節，默認值64
ziplist本身沒有排序功能，而且沒有鍵值對的概念，因此需要有zset通過編碼實現：
- ZipList是連續內存，因此score和element是緊挨在一起的兩個entry， element在前，score在后
- score越小越接近隊首，score越大越接近隊尾，按照score值升序排列
圖片
圖片
10.3. Redis數據結構-Hash
Hash結構與Redis中的Zset非常類似：
- 都是鍵值存儲
- 都需求根據鍵獲取值
- 鍵必須唯一
區別如下：
- zset的鍵是member，值是score；hash的鍵和值都是任意值
- zset要根據score排序；hash則無需排序
（1）底層實現方式：壓縮列表ziplist 或者 字典dict 當Hash中數據項比較少的情況下，Hash底層才?壓縮列表ziplist進?存儲數據，隨著數據的增加，底層的ziplist就可能會轉成dict，具體配置如下：
- hash-max-ziplist-entries 512
- hash-max-ziplist-value 64
當滿足上面兩個條件其中之?的時候，Redis就使?dict字典來實現hash。Redis的hash之所以這樣設計，是因為當ziplist變得很?的時候，它有如下幾個缺點：
- 每次插?或修改引發的realloc操作會有更?的概率造成內存拷貝，從而降低性能。
- ?旦發生內存拷貝，內存拷貝的成本也相應增加，因為要拷貝更?的?塊數據。
- 當ziplist數據項過多的時候，在它上?查找指定的數據項就會性能變得很低，因為ziplist上的查找需要進行遍歷。
總之，ziplist本來就設計為各個數據項挨在?起組成連續的內存空間，這種結構并不擅長做修改操作。?旦數據發?改動，就會引發內存realloc，可能導致內存拷貝。
hash結構如下：
圖片
zset集合如下：
圖片
因此，Hash底層采用的編碼與Zset也基本一致，只需要把排序有關的SkipList去掉即可：
Hash結構默認采用ZipList編碼，用以節省內存。ZipList中相鄰的兩個entry 分別保存field和value
當數據量較大時，Hash結構會轉為HT編碼，也就是Dict，觸發條件有兩個：
- ZipList中的元素數量超過了hash-max-ziplist-entries（默認512）
- ZipList中的任意entry大小超過了hash-max-ziplist-value（默認64字節）
圖片
