[[red - это изучение исходного кода 5] анализ ключей команды redis

байюнь

Синтаксис команд

Значение команды: найдите и верните все ключи, соответствующие заданному формату команды pattern pattern:

KEYS pattern

Командуйте реальным боем:

127.0.0.1:6379> keys *
1) "kkk"
2) "key1"

Возвращаемое значение: набор всех ключей, подобранных в соответствии с шаблоном

Анализ исходного кода

Соответствующей функцией обработки команды keys является команда keys():

void keysCommand(client *c) {
    dictIterator *di; 
    dictEntry *de;
    SDS pattern = C - > argv [1] - > ptr; // get the pattern we entered
    int plen = sdslen(pattern), allkeys;
    unsigned long numkeys = 0;
    void *replylen = addDeferredMultiBulkLength(c); 

    Di = dictgetsafeiterator (C - > DB - > dict); // initializes a security iterator
    Allkeys = (pattern [0] = = '*' & & Pattern [1] = '\ 0'); // judge whether to return the set of all keys
    While ((de = dictnext (DI))! = null) {// traverses the entire key space dictionary
        SDS key = dictgetkey (DE); // get the key value
        robj *keyobj;

        //If it is a collection of returned all keys, or the current key matches the pattern given by us, it will be added to the return list
        if (allkeys || stringmatchlen(pattern,plen,key,sdslen(key),0)) {
            keyobj = createStringObject(key,sdslen(key));
            If (! Keyisexpired (C - > dB, keyobj)) {// filter out the keys without expiration
                Addreplybulk (C, keyobj); // add to the return list
                Numkeys + +; // returns the number of keys++
            }
            decrRefCount(keyobj); 
        }
    }
    Dictreleaseiterator (DI); // release the security iterator
    Setdeferredmultibulklength (C, replylen, numkeys); // set the length of the returned value
}

Поскольку мы используем команду keys*, нам нужно вернуть коллекцию всех ключей. Давайте сначала рассмотрим этот код, который использует итератор безопасности для обхода всего словаря пространства ключей. В то же время при обходе мы отфильтровываем те ключи, которые соответствуют нашему шаблону и срок действия которых не истек, а затем возвращаем их клиенту. Поскольку временная сложность его обхода прямо пропорциональна размеру словаря, это приведет к проблеме. Когда ключей много, словарь пространства клавиш может быть очень большим. Мы используем клавиши для одновременного просмотра словаря сверху вниз, что отнимет много времени. Поскольку redis является приложением с одним процессом, выполнение команды keys в течение длительного времени заблокирует процесс redis, что приведет к внешнему недоступному статусу службы redis. Поэтому многие компании запретят разработчикам использовать команду keys, что может привести к тому, что служба redis будет недоступна в течение длительного времени. Справочный случай: команда keys redis вызвала

расширять

Итератор безопасности и итератор без безопасности

В процессе обхода команды keys используется концепция итератора безопасности. Напротив, существуют небезопасные итераторы. Итак, как работает итератор и в чем разница между безопасным и небезопасным? Давайте сначала рассмотрим структуру хранения итератора:

typedef struct dictIterator {
    Dict * D; // points to the dictionary to traverse
    Long index; // index location of bucket in hash table
    Int table, safe; // table index (reference dict structure can only be 0 or 1), and whether the iterator is safe
    Dictentry * entry, * nextentry; // stores the current entry and the next entry
    Long long fingerprint; // fingerprint, only in the case of non security iteration
} dictIterator;

Чтобы вы могли видеть функцию полей индекса и таблицы, нам нужно вставить структуру dict: поле таблицы может быть только 0 или 1. 0-это хэш-таблица, которая будет использоваться в обычном состоянии, а 1-хэш-таблица перехода, которая будет использоваться в процессе повторного хэширования. Индекс составляет 01234567 в каждой хэш-таблице. Безопасное поле в итераторе используется для определения того, является ли тип итератора безопасным или нет. Так называемая безопасность означает, что в процессе обхода работа словаря не повлияет на результаты обхода; в то время как итератор без защиты может приводить к ошибкам в результатах обхода из-за перефразирования и других операций, но его производительность выше.

