Redis的底層資料結構詳解：dict、ziplist、quicklist

詳細介紹了Redis的底層資料結構：dict、ziplist、quicklist。

此前我們學習了常見的Reids資料類型，這些資料類型都需要底層的資料結構的支援，現在我們來看看Redis常見的底層資料結構：dict、ziplist、quicklist。

文章目錄

• 1 Redis dict
• • 1.1 擴縮容的條件
  • 1.2 漸進式rehash操作
• 2 Redis ziplist
• • 2.1 ziplist結構
  • 2.2 entry結構
• 3 Redis quicklist

1 Redis dict

dict就是“字典”的意思，它是Redis中的一種使用的非常多的底層的資料結構，除了hash會使用字段之外，整個 Redis 資料庫的所有 key 和 value 也組成了一個全局字典dict，還有帶過期時間的 key 也是一個字典expires(存儲在 RedisDb 資料結構中)。

Redis 中的字典相當于 JDK1.7中的 HashMap，内部實作也差不多類似，都是通過 “數組 + 連結清單” 的鍊位址法來解決部分哈希沖突，同時這樣的結構也吸收了兩種不同資料結構的優點。

和JDK1.7中的hashmap不同的是，Reids的字典結構内部包含兩個hashtable變量，通常情況下隻有一個hashtable有值，另一個為空表，但是在字典擴容縮容時，需要配置設定新的hashtable，并且使用了一種叫做漸進式搬遷(rehash)的機制來提高dict的縮放效率，這時候兩個hashtable分别存儲舊的和新的 hashtable，待搬遷結束後，舊的将被删除，新的 hashtable 取而代之。

1.1 擴縮容的條件

正常情況下，當 hash 表中元素的個數等于數組的長度時，就會開始擴容，擴容的新數組是原數組大小的2倍。不過如果 Redis 正在做 BGSAVE或者BGREWRITEAOF(持久化)，為了減少記憶體占用，Redis 盡量不去擴容，但是如果 hash 表非常滿了，達到了數組長度的 5 倍了，這個時候就會強制擴容。

當 hash 表因為元素逐漸被删除變得越來越稀疏時，Redis 會對 hash 表進行縮容來減少hash表的第一維數組空間占用。所用的條件是：元素個數低于數組長度的10%，縮容不會考慮 Redis 是否在做 bgsave。

1.2 漸進式rehash操作

在擴容和收縮的時候，如果哈希字典中有很多元素，一次性将這些鍵從ht0（正在使用的hashtable）全部rehash到ht1（另一個空的hashtable）的話，由于Redis是單線程模型，那麼可能會導緻伺服器在一段時間内停止服務。是以，采用漸進式rehash的方式，資料的遷移并不是一步完成的，是以dict内部還有一個rehashidx屬性用來控制rehash，預設置為-1。

1. 為ht[1]配置設定空間，讓字典同時持有ht[0]和ht[1]兩個哈希表。
2. 将rehashindex的值設定為0，表示rehash工作正式開始。
3. 在rehash期間，每次對字典執行增删改查操作時，程式除了執行指定的操作以外，還會順帶将ht[0]哈希表在rehashindex索引上的所有鍵值對rehash到ht[1]，當一次rehash工作完成以後，rehashindex的值+1。
4. 随着字典操作的不斷執行，最終會在某一時間段上ht[0]的所有鍵值對都會被rehash到ht[1]，将rehashindex的值設定為-1，表示rehash操作結束。
5. 把ht[1]設定為ht[0]，并重新在ht[1]上建立一個空表，為下次rehash做準備。

漸進式rehash采用的是一種分而治之的方式，它以bucket(桶)為基本機關進行漸進式的資料遷移，每步完成一個bucket的遷移，直至所有資料遷移完畢。這種方式将rehash的操作分攤在每一個的通路中，避免集中式rehash而帶來的龐大計算量。

