Логика процесса обхода словаря Redis относительно сложна, и в Интернете очень мало анализа и пояснений по этому фрагменту. Я также потратил много времени на разбор деталей исходного кода и представление читателям моего личного понимания логики обхода словаря. Возможно, читатели лучше меня понимают процесс обхода словаря, пожалуйста, не стесняйтесь советовать.
Изменить во время обхода
Мы знаем, что объект ствола дерева Redis является словарем, если объект много, костяк словаря будет велик. Когда мы используем ключи команды Search 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);
}
Итак, вы подумали о сложности, вам нужно модифицировать словарь при обходе словаря, будет ли проблема безопасности указателя?
повторять
Когда словарь расширится, его нужно будет постепенно мигрировать, и хэш-таблиц будет две, старая и новая. Обход должен выполняться для этих двух хэш-таблиц по очереди, сначала обходя старую хеш-таблицу, а затем продолжая обход новой хеш-таблицы. Если rehashStep выполняется во время процесса обхода, и элементы старой хеш-таблицы, которые были пройдены, переносятся в новую хэш-таблицу, приведет ли обход к повторяющимся элементам? Это также сложный момент для рассмотрения при обходе.Давайте посмотрим, как Redis решает эту проблему.
структура итератора
Redis предоставляет два типа итераторов для обхода словаря: один — безопасный итератор, а другой — небезопасный итератор.
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 только для непрерывного обхода словаря, и вы не должны вызывать какие-либо функции, которые могут вызвать суждение об истечении срока действия. Однако преимущество состоит в том, что это не влияет на перефразирование, а цена заключается в том, что пройденные элементы могут повторяться.
Когда безопасный итератор начнет обход, он пометит словарь меткой, с этой меткой не будет выполняться 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);
}
Итерационный процесс
Безопасные итераторы позволяют удалять элементы в процессе обхода, а это значит, что элементы в связанном списке, прикрепленном под одномерным массивом словаря, могут быть удалены, а следующий указатель элемента изменится.Повлияет ли это на итерацию процесс? Давайте подробнее рассмотрим логику кода функции итерации.
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;
}
Стоит отметить, что перехеширование выполняется при расширении словаря, а связанный список в старом массиве переносится в новый массив. Связанный список под определенным слотом может быть перенесен только в два слота нового массива.
hash mod 2^n = k
hash mod 2^(n+1) = k or k+2^n
Выбор итератора
За исключением того, что директива keys использует безопасный итератор, потому что результат не допускает дублирования. Существуют ли другие места, где используются безопасные итераторы, и при каких обстоятельствах небезопасные итераторы подходят для обхода?
Проще говоря, если повторение не разрешено в процессе обхода, используйте SafeIterator, например, в следующих двух случаях.
- bgaofrewrite должен пройти через все преобразования объектов, называемые инструкциями по операциям, для постоянства, и повторение абсолютно не допускается.
- bgsave также должен пройти через все объекты, чтобы сохраниться, а также не допускает дублирования
Если при обходе необходимо обработать истечение срока действия элемента и изменить словарь, необходимо также использовать SafeIterator, поскольку небезопасные итераторы доступны только для чтения.
В остальных случаях, когда при обходе допускается повторение отдельных элементов и не требуется структурной модификации словаря, всегда используются небезопасные итераторы.
считать
Пожалуйста, продолжайте думать о влиянии перефразирования на небезопасный процесс обхода, какие элементы будут повторяться, будут ли повторяющиеся элементы очень большими или только небольшими?
Сканируйте в WeChat и подпишитесь на общедоступную учетную запись «Code Cave», чтобы шаг за шагом «кодировать будущее».