1. Redis數(shù)據(jù)結(jié)構(gòu)-動態(tài)字符串

Redis中保存的Key是字符串，value是字符串或者字符串的集合。可見字符串是Redis中最常用的一種數(shù)據(jù)結(jié)構(gòu)。

Redis沒有直接使用C語言中的字符串，因為C語言字符串存在很多問題：

• 獲取字符串長度的需要通過運算
• 非二進制安全
• 不可修改Redis構(gòu)建了一種新的字符串結(jié)構(gòu)，稱為簡單動態(tài)字符串（Simple Dynamic String），簡稱SDS。例如，我們執(zhí)行命令：

圖片

那么Redis將在底層創(chuàng)建兩個SDS，其中一個是包含“name”的SDS，另一個是包含“虎哥”的SDS。

Redis是C語言實現(xiàn)的，其中SDS是一個結(jié)構(gòu)體，源碼如下：

圖片

例如，一個包含字符串“name”的sds結(jié)構(gòu)如下：

圖片

SDS之所以叫做動態(tài)字符串，是因為它具備動態(tài)擴容的能力，例如一個內(nèi)容為“hi”的SDS：

圖片

假如我們要給SDS追加一段字符串“,Amy”，這里首先會申請新內(nèi)存空間：

• 如果新字符串小于1M，則新空間為擴展后字符串長度的兩倍+1；
• 如果新字符串大于1M，則新空間為擴展后字符串長度+1M+1。稱為內(nèi)存預(yù)分配。

圖片

2. Redis數(shù)據(jù)結(jié)構(gòu)-intset

IntSet是Redis中set集合的一種實現(xiàn)方式，基于整數(shù)數(shù)組來實現(xiàn)，并且具備長度可變、有序等特征。結(jié)構(gòu)如下：

圖片

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

圖片

為了方便查找，Redis會將intset中所有的整數(shù)按照升序依次保存在contents數(shù)組中，結(jié)構(gòu)如圖：

圖片

現(xiàn)在，數(shù)組中每個數(shù)字都在int16_t的范圍內(nèi)，因此采用的編碼方式是INTSET_ENC_INT16，每部分占用的字節(jié)大小為：encoding：4字節(jié) length：4字節(jié) contents：2字節(jié) * 3  = 6字節(jié)

圖片

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

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

圖片

源碼如下：

圖片

圖片

小總結(jié)：

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

• Redis會確保Intset中的元素唯一、有序
• 具備類型升級機制，可以節(jié)省內(nèi)存空間
• 底層采用二分查找方式來查詢

1.3. Redis數(shù)據(jù)結(jié)構(gòu)-Dict

我們知道Redis是一個鍵值型（Key-Value Pair）的數(shù)據(jù)庫，我們可以根據(jù)鍵實現(xiàn)快速的增刪改查。而鍵與值的映射關(guān)系正是通過Dict來實現(xiàn)的

Dict由三部分組成:

• 哈希表（DictHashTable）
• 哈希節(jié)點（DictEntry）
• 字典（Dict）

圖片

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

圖片

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

圖片

圖片

Dict的擴容

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

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

圖片

Dict的rehash

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

• 計算新hash表的realeSize，值取決于當前要做的是擴容還是收縮：

• 如果是擴容，則新size為第一個大于等于dict.ht[0].used + 1的2^n
• 如果是收縮，則新size為第一個大于等于dict.ht[0].used的2^n （不得小于4）

• 按照新的realeSize申請內(nèi)存空間，創(chuàng)建dictht，并賦值給dict.ht[1]
• 設(shè)置dict.rehashidx = 0，標示開始rehash
• 將dict.ht[0]中的每一個dictEntry都rehash到dict.ht[1]
• 將dict.ht[1]賦值給dict.ht[0]，給dict.ht[1]初始化為空哈希表，釋放原來的dict.ht[0]的內(nèi)存
• 將rehashidx賦值為-1，代表rehash結(jié)束
• 在rehash過程中，新增操作，則直接寫入ht[1]，查詢、修改和刪除則會在dict.ht[0]和dict.ht[1]依次查找并執(zhí)行。這樣可以確保ht[0]的數(shù)據(jù)只減不增，隨著rehash最終為空

