跋山涉水 —— 深入 Redis 字典遍歷

來自專欄碼洞9 人贊了文章

Redis 字典的遍歷過程邏輯比較複雜，互聯網上對這一塊的分析講解非常少。我也花了不少時間對源碼的細節進行了整理，將我個人對字典遍歷邏輯的理解呈現給各位讀者。也許讀者們對字典的遍歷過程有比我更好的理解，還請不吝指教。

一邊遍歷一邊修改

我們知道 Redis 對象樹的主幹是一個字典，如果對象很多，這個主幹字典也會很大。當我們使用 keys 命令搜尋指定模式的 key 時，它會遍歷整個主幹字典。值得注意的是，在遍歷的過程中，如果滿足模式匹配條件的 key 被找到了，還需要判斷 key 指向的對象是否已經過期。如果過期了就需要從主幹字典中將該 key 刪除。

void keysCommand(client *c) { dictIterator *di; // 迭代器 dictEntry *de; // 迭代器當前的entry sds pattern = c->argv[1]->ptr; // keys的匹配模式參數 int plen = sdslen(pattern); int allkeys; // 是否要獲取所有key，用於keys *這樣的指令 unsigned long numkeys = 0; void *replylen = addDeferredMultiBulkLength(c); // why safe? di = dictGetSafeIterator(c->db->dict); allkeys = (pattern[0] == * && pattern[1] == ); while((de = dictNext(di)) != NULL) { sds key = dictGetKey(de); robj *keyobj; if (allkeys || stringmatchlen(pattern,plen,key,sdslen(key),0)) { keyobj = createStringObject(key,sdslen(key)); // 判斷是否過期，過期了要刪除元素 if (expireIfNeeded(c->db,keyobj) == 0) { addReplyBulk(c,keyobj); numkeys++; } decrRefCount(keyobj); } } dictReleaseIterator(di); setDeferredMultiBulkLength(c,replylen,numkeys);}

那麼，你是否想到了其中的困難之處，在遍歷字典的時候還需要修改字典，會不會出現指針安全問題？

重複遍歷

字典在擴容的時候要進行漸進式遷移，會存在新舊兩個 hashtable。遍歷需要對這兩個 hashtable 依次進行，先遍歷完舊的 hashtable，再繼續遍歷新的 hashtable。如果在遍歷的過程中進行了 rehashStep，將已經遍歷過的舊的 hashtable 的元素遷移到了新的 hashtable中，那麼遍歷會不會出現元素的重複？這也是遍歷需要考慮的疑難之處，下面我們來看看 Redis 是如何解決這個問題的。

迭代器的結構

Redis 為字典的遍歷提供了 2 種迭代器，一種是安全迭代器，另一種是不安全迭代器。

typedef struct dictIterator { dict *d; // 目標字典對象 long index; // 當前遍歷的槽位置，初始化為-1 int table; // ht[0] or ht[1] int safe; // 這個屬性非常關鍵，它表示迭代器是否安全 dictEntry *entry; // 迭代器當前指向的對象 dictEntry *nextEntry; // 迭代器下一個指向的對象 long long fingerprint; // 迭代器指紋，放置迭代過程中字典被修改} dictIterator;// 獲取非安全迭代器，只讀迭代器，允許rehashStepdictIterator *dictGetIterator(dict *d){ dictIterator *iter = zmalloc(sizeof(*iter)); iter->d = d; iter->table = 0; iter->index = -1; iter->safe = 0; iter->entry = NULL; iter->nextEntry = NULL; return iter;}// 獲取安全迭代器，允許觸發過期處理，禁止rehashStepdictIterator *dictGetSafeIterator(dict *d) { dictIterator *i = dictGetIterator(d); i->safe = 1; return i;}

迭代器的「安全」指的是在遍歷過程中可以對字典進行查找和修改，不用感到擔心，因為查找和修改會觸發過期判斷，會刪除內部元素。「安全」的另一層意思是迭代過程中不會出現元素重複，為了保證不重複，就會禁止 rehashStep。

而「不安全」的迭代器是指遍歷過程中字典是只讀的，你不可以修改，你只能調用 dictNext 對字典進行持續遍歷，不得調用任何可能觸發過期判斷的函數。不過好處是不影響 rehash，代價就是遍歷的元素可能會出現重複。

安全迭代器在剛開始遍歷時，會給字典打上一個標記，有了這個標記，rehashStep 就不會執行，遍歷時元素就不會出現重複。

typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; // 這個就是標記，它表示當前加在字典上的安全迭代器的數量 unsigned long iterators;} dict;// 如果存在安全的迭代器，就禁止rehashstatic void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1);}

迭代過程

安全的迭代器在遍歷過程中允許刪除元素，意味著字典第一維數組下面掛接的鏈表中的元素可能會被摘走，元素的 next 指針就會發生變動，這是否會影響迭代過程呢？下面我們仔細研究一下迭代函數的代碼邏輯。

dictEntry *dictNext(dictIterator *iter){ while (1) { if (iter->entry == NULL) { // 遍歷一個新槽位下面的鏈表，數組的index往前移動了 dictht *ht = &iter->d->ht[iter->table]; if (iter->index == -1 && iter->table == 0) { // 第一次遍歷，剛剛進入遍歷過程 // 也就是ht[0]數組的第一個元素下面的鏈表 if (iter->safe) { // 給字典打安全標記，禁止字典進行rehash iter->d->iterators++; } else { // 記錄迭代器指紋，就好比字典的md5值 // 如果遍歷過程中字典有任何變動，指紋就會改變 iter->fingerprint = dictFingerprint(iter->d); } } iter->index++; // index=0，正式進入第一個槽位 if (iter->index >= (long) ht->size) { // 最後一個槽位都遍歷完了 if (dictIsRehashing(iter->d) && iter->table == 0) { // 如果處於rehash中，那就繼續遍歷第二個 hashtable iter->table++; iter->index = 0; ht = &iter->d->ht[1]; } else { // 結束遍歷 break; } } // 將當前遍歷的元素記錄到迭代器中 iter->entry = ht->table[iter->index]; } else { // 直接將下一個元素記錄為本次迭代的元素 iter->entry = iter->nextEntry; } if (iter->entry) { // 將下一個元素也記錄到迭代器中，這點非常關鍵 // 防止安全迭代過程中當前元素被過期刪除後，找不到下一個需要遍歷的元素 // 試想如果後面發生了rehash，當前遍歷的鏈表被打散了，會發生什麼 // 這裡要使勁發揮自己的想像力來理解 // 舊的鏈表將一分為二，打散後重新掛接到新數組的兩個槽位下 // 結果就是會導致當前鏈表上的元素會重複遍歷 // 如果rehash的鏈表是index前面的鏈表，那麼這部分鏈表也會被重複遍歷 iter->nextEntry = iter->entry->next; return iter->entry; } } return NULL;}// 遍歷完成後要釋放迭代器，安全迭代器需要去掉字典的禁止rehash的標記// 非安全迭代器還需要檢查指紋，如果有變動，伺服器就會奔潰(failfast)void dictReleaseIterator(dictIterator *iter){ if (!(iter->index == -1 && iter->table == 0)) { if (iter->safe) iter->d->iterators--; // 去掉禁止rehash的標記 else assert(iter->fingerprint == dictFingerprint(iter->d)); } zfree(iter);}// 計算字典的指紋，就是將字典的關鍵欄位進行按位糅合到一起// 這樣只要有任意的結構變動，指紋都會發生變化// 如果只是某個元素的value被修改了，指紋不會發生變動long long dictFingerprint(dict *d) { long long integers[6], hash = 0; int j; integers[0] = (long) d->ht[0].table; integers[1] = d->ht[0].size; integers[2] = d->ht[0].used; integers[3] = (long) d->ht[1].table; integers[4] = d->ht[1].size; integers[5] = d->ht[1].used; for (j = 0; j < 6; j++) { hash += integers[j]; hash = (~hash) + (hash << 21); hash = hash ^ (hash >> 24); hash = (hash + (hash << 3)) + (hash << 8); hash = hash ^ (hash >> 14); hash = (hash + (hash << 2)) + (hash << 4); hash = hash ^ (hash >> 28); hash = hash + (hash << 31); } return hash;}

值得注意的是在字典擴容時進行rehash，將舊數組中的鏈表遷移到新的數組中。某個具體槽位下的鏈表只可能會遷移到新數組的兩個槽位中。

hash mod 2^n = khash mod 2^(n+1) = k or k+2^n

迭代器的選擇

除了keys指令使用了安全迭代器，因為結果不允許重複。那還有其它的地方使用了安全迭代器么，什麼情況下遍歷適合使用非安全迭代器呢？

簡單一點說，那就是如果遍歷過程中不允許出現重複，那就使用SafeIterator，比如下面的兩種情況

1. bgaofrewrite需要遍歷所有對象轉換稱操作指令進行持久化，絕對不允許出現重複
2. bgsave也需要遍歷所有對象來持久化，同樣不允許出現重複

如果遍歷過程中需要處理元素過期，需要對字典進行修改，那也必須使用SafeIterator，因為非安全的迭代器是只讀的。

其它情況下，也就是允許遍歷過程中出現個別元素重複，不需要對字典進行結構性修改的情況下一律使用非安全迭代器。

思考

請繼續思考rehash對非安全遍歷過程的影響，會重複哪些元素，重複的元素會非常多麼還是只是少量重複？

微信搜索「codehole」關注公眾號「碼洞」，裡面有很多免費深度技術文章

本文節選自《Redis 深度歷險》，點擊《Redis 深度歷險》在線閱讀更多文章