redis底层数据结构之dict 字典2
针对 上一文中提出的问题，这一次就进行解答：由rehash过程可以看出，在rehash过程中，ht和ht同时具有条目，即字典中的所有条目分布在ht和ht中，
这时麻烦也就出来了。主要有以下问题：（现在暂不解答是如何解决的）
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.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表上查找
for (table = 0; table <= 1; table++) {
idx = h & d->ht.sizemask;
he = d->ht.table;
while(he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
//在ht上找不到时，如果现在正进行rehash，key有可能在ht上，需要在ht上查找
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
因为rehash时，ht与ht上都有条目，所以需要在两个表中都查找不到元素时，才能确定元素是否存在。至于先查找哪一个表，并不会影响结果。
在查找过程中，如果正在进行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中，否则插入到ht
/* Allocate the memory and store the new entry */
ht = dictIsRehashing(d) ? &d->ht : &d->ht;
entry = zmalloc(sizeof(*entry));
entry->next = ht->table;
ht->table = entry;
ht->used++;
/* Set the hash entry fields. */
dictSetKey(d, entry, key);//插入
return entry;
}
当dict没有进行rehash时，元素插入到ht是比较容易的。但如果正在进行rehash，则要把元素插入到ht中。为什么一定要把元素插入到ht中，而不能是ht？原因就在rehash的过程。rehash的过程是把条目由ht移动到ht的过程，当所有条目都移动完毕时，rehash的过程也就完成。要保证rehash过程能完成，需要注意几点：
a. ht的元素不能一直在增，即使元素在增长也不能快于移动元素到ht的速度。
b. 确定下一个要移动的条目（如按某种方法支确定下一个条目，能否遍历所有ht上的条目）
c. 确定何时移动完所有条目
元素不能插入到ht的原因，就是确保b。rehash过程中，通过rehashidx记录已经处理过的桶，因为rehashidx是线性增长的，终会遍历完ht上所有的桶，但要想rehash能遍历所有的条目，则还需要确保被处理过的桶不能再插入新的元素。所以新的元素只能插入到ht上。另外，因为没有新的元素插入到ht中，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中查找，如找不到则在ht中查找，有则删除。
/* 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.size == 0) return DICT_ERR; /* d->ht.table is NULL */
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht.sizemask;
he = d->ht.table;
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 = he->next;
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
}
zfree(he);
d->ht.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;
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，则遍历ht
if (dictIsRehashing(iter->d) && iter->table == 0) {
iter->table++;
iter->index = 0;
ht = &iter->d->ht;
} else {
break; //遍历完毕
}
}
//记下当前条目
iter->entry = ht->table;
} 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，如果正在进行rehash，则遍历完ht的所有桶后，遍历ht
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某个元素x，此时x位于2号桶，由于rehash可以进行，刚好把ht的1号桶的元素Y移动到ht中，此后迭代器遍历完ht后就会遍历到ht，会把Y再一次遍历。
b. 迭代器此时正遍历到ht的4号桶，后面的桶都还没遍历，此时rehash过程进行且刚好把ht的所有元素都移动到ht上，rehash过程完成，ht切换到ht。由于迭代器中记录目前正在遍历ht，所以此后迭代器遍历ht（原来的ht）的4号桶后的元素时已经没有元素了，遍历过程结束，而实际上还有一些元素没有被遍历。
从上面讨论可以看出，遍历过程中是不能允许rehash的。
综合上面的讨论，可以看出，使用安全迭代器，只要不进行删除元素的操作，遍历过程基本是没有问题的，在遍历开始时已经存在的元素是会被遍历到的。只不过使用安全迭代器本身对dict是有一定的影响的。一是暂停rehash过程，二是如果一直持有安全迭代器不释放，rehash过程无法进行下去。
页:
[1]