一、鍵值對的結(jié)構(gòu)
了解 Redis 朋友的都知道，Redis 是一種鍵值對 ( Key-Value Pair ) 數(shù)據(jù)庫，在內(nèi)存中鍵值對是以字典 ( Dict ) 的方式保存的，而字典的底層其實是通過 哈希表 來實現(xiàn)的。通過哈希表中的節(jié)點保存字典中的鍵值對。而這個哈希表的數(shù)據(jù)結(jié)構(gòu)就是一個數(shù)組。
也就是說當(dāng)我們添加或修改數(shù)據(jù)時，只需要計算出鍵的哈希值，然后，跟數(shù)組的大小取模，就可以很快的定位到它所對應(yīng)的哈希桶的位置。所以，哈希表的最大好處就是我們可用O(1)的時間復(fù)雜度來快速查找鍵值對。(如下圖所示)。
[圖片上傳失敗...(image-2f13f0-1617843426474)]
但是，這里存在一個問題，就是當(dāng)存入的鍵之間計算的哈希值相同時，就會出現(xiàn)鍵沖突的問題。那么，Redis是如何解決的呢？
二、鍵的哈希值沖突了怎么辦
當(dāng)往 Redis寫入大量的數(shù)據(jù)時，不可避免的會出現(xiàn)鍵沖突的問題。這里的哈希沖突，也就是指，兩個 key 的哈希值和哈希桶計算對應(yīng)關(guān)系時，正好落在了同一個哈希桶中。畢竟，哈希桶的個數(shù)通常要少。
Redis 解決沖突的方式，跟 Java中的 HashMap 相同，也是以鏈表的方式解決的。也就是當(dāng)多個鍵的哈希值相同，落到同一個哈希桶上時，它們之間以鏈表的形式保存。如下圖所示：
但是，這里存在一個問題，哈希沖突鏈上的元素只能通過指針逐一查找再操作。如果哈希表里寫入的數(shù)據(jù)越來越多，哈希沖突可能也會越來越多，這就會導(dǎo)致某些哈希沖突鏈過長，進(jìn)而導(dǎo)致這個鏈上的元素查找耗時長，效率降低。對于追求“快”的 Redis 來說，這是不太能接受的。
所以，Redis 是通過擴(kuò)容，也就是擴(kuò)大哈希表的長度來解決此問題。
三、Redis中的Rehash
Redis 中是通過對哈希表進(jìn)行 Rehash 操作，也就是增加現(xiàn)有哈希桶的數(shù)量，讓主鍵增多的 數(shù)據(jù)能在更多的哈希桶之間分散保存，減少了每個桶中的元素數(shù)量，從而減少單個桶中的沖突。那它具體是怎么做的呢？
1、字典結(jié)構(gòu)
我們先通過Redis 源碼看看 它的字典 ( dict )結(jié)構(gòu)是如何實現(xiàn)。
/* 源碼文件 src\dict.h */
/* 哈希表
* 每個字典都使用兩個哈希表，以實現(xiàn)漸進(jìn)式 rehash 。
*/
typedef struct dictht {
dictEntry **table; // 哈希表數(shù)組
unsigned long size; // 哈希表大小
unsigned long sizemask; // 哈希表大小掩碼，用于計算索引值，總是等于 size - 1
unsigned long used; // 該哈希表 已有節(jié)點數(shù)量
} dictht;
// Redis 中的字典結(jié)構(gòu)
typedef struct dict {
dictType *type; // 類型特定函數(shù)
void *privdata; // 私有數(shù)據(jù)
dictht ht[2]; // 哈希表
long rehashidx; /* Rehash 索引，當(dāng)不在進(jìn)行Rehash時 值為 -1 */
unsigned long iterators; /* 目前正在運行的安全迭代器的數(shù)量 */
} dict;
由 Redis 源碼我們不難發(fā)現(xiàn)，在 dict 結(jié)構(gòu)中定義了兩個 dictht ，也就是存在兩個哈希表。Redis 這么做的目的就是為了使 rehash 操作更高效。Redis 正常情況下都是使用 哈希表1( 即 dict->ht[0] )，哈希表2( 即 dict->ht[1] )并不會分配空間，只有當(dāng)數(shù)據(jù)不斷增多，需要進(jìn)行 rehash 時采用用到 哈希表2。
2、何時 rehash
在 Redis 中是跟 Java 中的 HashMap 一樣，也是當(dāng)哈希表中保存的元素達(dá)到某個閾值的時候，就會觸發(fā) rehash操作。同樣我們也通過 Redis 源碼來看看它是什么時候觸發(fā)的。
/*源碼文件 src\dict.c */
// 添加元素
int dictAdd(dict *d, void *key, void *val){
// 掉方法 dictAddRaw
dictEntry *entry = dictAddRaw(d,key,NULL);
// 省略部分代碼
return DICT_OK;
}
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){
long index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d); // 判斷是否整在進(jìn)行 rehash
/*
* 獲取新元素 在哈希表中的下標(biāo)，如果已經(jīng)存在返回 -1
*/
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
// 省略部分代碼
return entry;
}
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing){
unsigned long idx, table;
dictEntry *he;
if (existing) *existing = NULL;
/* Expand the hash table if needed */
/* 判斷 是否需要進(jìn)行擴(kuò)容 */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
// 省略部分代碼
return idx;
}
/* 判斷是否需要進(jìn)行擴(kuò)容操作 */
static int _dictExpandIfNeeded(dict *d){
/* 如果正在進(jìn)行 rehash 則直接返回 OK. */
if (dictIsRehashing(d)) return DICT_OK;
/* 如果當(dāng)前 哈希表1 為空，即第一次添加元素，則直接創(chuàng)建 */
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/*
* 如果當(dāng)前已有元素大于等于哈希表的大小，并且允許 rehash 或者已經(jīng)
* 超過了安全閾值，則進(jìn)行擴(kuò)容操作
*
*/
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
說明：
1、d->ht[0].used >= d->ht[0].size 判斷哈希表1 中的已有元素是否大于等于哈希表的長度。
2、dict_can_resize 是否允許進(jìn)行 rehash 的標(biāo)準(zhǔn) ，0-不允許，1-允許。當(dāng) redis 正在進(jìn)行 生成 RDB 快照或者 重新AOF 文件時，此值設(shè)置為0
3、d->ht[0].used/d->ht[0].size > dict_force_resize_ratio 判斷哈希表 中的已有元素與哈希表長度的比率是超過安全比率 dict_force_resize_ratio。 dict_force_resize_ratio 值為 5。
總結(jié)，當(dāng) Redis 中哈希表中的已有元素個數(shù)大于等于哈希表的長度，并且 Redis 不在處于 正在生產(chǎn) RDB快照或者重寫AOF文件，或者 哈希表已有元素個與哈希表的長度的比率大于 5 時，就會觸發(fā) rehash 操作。
<span style="color: #FF0000">強(qiáng)調(diào)：Redis中的閾值時固定，不可改的。</span>
3、rehash 步驟
擴(kuò)展和收縮哈希表的工作可以通過執(zhí)行rehash（重新散列）操作來完成，Redis 中執(zhí)行 rehash 的步驟如下：
-
給哈希表2 ( ht[1] )分配的空間。這個哈希表的空間大小取決于要執(zhí)行的操作，以及ht[0]當(dāng)前包含的鍵值對數(shù)量（也即是ht[0].used屬性的值）：
- 如果執(zhí)行的是擴(kuò)展操作，那么 ht[1] 的大小為第一個大于等于 ht[0].used*2 的 2 n（2的n次方冪）；
- 如果執(zhí)行的是收縮操作，那么 ht[1] 的大小為第一個大于等于 ht[0].used 的2 n
將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面：rehash指的是重新計算鍵的哈希值和索引值，然后將鍵值對放置到ht[1]哈希表的指定位置上。
當(dāng) ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之后（ht[0]變?yōu)榭毡恚?，釋放ht[0]，將ht[1]設(shè)置為ht[0]，并在ht[1]新創(chuàng)建一個空白哈希表，為下一次rehash做準(zhǔn)備。
上面的步驟看似很簡單，但是，我們知道 Redis 是單線程的，那么如果一次性把哈希表1中的數(shù)據(jù)全部遷移完，勢必會造成 Redis 線程阻塞，無法服務(wù)其他請求，此時，Redis 就無法快速訪問數(shù)據(jù)了。
為了避免這個問題，Redis 采用了 漸進(jìn)式rehash
4、漸進(jìn)式 rehash
何為漸進(jìn)式rehash ？簡單來說就是在第二步拷貝數(shù)據(jù)時，Redis 不是集中式的一次性完成的，而是分多次、漸進(jìn)式地完成的。 Redis 是把數(shù)據(jù)的遷移任務(wù)分散到了每次的請求中。
- 操作步驟
- 在字典中維護(hù)了一個 rehashidx 變量，當(dāng)開始 rehash 時，他的值設(shè)置為 0，也就是表示從哈希表1，索引0 開始。
- 在每次的 增、刪、改、查操作時，除了執(zhí)行指定操作之外，還會判斷是否正在 rehash，即 rehashidx != -1，如果是，就會順帶把 rehashidx 索引位置的 元素遷移到 哈希表2中。
- 隨著操作不斷的執(zhí)行，最終會在某個時間點上，哈希表1 中的所有鍵值都會被 rehash 到哈希表2中。這時會把rehashidx的值設(shè)置為 -1，表示 rehash 操作已完成。
如下圖所示：
-
源碼分析
由上面介紹的 rehash 觸發(fā)條件的源碼中我們可知當(dāng)滿足條件后回調(diào)用
dictExpand方法，那么我們看下此方法的詳細(xì)實現(xiàn)int dictExpand(dict *d, unsigned long size){ /* the size is invalid if it is smaller than the number of * elements already inside the hash table */ if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR; dictht n; /* the new hash table */ // 計算新表格的長度 unsigned long realsize = _dictNextPower(size); /* Rehashing to the same table size is not useful. */ if (realsize == d->ht[0].size) return DICT_ERR; /* Allocate the new hash table and initialize all pointers to NULL */ /* 分配一個新的 哈希表， 并且初始化所有的指針指向 null */ n.size = realsize; n.sizemask = realsize-1; n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; /* Is this the first initialization? If so it's not really a rehashing * we just set the first hash table so that it can accept keys. */ if (d->ht[0].table == NULL) { // 第一次創(chuàng)建 d->ht[0] = n; return DICT_OK; } /* Prepare a second hash table for incremental rehashing */ d->ht[1] = n; d->rehashidx = 0; // 把 rehash 標(biāo)志設(shè)置為 0， return DICT_OK; }此方法主要實現(xiàn)了以下功能：
- 計算需要擴(kuò)容的新的哈希表的大小
- 給哈希表分配空間，并且所有的指針都指向 null
- 把rehash索引 rehashidx 設(shè)置為 0，也就是說 rehash 是從哈希表 1 的 0 位桶開始拷貝。
接下來我們在看看，Redis中 增刪改查的代碼中是如何進(jìn)行 rehash 的。
/* 增加方法 */ dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){ long index; dictEntry *entry; dictht *ht; // 判斷是否整在進(jìn)行 rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 省略部分代碼 } /* 查詢方法 */ dictEntry *dictFind(dict *d, const void *key){ dictEntry *he; uint64_t h, idx, table; if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */ // 判斷是否整在進(jìn)行 rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 省略部分代碼 } /* 刪除方法 */ static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) { uint64_t h, idx; dictEntry *he, *prevHe; int table; if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL; // 判斷是否整在進(jìn)行 rehash if (dictIsRehashing(d)) _dictRehashStep(d); // 省略部分代碼 }有增、刪、查的方法我們可以發(fā)現(xiàn)所有的方法中都要
if (dictIsRehashing(d)) _dictRehashStep(d);這段代碼，此行代碼就是 判斷當(dāng)前是否正在進(jìn)行 rehash 也就是rehashidx != -1則進(jìn)行一步 rehash 操作。
5、定時輔助 rehash
由于，Redis 是漸進(jìn)的方式進(jìn)行 rehash 的，所以，在 Redis 中的鍵值對很多的情況下，那么，哈希表1 和 哈希表2 將共存很長時間，Redis 在漸進(jìn)式 rehash 的同時，還會在 Redis 空閑時也會定時輔助進(jìn)行 rehash 。
下面我們通過 Redis 源碼，看看是如何實現(xiàn)的。
- 調(diào)度方法
serverCron
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
// 省略部分代碼
/* We need to do a few operations on clients asynchronously. */
clientsCron();
/* 處理 Redis 數(shù)據(jù)庫后端操作，再次方法中執(zhí)行定時 rehash 操作 */
databasesCron();
// 省略部分代碼
}
-
databaseCron 方法
void databasesCron(void) { /* 處理過期鍵 */ if (server.active_expire_enabled) { if (server.masterhost == NULL) { activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW); } else { expireSlaveKeys(); } } /* Defrag keys gradually. */ if (server.active_defrag_enabled) activeDefragCycle(); /* 如果當(dāng)前系統(tǒng)沒有在 生成 RDB 快照或 重寫 AOF 文件，則進(jìn) */ if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) { // 省略部分代碼 /* Rehash 操作 */ if (server.activerehashing) { for (j = 0; j < dbs_per_call; j++) { int work_done = incrementallyRehash(rehash_db); if (work_done) { /* If the function did some work, stop here, we'll do * more at the next cron loop. */ break; } else { /* If this db didn't need rehash, we'll try the next one. */ rehash_db++; rehash_db %= server.dbnum; } } } } }說明：
可以在 redis.conf 配置文件中配置 activerehashing 的值是否啟動，定時輔助 rehash，默認(rèn)為 yes 啟動。
四、擴(kuò)展知識
1、rehash 期間如何查找值
因為在進(jìn)行漸進(jìn)式 rehash 的過程中，字典會同時使用 ht[0] 和 ht[1] 兩個哈希表，所以在漸進(jìn)式 rehash 進(jìn)行期間，字典的刪除（delete）、查找（find）、更新（update）等操作會在兩個哈希表上進(jìn)行。首先會現(xiàn)在 ht[0] 上查找，如果不存在，則到 ht[1] 上查找。
2、rehash期間有新增怎么存
在漸進(jìn)式 rehash 執(zhí)行期間，新添加到字典的鍵值對一律會被保存到 ht[1] 里面，而 ht[0] 則不再進(jìn)行任何添加操作，這一措施保證了 ht[0] 包含的鍵值對數(shù)量會只減不增，并隨著 rehash 操作的執(zhí)行而最終變成空表。
3、生成 RDB 文件或 重寫 AOF 期間為什么不能 rehash 操作
這是因為在 Redis 中是通過創(chuàng)建子進(jìn)程的方式，生成 RDB 快照或 重寫 AOF 文件的，而大多數(shù)操作系統(tǒng)都采用寫時復(fù)制（copy-on-write）技術(shù)來優(yōu)化子進(jìn)程的使用效率。因為 rehash 操作需要父進(jìn)程申請新的哈希表，所有在 生成RDB或 AOF重寫 期間，會造成父進(jìn)程大量的 COW操作，影響父進(jìn)程的性能。
說明：
如果負(fù)載因子大于一定值(固定為 5) 時，即時正在進(jìn)行 生成RDB 或 重寫 AOF 也會進(jìn)行 rehash 操作。
4、為什么rehash期間，允許RDB和AOF rewrite？
因為 rehash 已經(jīng)開始，說明新的哈希表內(nèi)存已經(jīng)申請完成了，之后的 rehash 過程只是遷移哈希桶下的數(shù)據(jù)指針，不涉及到內(nèi)存申請了，所以 RDB 和 AOF rewrite 沒影響。
五、小結(jié)
在 Redis 中是以 哈希表的方式來保存鍵值對數(shù)據(jù)的，但是隨著鍵值對的增多，會出現(xiàn) 哈希沖突的情況，這種情況，Redis 是以鏈表的方式解決哈希沖突的。當(dāng)鏈表變得很長時，會影響 Redis 的查找性能，為了減小 鏈表的長度，Redis 采用了 rehash 操作，也就是把擴(kuò)大當(dāng)前哈希表的長度，Redis 在 rehash 是不是一次性rehash ，而是采用了漸進(jìn)式方式，這樣可以解決長時間阻塞，在 漸進(jìn)式 rehash 的同時，Redis 在空閑時間也會進(jìn)行 1Ms 的定時 rehash。