整個過程可以描述成：

圖片

小總結(jié)：

Dict的結(jié)構(gòu)：

• 類似java的HashTable，底層是數(shù)組加鏈表來解決哈希沖突
• Dict包含兩個哈希表，ht[0]平常用，ht[1]用來rehash

Dict的伸縮：

• 當LoadFactor大于5或者LoadFactor大于1并且沒有子進程任務(wù)時，Dict擴容
• 當LoadFactor小于0.1時，Dict收縮
• 擴容大小為第一個大于等于used + 1的2^n
• 收縮大小為第一個大于等于used 的2^n
• Dict采用漸進式rehash，每次訪問Dict時執(zhí)行一次rehash
• rehash時ht[0]只減不增，新增操作只在ht[1]執(zhí)行，其它操作在兩個哈希表

4. Redis數(shù)據(jù)結(jié)構(gòu)-ZipList

ZipList 是一種特殊的“雙端鏈表” ，由一系列特殊編碼的連續(xù)內(nèi)存塊組成?？梢栽谌我庖欢诉M行壓入/彈出操作, 并且該操作的時間復(fù)雜度為 O(1)。

圖片

圖片

ZipListEntry

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

圖片

• previous_entry_length：前一節(jié)點的長度，占1個或5個字節(jié)。

• 如果前一節(jié)點的長度小于254字節(jié)，則采用1個字節(jié)來保存這個長度值
• 如果前一節(jié)點的長度大于254字節(jié)，則采用5個字節(jié)來保存這個長度值，第一個字節(jié)為0xfe，后四個字節(jié)才是真實長度數(shù)據(jù)

• encoding：編碼屬性，記錄content的數(shù)據(jù)類型（字符串還是整數(shù)）以及長度，占用1個、2個或5個字節(jié)
• contents：負責保存節(jié)點的數(shù)據(jù)，可以是字符串或整數(shù)

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

Encoding編碼

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

例如，我們要保存字符串：“ab”和 “bc”

圖片

ZipListEntry中的encoding編碼分為字符串和整數(shù)兩種：

• 整數(shù)：如果encoding是以“11”開始，則證明content是整數(shù)，且encoding固定只占用1個字節(jié)

圖片

圖片

5. Redis數(shù)據(jù)結(jié)構(gòu)-ZipList的連鎖更新問題

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

圖片

ZipList這種特殊情況下產(chǎn)生的連續(xù)多次空間擴展操作稱之為連鎖更新（Cascade Update）。新增、刪除都可能導(dǎo)致連鎖更新的發(fā)生。

小總結(jié)：

ZipList特性：

• 壓縮列表的可以看做一種連續(xù)內(nèi)存空間的"雙向鏈表"
• 列表的節(jié)點之間不是通過指針連接，而是記錄上一節(jié)點和本節(jié)點長度來尋址，內(nèi)存占用較低
• 如果列表數(shù)據(jù)過多，導(dǎo)致鏈表過長，可能影響查詢性能
• 增或刪較大數(shù)據(jù)時有可能發(fā)生連續(xù)更新問題

6. Redis數(shù)據(jù)結(jié)構(gòu)-QuickList

問題1：ZipList雖然節(jié)省內(nèi)存，但申請內(nèi)存必須是連續(xù)空間，如果內(nèi)存占用較多，申請內(nèi)存效率很低。怎么辦？

答：為了緩解這個問題，我們必須限制ZipList的長度和entry大小。

問題2：但是我們要存儲大量數(shù)據(jù)，超出了ZipList最佳的上限該怎么辦？

答：我們可以創(chuàng)建多個ZipList來分片存儲數(shù)據(jù)。

問題3：數(shù)據(jù)拆分后比較分散，不方便管理和查找，這多個ZipList如何建立聯(lián)系？

答：Redis在3.2版本引入了新的數(shù)據(jù)結(jié)構(gòu)QuickList，它是一個雙端鏈表，只不過鏈表中的每個節(jié)點都是一個ZipList。

圖片

