圖解Redis之資料結構篇——字典
前言
字典在Redis中的應用非常廣泛，資料庫與雜湊物件的底層實現就是字典。
系列文章
ofollow,noindex" target="_blank">圖解Redis之資料結構篇——簡單動態字串SDS
一、複習散列表
1.1 散列表
散列表(雜湊表)，其思想主要是基於陣列支援按照下標隨機訪問資料時間複雜度為O(1)的特性。可是說是陣列的一種擴充套件。假設，我們為了方便記錄某高校數學專業的所有學生的資訊。要求可以按照學號(學號格式為:入學時間+年級+專業+專業內自增序號，如2011 1101 0001)能夠快速找到某個學生的資訊。這個時候我們可以取學號的自增序號部分，即後四位作為陣列的索引下標，把學生相應的資訊儲存到對應的空間內即可。
如上圖所示,我們把學號作為key,通過擷取學號後四位的函式後計算後得到索引下標，將資料儲存到陣列中。當我們按照鍵值(學號)查詢時，只需要再次計算出索引下標，然後取出相應資料即可。以上便是雜湊思想。
1.2 雜湊函式
上面的例子中，擷取學號後四位的函式即是一個簡單的雜湊函式。
//雜湊函式 虛擬碼
int Hash(string key) {
// 獲取後四位字元
string hashValue =int.parse(key.Substring(key.Length-4, 4));
// 將後兩位字元轉換為整數
return hashValue;
}
在這裡雜湊函式的作用就是講key值對映成陣列的索引下標。關於雜湊函式的設計方法有很多，如:直接定址法、數字分析法、隨機數法等等。但即使是再優秀的設計方法也不能避免雜湊衝突。在散列表中雜湊函式不應設計太複雜。
1.3 雜湊衝突
雜湊函式具有確定性和不確定性。
- 確定性:雜湊的雜湊值不同，那麼雜湊的原始輸入也就不同。即:key1=key2,那麼hash(key1)=hash(key2)。
- 不確定性:同一個雜湊值很有可能對應多個不同的原始輸入。即:key1≠key2，hash(key1)=hash(key2)。
雜湊衝突,即key1≠key2，hash(key1)=hash(key2)的情況。雜湊衝突是不可避免的，如果我們key的長度為100，而陣列的索引數量只有50，那麼再優秀的演算法也無法避免雜湊衝突。關於雜湊衝突也有很多解決辦法，這裡簡單複習兩種：開放定址法和連結串列法。
1.3.1 開放定址法
開放定址法的核心思想是，如果出現了雜湊衝突，我們就重新探測一一個空閒位置，將其插入。比如，我們可以使用線性探測法。當我們往散列表中插入資料時，如果某個資料經過雜湊函式雜湊之後，儲存位置已經被佔用了，我們就從當前位置開始，依次往後查詢，看是否有空閒位置，如果遍歷到尾部都沒有找到空閒的位置，那麼我們就再從表頭開始找，直到找到為止。
散列表中查詢元素的時候，我們通過雜湊函式求出要查詢元素的鍵值對應的雜湊值，然後比較陣列中下標為雜湊值的元素和要查詢的元素。如果相等，則說明就是我們要找的元素；否則就順序往後依次查詢。如果遍歷到陣列中的空閒位置還沒有找到，就說明要查詢的元素並沒有在散列表中。
對於刪除操作稍微有些特別，不能單純地把要刪除的元素設定為空。因為在查詢的時候，一旦我們通過線性探測方法，找到一個空閒位置，我們就可以認定散列表中不存在這個資料。但是，如果這個空閒位置是我們後來刪除的，就會導致原來的查詢演算法失效。這裡我們可以將刪除的元素，特殊標記為 deleted。當線性探測查詢的時候，遇到標記為 deleted 的空間，並不是停下來，而是繼續往下探測。
線性探測法存在很大問題。當散列表中插入的資料越來越多時，其雜湊衝突的可能性就越大，極端情況下甚至要探測整個散列表,因此最壞時間複雜度為O(N)。在開放定址法中，除了線性探測法，我們還可以二次探測和雙重雜湊等方式。
1.3.2 連結串列法
連結串列法是一種比較常用的雜湊衝突解決辦法,Redis使用的就是連結串列法來解決雜湊衝突。連結串列法的原理是:如果遇到衝突，他就會在原地址新建一個空間，然後以連結串列結點的形式插入到該空間。當插入的時候，我們只需要通過雜湊函式計算出對應的雜湊槽位，將其插入到對應連結串列中即可。
1.3.3 負載因子與rehash
我們可以使用裝載因子來衡量散列表的“健康狀況”。
散列表的負載因子 = 填入表中的元素個數/散列表的長度
散列表負載因子越大，代表空閒位置越少，衝突也就越多，散列表的效能會下降。
對於散列表來說，負載因子過大或過小都不好，負載因子過大，散列表的效能會下降。而負載因子過小，則會造成記憶體不能合理利用，從而形成記憶體浪費。因此我們為了保證負載因子維持在一個合理的範圍內，要對散列表的大小進行收縮或擴充套件，即rehash。散列表的rehash過程類似於陣列的收縮與擴容。
1.3.4 開放定址法與連結串列法比較
對於開放定址法解決衝突的散列表，由於資料都儲存在陣列中，因此可以有效地利用 CPU 快取加快查詢速度(陣列佔用一塊連續的空間)。但是刪除資料的時候比較麻煩，需要特殊標記已經刪除掉的資料。而且，在開放定址法中，所有的資料都儲存在一個數組中，比起連結串列法來說，衝突的代價更高。所以，使用開放定址法解決衝突的散列表，負載因子的上限不能太大。這也導致這種方法比連結串列法更浪費記憶體空間。
對於連結串列法解決衝突的散列表,對記憶體的利用率比開放定址法要高。因為連結串列結點可以在需要的時候再建立，並不需要像開放定址法那樣事先申請好。連結串列法比起開放定址法，對大裝載因子的容忍度更高。開放定址法只能適用裝載因子小於1的情況。接近1時，就可能會有大量的雜湊衝突，效能會下降很多。但是對於連結串列法來說，只要雜湊函式的值隨機均勻，即便裝載因子變成10，也就是連結串列的長度變長了而已，雖然查詢效率有所下降，但是比起順序查詢還是快很多。但是，連結串列因為要儲存指標，所以對於比較小的物件的儲存，是比較消耗記憶體的，而且連結串列中的結點是零散分佈在記憶體中的，不是連續的，所以對CPU快取是不友好的，這對於執行效率有一定的影響。
二、Redis字典
2.1 Redis字典的實現
Redis字典使用散列表最為底層實現，一個散列表裡面有多個散列表節點，每個散列表節點就儲存了字典中的一個鍵值對。
2.1.1 字典
typedef struct dict{
//型別特定函式
void *type;
//私有資料
void *privdata;
//雜湊表-見2.1.2
dictht ht[2];
//rehash 索引 當rehash不在進行時 值為-1
int trehashidx;
}dict;
type屬性和privdata屬性是針對不同型別的鍵值對，為建立多型字典而設定的。
- type屬性是一個指向dictType結構的指標，每個dictType用於操作特定型別鍵值對的函式，Redis會為用途不同的字典設定不同的型別特定函式。
- privdata屬性則儲存了需要傳給給那些型別特定函式的可選引數。
typedef struct dictType
{
//計算雜湊值的函式
unsigned int(*hashFunction) (const void *key);
//複製鍵的函式
void *(*keyDup) (void *privdata,const void *key);
//複製值的函式
void *(*keyDup) (void *privdata,const void *obj);
//複製值的函式
void *(*keyCompare) (void *privdata,const void *key1, const void *key2);
//銷燬鍵的函式
void (*keyDestructor) (void *privdata, void *key);
//銷燬值的函式
void (*keyDestructor) (void *privdata, void *obj);
}dictType;
- ht屬性是一個包含兩個項的陣列，陣列中的每個項都是一個dictht雜湊表， 一般情況下，字典只使用ht[0] 雜湊表, ht[1]雜湊表只會對ht[0]雜湊表進行rehash時使用。
- rehashidx記錄了rehash目前的進度，如果目前沒有進行rehash，值為-1。
2.1.2 散列表
typedef struct dictht
{
//雜湊表陣列，C語言中，*號是為了表明該變數為指標，有幾個* 號就相當於是幾級指標，這裡是二級指標，理解為指向指標的指標
dictEntry **table;
//雜湊表大小
unsigned long size;
//雜湊表大小掩碼，用於計算索引值
unsigned long sizemask;
//該雜湊已有節點的數量
unsigned long used;
}dictht;
- table屬性是一個數組，陣列中的每個元素都是一個指向dict.h/dictEntry結構的指標，每個dictEntry結構儲存著一個鍵值對
- size屬性記錄了雜湊表的大小，也是table陣列的大小
- used屬性則記錄雜湊表目前已有節點(鍵值對)的數量
- sizemask屬性的值總是等於 size-1(從0開始)，這個屬性和雜湊值一起決定一個鍵應該被放到table陣列的哪個索引上面（索引下標值）。
2.1.3 散列表節點
//雜湊表節點定義dictEntry結構表示，每個dictEntry結構都儲存著一個鍵值對。
typedef struct dictEntry
{
//鍵
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
// 指向下個雜湊表節點，形成連結串列
struct dictEntry *next;
}dictEntry;
key屬性儲存著鍵值中的鍵，而v屬性則儲存著鍵值對中的值，其中鍵值(v屬性)可以是一個指標，或uint64_t整數，或int64_t整數。 next屬性是指向另一個雜湊表節點的指標，這個指標可以將多個雜湊值相同的鍵值對連線在一起，解決鍵衝突問題。
2.2 Redis如何解決雜湊衝突
2.2.1 連結串列法
當有兩個或以上的鍵被分配到散列表陣列同一個索引上時，就發生了鍵衝突。Redis使用連結串列法解決雜湊衝突。每個散列表節點都有一個next指標，多個散列表節點next可以用next指標構成一個單向連結串列，被分配到同一個索引上的多個節點可以使用這個單向連結串列連線起來。
如圖所示,當鍵k0和k1的經過雜湊函式得到索引值都為1時，就會使用next指標將兩個節點連線起來。而由於節點沒有指向鏈尾的指標，因此新的節點總是插入到連結串列的頭部，排在已有節點的前面。
2.2.2 Redis rehash
隨著操作的進行，散列表中儲存的鍵值對會也會不斷地增加或減少，為了保證負載因子維持在一個合理的範圍，當散列表內的鍵值對過多或過少時，內需要定期進行rehash，以提升效能或節省記憶體。Redis的rehash的步驟如下:
-
為字典的ht[1]散列表分配空間，這個空間的大小取決於要執行的操作以及ht[0]當前包含的鍵值對數量(即:ht[0].used的屬性值)
- 擴充套件操作：ht[1]的大小為 第一個大於等於ht[0].used*2的2的n次方冪。如:ht[0].used=3則ht[1]的大小為8，ht[0].used=4則ht[1]的大小為8。
- 收縮操作: ht[1]的大小為 第一個大於等於ht[0].used的2的n次方冪。
-
將儲存在ht[0]中的鍵值對重新計算鍵的雜湊值和索引值，然後放到ht[1]指定的位置上。
-
將ht[0]包含的所有鍵值對都遷移到了ht[1]之後，釋放ht[0],將ht[1]設定為ht[0],並建立一個新的ht[1]雜湊表為下一次rehash做準備。
rehash操作需要滿足以下條件:
- 伺服器目前沒有執行BGSAVE(rdb持久化)命令或者BGREWRITEAOF(AOF檔案重寫)命令，並且散列表的負載因子大於等於1。
- 伺服器目前正在執行BGSAVE命令或者BGREWRITEAOF命令，並且負載因子大於等於5。
- 當負載因子小於0.1時，程式自動開始執行收縮操作。
Redis這麼做的目的是基於作業系統建立子程序後寫時複製技術，避免不必要的寫入操作。(有關BGSAVE、BGREWRITEAOF以及寫時複製會在後續持久化一文詳細介紹)。
2.2.3 漸進式 rehash
對於rehash我們思考一個問題如果散列表當前大小為 1GB，要想擴容為原來的兩倍大小，那就需要對 1GB 的資料重新計算雜湊值，並且從原來的散列表搬移到新的散列表。這種情況聽著就很耗時，而生產環境中甚至會更大。為了解決一次性擴容耗時過多的情況，可以將擴容操作穿插在插入操作的過程中，分批完成。當負載因子觸達閾值之後，只申請新空間，但並不將老的資料搬移到新散列表中。當有新資料要插入時，將新資料插入新散列表中，並且從老的散列表中拿出一個數據放入到新散列表。每次插入一個數據到散列表，都重複上面的過程。經過多次插入操作之後，老的散列表中的資料就一點一點全部搬移到新散列表中了。這樣沒有了集中的一次一次性資料搬移，插入操作就都變得很快了。
Redis為了解決這個問題採用漸進式rehash方式。以下是Redis漸進式rehash的詳細步驟:
- 為
ht[1]分配空間， 讓字典同時持有ht[0]和ht[1]兩個雜湊表。 - 在字典中維持一個索引計數器變數
rehashidx， 並將它的值設定為0，表示 rehash 工作正式開始。 - 在 rehash 進行期間， 每次對字典執行新增、刪除、查詢或者更新操作時， 程式除了執行指定的操作以外， 還會順帶將
ht[0]雜湊表在rehashidx索引上的所有鍵值對 rehash 到ht[1]， 當 rehash 工作完成之後， 程式將rehashidx屬性的值增一。 - 隨著字典操作的不斷執行， 最終在某個時間點上，
ht[0]的所有鍵值對都會被 rehash 至ht[1]， 這時程式將rehashidx屬性的值設為-1， 表示 rehash 操作已完成。
說明:
1.因為在進行漸進式 rehash 的過程中，字典會同時使用 ht[0] 和 ht[1] 兩個雜湊表，所以在漸進式 rehash 進行期間，字典的刪除（delete）、查詢（find）、更新（update）等操作會在兩個雜湊表上進行。
2. 在漸進式 rehash 執行期間，新新增到字典的鍵值對一律會被儲存到 ht[1] 裡面，而 ht[0] 則不再進行任何新增操作：這一措施保證了 ht[0] 包含的鍵值對數量會只減不增，並隨著 rehash 操作的執行而最終變成空表。
2.3 時間複雜度
下面給出幾個Redis字典常見操作的時間複雜度，可以結合上面的內容分析為什麼。
| 操作 | 時間複雜度 |
|---|---|
| 建立一個新字典 | O(1) |
| 將給定的鍵值對新增到字典內 | O(1) |
| 將給定的鍵值對新增到字典內，如果鍵存在則替換之 | O(1) |
| 返回給定鍵的值 | O(1) |
| 從字典中隨機返回一個鍵值對 | O(1) |
| 從字典中刪除給定鍵所對應的鍵值對 | O(1) |
| 釋放給定字典以及字典中包含的鍵值對 | O(N)，N為字典包含的鍵值對的數量 |
本文重點
- 字典在redis中廣泛應用，包括資料庫和hash資料結構。
- 每個字典有兩個雜湊表，一個是正常使用，一個用於rehash期間使用。
- 當redis計算雜湊時，採用的是MurmurHash2雜湊演算法。
- 雜湊表採用連結串列法解決雜湊衝突，被分配到同一個地址的鍵會構成一個單向連結串列。
- 在rehash對雜湊表進行擴充套件或者收縮過程中，會將所有鍵值對進行遷移，並且這個遷移是漸進式的遷移。
小結
本篇文章主要回顧了散列表的概念，雜湊函式以及如何解決雜湊衝突。並分析了Redis中字典的實現。下篇文章將介紹跳躍表以及跳躍表在Redis中的實現。
參考
《Redis設計與實現》
《Redis開發與運維》
《Redis官方文件》