redis系列之------字典

来源:https://www.cnblogs.com/wenbochang/archive/2019/10/15/11673590.html
-Advertisement-
Play Games

前言 字典， 又稱符號表（symbol table）、關聯數組（associative array）或者映射（map）， 是一種用於保存鍵值對（key-value pair）的抽象數據結構。 在字典中， 一個鍵（key）可以和一個值（value）進行關聯（或者說將鍵映射為值）， 這些關聯的鍵和值就被 ...


前言

字典， 又稱符號表（symbol table）、關聯數組（associative array）或者映射（map）， 是一種用於保存鍵值對（key-value pair）的抽象數據結構。

在字典中， 一個鍵（key）可以和一個值（value）進行關聯（或者說將鍵映射為值）， 這些關聯的鍵和值就被稱為鍵值對。

字典中的每個鍵都是獨一無二的， 程式可以在字典中根據鍵查找與之關聯的值， 或者通過鍵來更新值， 又或者根據鍵來刪除整個鍵值對， 等等。

字典經常作為一種數據結構內置在很多高級編程語言裡面， 但 Redis 所使用的 C 語言並沒有內置這種數據結構， 因此 Redis 構建了自己的字典實現。

字典在 Redis 中的應用相當廣泛， 比如 Redis 的資料庫就是使用字典來作為底層實現的， 對資料庫的增、刪、查、改操作也是構建在對字典的操作之上的。

因此，瞭解字典對我們瞭解Redis資料庫有很大的幫助。同時可以跟Java的HashMap進行對比，看看孰好孰壞。

 

字典的定義

 1 typedef struct dict {
 2 
 3     // 類型特定函數
 4     dictType *type;
 5 
 6     // 私有數據
 7     void *privdata;
 8 
 9     // 哈希表
10     dictht ht[2];
11 
12     // rehash 索引
13     // 當 rehash 不在進行時，值為 -1
14     int rehashidx; /* rehashing not in progress if rehashidx == -1 */
15 
16 } dict;

主要看ht，和rehashidx兩個參數。

ht 屬性是一個包含兩個項的數組， 數組中的每個項都是一個 dictht 哈希表， 一般情況下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只會在對 ht[0] 哈希表進行 rehash 時使用。

除了 ht[1] 之外， 另一個和 rehash 有關的屬性就是 rehashidx ： 它記錄了 rehash 目前的進度， 如果目前沒有在進行 rehash ， 那麼它的值為 -1 。

 

 1 typedef struct dictht {
 2 
 3     // 哈希表數組
 4     dictEntry **table;
 5 
 6     // 哈希表大小
 7     unsigned long size;
 8 
 9     // 哈希表大小掩碼，用於計算索引值
10     // 總是等於 size - 1
11     unsigned long sizemask;
12 
13     // 該哈希表已有節點的數量
14     unsigned long used;
15 
16 } dictht;

table 屬性是一個數組， 數組中的每個元素都是一個指向 dict.h/dictEntry 結構的指針， 每個 dictEntry 結構保存著一個鍵值對。

size 屬性記錄了哈希表的大小， 也即是 table 數組的大小

sizemask 屬性的值總是等於 size-1 ， 這個屬性和哈希值一起決定一個鍵應該被放到 table 數組的哪個索引上面。(不是很清楚，為什麼要單獨定義一個mask，而不直接size-1)；

而 used 屬性則記錄了哈希表目前已有節點（鍵值對）的數量。

 

 1 typedef struct dictEntry {
 2 
 3     // 鍵
 4     void *key;
 5 
 6     // 值
 7     union {
 8         void *val;
 9         uint64_t u64;
10         int64_t s64;
11     } v;
12 
13     // 指向下個哈希表節點，形成鏈表
14     struct dictEntry *next;
15 
16 } dictEntry;

key 屬性保存著鍵值對中的鍵， 而 v 屬性則保存著鍵值對中的值， 其中鍵值對的值可以是一個指針， 或者是一個 uint64_t 整數， 又或者是一個 int64_t 整數。

next 屬性是指向另一個哈希表節點的指針， 這個指針可以將多個哈希值相同的鍵值對連接在一次， 以此來解決鍵衝突（collision）的問題。

可以明顯的看出來，redis是通過鏈表來解決hash衝突的。

 

因此，redis的字典大概如下：

 

 

 

 

                                                                   

 

                                   

 

Rehash

隨著操作的不斷執行， 哈希表保存的鍵值對會逐漸地增多或者減少， 為了讓哈希表的負載因數（load factor）維持在一個合理的範圍之內， 當哈希表保存的鍵值對數量太多或者太少時， 程式需要對哈希表的大小進行相應的擴展或者收縮。

也就是我們常說的，擴容，再次hash。

Redis rehash過程：

  • 為字典的 ht[1] 哈希表分配空間。一般為原字典的兩倍，即 ht[0] * 2；
  • 將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面
  • 當 ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之後 （ht[0] 變為空表）， 釋放 ht[0] ， 將 ht[1] 設置為 ht[0] ， 併在 ht[1] 新創建一個空白哈希表， 為下一次 rehash 做準備。