在漸進式rehash的過程中，如果有删除、修改、查詢操作，則會在兩個哈希表ht[0]和ht[1]上進行，先操作ht[0]，如果沒找到，再操作ht[1]，則新增的資料則會被儲存在ht[1]中，ht[0]中包含的鍵值對數量會隻減不增，并随着 rehash 操作的執行而最終變成空表。

2 Redis ziplist

ziplist又名壓縮清單，見其名知其意，這種資料結構就比較節省記憶體空間，Redis中對于list（3.2版本之前）、hash、zset類型的資料，如果元素較少，并且每個清單項要麼就是小整數值，要麼就是長度比較短的字元串，那麼Redis就會使用壓縮清單來存儲。

ziplist本身可以有序也可以無序。當作為list（3.2版本之前）和hash的底層實作時，節點之間沒有順序；當作為zset的底層實作時，節點之間會按照score大小順序排列，元素和score被分别存儲為兩個節點，元素在前，score在後。

ziplist的節省空間是相較于數組而言的，ziplist和數組一樣同樣采用一整塊連續的空間來存儲資料，數組在實際存儲時，每一個元素所占的實際大小是一樣的，并且是以最大的元素的大小為準，這樣就能進行快速的根據索引通路，而ziplist則允許每一個entry節點（對于數組中的元素）所占的實際大小不同，另外，節點之間沒有存儲前驅和後繼的指針，以此節約空間。

ziplist支援正序或者倒序的周遊，往ziplist裡插入一個entry 時間複雜度 平均:O(n),最壞:O(n²)，從ziplist裡删除一個entry 時間複雜度 平均:O(n), 最壞:O(n²)。最壞為O(n²)是因為Redis連鎖更新導緻的，但這種情況出現的機率不高。

ziplist和數組類似，删除和添加節點都可能涉及到其他節點位置的移動，是以隻适用于元素資料量較少，并且每個清單項要麼就是小整數值，要麼就是長度比較短的字元串的情況。

2.1 ziplist結構

Redis的ziplist采用一系列特殊編碼的連續記憶體塊，一個壓縮清單出了在頭部包含一些整體資訊之外，剩下的部分可以包含任意多個節點(entry)。

整體結構如下：

1. zlbytes：32位無符号整數，表示ziplist的整體長度（位元組)。在對ziplist重新配置設定記憶體或者計算zlend的位置時有用。
2. zltail：32位無符号整數，最後一個節點距離頭部的偏移量，通過該偏移量程式無需周遊整個ziplist即可确定尾節點的位址，在反向周遊ziplist或者pop尾部節點的時候很有用。
3. zllen：16位無符号整數，ziplist的節點（entry）個數。當小于值小于65535時，該值時準确的，等于65535（16位的最大值）時，需要周遊整個連結清單才能得到真實節點數量。
4. entry：ziplist中的資料節點，長度不固定，自己的長度儲存在每一個entry節點内部。
5. zlend：8位無符号整數固定值為0xFF，用于标記ziplist的結尾。

2.2 entry結構

ziplist的entry用于存儲正數或者字元串（位元組數組），且每個節點的長度都是不一樣的，是以節點的長度隻能由這個節點自己來儲存，Redis的ziplist中，entry由三部分構成：

1. previous_entry_length：8bit或者40bit，用于記錄上一個節點的長度（位元組），為了友善反向周遊ziplist。
2. encoding：目前節點資料的編碼規則，即data屬性的資料類型以及長度。
3. content：目前節點的值，可以是數字或字元串（位元組數組）。

previous_entry_length用于記錄上一個節點的長度（位元組），為了友善反向周遊ziplist，其本身的長度可能是8bit或者40bit。

1. 如果前一節點的長度小于254位元組，那麼prevlengh屬性的長度為1位元組，前一節點的長度就儲存在這一個位元組裡面，這樣更加節約記憶體。
2. 如果前一節點的長度大于等于254位元組，那麼prevlengh屬性的總長度為5位元組，第一位元組被固定設定為0xFE（十進制值254），而之後的四個位元組則用于儲存前一節點的長度。
3. 第二種情況下，第一個位元組254而不用255（0xFF）是因為255是zlend的值，它用于判斷ziplist是否到達尾部。

