我正在參與掘金創(chuàng)作者訓練營第4期，點擊了解活動詳情，一起學習吧！

咱們接著上一部分來進行分享，我們可以在如下地址下載 redis 的源碼：

https://redis.io/download

此處我下載的是 redis-6.2.5 版本的，xdm 可以直接下載上圖中的 **redis-6.2.6 **版本，

redis 中 hash 表的數(shù)據(jù)結構

redis hash 表的數(shù)據(jù)結構定義在：

redis-6.2.5\src\dict.h

哈希表的結構，每一個字典都有兩個實現(xiàn)從舊表到新表的增量重哈希

typedef?struct?dictht?{
????dictEntry?**table;
????unsigned?long?size;
????unsigned?long?sizemask;
????unsigned?long?used;
}?dictht;


table：

table 是一個二級指針，對應這一個數(shù)組，數(shù)組中的每個元素都是指向了一個 dictEntry 結構體指針的，dictEntry 具體的數(shù)據(jù)結構是保存一個鍵值對

具體的 ?dictEntry ?數(shù)據(jù)結構是這樣的：

size：

size 屬性是記錄了整個 hash 表的大小，也可以理解為上述 table 數(shù)組的大小

sizemask：

sizemask 屬性，和具體的 hash 值來一起決定鍵要放在 table 數(shù)組的哪個位置

sizemask ?的值，總是會比 size 小 1 ，我們可以來演示一下

使用取余的方式，實際上是很低效的，咱們的計算機是不會做乘除法的，同樣都是用加減法來進行處理的，為了高效處理，我們可以使用二進制的方式

使用二進制的方式，就會用到該字段 sizemask ，主要是用來 和 具體的 hash 值做按位與操作

如圖就很明確了， size = 4，sizemask = 3，hash 值為 7， 最后 hash 值 & sizemask = 0011， 也就是 3，因此就會插入到上圖的具體位置

used：

used 屬性表示 hash 表里面已經(jīng)有鍵值對的數(shù)量

對于上述的案例，可以用一個簡圖來表示一下 hash 表結構 dictht

dictEntry 結構每個屬性的含義

typedef?struct?dictEntry?{
????void?*key;
????union?{
????????void?*val;
????????uint64_t?u64;
????????int64_t?s64;
????????double?d;
????}?v;
????struct?dictEntry?*next;
}?dictEntry;


上面我們看到數(shù)組中的節(jié)點信息，是 ?dictEntry 結構，屬性分別是這些意思：

• key

  具體的 redis 鍵

• union v

• val

  指向不同類型的數(shù)據(jù)，此處是 void * ，使用該類型，是為了節(jié)省內存

• u64

  用于 redis 集群中的哨兵模式和選舉模式

• s64

  記錄過期時間的

• next

  指向下一個節(jié)點的指針

dict 結構

在 src\dict.h 文件中，咱們接著往下看，能夠看到一個非常關鍵的結構，就是 dict ，redis 中都是使用這個結構來進行組織的

typedef?struct?dict?{
????dictType?*type;
????void?*privdata;
????dictht?ht[2];
????long?rehashidx;?/*?rehashing?not?in?progress?if?rehashidx?==?-1?*/
????int16_t?pauserehash;?/*?If?>0?rehashing?is?paused?(<0?indicates?coding?error)?*/
}?dict;


• type

字段對應的操作函數(shù)，具體有哪些操作函數(shù)，我們可以看到typedef struct dictType 給出的信息

• privdata

字典依賴的數(shù)據(jù)，例如 redis 具體的操作等等

• ht[2]

hash 表的鍵值對，放在此處，一個舊的，一個新的

ht[0] ：是擴容前的數(shù)組

ht[1]：是擴容后的數(shù)組

這個是當數(shù)據(jù)量大的時候，用于漸進式 rehash 的

• rehashidx

來指定具體 rehash 的位置，對應到 ht[0] 的索引上，rehashidx == -1 ，就是沒有進行再 hash ， rehashidx != -1 ?時，說明正在進行再 hash

還記得我們之前說到 redis 有 16 個 db 嗎？

我們在 redis 源碼中 src\server.h 也能夠看到 redisdb 的數(shù)據(jù)結構

我們可以看到 dict 這個字典，是 redis 中使用是相當頻繁和關鍵的

上面有說到 ?ht[2] 會用在漸進式 rehash 上，那么為什么要用漸進式 rehash 以及他是如何做的？

擴容的時候，會觸發(fā) rehash

