此前我們學(xué)習(xí)了常見(jiàn)的Reids數(shù)據(jù)類型，這些數(shù)據(jù)類型都需要底層的數(shù)據(jù)結(jié)構(gòu)的支持，現(xiàn)在我們來(lái)看看Redis常見(jiàn)的底層數(shù)據(jù)結(jié)構(gòu)：dict、ziplist、quicklist。

1 Redis dict

dict就是“字典”的意思，它是Redis中的一種使用的非常多的底層的數(shù)據(jù)結(jié)構(gòu)，除了hash會(huì)使用字段之外，整個(gè) Redis 數(shù)據(jù)庫(kù)的所有 key 和 value 也組成了一個(gè)全局字典dict，還有帶過(guò)期時(shí)間的 key 也是一個(gè)字典expires(存儲(chǔ)在 RedisDb 數(shù)據(jù)結(jié)構(gòu)中)。

Redis 中的字典相當(dāng)于 JDK1.7中的 HashMap，內(nèi)部實(shí)現(xiàn)也差不多類似，都是通過(guò) “數(shù)組 + 鏈表” 的鏈地址法來(lái)解決部分哈希沖突，同時(shí)這樣的結(jié)構(gòu)也吸收了兩種不同數(shù)據(jù)結(jié)構(gòu)的優(yōu)點(diǎn)。

和JDK1.7中的hashmap不同的是，Reids的字典結(jié)構(gòu)內(nèi)部包含兩個(gè)hashtable變量，通常情況下只有一個(gè)hashtable有值，另一個(gè)為空表，但是在字典擴(kuò)容縮容時(shí)，需要分配新的hashtable，并且使用了一種叫做漸進(jìn)式搬遷(rehash)的機(jī)制來(lái)提高dict的縮放效率，這時(shí)候兩個(gè)hashtable分別存儲(chǔ)舊的和新的 hashtable，待搬遷結(jié)束后，舊的將被刪除，新的 hashtable 取而代之。

1.1 擴(kuò)縮容的條件

正常情況下，當(dāng) hash 表中元素的個(gè)數(shù)等于數(shù)組的長(zhǎng)度時(shí)，就會(huì)開(kāi)始擴(kuò)容，擴(kuò)容的新數(shù)組是原數(shù)組大小的2倍。不過(guò)如果 Redis 正在做 BGSAVE或者BGREWRITEAOF(持久化)，為了減少內(nèi)存占用，Redis 盡量不去擴(kuò)容，但是如果 hash 表非常滿了，達(dá)到了數(shù)組長(zhǎng)度的 5 倍了，這個(gè)時(shí)候就會(huì)強(qiáng)制擴(kuò)容。

當(dāng) hash 表因?yàn)樵刂饾u被刪除變得越來(lái)越稀疏時(shí)，Redis 會(huì)對(duì) hash 表進(jìn)行縮容來(lái)減少hash表的第一維數(shù)組空間占用。所用的條件是：元素個(gè)數(shù)低于數(shù)組長(zhǎng)度的10%，縮容不會(huì)考慮 Redis 是否在做 bgsave。

1.2 漸進(jìn)式rehash操作

在擴(kuò)容和收縮的時(shí)候，如果哈希字典中有很多元素，一次性將這些鍵從ht0（正在使用的hashtable）全部rehash到ht1（另一個(gè)空的hashtable）的話，由于Redis是單線程模型，那么可能會(huì)導(dǎo)致服務(wù)器在一段時(shí)間內(nèi)停止服務(wù)。所以，采用漸進(jìn)式rehash的方式，數(shù)據(jù)的遷移并不是一步完成的，因此dict內(nèi)部還有一個(gè)rehashidx屬性用來(lái)控制rehash，默認(rèn)置為-1。

• 為ht[1]分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表。
• 將rehashindex的值設(shè)置為0，表示rehash工作正式開(kāi)始。
• 在rehash期間，每次對(duì)字典執(zhí)行增刪改查操作時(shí)，程序除了執(zhí)行指定的操作以外，還會(huì)順帶將ht[0]哈希表在rehashindex索引上的所有鍵值對(duì)rehash到ht[1]，當(dāng)一次rehash工作完成以后，rehashindex的值+1。
• 隨著字典操作的不斷執(zhí)行，最終會(huì)在某一時(shí)間段上ht[0]的所有鍵值對(duì)都會(huì)被rehash到ht[1]，將rehashindex的值設(shè)置為-1，表示rehash操作結(jié)束。
• 把ht[1]設(shè)置為ht[0]，并重新在ht[1]上新建一個(gè)空表，為下次rehash做準(zhǔn)備。

