redis底层数据结构之dict 字典2

kjfhgds

针对 上一文中提出的问题，这一次就进行解答：

由rehash过程可以看出，在rehash过程中，ht[0]和ht[1]同时具有条目，即字典中的所有条目分布在ht[0]和ht[1]中，
这时麻烦也就出来了。主要有以下问题：（现在暂不解答是如何解决的）

1.如何查找key。
2.如何插入新的key。
3.如何删除一个key。
4.如何确保rehash过程不断插入、删除条目，而rehash没有出错。
5.如何遍历dict所有条目，如何确保遍历顺序。
6.如何确保迭代器有效，且正确。

1. 如何查找key

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

dictEntry *dictFind(dict *d, const void *key) {     dictEntry *he;     unsigned int h, idx, table;     if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */     if (dictIsRehashing(d)) _dictRehashStep(d);//如果正在进行rehash，则进行一次rehash操作     h = dictHashKey(d, key);//计算key的哈希值     //先在ht[0]表上查找     for (table = 0; table <= 1; table++) {         idx = h & d->ht[table].sizemask;         he = d->ht[table].table[idx];         while(he) {             if (dictCompareKeys(d, key, he->key))                 return he;             he = he->next;         }         //在ht[0]上找不到时，如果现在正进行rehash，key有可能在ht[1]上，需要在ht[1]上查找         if (!dictIsRehashing(d)) return NULL;     }     return NULL; }

因为rehash时，ht[0]与ht[1]上都有条目，所以需要在两个表中都查找不到元素时，才能确定元素是否存在。至于先查找哪一个表，并不会影响结果。
在查找过程中，如果正在进行rehash，则会进行一次rehash操作，这样的做法跟rehash的实现是相对应的，因为rehash并不会一次完成，需要分成多次完成。那么如何分成多次，什么时候该执行一次rehash操作？在dictRehash函数中已经知道是如何分成多次的，执行则是分散到一些操作中，如查找元素等。这样分散rehash步骤不会对一次查询请求有很大的影响，保持查询性能的稳定。

2. 如何插入新的key

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

//添加条目到字典中 /* Add an element to the target hash table */ int dictAdd(dict *d, void *key, void *val) {     dictEntry *entry = dictAddRaw(d,key);//插入key     if (!entry) return DICT_ERR;     dictSetVal(d, entry, val);//设置key所对应的value     return DICT_OK; } /* Low level add. This function adds the entry but instead of setting * a value returns the dictEntry structure to the user, that will make * sure to fill the value field as he wishes. * * This function is also directly exposed to the user API to be called * mainly in order to store non-pointers inside the hash value, example: * * entry = dictAddRaw(dict,mykey); * if (entry != NULL) dictSetSignedIntegerVal(entry,1000); * * Return values: * * If key already exists NULL is returned. * If key was added, the hash entry is returned to be manipulated by the caller. */ dictEntry *dictAddRaw(dict *d, void *key) {     int index;     dictEntry *entry;     dictht *ht;     if (dictIsRehashing(d)) _dictRehashStep(d);  //rehash     //如果key已经存在，则返回null     /* Get the index of the new element, or -1 if      * the element already exists. */     if ((index = _dictKeyIndex(d, key)) == -1)         return NULL;     //如果正在进行rehash，则就把新的元素插入到ht[1]中，否则插入到ht[0]     /* Allocate the memory and store the new entry */     ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];     entry = zmalloc(sizeof(*entry));     entry->next = ht->table[index];     ht->table[index] = entry;     ht->used++;     /* Set the hash entry fields. */     dictSetKey(d, entry, key);  //插入     return entry; }

当dict没有进行rehash时，元素插入到ht[0]是比较容易的。但如果正在进行rehash，则要把元素插入到ht[1]中。为什么一定要把元素插入到ht[1]中，而不能是ht[0]？原因就在rehash的过程。rehash的过程是把条目由ht[0]移动到ht[1]的过程，当所有条目都移动完毕时，rehash的过程也就完成。要保证rehash过程能完成，需要注意几点：
a. ht[0]的元素不能一直在增，即使元素在增长也不能快于移动元素到ht[1]的速度。
b. 确定下一个要移动的条目（如按某种方法支确定下一个条目，能否遍历所有ht[0]上的条目）
c. 确定何时移动完所有条目

元素不能插入到ht[0]的原因，就是确保b。rehash过程中，通过rehashidx记录已经处理过的桶，因为rehashidx是线性增长的，终会遍历完ht[0]上所有的桶，但要想rehash能遍历所有的条目，则还需要确保被处理过的桶不能再插入新的元素。所以新的元素只能插入到ht[1]上。另外，因为没有新的元素插入到ht[0]中，a 也得到确保。

3.如何删除一个key。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

//先在ht[0]中查找，如找不到则在ht[1]中查找，有则删除。 /* Search and remove an element */ static int dictGenericDelete(dict *d, const void *key, int nofree) {     unsigned int h, idx;     dictEntry *he, *prevHe;     int table;     if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */     if (dictIsRehashing(d)) _dictRehashStep(d);     h = dictHashKey(d, key);     for (table = 0; table <= 1; table++) {         idx = h & d->ht[table].sizemask;         he = d->ht[table].table[idx];         prevHe = NULL;         while(he) {             if (dictCompareKeys(d, key, he->key)) {                 /* Unlink the element from the list */                 if (prevHe)                     prevHe->next = he->next;                 else                     d->ht[table].table[idx] = he->next;                 if (!nofree) {                     dictFreeKey(d, he);                     dictFreeVal(d, he);                 }                 zfree(he);                 d->ht[table].used--;                 return DICT_OK;             }             prevHe = he;             he = he->next;         }         if (!dictIsRehashing(d)) break;     }     return DICT_ERR; /* not found */ }

4.如何确保rehash过程不断插入、删除条目，而rehash没有出错。

从插入和删除过程可以看出，是不会使rehash出错的。

5. 如何遍历dict所有条目，如何确保遍历顺序。
6.如何确保迭代器有效，且正确。

dict的遍历是用迭代器，迭代器有两种，一种是普通的迭代器，一种是安全迭代器，相比而言，普通迭代器就是不安全了。

迭代器是很多数据结构（容器）都会有的用于遍历数据元素的工具。使用迭代器需要注意一些问题：
a. 迭代器的遍历顺序
b. 迭代器遍历元素过程中是否可以改变容器的元素，如改变容器的元素会有什么影响，如遍历顺序、迭代器失效

现在了看看dict的迭代器。

遍历顺序不确定，基本可认为是无序。
普通迭代器不允许在遍历过程中个性dict。安全迭代器则允许。

下面看代码，

1 2 3 4 5 6 7 8 9 10 11 12

//创建一个普通迭代器 dictIterator *dictGetIterator(dict *d) {     dictIterator *iter = zmalloc(sizeof(*iter));     iter->d = d;  //记录dict     iter->table = 0;     iter->index = -1;     iter->safe = 0; //普通迭代器     iter->entry = NULL;     iter->nextEntry = NULL;     return iter; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

//创建一个安全迭代器 dictIterator *dictGetSafeIterator(dict *d) {     dictIterator *i = dictGetIterator(d);     i->safe = 1;  //安全迭代器     return i; } //遍历过程 dictEntry *dictNext(dictIterator *iter) {     while (1) {         if (iter->entry == NULL) {             //当前条目为null，可能是刚创建，可能是一个为空的桶，可能是到达桶的最后一个条目，也可能是遍历完所有的桶             dictht *ht = &iter->d->ht[iter->table];             if (iter->index == -1 && iter->table == 0) {                 //刚创建的迭代器                 if (iter->safe)                     iter->d->iterators++; //如是安全迭代器，dict中记下                 else                     iter->fingerprint = dictFingerprint(iter->d); //普通迭代器，记下当前的Fringerprint             }             iter->index++; //下一个桶             if (iter->index >= (long) ht->size) {                 //如果已经遍历完表，如果当前正在进行rehash，且遍历完ht[0]，则遍历ht[1]                 if (dictIsRehashing(iter->d) && iter->table == 0) {                     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) {             //找到条目，记下此条目的下一个条目             /* We need to save the 'next' here, the iterator user              * may delete the entry we are returning. */             iter->nextEntry = iter->entry->next;             return iter->entry; //返回找到的条目         }     }     //找不到条目了，已经遍历完dict     return NULL; }

从上面的遍历过程可以看到迭代器遍历的三个顺序：
a. 先遍历ht[0]，如果正在进行rehash，则遍历完ht[0]的所有桶后，遍历ht[1]
b. 在一个ht中，遍历是按桶从小到大遍历
c. 同一个桶中的多个条目，遍历顺序是从链头遍历到链尾，但是条目在链中的位置本身也是不确定的。

从上面三个顺序中可以得出，迭代器遍历过程是无序的。

下面来讨论迭代器是否能遍历所有条目的问题。此时要分开普通迭代器与安全迭代器来讨论。

普通迭代器，从代码上看到在普通迭代器开始遍历时会计算dict的fingerprint，遍历过程中可以允许dict插入、删除条目，以及进行rehash。但是，在释放迭代器时，会比较遍历完的dict跟遍历前的dict的fingerprint是否一致，如不一致则程序退出。此时便可以知道，普通迭代器其实并不允许遍历，尽管遍历时代码上并没有阻止，但最后却会导致程序出错退出。不过，比较fingerprint相同，并不能说明dict没有变化，只能说如果fingerprint不同dict一定发出了变化。

void dictReleaseIterator(dictIterator *iter)
{
    if (!(iter->index == -1 && iter->table == 0)) {
        if (iter->safe)
            iter->d->iterators--;
        else
            assert(iter->fingerprint == dictFingerprint(iter->d));
    }
    zfree(iter);
}

安全迭代器，在开始遍历时会在dict上记下，遍历过程则跟普通迭代器无区别。那么在dict上记下有安全迭代器是用来做什么的呢？通过查找代码，可以看到使用dict的安全迭代器计数器的地方是 _dictRehashStep 函数。

/* This function performs just a step of rehashing, and only if there are
* no safe iterators bound to our hash table. When we have iterators in the
* middle of a rehashing we can't mess with the two hash tables otherwise
* some element can be missed or duplicated.
*
* This function is called by common lookup or update operations in the
* dictionary so that the hash table automatically migrates from H1 to H2
* while it is actively used. */
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);  //如果安全迭代器计数器为0，则允许进行rehash操作
}