當數(shù)據(jù)量很大的時候，會涉及到擴容，若一次性從 ht[0] 拷貝到 ht[1] 是比較慢的，會阻塞其他操作，那么就沒有辦法處理其他請求了，因為 redis 是單線程處理任務的

ht[0] 數(shù)據(jù)拷貝到 ht[1] ?的方式一

是這樣進行 rehash 的 ：

擴容的時候，rehash 是這樣做的：

• 先會對上述說到的 ht[1] 開辟內存空間，會將 ht[0].size * 2 給到 ht[1]

• 然后再將 ht[0] 的數(shù)據(jù)，從 ht[0][0] ... ht[0][size-1] 將數(shù)據(jù)拷貝到 ht[1] 里面

如何做到漸進式呢？

使用分而治之的思想，無論 redis 目前是否在做持久化的時候，當我們每次操作 redis 增刪改查，就會進行邊枚舉邊篩查的方式，逐步的將 ht[0][0] ... ht[0][size-1] rehash 到 ht[1] 中

可以追一下代碼流程 ， 我們從 src\server.c 注冊 setCommand 命令開始追起，代碼設計關鍵流程如下

當追到 dictAddRaw 函數(shù)的時候，我們可以清晰的看出來，當 redis 加入數(shù)據(jù)的時候，使用的是頭插法

• 先對新的節(jié)點開辟相應的內存

• 將新建節(jié)點的 next 對象指向鏈表的頭

• 然后將鏈表的頭指向新建的節(jié)點地址，即完成了一次 頭插

此處我們可以看到，實際上是做了一次 rehash

追到 dictRehash 函數(shù)的時候，可以看到此處的再 hash 函數(shù) dictRehash，我們可以看到 rehash 的做法是：

• 在 ht[0] 數(shù)組中，取得 rehashidx 對應的桶，或者腳數(shù)組對應的索引位置

• 通過上述找到的索引位置，取 ht[0].table[d->rehashidx] 對應的鏈表

• 然后將鏈表中的數(shù)據(jù)依次進行 rehash

此處 dictRehash ?的 ?n 的參數(shù)，表示再 hash 的次數(shù)，再 hash ?1 次，表示對于數(shù)組的這個桶對應的鏈表上的所有數(shù)據(jù)，進行一輪 hash

可以看到代碼中

?/*?Get?the?index?in?the?new?hash?table?*/
??h?=?dictHashKey(d,?de->key)?&?d->ht[1].sizemask;


此處正是 dictHashKey 計算出一個整數(shù)，然后和我們 dictht 中的 sizemask 進行一次按位與操作 ， 旨在得到一個新的 hash 表索引位置

redis 調用 ?_dictRehashStep 的位置

通過查看代碼中調用 _dictRehashStep 函數(shù)的位置并不多，我們一次查看調用關系，我們會知道確實是當我們每次操作 redis 增刪改查的時候，會發(fā)生漸進式的 rehash ， 這些是在我們進行擴容之后，如何將 ht[0] 的數(shù)據(jù)拷貝到 ht[1] 的實現(xiàn)方式

實際 redis 中涉及到如上幾個函數(shù) 都會調用 _dictRehashStep：

• dictAddRaw

• dictGenericDelete

• dictFind

• dictGetRandomKey

• dictGetSomeKeys

ht[0] 數(shù)據(jù)拷貝到 ht[1] ?的方式二

定時器調用 dictRehash的邏輯

當 redis 中沒有持久化操作的時候，redis 中的定時操作就會就會走定時的邏輯，邏輯是這樣的

我們可以在 redis 源碼中搜索使用 dictRehash 函數(shù)的位置

使用的位置也并不多，我們很容易就能找到按照毫秒級別來定時操作的位置

dictRehashMilliseconds

此處的邏輯是，while 循環(huán)是以 100 次 rehash 為一輪，時間限制是 1ms，只要時間不超過 1ms，能做的 rehash 次數(shù)至少是 100 次（每一輪 100 次），若超過 1 ms，則會立刻結束本次定時操作

此處我們可以看到，dictRehash(d,100) 傳遞的參數(shù)是 100，表示 rehash 100 次，還記得之前的漸進式 rehash 是 傳入的 1 次 嗎，可以往上看看文章內容

今天就到這里，學習所得，若有偏差，還請斧正

歡迎點贊，關注，收藏

朋友們，你的支持和鼓勵，是我堅持分享，提高質量的動力

好了，本次就到這里

技術是開放的，我們的心態(tài)，更應是開放的。擁抱變化，向陽而生，努力向前行。

我是阿兵云原生，歡迎點贊關注收藏，下次見~