Словарь Redis

Хэш-структура, которую мы часто используем в Redis, а также структура ключ-значение во всей базе данных Redis, все они существуют в форме dict, который является словарем.

структура исходного кода

    // 字典结构
    typedef struct dict {
    	// 类型特定函数
        dictType *type; 
    	// 保存类型特定函数需要使用的参数
        void *privdata; 
    	// 保存的两个哈希表，ht[0]是真正使用的，ht[1]会在rehash时使用
        dictht ht[2]; 
    	// rehash进度，如果不等于-1，说明还在进行rehash
        long rehashidx;
    	// 正在运行中的遍历器数量
        unsigned long iterators; 
    } dict;
    
    // hashtable结构
    typedef struct dictht {
    	// 哈希表节点数组
        dictEntry **table; 
    	// 哈希表大小
        unsigned long size; 
    	// 哈希表大小掩码，用于计算哈希表的索引值，大小总是dictht.size - 1
        unsigned long sizemask; 
    	// 哈希表已经使用的节点数量
        unsigned long used; 
    } dictht;
    
    // hashtable的键值对节点结构
    typedef struct dictEntry {
    	// 键名
        void *key; 
    	// 值
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
            double d;
        } v; 
    	// 指向下一个节点, 将多个哈希值相同的键值对连接起来
        struct dictEntry *next; 
    } dictEntry;

Из вышеприведенной структуры видно, что структура dict содержит две хеш-таблицы (далее ht), и обычно только одна ht имеет значение. ht — это структура dicttht, структура dicttht почти такая же, как у HashMap в Java, а конфликты хэшей разрешаются путем группирования. Первое измерение представляет собой массив, а второе измерение — связанный список. В массиве хранится указатель на первый элемент двумерного связанного списка. Этот указатель в ht указывает на структуру dictEntry, в которой хранятся данные пары ключ-значение и указатель на следующий узел.

Расчет хэша

Redis вычисляет значения хеша и индекса следующим образом:

    // 使用字典设置的哈希函数，计算键 key 的哈希值
    hash = dict->type->hashFunction(key);
    // 使用哈希表的 sizemask 属性和哈希值，计算出索引值
    // 根据情况不同， ht 可以是 ht[0] 或者 ht[1]
    index = hash & dict->ht.sizemask;

Мы не будем объяснять здесь хэш-функцию.После вычисленного хеш-значения значение и маска длины (длина - 1) ht объединяются по И для получения значения индекса массива.Здесь я объясню причину этого:

Гарантирует, что выход за пределы массива не произойдетПрежде всего, нам нужно знать, что длина массива в ht должна быть степенью двойки (2 в n-й степени) по регламенту. Итак, двоичная форма длины массива: 10000...000, с кучей нулей после единиц. Тогда бинарная форма dict->ht.sizemask (dict->ht.size - 1) будет 01111...111 с кучей единиц после 0. Старший бит равен 0, что означает "И" со значением хеша. Результирующее значение не должно превышать длину массива, чтобы массив не вышел за пределы.
Убедитесь, что элементы распределены как можно более равномерно.Из приведенного выше анализа видно, что dict->ht.size должен быть четным числом, а dict->ht.sizemask должен быть нечетным числом. Предполагая, что текущая длина массива (dict->ht.size) равна 16, после вычитания 1 (dict->ht.sizemask) будет 15, а двоичный файл, соответствующий 15, будет: 1111. Теперь предположим, что нужно вставить два элемента: один с хеш-значением 8 и двоичным кодом 1000, а другой с хэш-значением 9 и двоичным кодом 1001. После операции «И» с 1111 результаты равны 1000 и 1001 соответственно, которые располагаются в разных позициях массива, так что распределение хэшей очень равномерное.

Что делать, если длина массива нечетная? После вычитания 1 (dict->ht.sizemask) получается четное число, и младший двоичный бит, соответствующий четному числу, должен быть равен 0, например 14 двоичных 1110. «И» два числа выше, чтобы получить 1000 и 1000. Все результаты имеют одинаковую ценность. Затем элементы с хеш-значениями 8 и 9 сохраняются в связанном списке в той же позиции индекса массива. При работе чем больше элементов в связанном списке, тем ниже эффективность, потому что связанный список должен постоянно сравниваться в цикле.

Почему длина массива в ht должна быть равна 2 в энной степени? Потому что на самом деле процесс вычисления индекса фактически берется по модулю (остаток), но эффективность операции остатка % не так высока, как у битовой операции &, и условие хэш%длина==хэш&( length-1) заключается в том, что длина умножается на 2. Клык, причина здесь также объяснена выше.

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

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

Шаги, которые Redis выполняет для повторного хеширования хэш-таблицы словаря, следующие:

для словаряht[1]Хеш-таблица выделяет пространство, размер которого зависит от выполняемой операции, иht[0]Количество пар ключ-значение, содержащихся в данный момент (т. е.ht[0].usedстоимость имущества):
- Если выполняется операция расширения, тоht[1]Размер первого больше или равенht[0].used * 22^n из (2 из nвласть);
- Если выполняется операция сжатия, тоht[1]Размер первого больше или равенht[0].used2^n из .
будет сохранен вht[0]Все пары ключ-значение в перефразированииht[1]Вверху: перехеширование означает пересчет хеш-значения и значения индекса ключа, а затем размещение пары ключ-значение вht[1]в указанном месте в хеш-таблице.
когда ht[0]Все включенные пары ключ-значение перенесены вht[1] Позже (ht[0]становится пустым), отпуститеht[0] , Буду ht[1]Установить какht[0], И вht[1]Создайте новую пустую хеш-таблицу, чтобы подготовиться к следующему повторному хэшированию.

Вот почему 2 файла ht хранятся в словаре Redis, чтобы облегчить миграцию и замену 2 файлов ht.

Почему бы просто не скопироватьht[0]Все узлы вht[1]но перефразировать его снова?

Смотрим формулу расчета индекса:index = hash & dict->ht.sizemask;

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

Итак, каковы условия перефразирования и какое количество ht будет выполнять Redis?

При выполнении любого из следующих условий программа автоматически начнет выполнять операции раскрытия хеш-таблицы:

В настоящее время сервер не выполняет команду BGSAVE или команду BGREWRITEAOF, а коэффициент загрузки хэш-таблицы больше или равен1;
В настоящее время сервер выполняет команду BGSAVE или команду BGREWRITEAOF, а коэффициент загрузки хэш-таблицы больше или равен5;

Коэффициент загрузки хеш-таблицы можно рассчитать по формуле:

    // 负载因子 = 哈希表已保存节点数量 / 哈希表大小
    load_factor = ht[0].used / ht[0].size

Фактор загрузки на самом деле является коэффициентом использования хеш-таблицы, который используется для измерения состояния емкости хэш-таблицы.

Команда bgsave или bgrewriteaof приведет к чрезмерному разделению страниц памяти (Copy On Write).Redis старается не расширяться, но если хеш-таблица очень заполнена, количество элементов достигло 5-кратного размера массива первой размерности. быть вынужден расширяться.

С другой стороны, когда коэффициент загрузки хеш-таблицы меньше0.1, программа автоматически начнет сжимать хеш-таблицу.

Почему он называется прогрессивным?

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

Ниже приведены подробные шаги прогрессивного перефразирования хеш-таблицы:

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

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

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

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