實現數據庫鍵空間
Redis 是一個鍵值對數據庫， 數據庫中的鍵值對就由字典保存： 每個數據庫都有一個與之相對應的字典， 這個字典被稱之為鍵空間（key space）。
當用戶添加一個鍵值對到數據庫時（不論鍵值對是什么類型）， 程序就將該鍵值對添加到鍵空間； 當用戶從數據庫中刪除一個鍵值對時， 程序就會將這個鍵值對從鍵空間中刪除； 等等。
舉個例子，執行 FLUSHDB 可以清空鍵空間上的所有鍵值對數據：
redis> FLUSHDB
OK
執行 DBSIZE 則返回鍵空間上現有的鍵值對：redis> DBSIZE
(integer) 0
還可以用 SET 設置一個字符串鍵到鍵空間， 并用 GET 從鍵空間中取出該字符串鍵的值：redis> SET number 10086
OK
redis> GET number
"10086"
redis> DBSIZE
(integer) 1
后面的《數據庫》一章會對鍵空間以及數據庫的實現作詳細的介紹， 到時我們將看到， 大部分針對數據庫的命令， 比如 DBSIZE 、FLUSHDB 、:ref:RANDOMKEY ， 等等， 都是構建于對字典的操作之上的； 而那些創建、更新、刪除和查找鍵值對的命令， 也無一例外地需要在鍵空間上進行操作。
用作 Hash 類型鍵的其中一種底層實現
Redis 的 Hash 類型鍵使用以下兩種數據結構作為底層實現:
- 字典；
- 壓縮列表；
因為壓縮列表比字典更節省內存， 所以程序在創建新 Hash 鍵時， 默認使用壓縮列表作為底層實現， 當有需要時， 程序才會將底層實現從壓縮列表轉換到字典。
當用戶操作一個 Hash 鍵時， 鍵值在底層就可能是一個哈希表：
redis> HSET book name "The design and implementation of Redis"
(integer) 1
redis> HSET book type "source code analysis"
(integer) 1
redis> HSET book release-date "2013.3.8"
(integer) 1
redis> HGETALL book
1) "name"
2) "The design and implementation of Redis"
3) "type"
4) "source code analysis"
5) "release-date"
6) "2013.3.8"
《哈希表》章節給出了關于哈希類型鍵的更多信息， 并介紹了壓縮列表和字典之間的轉換條件。
介紹完了字典的用途， 現在讓我們來看看字典數據結構的定義。
字典的實現
實現字典的方法有很多種：
- 最簡單的就是使用鏈表或數組， 但是這種方式只適用于元素個數不多的情況下；
- 要兼顧高效和簡單性，可以使用哈希表；
- 如果追求更為穩定的性能特征， 并且希望高效地實現排序操作的話， 則可以使用更為復雜的平衡樹；
在眾多可能的實現中， Redis 選擇了高效且實現簡單的哈希表作為字典的底層實現。
dict.h/dict 給出了這個字典的定義：
/*
* 字典
*
* 每個字典使用兩個哈希表，用于實現漸進式 rehash
*/
typedef struct dict {
// 特定于類型的處理函數
dictType *type;
// 類型處理函數的私有數據
void *privdata;
// 哈希表（2個）
dictht ht[2];
// 記錄 rehash 進度的標志，值為-1 表示 rehash 未進行
int rehashidx;
// 當前正在運作的安全迭代器數量
int iterators;
} dict;
以下是用于處理 dict 類型的 API ， 它們的作用及相應的算法復雜度：
| 操作類型 | 操作 | 函數 | 算法復雜度 |
|---|
| 創建 | 創建一個新字典 | dictCreate | O(1) |
| 添加/更新 | 添加新鍵值對到字典 | dictAdd | O(1) |
| 添加或更新給定鍵的值 | dictReplace | O(1) |
| 獲取 | 在字典中查找給定鍵所在的節點 | dictFind | O(1) |
| 在字典中查找給定鍵的值 | dictFetchValue | O(1) |
| 從字典中隨機返回一個節點 | dictGetRandomKey | O(N) |
| 刪除 | 根據給定鍵，刪除字典中的鍵值對 | dictDelete | O(1) |
| 清空并釋放字典 | dictRelease | O(N) |
| 清空并重置（但不釋放）字典 | dictEmpty | O(N) |
| 空間調整 | 縮小字典 | dictResize | O(N) |
| 擴大字典 | dictExpand | O(N) |
| 對字典進行給定步數的 rehash | dictRehash | O(N) |
| 在給定毫秒內，對字典進行rehash | dictRehashMilliseconds | O(N) |
注意 dict 類型使用了兩個指針分別指向兩個哈希表。
其中， 0 號哈希表（ht[0]）是字典主要使用的哈希表， 而 1 號哈希表（ht[1]）則只有在程序對 0 號哈希表進行 rehash 時才使用。
接下來兩個小節將對哈希表的實現，以及哈希表所使用的哈希算法進行介紹。
哈希表實現¶
字典所使用的哈希表實現由 dict.h/dictht 類型定義：
/*
* 哈希表
*/
typedef struct dictht {
// 哈希表節點指針數組（俗稱桶，bucket）
dictEntry **table;
// 指針數組的大小
unsigned long size;
// 指針數組的長度掩碼，用于計算索引值
unsigned long sizemask;
// 哈希表現有的節點數量
unsigned long used;
} dictht;
table 屬性是一個數組， 數組的每個元素都是一個指向 dictEntry 結構的指針。
每個 dictEntry 都保存著一個鍵值對， 以及一個指向另一個 dictEntry 結構的指針：
/*
* 哈希表節點
*/
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 鏈往后繼節點
struct dictEntry *next;
} dictEntry;
next 屬性指向另一個 dictEntry 結構， 多個 dictEntry 可以通過 next 指針串連成鏈表， 從這里可以看出， dictht 使用鏈地址法來處理鍵碰撞： 當多個不同的鍵擁有相同的哈希值時，哈希表用一個鏈表將這些鍵連接起來。
下圖展示了一個由 dictht 和數個 dictEntry 組成的哈希表例子：
如果再加上之前列出的 dict 類型，那么整個字典結構可以表示如下：
在上圖的字典示例中， 字典雖然創建了兩個哈希表， 但正在使用的只有 0 號哈希表， 這說明字典未進行 rehash 狀態。
創建新字典
dictCreate 函數創建并返回一個新字典：
dict *d = dictCreate(&hash_type, NULL);
d 的值可以用圖片表示如下：
新創建的兩個哈希表都沒有為 table 屬性分配任何空間：
- ht[0]->table 的空間分配將在第一次往字典添加鍵值對時進行；
- ht[1]->table 的空間分配將在 rehash 開始時進行；
添加鍵值對到字典
根據字典所處的狀態， 將一個給定的鍵值對添加到字典可能會引起一系列復雜的操作：
- 如果字典為未初始化（也即是字典的 0 號哈希表的 table 屬性為空），那么程序需要對 0 號哈希表進行初始化；
- 如果在插入時發生了鍵碰撞，那么程序需要處理碰撞；
- 如果插入新元素使得字典滿足了 rehash 條件，那么需要啟動相應的 rehash 程序；
當程序處理完以上三種情況之后，新的鍵值對才會被真正地添加到字典上。
整個添加流程可以用下圖表示：
在接下來的三節中， 我們將分別看到添加操作如何在以下三種情況中執行：
- 字典為空;
- 添加新鍵值對時發生碰撞處理；
- 添加新鍵值對時觸發了 rehash 操作；
添加新元素到空白字典
當第一次往空字典里添加鍵值對時， 程序會根據 dict.h/DICT_HT_INITIAL_SIZE 里指定的大小為 d->ht[0]->table 分配空間 （在目前的版本中， DICT_HT_INITIAL_SIZE 的值為 4 ）。
以下是字典空白時的樣子：
以下是往空白字典添加了第一個鍵值對之后的樣子：
添加新鍵值對時發生碰撞處理
在哈希表實現中， 當兩個不同的鍵擁有相同的哈希值時， 我們稱這兩個鍵發生碰撞（collision）， 而哈希表實現必須想辦法對碰撞進行處理。
字典哈希表所使用的碰撞解決方法被稱之為鏈地址法： 這種方法使用鏈表將多個哈希值相同的節點串連在一起， 從而解決沖突問題。
假設現在有一個帶有三個節點的哈希表，如下圖：
對于一個新的鍵值對 key4 和 value4 ， 如果 key4 的哈希值和 key1 的哈希值相同， 那么它們將在哈希表的 0 號索引上發生碰撞。
通過將 key4-value4 和 key1-value1 兩個鍵值對用鏈表連接起來， 就可以解決碰撞的問題：
添加新鍵值對時觸發了 rehash 操作
對于使用鏈地址法來解決碰撞問題的哈希表 dictht 來說， 哈希表的性能依賴于它的大小（size屬性）和它所保存的節點的數量（used屬性）之間的比率：
- 比率在 1:1 時，哈希表的性能最好；
- 如果節點數量比哈希表的大小要大很多的話，那么哈希表就會退化成多個鏈表，哈希表本身的性能優勢就不再存在；
舉個例子， 對于下面這個哈希表， 平均每次失敗查找只需要訪問 1 個節點（非空節點訪問 2 次，空節點訪問 1 次）：
而對于下面這個哈希表， 平均每次失敗查找需要訪問 5 個節點：
為了在字典的鍵值對不斷增多的情況下保持良好的性能， 字典需要對所使用的哈希表（ht[0]）進行 rehash 操作： 在不修改任何鍵值對的情況下，對哈希表進行擴容， 盡量將比率維持在 1:1 左右。
dictAdd 在每次向字典添加新鍵值對之前， 都會對哈希表 ht[0] 進行檢查， 對于 ht[0] 的 size 和 used 屬性， 如果它們之間的比率 ratio =used / size 滿足以下任何一個條件的話，rehash 過程就會被激活：
- 自然 rehash ： ratio >= 1 ，且變量 dict_can_resize 為真。
- 強制 rehash ： ratio 大于變量 dict_force_resize_ratio （目前版本中， dict_force_resize_ratio 的值為 5 ）。
什么時候 dict_can_resize 會為假？
在前面介紹字典的應用時也說到過， 一個數據庫就是一個字典， 數據庫里的哈希類型鍵也是一個字典， 當 Redis 使用子進程對數據庫執行后臺持久化任務時（比如執行 BGSAVE 或 BGREWRITEAOF 時）， 為了最大化地利用系統的 copy on write 機制， 程序會會暫時將 dict_can_resize 設為假， 避免執行自然 rehash ， 從而減少程序對內存的觸碰（touch）。
當持久化任務完成之后， dict_can_resize 會重新被設為真。
另一方面， 當字典滿足了強制 rehash 的條件時， 即使 dict_can_resize 不為真（有 BGSAVE 或 BGREWRITEAOF 正在執行）， 這個字典一樣會被 rehash 。
Rehash 執行過程
字典的 rehash 操作實際上就是執行以下任務：
- 創建一個比 ht[0]->table 更大的 ht[1]->table ；
- 將 ht[0]->table 中的所有鍵值對遷移到 ht[1]->table ；
- 將原有 ht[0] 的數據清空，并將 ht[1] 替換為新的 ht[0] ；
經過以上步驟之后， 程序就在不改變原有鍵值對數據的基礎上， 增大了哈希表的大小。
作為例子， 以下四個小節展示了一次對哈希表進行 rehash 的完整過程。
1. 開始 rehash
這個階段有兩個事情要做：
- 設置字典的 rehashidx 為 0 ，標識著 rehash 的開始；
- 為 ht[1]->table 分配空間，大小至少為 ht[0]->used 的兩倍；
這時的字典是這個樣子：
2. Rehash 進行中
在這個階段， ht[0]->table 的節點會被逐漸遷移到 ht[1]->table ， 因為 rehash 是分多次進行的（細節在下一節解釋）， 字典的 rehashidx變量會記錄 rehash 進行到 ht[0] 的哪個索引位置上。
以下是 rehashidx 值為 2 時，字典的樣子：
注意除了節點的移動外， 字典的 rehashidx 、 ht[0]->used 和 ht[1]->used 三個屬性也產生了變化。
3. 節點遷移完畢
到了這個階段，所有的節點都已經從 ht[0] 遷移到 ht[1] 了：
4. Rehash 完畢
在 rehash 的最后階段，程序會執行以下工作：
- 釋放 ht[0] 的空間；
- 用 ht[1] 來代替 ht[0] ，使原來的 ht[1] 成為新的 ht[0] ；
- 創建一個新的空哈希表，并將它設置為 ht[1] ；
- 將字典的 rehashidx 屬性設置為 -1 ，標識 rehash 已停止；
以下是字典 rehash 完畢之后的樣子：
對比字典 rehash 之前和 rehash 之后， 新的 ht[0] 空間更大， 并且字典原有的鍵值對也沒有被修改或者刪除。
漸進式 rehash
在上一節，我們了解了字典的 rehash 過程， 需要特別指出的是， rehash 程序并不是在激活之后就馬上執行直到完成的， 而是分多次、漸進式地完成的。
假設這樣一個場景：在一個有很多鍵值對的字典里， 某個用戶在添加新鍵值對時觸發了 rehash 過程， 如果這個 rehash 過程必須將所有鍵值對遷移完畢之后才將結果返回給用戶， 這樣的處理方式將是非常不友好的。
另一方面， 要求服務器必須阻塞直到 rehash 完成， 這對于 Redis 服務器本身也是不能接受的。
為了解決這個問題， Redis 使用了漸進式（incremental）的 rehash 方式： 通過將 rehash 分散到多個步驟中進行， 從而避免了集中式的計算。
漸進式 rehash 主要由 _dictRehashStep 和 dictRehashMilliseconds 兩個函數進行：
- _dictRehashStep 用于對數據庫字典、以及哈希鍵的字典進行被動 rehash ；
- dictRehashMilliseconds 則由 Redis 服務器常規任務程序（server cron job）執行，用于對數據庫字典進行主動 rehash ；
_dictRehashStep
每次執行 _dictRehashStep ， ht[0]->table 哈希表第一個不為空的索引上的所有節點就會全部遷移到 ht[1]->table 。
在 rehash 開始進行之后（d->rehashidx 不為 -1）， 每次執行一次添加、查找、刪除操作， _dictRehashStep 都會被執行一次：
因為字典會保持哈希表大小和節點數的比率在一個很小的范圍內， 所以每個索引上的節點數量不會很多（從目前版本的 rehash 條件來看，平均只有一個，最多通常也不會超過五個）， 所以在執行操作的同時，對單個索引上的節點進行遷移， 幾乎不會對響應時間造成影響。
dictRehashMilliseconds
dictRehashMilliseconds 可以在指定的毫秒數內， 對字典進行 rehash 。
當 Redis 的服務器常規任務執行時， dictRehashMilliseconds 會被執行， 在規定的時間內， 盡可能地對數據庫字典中那些需要 rehash 的字典進行 rehash ， 從而加速數據庫字典的 rehash 進程（progress）。
其他措施
在哈希表進行 rehash 時， 字典還會采取一些特別的措施， 確保 rehash 順利、正確地進行：
- 因為在 rehash 時，字典會同時使用兩個哈希表，所以在這期間的所有查找、刪除等操作，除了在 ht[0] 上進行，還需要在 ht[1] 上進行。
- 在執行添加操作時，新的節點會直接添加到 ht[1] 而不是 ht[0] ，這樣保證 ht[0] 的節點數量在整個 rehash 過程中都只減不增。
字典的收縮
上面關于 rehash 的章節描述了通過 rehash 對字典進行擴展（expand）的情況， 如果哈希表的可用節點數比已用節點數大很多的話， 那么也可以通過對哈希表進行 rehash 來收縮（shrink）字典。
收縮 rehash 和上面展示的擴展 rehash 的操作幾乎一樣，它執行以下步驟：
- 創建一個比 ht[0]->table 小的 ht[1]->table ；
- 將 ht[0]->table 中的所有鍵值對遷移到 ht[1]->table ；
- 將原有 ht[0] 的數據清空，并將 ht[1] 替換為新的 ht[0] ；
擴展 rehash 和收縮 rehash 執行完全相同的過程， 一個 rehash 是擴展還是收縮字典， 關鍵在于新分配的 ht[1]->table 的大小：
- 如果 rehash 是擴展操作，那么 ht[1]->table 比 ht[0]->table 要大；
- 如果 rehash 是收縮操作，那么 ht[1]->table 比 ht[0]->table 要小；
對于不同的字典， Redis 使用不同的收縮和擴展策略：
字典其他操作
除了添加操作和伸展/收縮操作之外， 字典還定義了其他一些操作， 比如常見的查找、刪除和更新。
因為鏈地址法哈希表實現的相關信息可以從任何一本數據結構或算法書上找到， 這里不再對字典的其他操作進行介紹， 不過前面對創建字典、添加鍵值對、收縮和擴展 rehash 的討論已經涵蓋了字典模塊的核心內容。
字典的迭代
字典帶有自己的迭代器實現 —— 對字典進行迭代實際上就是對字典所使用的哈希表進行迭代：
- 迭代器首先迭代字典的第一個哈希表， 然后，如果 rehash 正在進行的話， 就繼續對第二個哈希表進行迭代。
- 當迭代哈希表時， 找到第一個不為空的索引， 然后迭代這個索引上的所有節點。
- 當這個索引迭代完了， 繼續查找下一個不為空的索引， 如此循環， 一直到整個哈希表都迭代完為止。
整個迭代過程可以用偽代碼表示如下：
def iter_dict(dict):
# 迭代 0 號哈希表
iter_table(ht[0]->table)
# 如果正在執行 rehash ，那么也迭代 1 號哈希表
if dict.is_rehashing(): iter_table(ht[1]->table)
def iter_table(table):
# 遍歷哈希表上的所有索引
for index in table:
# 跳過空索引
if table[index].empty():
continue
# 遍歷索引上的所有節點
for node in table[index]:
# 處理節點
do_something_with(node)
字典的迭代器有兩種：
- 安全迭代器：在迭代進行過程中，可以對字典進行修改。
- 不安全迭代器： 在迭代進行過程中，不對字典進行修改。
以下是迭代器的數據結構定義：
/*
* 字典迭代器
*/
typedef struct dictIterator {
dict *d; // 正在迭代的字典
int table, // 正在迭代的哈希表的號碼（0 或者 1）
index, // 正在迭代的哈希表數組的索引
safe; // 是否安全？
dictEntry *entry, // 當前哈希節點
*nextEntry; // 當前哈希節點的后繼節點
} dictIterator;
以下函數是這個迭代器的 API ，它們的作用及相關算法復雜度：
| 函數 | 作用 | 算法復雜度 |
|---|
| dictGetIterator | 創建一個不安全迭代器。 | O(1) |
| dictGetSafeIterator | 創建一個安全迭代器。 | O(1) |
| dictNext | 返回迭代器指向的當前節點，如果迭代完畢，返回 NULL 。 | O(1) |
| dictReleaseIterator | 釋放迭代器。 | O(1) |
- 字典由鍵值對構成的抽象數據結構。
- Redis 中的數據庫和哈希鍵都基于字典來實現。
- Redis 字典的底層實現為哈希表，每個字典使用兩個哈希表，一般情況下只使用 0 號哈希表，只有在 rehash 進行時，才會同時使用 0 號和 1 號哈希表。
- 哈希表使用鏈地址法來解決鍵沖突的問題。
- Rehash 可以用于擴展或收縮哈希表。
- 對哈希表的 rehash 是分多次、漸進式地進行的。