但其實rehash是非常的耗時間的。假設ht[0]非常的大呢？ 40W，400W，甚至4000W呢？

一次rehash甚至可能導致redis宕機，所以出現了漸進式hash。

 

漸進式Rehash

這個 rehash 動作並不是一次性、集中式地完成的， 而是分多次、漸進式地完成的。為了避免 rehash 對伺服器性能造成影響， 伺服器不是一次性將 ht[0] 裡面的所有鍵值對全部 rehash 到 ht[1] ， 而是分多次、漸進式地將 ht[0] 裡面的鍵值對慢慢地 rehash 到 ht[1] 。

  • 為 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 int dictRehash(dict *d, int n) {
 2     int empty_visits = n*10; /* Max number of empty buckets to visit. */
 3 
 4     // 判斷是否正在擴容
 5     if (!dictIsRehashing(d)) return 0;
 6 
 7     while(n-- && d->ht[0].used != 0) {
 8         dictEntry *de, *nextde;
 9 
10         /* Note that rehashidx can't overflow as we are sure there are more
11          * elements because ht[0].used != 0 */
12         assert(d->ht[0].size > (unsigned long)d->rehashidx);
13 
14         // 找到一個不為空的桶，進行遷移
15         while(d->ht[0].table[d->rehashidx] == NULL) {
16             d->rehashidx++;
17             if (--empty_visits == 0) return 1;
18         }
19         // 找到這個桶第一個指針節點
20         de = d->ht[0].table[d->rehashidx];
21         // 將這個桶中的所有的key節點轉移到新的數組中。while迴圈鏈表
22         while(de) {
23             uint64_t h;
24 
25             nextde = de->next;
26             /* Get the index in the new hash table */
27             h = dictHashKey(d, de->key) & d->ht[1].sizemask;
28             de->next = d->ht[1].table[h];
29             d->ht[1].table[h] = de;
30             d->ht[0].used--;
31             d->ht[1].used++;
32             de = nextde;
33         }
34         // 舊的桶節點置為null，並且rehashidx+1
35         d->ht[0].table[d->rehashidx] = NULL;
36         d->rehashidx++;
37     }
38 
39     /* Check if we already rehashed the whole table... */
40     if (d->ht[0].used == 0) {
41         zfree(d->ht[0].table);
42         d->ht[0] = d->ht[1];
43         _dictReset(&d->ht[1]);
44         d->rehashidx = -1;
45         return 0;
46     }
47 
48     /* More to rehash... */
49     return 1;
50 }

 

在進行漸進式 rehash 的過程中， 字典會同時使用 ht[0] 和 ht[1] 兩個哈希表， 所以在漸進式 rehash 進行期間， 字典的刪除（delete）、查找（find）、更新（update）等操作會在兩個哈希表上進行： 比如說， 要在字典裡面查找一個鍵的話， 程式會先在 ht[0]裡面進行查找， 如果沒找到的話， 就會繼續到 ht[1] 裡面進行查找， 諸如此類。

另外， 在漸進式 rehash 執行期間， 新添加到字典的鍵值對一律會被保存到 ht[1] 裡面， 而 ht[0] 則不再進行任何添加操作： 這一措施保證了 ht[0] 包含的鍵值對數量會只減不增， 並隨著 rehash 操作的執行而最終變成空表。

 

所遇到問提

問題一：

要在字典裡面查找一個鍵的話， 程式會先在 ht[0]裡面進行查找， 如果沒找到的話， 就會繼續到 ht[1] 裡面進行查找， 諸如此類。

這一點其實我比較有疑惑？為何要先去ht[0]中查找，找不到再去ht[1]中查找，這樣豈不是效率低下，查找了兩張表。不能根據hash值和rehashidx進行比較判斷麽？只查一張表不行麽？

為此我翻閱了不少資料：

這是redis官方其他人的pull request：https://github.com/antirez/redis/pull/5692    暫時還沒有merge

同時這是我和一位大佬的討論：https://github.com/Junnplus/blog/issues/35   最終得出結論

還是看源碼：(源碼真是一個好東西)

 1 for (table = 0; table <= 1; table++) {
 2     // 找到key的index
 3     idx = h & d->ht[table].sizemask;
 4     // 拿到key值對應的value
 5     he = d->ht[table].table[idx];
 6     while(he) {
 7         if (key==he->key || dictCompareKeys(d, key, he->key))
 8             return he;
 9         he = he->next;
10     }
11     if (!dictIsRehashing(d)) return NULL;
12 }

其實只有兩種情況

  • key在ht[0]，還沒有遷移
  • key在ht[1]，已經遷移了。

針對第一種情況，他在第一層的迴圈已經找到了key值，並且返回(第八行)，不再繼續後面操作，因此不存在效率問題。

第二種情況，看第五行，he此時為null，根本不會迴圈鏈表。然後第二次迴圈才能找到key。而第一次是做了一次hash，複雜度為O(1)。效率幾乎是沒有損失，因此也不存在效率問題。

