Привет всем, меня зовут Сяои. Сегодня давайте поговорим о перехешировании Redis, которое представляет собой операцию расширения хеш-таблицы.

Я думаю, что все знакомы с hashMap. Его базовая структура представляет собой массив плюс связанный список плюс красно-черное дерево (красно-черное дерево здесь не раскрывается). Размер массива по умолчанию равен 16. Быстрый доступ от ключа к. Значение может быть достигнуто через хэш-значение ключа.

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

базовая структура данных

Хэш-таблица представляет собой массив. Каждый элемент массива называется хэш-ведром (dictEntity). В каждом хэш-ведре хранятся данные пары ключ-значение (указатели на определенные значения).

Как мы все знаем, Redis написан на языке C. Redis использует структуру данных словаря dict для хранения хэш-таблиц. Экземпляр Redis соответствует dict.

#dictdict структура данных
typedef struct dict{
    dictType *type; //Прямая структура dictType, структура dictType содержит пользовательскую функцию, эта функция позволяет ключу и значению хранить данные любого типа.
    void *privdata; //Личные данные, сохраняет функцию в структуре dictType параметр
    dictht ht[2]; //Две хеш-таблицы
    long rehashidx; //Отметка повторного хэширования, rehasidx=-1 означает, что повторное хэширование не выполняется. Во время повторного хэширования значение rehasidx будет увеличиваться на единицу для каждого перенесенного сегмента.
    int itreators;  //Количество итераторов для существования положительной итерации
}

#Структура хеш-таблицы ht[0], ht[1] в структуре dict данных
typedef struct dictht{
    dictEntry[] table;        //Сохраняем множество адресов, сохраняем адрес хэш-узла dictEntry во многих
    unsingned long size;      //Размер хеш-таблицы, начальный размер для4
    unsingned long  sizemask; // индекс для отображения значений Воляхаша приезжать в таблицу, размер для (size-1)
    unsingned long  used;     //Записываем количество существующих узлов (пар ключ-значение) в хеш-таблицу
}

#Определение структуры узла хэш-таблицы
typedef struct dictEntity{
    void *ключ;//ключ
    //ценить
    union{
        void *val;//Пользовательский тип
        uint64_t u64;//Целое без знака
        int64_t s64;//Соответствует пластической хирургии
        double d;//Тип с плавающей запятой
    } v;
    struct dictEntity *next;//Используется при возникновении конфликта хэшей. Укажите на следующий узел хэш-таблицы, образуя связанный список.
}

перефразировать спусковой механизм

При добавлении ключей в redis будет вызываться функция _dictExpandIfNeeded, чтобы определить, необходимо ли расширение.

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    // Если выполняется расширение емкости, верните ОК.
    if (dictIsRehashing(d)) return DICT_OK;
  
    /* If the hash table is empty expand it to the initial size. */
    // Если размер хеш-таблицы ht[0] равен 0, словарь инициализируется.
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
  
    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    /*
     * Если соотношение количества ключей, сохраненных в хеш-таблице ht[0] к размеру хеш-таблицы достигло приезжать1:1, то есть количество сохраненных узлов больше размера хеш-таблицы.
     * А сервис redis в данный момент разрешает выполнение перехеширования или соотношение количества сохраняемых узлов к размеру хеш-таблицы превышает порог безопасности (значение по умолчанию для5)
     * Затем размер хеш-таблицы Воля увеличивается в два раза по сравнению с исходным размером.
     */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

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

• Коэффициент загрузки ≥ 1, и хеш-таблицу можно перехешировать. Когда выполняются генерация RDB и перезапись AOF, перехеширование хеш-таблицы запрещено, чтобы избежать влияния на перезапись RDB и AOF.
• Коэффициент загрузки ≥ 5.

Прогрессивная перефразировка

Расширение или сжатие хеш-таблицы требует перемещения всех пар ключ-значение из ht[0] (старая глобальная хэш-таблица) в ht[1] (новая глобальная хэш-таблица). Это действие повторяется несколько раз и постепенно. Причина в том, что если пар «ключ-значение» слишком много, перемещение всех пар «ключ-значение» одновременно приведет к тому, что Redis не сможет предоставлять внешние сервисы в течение определенного периода времени.

Шаги для прогрессивного перефразирования следующие:

1. Выделите пространство памяти для ht[1]. В настоящее время в словаре одновременно имеются две хеш-таблицы.
2. Установите dict::rehashidx на 0, и работа по перехэшированию официально начнется.
3. существовать rehash В ходе процесса каждый раз, когда в словаре выполняется операция добавления, удаления, изменения или поиска, программа существует не только выполнять операции, указанные клиентом, но и воля. ht[0] существовать rehashidx Все пары ключ-значение при перехешировании индекса приезжать ht[1], а затем rehashidx значение плюс один. То есть из ht[0] Начиная с первой позиции индекса, Воля все на этой позиции индекса entries Копировать проживание[1] , а затем последовательно обработать следующий хеш-блок.

1. Поскольку словарные операции продолжают выполняться, ht[0] Все пары «ключ-значение» в конечном итоге будут перенесены. ht[1], в это время программа будет rehashidx установлен на -1 освобождает пространство ht[0], указывая rehash Операция завершена.

Следует отметить, что во время операции постепенного перехэширования, поскольку одновременно существуют две хеш-таблицы, операции удаления, поиска и обновления ключа будут выполняться над двумя хеш-таблицами. Redis сначала попытается найти целевую пару ключ-значение в ht[0]. Если она не найдена, он снова выполнит поиск в ht[1].

Но новая операция отличается. Новый ключ будет выполняться только с новой хеш-таблицей ht[1], чтобы гарантировать, что никакие новые элементы не будут добавлены в очищенный односторонний связанный список в ht[0]. После запуска перехэширования, даже если новый запрос не получен, Redis будет регулярно выполнять операцию перехеширования, и каждое выполнение не будет превышать 1 мс, чтобы не влиять на другие задачи.