漸進(jìn)式rehash采用的是一種分而治之的方式，它以bucket(桶)為基本單位進(jìn)行漸進(jìn)式的數(shù)據(jù)遷移，每步完成一個(gè)bucket的遷移，直至所有數(shù)據(jù)遷移完畢。這種方式將rehash的操作分?jǐn)傇诿恳粋€(gè)的訪問(wèn)中，避免集中式rehash而帶來(lái)的龐大計(jì)算量。

在漸進(jìn)式rehash的過(guò)程中，如果有刪除、修改、查詢操作，則會(huì)在兩個(gè)哈希表ht[0]和ht[1]上進(jìn)行，先操作ht[0]，如果沒(méi)找到，再操作ht[1]，則新增的數(shù)據(jù)則會(huì)被保存在ht[1]中，ht[0]中包含的鍵值對(duì)數(shù)量會(huì)只減不增，并隨著 rehash 操作的執(zhí)行而最終變成空表。

2 Redis ziplist

ziplist又名壓縮列表，見(jiàn)其名知其意，這種數(shù)據(jù)結(jié)構(gòu)就比較節(jié)省內(nèi)存空間，Redis中對(duì)于list（3.2版本之前）、hash、zset類型的數(shù)據(jù)，如果元素較少，并且每個(gè)列表項(xiàng)要么就是小整數(shù)值，要么就是長(zhǎng)度比較短的字符串，那么Redis就會(huì)使用壓縮列表來(lái)存儲(chǔ)。

ziplist本身可以有序也可以無(wú)序。當(dāng)作為list（3.2版本之前）和hash的底層實(shí)現(xiàn)時(shí)，節(jié)點(diǎn)之間沒(méi)有順序；當(dāng)作為zset的底層實(shí)現(xiàn)時(shí)，節(jié)點(diǎn)之間會(huì)按照score大小順序排列，元素和score被分別存儲(chǔ)為兩個(gè)節(jié)點(diǎn)，元素在前，score在后。

ziplist的節(jié)省空間是相較于數(shù)組而言的，ziplist和數(shù)組一樣同樣采用一整塊連續(xù)的空間來(lái)存儲(chǔ)數(shù)據(jù)，數(shù)組在實(shí)際存儲(chǔ)時(shí)，每一個(gè)元素所占的實(shí)際大小是一樣的，并且是以最大的元素的大小為準(zhǔn)，這樣就能進(jìn)行快速的根據(jù)索引訪問(wèn)，而ziplist則允許每一個(gè)entry節(jié)點(diǎn)（對(duì)于數(shù)組中的元素）所占的實(shí)際大小不同，另外，節(jié)點(diǎn)之間沒(méi)有存儲(chǔ)前驅(qū)和后繼的指針，以此節(jié)約空間。

ziplist支持正序或者倒序的遍歷，往ziplist里插入一個(gè)entry 時(shí)間復(fù)雜度 平均:O(n),最壞:O(n²)，從ziplist里刪除一個(gè)entry 時(shí)間復(fù)雜度 平均:O(n), 最壞:O(n²)。最壞為O(n²)是因?yàn)镽edis連鎖更新導(dǎo)致的，但這種情況出現(xiàn)的概率不高。

ziplist和數(shù)組類似，刪除和添加節(jié)點(diǎn)都可能涉及到其他節(jié)點(diǎn)位置的移動(dòng)，因此只適用于元素?cái)?shù)據(jù)量較少，并且每個(gè)列表項(xiàng)要么就是小整數(shù)值，要么就是長(zhǎng)度比較短的字符串的情況。

2.1 ziplist結(jié)構(gòu)

Redis的ziplist采用一系列特殊編碼的連續(xù)內(nèi)存塊，一個(gè)壓縮列表出了在頭部包含一些整體信息之外，剩下的部分可以包含任意多個(gè)節(jié)點(diǎn)(entry)。

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

