跋山涉水——深入 Redis 字典遍歷
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] == '\0');
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;
// 獲取非安全迭代器，只讀迭代器，允許rehashStep
dictIterator *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;
}
// 獲取安全迭代器，允許觸發過期處理，禁止rehashStep
dictIterator *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;
// 如果存在安全的迭代器，就禁止rehash
static 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 = k
hash mod 2^(n+1) = k or k+2^n
複製代碼
迭代器的選擇
除了keys指令使用了安全迭代器，因爲結果不允許重複。那還有其它的地方使用了安全迭代器麼，什麼情況下遍歷適合使用非安全迭代器呢？
簡單一點說，那就是如果遍歷過程中不允許出現重複，那就使用SafeIterator，比如下面的兩種情況
bgaofrewrite需要遍歷所有對象轉換稱操作指令進行持久化，絕對不允許出現重複bgsave也需要遍歷所有對象來持久化，同樣不允許出現重複
如果遍歷過程中需要處理元素過期，需要對字典進行修改，那也必須使用SafeIterator，因爲非安全的迭代器是隻讀的。
其它情況下，也就是允許遍歷過程中出現個別元素重複，不需要對字典進行結構性
需要架構資料的關注私聊我：“資料”