為了避免QuickList中的每個ZipList中entry過多，Redis提供了一個配置項：list-max-ziplist-size來限制。如果值為正，則代表ZipList的允許的entry個數(shù)的最大值 如果值為負，則代表ZipList的最大內(nèi)存大小，分5種情況：

• -1：每個ZipList的內(nèi)存占用不能超過4kb
• -2：每個ZipList的內(nèi)存占用不能超過8kb
• -3：每個ZipList的內(nèi)存占用不能超過16kb
• -4：每個ZipList的內(nèi)存占用不能超過32kb
• -5：每個ZipList的內(nèi)存占用不能超過64kb

其默認值為 -2：

圖片

以下是QuickList的和QuickListNode的結(jié)構(gòu)源碼：

圖片

我們接下來用一段流程圖來描述當前的這個結(jié)構(gòu)

圖片

總結(jié)：

QuickList的特點：

• 是一個節(jié)點為ZipList的雙端鏈表
• 節(jié)點采用ZipList，解決了傳統(tǒng)鏈表的內(nèi)存占用問題
• 控制了ZipList大小，解決連續(xù)內(nèi)存空間申請效率問題
• 中間節(jié)點可以壓縮，進一步節(jié)省了內(nèi)存

7. Redis數(shù)據(jù)結(jié)構(gòu)-SkipList

SkipList（跳表）首先是鏈表，但與傳統(tǒng)鏈表相比有幾點差異：

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

圖片

SkipList（跳表）首先是鏈表，但與傳統(tǒng)鏈表相比有幾點差異：元素按照升序排列存儲 節(jié)點可能包含多個指針，指針跨度不同。

圖片

SkipList（跳表）首先是鏈表，但與傳統(tǒng)鏈表相比有幾點差異：元素按照升序排列存儲 節(jié)點可能包含多個指針，指針跨度不同。

圖片

小總結(jié)：

SkipList的特點：

• 跳躍表是一個雙向鏈表，每個節(jié)點都包含score和ele值
• 節(jié)點按照score值排序，score值一樣則按照ele字典排序
• 每個節(jié)點都可以包含多層指針，層數(shù)是1到32之間的隨機數(shù)
• 不同層指針到下一個節(jié)點的跨度不同，層級越高，跨度越大
• 增刪改查效率與紅黑樹基本一致，實現(xiàn)卻更簡單

8. Redis數(shù)據(jù)結(jié)構(gòu)-RedisObject

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

1、什么是redisObject：從Redis的使用者的角度來看，?個Redis節(jié)點包含多個database（非cluster模式下默認是16個，cluster模式下只能是1個），而一個database維護了從key space到object space的映射關(guān)系。這個映射關(guān)系的key是string類型，?value可以是多種數(shù)據(jù)類型，比如：string, list, hash、set、sorted set等。我們可以看到，key的類型固定是string，而value可能的類型是多個。?從Redis內(nèi)部實現(xiàn)的?度來看，database內(nèi)的這個映射關(guān)系是用?個dict來維護的。dict的key固定用?種數(shù)據(jù)結(jié)構(gòu)來表達就夠了，這就是動態(tài)字符串sds。而value則比較復(fù)雜，為了在同?個dict內(nèi)能夠存儲不同類型的value，這就需要?個通?的數(shù)據(jù)結(jié)構(gòu)，這個通用的數(shù)據(jù)結(jié)構(gòu)就是robj，全名是redisObject。

圖片

Redis的編碼方式

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

五種數(shù)據(jù)結(jié)構(gòu)

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

9. Redis數(shù)據(jù)結(jié)構(gòu)-String

String是Redis中最常見的數(shù)據(jù)存儲類型：

其基本編碼方式是RAW，基于簡單動態(tài)字符串（SDS）實現(xiàn)，存儲上限為512mb。

如果存儲的SDS長度小于44字節(jié)，則會采用EMBSTR編碼，此時object head與SDS是一段連續(xù)空間。申請內(nèi)存時

只需要調(diào)用一次內(nèi)存分配函數(shù)，效率更高。

• 底層實現(xiàn)?式：動態(tài)字符串sds 或者 long