1. zlbytes：32位無(wú)符號(hào)整數(shù)，表示ziplist的整體長(zhǎng)度（字節(jié))。在對(duì)ziplist重新分配內(nèi)存或者計(jì)算zlend的位置時(shí)有用。
2. zltail：32位無(wú)符號(hào)整數(shù)，最后一個(gè)節(jié)點(diǎn)距離頭部的偏移量，通過(guò)該偏移量程序無(wú)需遍歷整個(gè)ziplist即可確定尾節(jié)點(diǎn)的地址，在反向遍歷ziplist或者pop尾部節(jié)點(diǎn)的時(shí)候很有用。
3. zllen：16位無(wú)符號(hào)整數(shù)，ziplist的節(jié)點(diǎn)（entry）個(gè)數(shù)。當(dāng)小于值小于65535時(shí)，該值時(shí)準(zhǔn)確的，等于65535（16位的最大值）時(shí)，需要遍歷整個(gè)鏈表才能得到真實(shí)節(jié)點(diǎn)數(shù)量。
4. entry：ziplist中的數(shù)據(jù)節(jié)點(diǎn)，長(zhǎng)度不固定，自己的長(zhǎng)度保存在每一個(gè)entry節(jié)點(diǎn)內(nèi)部。
5. zlend：8位無(wú)符號(hào)整數(shù)固定值為0xFF，用于標(biāo)記ziplist的結(jié)尾。

 2.2 entry結(jié)構(gòu)

ziplist的entry用于存儲(chǔ)正數(shù)或者字符串（字節(jié)數(shù)組），且每個(gè)節(jié)點(diǎn)的長(zhǎng)度都是不一樣的，因此節(jié)點(diǎn)的長(zhǎng)度只能由這個(gè)節(jié)點(diǎn)自己來(lái)保存，Redis的ziplist中，entry由三部分構(gòu)成：

• previous_entry_length：8bit或者40bit，用于記錄上一個(gè)節(jié)點(diǎn)的長(zhǎng)度（字節(jié)），為了方便反向遍歷ziplist。
• encoding：當(dāng)前節(jié)點(diǎn)數(shù)據(jù)的編碼規(guī)則，即data屬性的數(shù)據(jù)類型以及長(zhǎng)度。
• content：當(dāng)前節(jié)點(diǎn)的值，可以是數(shù)字或字符串（字節(jié)數(shù)組）。

previous_entry_length用于記錄上一個(gè)節(jié)點(diǎn)的長(zhǎng)度（字節(jié)），為了方便反向遍歷ziplist，其本身的長(zhǎng)度可能是8bit或者40bit。

1. 如果前一節(jié)點(diǎn)的長(zhǎng)度小于254字節(jié)，那么prevlengh屬性的長(zhǎng)度為1字節(jié)，前一節(jié)點(diǎn)的長(zhǎng)度就保存在這一個(gè)字節(jié)里面，這樣更加節(jié)約內(nèi)存。
2. 如果前一節(jié)點(diǎn)的長(zhǎng)度大于等于254字節(jié)，那么prevlengh屬性的總長(zhǎng)度為5字節(jié)，第一字節(jié)被固定設(shè)置為0xFE（十進(jìn)制值254），而之后的四個(gè)字節(jié)則用于保存前一節(jié)點(diǎn)的長(zhǎng)度。
3. 第二種情況下，第一個(gè)字節(jié)254而不用255（0xFF）是因?yàn)?55是zlend的值，它用于判斷ziplist是否到達(dá)尾部。

content表示當(dāng)前節(jié)點(diǎn)的值，可以是數(shù)字或字符串（字節(jié)數(shù)組），encoding 表示當(dāng)前節(jié)點(diǎn)數(shù)據(jù)的編碼規(guī)則，即data屬性的數(shù)據(jù)類型以及長(zhǎng)度，其中encoding其中高2位用來(lái)區(qū)分整數(shù)節(jié)點(diǎn)和字符串節(jié)點(diǎn)（高2位為11時(shí)是整數(shù)節(jié)點(diǎn)），根據(jù)值的類型不同，一共有九種編碼類型。