而从释放迭代器的函数 dictReleaseIterator 可以看到并没有检查 fingerprint的操作，因此可以得出所谓的安全迭代器，实则是指：
a. 迭代过程中可以允许插入、删除条目
b. 迭代过程中不会进行rehash，如开始迭代前已经进行了rehash，则迭代开始后rehash会被暂停，直到迭代完成后rehash接着进行。

既然遍历过程中允许插入、删除，那如何遍历过程。
插入元素时，对遍历过程无大影响，但能否遍历到刚插入的元素则是不确定的。
删除元素时，要分四种情况：删除已经遍历的元素，删除当前元素，删除下一个要遍历的元素，删除非下一个要遍历的未遍历的元素。
  删除已经遍历的元素，对遍历过程是无影响的。
  删除当前元素，对遍历过程也是无影响的，因为当前元素已经被访问，迭代器取下一个元素时不再依靠当前元素。
  删除下一个要遍历的元素，又可以分成两种情况，下一个元素已经记录在迭代器的nextEntry中和没有记录在迭代器中。如果下一个元素没有记录在迭代器的nextEntry中，对遍历过程是无影响的。如果已经被记录在nextEntry中，则迭代器此时失效，企图访问下一个元素将会产生不可预期的效果。
  删除非下一个要遍历的未遍历的元素，对遍历过程也是影响的，只是已经删除了的元素是不会被遍历到了。

从上面的讨论可知，安全迭代器其实也并不是真正的安全，删除元素时有可能引起迭代器失效。

现在讨论为什么安全迭代器在遍历过程中不允许rehash，因为如果允许rehash，遍历过程将无法保证，有些元素可能会遍历多次，有些元素会没有遍历到。下面举一些情景：
a. 迭代器现在遍历到ht[0]某个元素x，此时x位于2号桶，由于rehash可以进行，刚好把ht[0]的1号桶的元素Y移动到ht[1]中，此后迭代器遍历完ht[0]后就会遍历到ht[1]，会把Y再一次遍历。
b. 迭代器此时正遍历到ht[1]的4号桶，后面的桶都还没遍历，此时rehash过程进行且刚好把ht[0]的所有元素都移动到ht[1]上，rehash过程完成，ht[1]切换到ht[0]。由于迭代器中记录目前正在遍历ht[1]，所以此后迭代器遍历ht[1]（原来的ht[0]）的4号桶后的元素时已经没有元素了，遍历过程结束，而实际上还有一些元素没有被遍历。

从上面讨论可以看出，遍历过程中是不能允许rehash的。

综合上面的讨论，可以看出，使用安全迭代器，只要不进行删除元素的操作，遍历过程基本是没有问题的，在遍历开始时已经存在的元素是会被遍历到的。只不过使用安全迭代器本身对dict是有一定的影响的。一是暂停rehash过程，二是如果一直持有安全迭代器不释放，rehash过程无法进行下去。