String的內(nèi)部存儲結(jié)構(gòu)?般是sds（Simple Dynamic String，可以動態(tài)擴展內(nèi)存），但是如果?個String類型的value的值是數(shù)字，那么Redis內(nèi)部會把它轉(zhuǎn)成long類型來存儲，從?減少內(nèi)存的使用。

圖片

如果存儲的字符串是整數(shù)值，并且大小在LONG_MAX范圍內(nèi)，則會采用INT編碼：直接將數(shù)據(jù)保存在RedisObject的ptr指針位置（剛好8字節(jié)），不再需要SDS了

圖片

圖片

圖片

確切地說，String在Redis中是??個robj來表示

用來表示String的robj可能編碼成3種內(nèi)部表?：

• OBJ_ENCODING_RAW
• OBJ_ENCODING_EMBSTR
• OBJ_ENCODING_INT

其中前兩種編碼使?的是sds來存儲，最后?種OBJ_ENCODING_INT編碼直接把string存成了long型。在對string進行incr, decr等操作的時候，如果它內(nèi)部是OBJ_ENCODING_INT編碼，那么可以直接行加減操作；如果它內(nèi)部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR編碼，那么Redis會先試圖把sds存儲的字符串轉(zhuǎn)成long型，如果能轉(zhuǎn)成功，再進行加減操作。對?個內(nèi)部表示成long型的string執(zhí)行append, setbit, getrange這些命令，針對的仍然是string的值（即?進制表示的字符串），而不是針對內(nèi)部表?的long型進?操作。比如字符串”32”，如果按照字符數(shù)組來解釋，它包含兩個字符，它們的ASCII碼分別是0x33和0x32。當我們執(zhí)行命令setbit key 7 0的時候，相當于把字符0x33變成了0x32，這樣字符串的值就變成了”22”。?如果將字符串”32”按照內(nèi)部的64位long型來解釋，那么它是0x0000000000000020，在這個基礎(chǔ)上執(zhí)?setbit位操作，結(jié)果就完全不對了。因此，在這些命令的實現(xiàn)中，會把long型先轉(zhuǎn)成字符串再進行相應(yīng)的操作。

10. Redis數(shù)據(jù)結(jié)構(gòu)-List

Redis的List類型可以從首、尾操作列表中的元素：

圖片

哪一個數(shù)據(jù)結(jié)構(gòu)能滿足上述特征？

• LinkedList ：普通鏈表，可以從雙端訪問，內(nèi)存占用較高，內(nèi)存碎片較多
• ZipList ：壓縮列表，可以從雙端訪問，內(nèi)存占用低，存儲上限低
• QuickList：LinkedList + ZipList，可以從雙端訪問，內(nèi)存占用較低，包含多個ZipList，存儲上限高

Redis的List結(jié)構(gòu)類似一個雙端鏈表，可以從首、尾操作列表中的元素：

在3.2版本之前，Redis采用ZipList和LinkedList來實現(xiàn)List，當元素數(shù)量小于512并且元素大小小于64字節(jié)時采用ZipList編碼，超過則采用LinkedList編碼。

在3.2版本之后，Redis統(tǒng)一采用QuickList來實現(xiàn)List：

圖片

10.1 Redis數(shù)據(jù)結(jié)構(gòu)-Set結(jié)構(gòu)

Set是Redis中的單列集合，滿足下列特點：

• 不保證有序性
• 保證元素唯一
• 求交集、并集、差集

圖片

可以看出，Set對查詢元素的效率要求非常高

思考一下，什么樣的數(shù)據(jù)結(jié)構(gòu)可以滿足？

HashTable，也就是Redis中的Dict，不過Dict是雙列集合（可以存鍵、值對）

Set是Redis中的集合，不一定確保元素有序，可以滿足元素唯一、查詢效率要求極高。為了查詢效率和唯一性，set采用HT編碼（Dict）。Dict中的key用來存儲元素，value統(tǒng)一為null。當存儲的所有數(shù)據(jù)都是整數(shù)，并且元素數(shù)量不超過set-max-intset-entries時，Set會采用IntSet編碼，以節(jié)省內(nèi)存

圖片

結(jié)構(gòu)如下：

圖片

10.2 Redis數(shù)據(jù)結(jié)構(gòu)-ZSET

ZSet也就是SortedSet，其中每一個元素都需要指定一個score值和member值：

• 可以根據(jù)score值排序后
• member必須唯一
• 可以根據(jù)member查詢分數(shù)

圖片

因此，zset底層數(shù)據(jù)結(jié)構(gòu)必須滿足鍵值存儲、鍵必須唯一、可排序這幾個需求。之前學(xué)習的哪種編碼結(jié)構(gòu)可以滿足？

• SkipList：可以排序，并且可以同時存儲score和ele值（member）
• HT（Dict）：可以鍵值存儲，并且可以根據(jù)key找value

圖片

圖片

當元素數(shù)量不多時，HT和SkipList的優(yōu)勢不明顯，而且更耗內(nèi)存。因此zset還會采用ZipList結(jié)構(gòu)來節(jié)省內(nèi)存，不過需要同時滿足兩個條件：

• 元素數(shù)量小于zset_max_ziplist_entries，默認值128
• 每個元素都小于zset_max_ziplist_value字節(jié)，默認值64

ziplist本身沒有排序功能，而且沒有鍵值對的概念，因此需要有zset通過編碼實現(xiàn)：

• ZipList是連續(xù)內(nèi)存，因此score和element是緊挨在一起的兩個entry， element在前，score在后
• score越小越接近隊首，score越大越接近隊尾，按照score值升序排列

圖片

圖片

10.3. Redis數(shù)據(jù)結(jié)構(gòu)-Hash

Hash結(jié)構(gòu)與Redis中的Zset非常類似：

• 都是鍵值存儲
• 都需求根據(jù)鍵獲取值
• 鍵必須唯一

區(qū)別如下：

• zset的鍵是member，值是score；hash的鍵和值都是任意值
• zset要根據(jù)score排序；hash則無需排序

（1）底層實現(xiàn)方式：壓縮列表ziplist 或者 字典dict 當Hash中數(shù)據(jù)項比較少的情況下，Hash底層才?壓縮列表ziplist進?存儲數(shù)據(jù)，隨著數(shù)據(jù)的增加，底層的ziplist就可能會轉(zhuǎn)成dict，具體配置如下：

• hash-max-ziplist-entries 512
• hash-max-ziplist-value 64

當滿足上面兩個條件其中之?的時候，Redis就使?dict字典來實現(xiàn)hash。Redis的hash之所以這樣設(shè)計，是因為當ziplist變得很?的時候，它有如下幾個缺點：

• 每次插?或修改引發(fā)的realloc操作會有更?的概率造成內(nèi)存拷貝，從而降低性能。
• ?旦發(fā)生內(nèi)存拷貝，內(nèi)存拷貝的成本也相應(yīng)增加，因為要拷貝更?的?塊數(shù)據(jù)。
• 當ziplist數(shù)據(jù)項過多的時候，在它上?查找指定的數(shù)據(jù)項就會性能變得很低，因為ziplist上的查找需要進行遍歷。

總之，ziplist本來就設(shè)計為各個數(shù)據(jù)項挨在?起組成連續(xù)的內(nèi)存空間，這種結(jié)構(gòu)并不擅長做修改操作。?旦數(shù)據(jù)發(fā)?改動，就會引發(fā)內(nèi)存realloc，可能導(dǎo)致內(nèi)存拷貝。

hash結(jié)構(gòu)如下：

圖片

zset集合如下：

圖片

因此，Hash底層采用的編碼與Zset也基本一致，只需要把排序有關(guān)的SkipList去掉即可：

Hash結(jié)構(gòu)默認采用ZipList編碼，用以節(jié)省內(nèi)存。ZipList中相鄰的兩個entry 分別保存field和value

當數(shù)據(jù)量較大時，Hash結(jié)構(gòu)會轉(zhuǎn)為HT編碼，也就是Dict，觸發(fā)條件有兩個：

• ZipList中的元素數(shù)量超過了hash-max-ziplist-entries（默認512）
• ZipList中的任意entry大小超過了hash-max-ziplist-value（默認64字節(jié)）

圖片