字節(jié)數(shù)組的encoding類型3種，encoding有8位、16位、40位三種長(zhǎng)度，context的長(zhǎng)度也是變化的：

整數(shù)值的encoding類型6種，固定長(zhǎng)度8位，高兩位固定11，表示整數(shù)，因此需要后兩位來(lái)表示不同的整數(shù)類型。整數(shù)類型的content的長(zhǎng)度雖然也是可變的，但固定范圍內(nèi)的整數(shù)長(zhǎng)度一樣，也就是說(shuō)content長(zhǎng)度只有固定的幾種。

3 Redis quicklist

Redis 的list在3.2版本之前在元素較少時(shí)實(shí)際上是采用ziplist結(jié)構(gòu)，當(dāng)鏈表entry數(shù)據(jù)超過(guò)512、或單個(gè)value 長(zhǎng)度超過(guò)64，底層就會(huì)轉(zhuǎn)化成linkedlist編碼，而Redis3.2及其之后則采用quicklist結(jié)構(gòu)代替ziplist和linkedlist。

ziplist存儲(chǔ)在一段連續(xù)的內(nèi)存上，所以存儲(chǔ)和查找效率很高，順序IO訪問(wèn)。但是，它不利于修改操作，插入和刪除操作需要頻繁的申請(qǐng)和釋放內(nèi)存。特別是當(dāng)ziplist長(zhǎng)度很長(zhǎng)的時(shí)候，一次realloc可能會(huì)導(dǎo)致大批量的數(shù)據(jù)拷貝，適用于存儲(chǔ)整數(shù)和短字符串。

雙向鏈表linkedlist便于在表的兩端進(jìn)行push和pop操作，在插入節(jié)點(diǎn)上復(fù)雜度很低，但是它的內(nèi)存開(kāi)銷比較大。首先，它在每個(gè)節(jié)點(diǎn)上除了要保存數(shù)據(jù)之外，還要額外保存兩個(gè)prev 和 next指針（64 位操作系統(tǒng)占用 8 個(gè)字節(jié)）；其次，雙向鏈表的各個(gè)節(jié)點(diǎn)是單獨(dú)的內(nèi)存塊，地址不連續(xù)，隨機(jī)IO訪問(wèn)，節(jié)點(diǎn)多了容易產(chǎn)生內(nèi)存碎片，影響內(nèi)存管理效率。

quickList將 linkedList 按段切分，每一段使用 zipList 來(lái)緊湊存儲(chǔ)，多個(gè) zipList 之間使用雙向指針串接起來(lái)。

首先quickList就是一個(gè)標(biāo)準(zhǔn)的雙向鏈表的配置，有head 和tail節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)是一個(gè)quicklistNode節(jié)點(diǎn)，包含prev和next指針，內(nèi)部還包含一個(gè)ziplist，使用ziplist來(lái)保存數(shù)據(jù)，而ziplist實(shí)際上含有多個(gè)entry節(jié)點(diǎn)，保存著數(shù)據(jù)。相當(dāng)與一個(gè)quicklistNode節(jié)點(diǎn)保存的是一片數(shù)據(jù)，而不再是一個(gè)數(shù)據(jù)。

quickList將二者的優(yōu)點(diǎn)結(jié)合起來(lái)，在宏觀上是一個(gè)雙向鏈表結(jié)構(gòu)，插入、刪除quicklistNode節(jié)點(diǎn)的成本很低，不需要移動(dòng)其他節(jié)點(diǎn)的位置，而在微觀上，每一個(gè)quicklistNode節(jié)點(diǎn)又是一個(gè)個(gè)的ziplist，內(nèi)部包含多個(gè)數(shù)據(jù)，ziplist內(nèi)存連續(xù)，減少了內(nèi)存碎片，同時(shí)由于每一個(gè)ziplist不是很大（大小可以配置），因此插入和刪除操作不會(huì)進(jìn)行大量的數(shù)據(jù)移動(dòng)。

相關(guān)文章：

https://redis.io/topics/data-types

https://redis.io/topics/data-types-intro

到此這篇關(guān)于Redis的底層數(shù)據(jù)結(jié)構(gòu)之dict、ziplist、quicklist詳解的文章就介紹到這了,更多相關(guān)Redis底層數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論