Рубрики
Uncategorized

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

Автор оригинала: David Wong.

байюнь

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

Значение команды: случайный возврат ключа из выбранного в данный момент формата команды базы данных:

RANDOMKEY

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

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

127.0.0.1:6379> randomkey
"key1"
127.0.0.1:6379> randomkey
"kkk"

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

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

Основной процесс

Функция обработки, соответствующая команде keys, – это команда случайного ключа():

void randomkeyCommand(client *c) {
    Robj * key; // store the obtained key

    If ((key = dbrandomkey (C - > dB)) = = null) {// call the core function dbrandomkey ()
        Addreply (C, shared. Nullbulk); // returns nil
        return;
    }

    Addreplybulk (C, key); // return key
    Decrefcount (key); // reduce the reference count
}

Случайная генерация ключей и решение об истечении срока действия

Команда Random key() вызывает функцию db random key (), чтобы фактически сгенерировать случайный ключ:

robj *dbRandomKey(redisDb *db) {
    dictEntry *de;
    int maxtries = 100;
    int allvolatile = dictSize(db->dict) == dictSize(db->expires);

    while(1) {
        sds key;
        robj *keyobj;

        De = dictgetrandomkey (DB - > dict); // get a random dictentry
        If (de = = null) return null; // get failure returns null

        Key = dictgetkey (DE); // get the key in dictentry
        Keyobj = createstringobject (key, sdslen (key)); // generate robj based on key string
        If (dictfind (DB - > expires, key)) {// find the key in the expiration dictionary
            ...
            If (expireifneed (DB, keyobj)) {// judge whether the key is expired
                Decrefcount (keyobj); // if expired, delete the key and reduce the reference count
                Continue; // the current key is expired and cannot be returned. Only the keys that are not expired will be returned for the next random generation
            }
        }
        return keyobj;
    }
}

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

Алгоритм получения реального случайного ключа

Затем мы продолжим следить за функцией dictgetrandomkey (), чтобы узнать, какой алгоритм используется для случайной генерации диктанта:

dictEntry *dictGetRandomKey(dict *d)
{
    dictEntry *he, *orighe;
    unsigned long h;
    int listlen, listele;

    If (dictsize (d) = = 0) return null; // the dictionary passed in is empty and does not need to be generated at all
    If (dictisrehashing (d))] dictrehashstep (d); // perform a rehash operation
    If (dictisrehashing (d)) {// if rehash is in progress, be sure to evenly distribute random seeds from two hash tables
        do {
            H = D - > rehashidx + (random()% (D - > HT [0]. Size + D - > HT [1]. Size - D - > rehashidx)); // calculate the random hash value, which must be at the back of rehashidx
            He = (H > = D - > HT [0]. Size)? D - > HT [1]. Table [H - D - > HT [0]. Size]: D - > HT [0]. Table [H]; // get the corresponding bucket according to the hash value calculated above
        }While (he = = null); // the last bucket whose calculation result is not empty is taken as the cycle calculation
    }Else {// not in rehash, only one hash table
        do {
            H = random() & D - > HT [0]. Sizemask; // directly calculate the hash value
            He = D - > HT [0]. Table [H]; // retrieve the h bucket on the hash table
        }While (he = = null); // the last bucket whose calculation result is not empty is taken as the cycle calculation
    }

    //Now we get a bucket that is not empty, and one or more dictentries are attached to the back of the bucket (the chain address method solves the hash conflict), so we also need to calculate a random index to determine which dickentry chain node to access
    listlen = 0;
    orighe = he;
    while(he) {
        he = he->next;
        Listlen + +; // calculate the length of the linked list
    }
    Listele = random()% listlen; // the random number takes the remainder of the length of the linked list and determines which node to get
    he = orighe;
    While (listele --) he = He - > next; // traverse the linked list on the bucket from the front to the back and find the node
    Return he; // finally return this node
}

Эта функция сначала определяет, что словарь пуст. Затем будет выполнена одноэтапная операция перефразирования, которая аналогична эффекту вызова функций словаря, таких как dictadd (), и является частью прогрессивной технологии перефразирования. Здесь мы сначала рассмотрим общую структуру словаря: Поскольку перестановка повлияет на генерацию начального числа случайных чисел, необходимо обсудить две ситуации в зависимости от того, выполняется ли перестановка текущего словаря: Во-первых: выполняется повторная операция. Тогда структура текущего словаря такова: в первой хэш-таблице есть несколько ключей, а остальные-во второй хэш-таблице. Чтобы равномерно распределить вероятность того, что могут быть извлечены две хэш-таблицы, необходимо объединить две хэш-таблицы. Алгоритм выглядит следующим образом:

H = D - > rehashidx + (random()% (D - > HT [0]. Size + D - > HT [1]. Size - D - > rehashidx)); // calculate the random hash value, which must be at the back of rehashidx

Здесь мы вычитаем rehashidx из суммы двух размеров хэш-таблицы случайным числом. Такая остаточная операция может гарантировать, что значение хэша случайным образом попадет в индекс больше, чем На ведре в rehashidx. Потому что rehashidx представляет прогресс перефразирования. Этот rehashidx представляет данные перед индексом в первой хэш-таблице, т. е. [0, rehashidx-1]. Данные в этом закрытом интервале были перенесены во вторую хэш-таблицу. Элементы, превышающие или равные этому rehashidx, все еще находятся в первой хэш-таблице. Таким образом, это гарантирует, что любое ведро в результате h не является пустым и имеет значение. Далее вам нужно только определить, в какой хэш-таблице находится это значение H, а затем перейти к значению корзины в соответствующей позиции в хэш-таблице:

he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] : d->ht[0].table[h];

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

H = random() & D - > HT [0]. Sizemask; // hash value is calculated by bitwise and operation of sizemask
He = D - > HT [0]. Table [H]; // retrieve the h bucket on the hash table

Затем мы находим непустое ведро, но это еще не конец. Потому что могут быть Коллизии хэшей Redis использует метод адреса цепочки для разрешения конфликтов хэшей, поэтому несколько записей dict будут прикреплены к корзине для формирования списка цепочек. Поэтому нам также нужно подумать о том, какой диктант в узле связанного списка выбрать. Этот алгоритм относительно прост. Вы можете напрямую использовать результат random() для вычисления длины связанного списка

Listele = random()% listlen; // the random number takes the remainder of the length of the linked list and determines which node to get
While (listele --) he = He - > next; // traverse the linked list on the bucket from the front to the back and find the node

До сих пор мы нашли случайный узел диктанта в случайном ведре, поэтому мы можем вернуть его клиенту.

Оригинал: “https://developpaper.com/redis5-source-code-learning-analysis-of-the-randomkey-part-of-redis-command/”

Читайте ещё по теме: