Словарь-это абстрактная структура данных, используемая для сохранения пар ключ-значение. Поскольку в языке C нет встроенного словаря, Redis создает свою собственную реализацию словаря.
В Redis словари используются для реализации базовой базы данных. Операции CRUD с базами данных также основаны на операциях со словарем.
В дополнение к представлению баз данных, словари являются одной из базовых реализаций хэш-ключей. Когда хэш-ключ содержит большое количество пар ключ-значение или когда элементы в парах ключ-значение являются длинными строками, Redis адаптируется к словарю в качестве базовой реализации хэш-ключа.
1. Внедрение словаря
Словарь Redis использует хэш-таблицы в качестве базовой реализации. В хэш-таблице может быть несколько узлов хэш-таблицы, и каждый узел хэш-таблицы сохраняет пару ключ-значение в словаре.
1.1 Хэш-таблица
Структура хэш-таблицы, используемая в словаре Redis:
typedef struct dictht {
DictEntry** table; //hash table array
Unsigned long size; //hash table size
Unsigned long sizemask; //hash table size mask for index calculation
Unsigned long used; //hash represents the number of nodes
} dictht;- Атрибут таблицы представляет собой массив. Каждый элемент в массиве является указателем на структуру записи dict, и каждая структура записи dict содержит пару ключ-значение.
- Атрибут size записывает размер хэш-таблицы, который является размером массива таблиц.
- Атрибут use записывает количество существующих узлов (пар ключ-значение) в хэш-таблице.
- Общее значение атрибута маски размера равно размеру-1, который вместе со значением хэша определяет, какой индекс ключа должен быть помещен в массив таблиц.
На рисунке 1 показана пустая хэш-таблица размером 4.
1.2 Узел Хэш-Таблицы
Узлы хэш-таблицы представлены структурой диктанта, и каждая структура записи диктанта содержит пару ключ-значение:
typedef struct dictEntry {
Void * key; // key
union {
Pointer to void * val; // value type
Unsigned Integers of uint64_t u64; //Value Types
In64_t s64; // Signed Integers of Value Types
Floating Point Type of Double d; //Value Type
} v;//value
Strct dictEntry * next; // points to the next hash table node to form a linked list
} dictEntry;- Атрибут key содержит ключ, в то время как атрибут V содержит значение.
- Следующий атрибут-это указатель на другой узел хэш-таблицы. Этот указатель может соединять несколько пар значений ключей с одним и тем же значением хэша, чтобы решить проблему конфликта ключей.
На рисунке 2 показано, как два ключа K1 и K0 с одинаковым индексом соединяются вместе с помощью следующего указателя.
1.3 словарь
Структура словаря:
typedef struct dict {
DictType*type;//type-specific function
Void * privdata; // private data
Dictht HT [2]; //hash table (two)
Long rehashidx; // Logging rehash progress. A value of - 1 indicates that rehash has not proceeded
Int iterators; // Number of iterators currently iterating
} dict;Структура типа dict выглядит следующим образом:
typedef struct dictType {
// Functions for calculating hash values
unsigned int (*hashFunction)(const void *key);
// Functions of duplicate keys
void *(*keyDup)(void *privdata, const void *key);
// Functions of duplicate values
void *(*valDup)(void *privdata, const void *obj);
// Functions of Contrast Bonds
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// Functions for Destroying Keys
void (*keyDestructor)(void *privdata, void *key);
// Function of Destruction Value
void (*valDestructor)(void *privdata, void *obj);
} dictType;Атрибут type и атрибут private заданы для создания полиморфных словарей для различных типов пар ключ-значение. Среди них:
- Атрибут type является указателем на структуру типа dict, и каждая структура типа канала содержит кластер функций для управления определенным типом пары ключ-значение. Redis устанавливает различные типы конкретных функций для словарей, которые не используются для использования.
- Атрибут private содержит необязательные параметры, которые необходимо передать этим типам конкретных функций.
Атрибут HT представляет собой массив, содержащий две хэш-таблицы. Как правило, словари используют только HT [0], а HT [1] используется только при повторном хэшировании HT [0].
Атрибут rehashidx, который записывает текущий ход выполнения повторной обработки, имеет значение – 1, если повторная обработка в данный момент не выполняется. Что касается того, что такое пересказ, не волнуйтесь. Это будет подробно объяснено позже.
На рисунке 3 показан словарь без перефразирования:
2 алгоритм вставки
Когда в словарь добавляется новая пара ключ-значение, Redis вычисляет значение хэша и значение индекса на основе ключа пары ключ-значение, а затем помещает узел хэш-таблицы, содержащий новую пару ключ-значение, в индекс, указанный массивом хэш-таблиц, в соответствии со значением индекса. Конкретный алгоритм заключается в следующем:
# Calculate the hash value of the key using the hash function set by the dictionary hash = dict->type->hashFunction(key); # Using the sizemask attribute and hash value of the hash table, the index value is calculated. # depending on the situation, use HT [0] or HT [1] index = hash & dict[x].sizemask;
Как показано на рисунке 4, если в словарь добавлена пара значений ключа [k0, v0], порядок вставки будет следующим:
hash = dict-type->hashFunction(k0); index = hash & dict->ht[0].sizemask; # 8 & 3 = 0
Вычисляется, что значение ключа [k0, v0] соответствует позиции, в которой индекс массива хэш-таблиц равен 0, как показано на рис. 5:
2.1 Ключевой Конфликт
Когда два или более ключей назначаются одному и тому же индексу массива хэш-таблиц, мы думаем, что эти ключи возникают Конфликт построения 。
Использование хэш-таблицы Redis Метод цепного адреса Для разрешения конфликта построения. Каждый узел хэш-таблицы имеет указатель next, несколько узлов хэш-таблицы могут использовать указатель next для формирования односторонне связанного списка, а несколько узлов, назначенных одному и тому же индексу, связаны с односторонне связанным списком с помощью следующего указателя.
Возьмем, к примеру, каштан. Предположим, мы добавляем пары ключей [k2, v2] в хэш-таблицу, показанную на рис. 6, и вычисляем, что значение индекса K2 равно 2, что противоречит k1. Поэтому мы используем следующий указатель для соединения узлов, где расположены K2 и K1, как показано на рисунке 7.
3 перефразирование и прогрессивное перефразирование
При работе со словарем количество пар ключ-значение ошибок хэш-таблицы постепенно увеличивается или уменьшается, чтобы сделать ошибки в хэш-таблице. Коэффициент загрузки Сохраняя разумный диапазон, когда количество ключевых значений, сообщаемых хэш-таблицей, слишком велико или слишком мало, программе необходимо соответственно расширить или уменьшить хэш-таблицу. Этот процесс расширения или сжатия называется перефразированием.
Для коэффициента нагрузки он может быть рассчитан по следующей формуле:
# Load factor = hash table number of saved nodes / hash table size load_factor = ht[0].used / ht[0].size;
3.1 Расширение и сжатие Хэш – таблицы
Расширение производственных мощностей
Для расширения хэш-таблицы исходный код выглядит следующим образом:
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);
}При выполнении следующих условий программа автоматически начинает расширять хэш-таблицу:
- В настоящее время сервер не выполняет повторную обработку;
- Количество сохраненных узлов в хэш-таблице больше, чем размер хэш-таблицы.
- Параметр Dict_can_resize равен 1, или коэффициент загрузки превышает заданное соотношение (по умолчанию 5);
сокращаться
Исходный код сокращения хэш-таблицы выглядит следующим образом:
int htNeedsResize(dict *dict) {
long long size, used;
Size = dictSlots (dict); the sum of the sizes of the two hash tables // HT [2]
Used = dictSize (dict); // HT [2] The sum of the number of saved nodes in two hash tables
# DICT_HT_INITIAL_SIZE defaults to 4 and HASHTABLE_MIN_FILL defaults to 10.
return (size > DICT_HT_INITIAL_SIZE &&
(used*100/size < HASHTABLE_MIN_FILL));
}
void tryResizeHashTables(int dbid) {
if (htNeedsResize(server.db[dbid].dict))
dictResize(server.db[dbid].dict);
if (htNeedsResize(server.db[dbid].expires))
dictResize(server.db[dbid].expires);
}Когда сумма размеров хэш-таблицы HT [] больше, чем DICT_HT_INITIAL_SIZE (по умолчанию 4), а отношение количества сохраненных узлов к общему размеру меньше 4, HASHTABLE_MIN_FILL (по умолчанию 10, то есть 10%) уменьшает хэш-таблицу.
3.2 перефразировать
Расширение и сжатие хэш-таблиц выполняются путем выполнения операций повторного хэширования. Хэш – таблицы выполняют следующие шаги повторного хэширования:
Выделите место для хэш-таблицы словарей HT [1], размер которой зависит от выполняемой операции и количества пар ключей, содержащихся в настоящее время в HT [0].
- Если выполняется операция расширения, размер HT [1] равен ** первый больше или равен 2 ^ n из HT [0]. используется x2.
- Если выполняется операция сжатия, размер HT [1] будет на первые 2 ^ n больше или равен HT [0]. используйте.
- Все пары ключ-значение, хранящиеся в HT [0], преобразуются в HT [1]: перестановка относится к пересчету значения хэша и значения индекса ключа, а затем переносу пар ключ-значение в указанное расположение хэш-таблицы HT [1].
- Когда все пары ключей, содержащиеся в HT [0], переносятся в HT [1], HT [0] становится пустой таблицей, освобождает HT [0], устанавливает HT [1] в HT [0] и создает новую пустую хэш-таблицу в HT [1] для подготовки к следующему повторному хэшу.
Пример:
Предполагая, что программа хочет расширить HT [0] словаря, показанного на рисунке 8, программа выполнит следующие действия: 1) Текущее значение HT [0]. пользователь равен 4, а 2^3 – первая n-я степень, большая или равная 8. Таким образом, программа устанавливает размер хэш-таблицы HT [1] равным 8. На рисунке 9 приведен словарь HT [1] после выделения места.
2) Перефразируйте в HT [1], как показано на рисунке 10.
3) Отпустите HT [0], установите HT [1] в HT [0], а затем назначьте пустую хэш-таблицу HT [1]. Как показано на рисунке 11:
На этом этапе операция расширения хэш-таблицы была завершена, и программа успешно изменила размер хэш-таблицы с 4 на 8.
3.3 прогрессивная перестановка
Для повторного выполнения Redis это не одноразовое централизованное завершение, а постепенное и многократное завершение, поэтому оно также называется повторным выполнением Redis. Прогрессивная перефразировка 。
Причина, по которой мы применяем постепенный подход, хорошо понятна. Когда в хэш-таблице сохраняется большое количество пар ключ-значение, вполне вероятно, что повторный хэш может выполняться сервером только в течение определенного периода времени и не может предоставлять услуги внешнему миру, если все пары ключ-значение будут повторно хэшированы в HT [1].
Поэтому, чтобы избежать перестановки, влияющей на производительность сервера, Redis делит ключевые значения в HT [0] на перестановку в HT [1] несколько раз и постепенно.
При инкрементном повторении используется переменная счетчика индексов rehashidx. Подробные шаги заключаются в следующем:
- Выделите место для HT [1], чтобы словарь содержал хэш-таблицы HT [0] и HT [1].
- Сохраните переменную счетчика индексов rehashidx в поле и установите ее значение равным 0, чтобы указать начало перестановки.
- Во время повторного хэширования каждый раз, когда выполняется операция ТВОРОГА со словарем, программа перемещает все пары ключей хэш-таблицы ht[0] по индексу rehashidx в ht[1] в дополнение к указанной операции. Когда повторная обработка завершена, программа добавляет значение rehashidx к единице.
- Поскольку словарь продолжает работать, в определенный момент времени все пары ключ-значение HT [0] будут преобразованы в HT [1], когда программа установит значение атрибута rehashidx равным – 1, что указывает на завершение преобразования.
Прогрессивная перестановка может разделять и побеждать, поэтому пары ключей перестановки выделяются для работы словарей в шпаргалке, что позволяет избежать проблем, вызванных централизованной перестановкой.
Кроме того, при переписывании словаря, удалении, поиске, обновлении и других операциях будут выполняться две хэш-таблицы. Например, если вы ищете ключ в словаре, программа теперь будет искать его в HT [0], а если нет, перейдите в HT [1].
Следует отметить, что все новые пары ключей хранятся в HT [1], и никакие дополнительные операции с HT [0] не выполняются. Это гарантирует, что количество пар ключей, содержащихся в HT [0], уменьшается и не увеличивается. При повторной операции количество пар ключей в конечном итоге станет пустыми таблицами.
На рисунках 12-17 показан полный инкрементный процесс повторной обработки:
1) Словарь без перефразирования
2) Пары Ключ-значение по индексу перефразирования 0
3) Пары Ключ-значение по индексу перефразирования 1
4) Пары Ключ-значение по индексу перефразирования 2
5) Пары Ключ-значение по индексу перефразирования 3
6) Повторный просмотр завершен
резюме
- Поля широко используются для реализации различных функций Redis, включая базы данных и хэш-ключи.
- Словари в Redis используют хэш-таблицы в качестве базовой реализации. В каждом словаре есть две хэш-таблицы, одна для обычного использования и одна только для повторного использования.
- Хэш-таблица использует метод адреса цепочки для разрешения конфликтов ключей, и несколько пар ключ-значение, назначенных одному и тому же индексу, связаны в односторонний список.
- При расширении или сжатии хэш-таблицы повторная обработка выполняется постепенно.