Как я могу быть в безопасности

В redis итератор безопасности делает итератор безопасным, напрямую запрещая операцию повторного кэширования. Так почему же безопасно запрещать перефразирование? Как мы все знаем, операции повторной обработки являются постепенными. Каждый раз, когда выполняется команда, будет производиться повторная обработка. Операция перефразирования использует обе таблицы словаря одновременно. Давайте рассмотрим ситуацию, когда итератор в настоящее время пересекает первую таблицу, и прогресс достиг позиции с индексом 3, и элемент не был перефразирован, и мы пересекли элемент. Затем повторная обработка и обход выполняются одновременно. Предполагая, что повторная обработка завершена, этот элемент перейдет в позицию, где индекс второй таблицы равен 33. В настоящее время итератор продвигается только до позиции индекса 13 второй таблицы, и он не прошел до позиции индекса 33. Если вы продолжите переход, так как этот элемент был пройден один раз в первой таблице, он неизбежно будет пройден во второй

typedef struct dict {
    dictType *type;
    void *privdata;
    Dictht HT [2]; // pointer to two tables
    Long rehashidx; // rehash flag. If it is - 1, it is not in rehash
    Unsigned long iterators; // number of security iterators currently running
} dict;

Мы видим, что поле итераторы в структуре словаря используется для описания количества итераторов безопасности. Если запущен итератор безопасности, это поле будет + +. Таким образом, в процессе итерации словарь станет относительно стабильным, что позволит избежать проблемы многократного обхода элемента. Если в настоящее время запущен итератор безопасности, поле итератора не должно быть равно 0. Если это поле равно 0, можно выполнить повторный ввод:

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

Фактически, в дополнение к простому и грубому запрету операций перефразирования, таких как итераторы безопасности, redis также предоставляет сканирование в качестве более продвинутого метода обхода. С помощью более сложного и хитроумного алгоритма он может гарантировать, что даже в процессе повторного просмотра результат обхода не повторится и не просочится. Это гарантирует, что операция перефразирования и операция обхода могут выполняться одновременно, а также позволяет избежать проблемы блокировки повторного доступа, вызванной сверхвысокой временной сложностью прохождения ключей при большом пространстве ключей, что значительно повышает эффективность.

Безопасен ли итератор безопасности

Так что продолжайте думать, просто не перефразируйте операцию, чтобы убедиться, что итератор безопасен? Поскольку redis-это приложение с одним процессом, когда мы выполняем команду keys, мы блокируем выполнение всех других команд. Поэтому при обходе итераторов мы не можем добавлять, удалять или изменять словари пространства клавиш, выполняя команды. Однако некоторые события времени в redis могут изменить словарь. Например: каждый второй период времени для проверки того, истек ли срок действия ключа, истекший срок его действия будет удален из пространства ключей. На данный момент я не думаю, что даже безопасный итератор может избежать работы со словарем во время обхода. Например, во время обхода, если событие redis удаляет элемент, который не был пройден, то последующий итератор продолжит его обход, и он не сможет обойти элемент. Так как же решить эту проблему? Если события не запускаются и функции обработки не выполняются во время обхода в redis, эти операции приведут к незначительным

Процесс обхода итератора

Оставляя эти детали в стороне, давайте рассмотрим конкретную логику обхода. Сначала нам нужно инициализировать итератор безопасности:

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;
}

Для итератора безопасности в дополнение к инициализации вышеуказанных полей необходимо установить безопасное поле равным 1:

dictIterator *dictGetSafeIterator(dict *d) {
    Dictiterator * I = dictgetiterator (d); // call the above method to initialize the remaining fields

    I - > safe = 1; // initialize the safe field
    return i;
}

Возвращаясь к началу команды keys, она вызывает функцию dict get safe iterator() для инициализации итератора безопасности. Затем команда keys по кругу вызывает метод dictnext() для обхода всех элементов в словаре пространства ключей:

dictEntry *dictNext(dictIterator *iter)
{
    while (1) {
    
        //There are two situations for entering this if:
        //1. This is the first time the iterator is running
        //2. The nodes in the current index linked list have been iterated
        if (iter->entry == NULL) {

            //Point to the traversed hash table, default to the first hash table
            dictht *ht = &iter->d->ht[iter->table];

            //Execute only the first traverse (index initialization value is - 1)
            if (iter->index == -1 && iter->table == 0) {
            
                //If it is a security iterator (safe = = 1), update the iterators counter
                if (iter->safe)
                    iter->d->iterators++;
                //If it's an insecure iterator, calculate the fingerprint
                else
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            
            //Update the index and continue to traverse the elements on the next bucket
            iter->index++;

            //If the current index of the iterator is larger than the size of the hash table being iterated
            //It means that the hash table has been iterated
            if (iter->index >= (signed) ht->size) {
                //If rehash is in progress, the second hash table is also in use
                //Then continue to traverse the second hash table
                if (dictIsRehashing(iter->d) && iter->table == 0) {
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                //If there is no rehash, you do not need to traverse the second hash table
                } else {
                    break;
                }
            }

            //If it is done here, the hash table is not traversed
            //Update the node pointer to the header node of the next index linked list (the index has already passed + +)
            iter->entry = ht->table[iter->index];
        } else {
            //When executed here, it means that the chain list on a bucket is being traversed (in order to solve the conflict, multiple dictentries will be attached to the back of a bucket to form a chain list)
            iter->entry = iter->nextEntry;
        }

        //If the current node is not empty, record the pointer of the next node of the node (that is, next)
        //Because when the security iterator is running, it may delete the current node returned by the iterator, so the next pointer cannot be found
        if (iter->entry) {
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }

    //Traversal complete
    return NULL;
}

Конкретный процесс обхода был представлен в форме комментариев. В коде есть еще одно новое понятие: отпечаток пальца. Давайте обсудим концепцию отпечатков пальцев.

Функция отпечатка пальца

В функции обхода dictnext() есть такой код:

If (ITER - > safe) {// if it is a security iterator (safe = = 1), update the iterators counter
     iter->d->iterators++;
}Else {// if it's an insecure iterator, calculate the fingerprint
     iter->fingerprint = dictFingerprint(iter->d);
}

Мы видим, что когда итератор небезопасен, он проверяет отпечаток пальца. Как следует из названия, отсутствие безопасности означает, что во время обхода может быть выполнена операция повторной обработки, что может привести к повторным результатам обхода и другим проблемам. Чтобы правильно идентифицировать эту проблему, redis использует механизм отпечатков пальцев, то есть собирает отпечатки пальцев один раз перед обходом, а затем снова после обхода. Если два соотношения отпечатков пальцев совпадают, это означает, что результат обхода не изменяется из-за влияния операции повторной обработки. Итак, как проверить отпечаток пальца? Суть проверки отпечатков пальцев состоит в том, чтобы определить, изменился ли словарь из-за операции перефразирования:

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];
        /* For the hashing step we use Tomas Wang's 64 bit integer hash. */
        hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1;
        hash = hash ^ (hash >> 24);
        hash = (hash + (hash << 3)) + (hash << 8); // hash * 265
        hash = hash ^ (hash >> 14);
        hash = (hash + (hash << 2)) + (hash << 4); // hash * 21
        hash = hash ^ (hash >> 28);
        hash = hash + (hash << 31);
    }
    return hash;
}

Мы видим, что проверка отпечатков пальцев основана на таблице, размере, используемых и других полях словаря. Если эти поля изменяются, это означает, что операция повторной обработки выполняется или завершена. После выполнения операции повторной обработки это может повлиять на результат обхода. Таким образом, проверка отпечатков пальцев небезопасного итератора может выявить возможность влияния операции повторной обработки на результаты обхода.