content表示目前節點的值，可以是數字或字元串（位元組數組），encoding 表示目前節點資料的編碼規則，即data屬性的資料類型以及長度，其中encoding其中高2位用來區分整數節點和字元串節點（高2位為11時是整數節點），根據值的類型不同，一共有九種編碼類型。

位元組數組的encoding類型3種，encoding有8位、16位、40位三種長度，context的長度也是變化的：

encoding長度	encoding格式	content格式
8bit	高兩位固定00，後6位表示位元組數組的長度	長度小于等于63(2^6-1)位元組的位元組數組
16bit	高兩位固定01，後14位表示位元組數組的長度。	長度小于等于16383(2^14-1)位元組的位元組數組
40bit	高兩位固定10，後38位表示位元組數組的長度。	長度小于等于4294967295(2^32-1)位元組的位元組數組

整數值的encoding類型6種，固定長度8位，高兩位固定11，表示整數，是以需要後兩位來表示不同的整數類型。整數類型的content的長度雖然也是可變的，但固定範圍内的整數長度一樣，也就是說content長度隻有固定的幾種。

encoding長度	encoding格式	content格式
1bit	1111xxxx，後四位用來表示content。	4bit長的無符号整數，即介于0至12之間，沒有content字段，在encoding中存儲。
11111110	8bit，有符号整數。
11000000	16bit，有符号整數。
11110000	24bit，有符号整數。
11010000	32bit，有符号整數。
11100000	64bit，有符号整數。

3 Redis quicklist

Redis 的list在3.2版本之前在元素較少時實際上是采用ziplist結構，當連結清單entry資料超過512、或單個value 長度超過64，底層就會轉化成linkedlist編碼，而Redis3.2及其之後則采用quicklist結構代替ziplist和linkedlist。

ziplist存儲在一段連續的記憶體上，是以存儲和查找效率很高，順序IO通路。但是，它不利于修改操作，插入和删除操作需要頻繁的申請和釋放記憶體。特别是當ziplist長度很長的時候，一次realloc可能會導緻大批量的資料拷貝，适用于存儲整數和短字元串。

雙向連結清單linkedlist便于在表的兩端進行push和pop操作，在插入節點上複雜度很低，但是它的記憶體開銷比較大。首先，它在每個節點上除了要儲存資料之外，還要額外儲存兩個prev 和 next指針（64 位作業系統占用 8 個位元組）；其次，雙向連結清單的各個節點是單獨的記憶體塊，位址不連續，随機IO通路，節點多了容易産生記憶體碎片，影響記憶體管理效率。

quickList将 linkedList 按段切分，每一段使用 zipList 來緊湊存儲，多個 zipList 之間使用雙向指針串接起來。

首先quickList就是一個标準的雙向連結清單的配置，有head 和tail節點，每個節點是一個quicklistNode節點，包含prev和next指針，内部還包含一個ziplist，使用ziplist來儲存資料，而ziplist實際上含有多個entry節點，儲存着資料。相當與一個quicklistNode節點儲存的是一片資料，而不再是一個資料。

quickList将二者的優點結合起來，在宏觀上是一個雙向連結清單結構，插入、删除quicklistNode節點的成本很低，不需要移動其他節點的位置，而在微觀上，每一個quicklistNode節點又是一個個的ziplist，内部包含多個資料，ziplist記憶體連續，減少了記憶體碎片，同時由于每一個ziplist不是很大（大小可以配置），是以插入和删除操作不會進行大量的資料移動。

相關文章：

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

如有需要交流，或者文章有誤，請直接留言。另外希望點贊、收藏、關注，我将不間斷更新各種Java學習部落格！