上一節說過, 擴展或收縮哈希表需要將?`ht[0]`?里面的所有鍵值對 rehash 到?`ht[1]`?里面, 但是, 這個 rehash 動作并不是一次性、集中式地完成的, 而是分多次、漸進式地完成的。
這樣做的原因在于, 如果?`ht[0]`?里只保存著四個鍵值對, 那么服務器可以在瞬間就將這些鍵值對全部 rehash 到?`ht[1]`?; 但是, 如果哈希表里保存的鍵值對數量不是四個, 而是四百萬、四千萬甚至四億個鍵值對, 那么要一次性將這些鍵值對全部 rehash 到?`ht[1]`?的話, 龐大的計算量可能會導致服務器在一段時間內停止服務。
因此, 為了避免 rehash 對服務器性能造成影響, 服務器不是一次性將?`ht[0]`?里面的所有鍵值對全部 rehash 到?`ht[1]`?, 而是分多次、漸進式地將?`ht[0]`?里面的鍵值對慢慢地 rehash 到?`ht[1]`?。
以下是哈希表漸進式 rehash 的詳細步驟:
1. 為?`ht[1]`?分配空間, 讓字典同時持有?`ht[0]`?和?`ht[1]`?兩個哈希表。
2. 在字典中維持一個索引計數器變量?`rehashidx`?, 并將它的值設置為?`0`?, 表示 rehash 工作正式開始。
3. 在 rehash 進行期間, 每次對字典執行添加、刪除、查找或者更新操作時, 程序除了執行指定的操作以外, 還會順帶將?`ht[0]`?哈希表在?`rehashidx`?索引上的所有鍵值對 rehash 到?`ht[1]`?, 當 rehash 工作完成之后, 程序將?`rehashidx`?屬性的值增一。
4. 隨著字典操作的不斷執行, 最終在某個時間點上,?`ht[0]`?的所有鍵值對都會被 rehash 至?`ht[1]`?, 這時程序將?`rehashidx`?屬性的值設為?`-1`?, 表示 rehash 操作已完成。
漸進式 rehash 的好處在于它采取分而治之的方式, 將 rehash 鍵值對所需的計算工作均灘到對字典的每個添加、刪除、查找和更新操作上, 從而避免了集中式 rehash 而帶來的龐大計算量。
圖 4-12 至圖 4-17 展示了一次完整的漸進式 rehash 過程, 注意觀察在整個 rehash 過程中, 字典的?`rehashidx`?屬性是如何變化的。






## 漸進式 rehash 執行期間的哈希表操作
因為在進行漸進式 rehash 的過程中, 字典會同時使用?`ht[0]`?和?`ht[1]`?兩個哈希表, 所以在漸進式 rehash 進行期間, 字典的刪除(delete)、查找(find)、更新(update)等操作會在兩個哈希表上進行: 比如說, 要在字典里面查找一個鍵的話, 程序會先在?`ht[0]`?里面進行查找, 如果沒找到的話, 就會繼續到?`ht[1]`?里面進行查找, 諸如此類。
另外, 在漸進式 rehash 執行期間, 新添加到字典的鍵值對一律會被保存到?`ht[1]`?里面, 而?`ht[0]`?則不再進行任何添加操作: 這一措施保證了?`ht[0]`?包含的鍵值對數量會只減不增, 并隨著 rehash 操作的執行而最終變成空表。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