綜上：我得出的結論是。可以拿idx和rehashidx進行對比，同時也可以像redis這樣寫，不會損失效率。redis可能為了代碼的簡潔以及統一，不想寫那麼多的判斷條件，因此沒有比較idx和rehashidx。

當我認為提前結束會更好，畢竟不用後續判斷了，也比較清楚。類似這個request：https://github.com/antirez/redis/pull/5692/files

 

問題二：

假如在redis準備進行rehash的時候，他需要為ht[1]申請一塊記憶體，這塊記憶體可是ht[0]的兩倍哦，那次是電腦記憶體不存會如何？

梳理一下哈希表大小和記憶體申請大小的對應關係：

                                                                         

正常狀態下，redis為ht[1]分配完記憶體後，會持續一段時間進行rehash。rehash完畢後，就會釋放ht[0]記憶體了。類似如下圖：

記憶體先上升，後下降。

 

但此時記憶體不存的話，Redis會進行大量的Key驅逐，也就是會淘汰掉很久未使用的key，跟LRU有點類似。

那麼此時可能就會影響到了業務，這是非常大的問題呢。

那麼針對在Redis滿容驅逐狀態下，如何避免因Rehash而導致Redis抖動的這種問題。

  • 我們在Redis Rehash源碼實現的邏輯上，加上了一個判斷條件，如果現有的剩餘記憶體不夠觸發Rehash操作所需申請的記憶體大小，即不進行Resize操作；
  • 通過提前運營進行規避，比如容量預估時將Rehash占用的記憶體考慮在內，或者通過監控定時擴容。

 

 

 

參考文獻：

《redis設計與實現》  http://redisbook.com/preview/dict/incremental_rehashing.html

《美團針對Redis Rehash機制的探索和實踐》  https://tech.meituan.com/2018/07/27/redis-rehash-practice-optimization.html

《Redis源碼分析》  https://github.com/Junnplus/blog/issues/35

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Ubuntu安裝scrcpy手機投屏和控制(Ubuntu用QQ微信的另一種方法)
    Scrcpy 安裝 adb服務安裝 adb配置 查看手機的USB識別號 手機通過USB連接電腦 找打自己手機的識別號, 我是04e8:6860 創建設備文件 下麵所有的 改成自己的識別號, 文件名可自定義 在文件中輸入: 保存後修改文件許可權 啟動adb服務 有設備就說明成功了, 如果沒有看看自己手機 ...
  • Centos7啟動流程及systemd中Nginx啟動配置
    Centos7啟動流程： 1.post(Power-On-Self-Test) 加電自檢 2. bootsequence(BIOS,選擇啟動設備) 3.bootloader(MBR) 4.kernel初始化 5.init管理用戶空間服務進程 編寫Nginx的systemd配置文件， 實現nginx進 ...
  • Mac 下安裝配置MongoDB講解
    1.訪問官網地址是：MongoDB Download Center | MongoDB，一般下載server的Community 版，對於一般開發人員來說已經夠用了。 2、點擊“DOWNLOAD(tgz)”按鈕，將解壓後的文件放入 /usr/local ，預設情況下在Finder中是看不到 /usr ...
  • MySQL的表定義語法
    表定義 只有成功創建資料庫後，才能創建數據表，數據表是欄位的集合，在表中數據按行和列的格式存儲 創建表 MySQL 使用 CREATE TABLE 創建表。其中有多個選擇，主要由表創建定義（create definition）、表選項定義（table options） 和區分選項（partition ...
  • 一、MySQL基礎知識
    一、背景介紹 我們每天都在訪問各種網站、APP，如微信、QQ、抖音，今日頭條等，這些東西上面都存在大量的信息，這些信息都需要有地方存儲，存儲在哪裡呢？資料庫。 所有我們需要開發一個網站、APP，資料庫我們必須掌握的技術。常用的資料庫有mysql,oracle、sqlserver、db2等。 orac ...
  • linux下安裝oracle資料庫--乾貨
    1、修改系統名稱，關閉防火牆，selinux。2、掛載鏡像,並寫入開機自動掛載。掛載點為/mnt/yummount -t iso9660 -o,loop /soft/Centos6.iso /mnt/yum3、查看swap分區大小2G以下配置swap2G*1.5=3G2G-16G配置相同G16G以上 ...
  • docker部署redis集群
    一、查詢最新redis鏡像 docker search redis 二、下載redis鏡像 docker pull redis 三、創建一個文件夾，以及創建redis-cluster.tmpl模板文件 mkdir redis-cluster-d cd redis-cluster-d port ${P ...
  • 能寫數據後臺，需要掌握哪些進階的sql語句？
    國慶假期花了一些時間，首次嘗試並玩轉 `grafana`，這幾天繼續不斷優化和完善，如今看著自己的成果，相當滿意。——逐步接近我想要的理想後臺啦。這篇筆記把這幾天玩轉 `grafana` 時用到的進階版的 `sql` 語句整理出來。 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類