Когда приходится работать большими redis базами в десятки Гб понимание “а как оно там?”, “откуда такой размер?”, “как правильно отстрелить ногу при проектировании схемы данных?” - может быть полезно. Вообще структура хеш-таблиц в redis используется достаточно широко. Возьмём, к примеру структуру базы данных.

База данных redis (статья написана по redis_version:8.0) это сложное хранилище состоящее из большого количества hash-таблиц

typedef struct redisDb {
	kvstore *keys; /* основное KV- хранилище*/
	kvstore *expires; /* Timeout of keys with a timeout set */
...
	dict *blocking_keys; /* Keys with clients waiting for data (BLPOP)*/
	dict *blocking_keys_unblock_on_nokey; /* Keys with clients waiting for
	* data, and should be unblocked if key is deleted (XREADEDGROUP).
	* This is a subset of blocking_keys*/
	dict *ready_keys; /* Blocked keys that received a PUSH */
	dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
	...
} redisDb;
….
struct kvstore {
...
	dict **dicts;
...
};

- watched_keys - организация работы [[Redis transactions|транзакции]]

- keys - основное хранилище ключ-значение redis. При однонодовой работе kvstore содержит один справочник, в кластерном режиме хеш-таблица создаётся для каждого слота. Собирается статистика вhtstats

- expires - хранилище времен окончания срока действия. Нюансы работы со слотам в кластерном режиме аналогичный keys. Собирается статистика вhtstats

- blocking_keys, blocking_keys_unblock_on_nokey - работа с блокирующими операциями типа BLPOP

- watched_keys - организация транзакции через команду WATCH транзакции

Если мы любим хранить ключи вида: USER_SESSIONS:IMPORTANT_INFORMATION:USER_ID_16780:FROM_2015:TO_2025 - это добро будет в нескольких хештаблицах как ключ и есть риск, что большую часть хранения займут как раз ключи.

Также хештаблицы используются в сложных структурах: set, hash, zlist,...

Лирическое отступление. Коллизии

Хеш-таблица представляет собой набор бакетов. Номер бакета получается после применения хеш-функции к ключу. Если несколько ключей попадают в один бакет - это называется "коллизия".

Обычно нельзя заранее предсказать, какой объём данных будет хранится в этой таблице. Хеш-таблица обычно инициализируется с меньшим размером с тем расчётом, что в конечном итоге количество ключей превысит первоначальный размер таблицы. Несоответствие между пространство ключей и количество бакетов хеш-таблицы проводит к тому, что хешфункция отображает разные ключи в одну и ту же ячейку.

Методы борьбы с коллизиями в redis

В Redis предложена классическая реализация хеш-таблиц. Исходный код работы с хеш-таблицей находится в файлах dict.h (описание структур, прототипы функций) и dict.c (реализация методов). Хеш-таблица определена как двумерный массив dictEntry **ht_table[2], каждый элемент массива, бакет - указатель на структуру dictEntry:

struct dict {
	dictType *type;
	dictEntry **ht_table[2];
	unsigned long ht_used[2]; //элементов в хеш-таблице
	long rehashidx; /* rehashing not in progress if rehashidx == -1 */
	unsigned pauserehash : 15; /* If >0 rehashing is paused */
	signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
...
};

Метод цепочек

Ключи в бакете хранятся в виде связанного списка. Соответственно, если ключ попадает в непустой бакет, он добавляется в конец списка При большой длине списка может быть проблема производительности. Для реализации метода цепочек в структуре есть указатель `next` на следующую структуру dictEntry в бакете.

typedef struct dictEntry {  
	void *key;  
	union {  
    	void *val;  
    	uint64_t u64;  
    	int64_t s64;  
    	double d;  
	} v;  
	struct dictEntry *next;  
} dictEntry;

структура v - вероятнее всего оптимизация, позволяющая хранить в структуре справочника типы, размеры которых известны: int64, double. Сама структура dictEntry занимает место - это надо учитывать при оценке размеров потенциального хранения.

Перехеширование

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

Вопрос: зачем иметь 2 пары ht_table, ht_used, ht_size_exp ?

Реализация перехеширования в Redis

Массив бакетов может как увеличиваться, так и уменьшаться в зависимости от фактического заполнения, соответственно держать его избыточно большим - дорого Фактическое заполнение считается по количеству ключей в хеш-таблице ht_table - ht_used[], длина конкретных списков внутри бакетов не контролируется ( рандом нам поможет). Перехеширование нужно, когда нам надо изменить размер хеш-таблицы.

Основной подход заключается в следующем:

Redis поочерёдно использует две hash-таблицы во время перехеширования:

- При нормальной работе все пары ключ-значение записываются в ht_table[0]

- При процедуре перехеширования значения постепенно переносятся из ht_table[0] в ht_table[1]

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

Перехеширование запускается при попытке изменения размера хеш-таблицы. Сначала увеличиваем размер - создаём ht_table[1] под “перспективное” заполнение, потом, запускаем перехеширование.

Увеличение или инициализация хештаблицы

Вариант когда таблица создаётся с нуля или увеличивается. Для проверки используется метод dictExpandIfNeeded. Проверка dictExpandIfNeeded запускается при любом добавлении или поиске элемента в таблице. При выполнении одного из условий создаётся ht_table[1] и запускается процесс перехеширования. Условия:

- размер ht_table[0]=0. Фактически инициализация с размером DICT_HT_INITIAL_SIZE=4.

- таблица заполнена d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0]) и изменение размера разрешено (DICT_RESIZE_ENABLE) - размер удваивается

- таблица заполнена более чем вчетверо d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0]) и изменение размера не запрещено (!DICT_RESIZE_FORBID - в форке процесса) - размер удваивается.

Уменьшение хештаблицы

ля проверки используется метод dictShrinkIfNeeded. dictShrinkIfNeeded запускается при любом удалении элемента из таблицы. При выполнении одного из условий создаётся ht_table[1] и запускается процесс перехеширования.

Условия:

- если изменение размера разрешено (DICT_RESIZE_ENABLE) то при заполнении 1/8 от размера таблицы

- если не запрещено (DICT_RESIZE_FORBID - в форке процесса запрещено) - то при 1/32

Мониторинг в debug режиме

Верхнеуровнево количество бакетов для двух основных хеш-таблиц можно посмотреть в дебаг-режиме. Режим не для прода.

Правим параметр enable-debug-command в yes. Через CONFIG SET не получится, т.к. параметр иммутабельный.

Команда HTSTATS [dbid] - можно получить статистику по хеш-таблицам базы. Пример ответа после установления 7х ключей и ttl одного из них: debug htstats 0 full

[Dictionary HT]
Hash table 0 stats (main hash table):
table size: 8
number of elements: 7
different slots: 5
max chain length: 2
avg chain length (counted): 1.40
avg chain length (computed): 1.40
Chain length distribution:
   0: 3 (37.50%)
   1: 3 (37.50%)
   2: 2 (25.00%)
[Expires HT]
Hash table 0 stats (main hash table):
table size: 4
number of elements: 1
different slots: 1
max chain length: 1
avg chain length (counted): 1.00
avg chain length (computed): 1.00
Chain length distribution:
   0: 3 (75.00%)
   1: 1 (25.00%)

Не густо (хотелось бы и по остальным таблицам посмотреть), но тем не менее достаточно, чтобы посмотреть как “теория” натягивается фактические данные.

Как работает инкрементальное перехеширование

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

Шаг перехеширования

Логика работы шага перехеширования закопана в функции dictRehash. dictRehash фактически копирует ключи принимая на вход хеш-таблицы источника и приёмника и количество ключей, которые надо скопировать. Копирование происходит бакетами. Логика работы dictRehash состоит из двух частей:

Копирование данных. Копируем ключи в соответствии с указанным количеством бакетов. Индекс бакета, который переносится в данный момент находится в переменной rehashidx хеш-таблицы. Если бакет пуст, он пропускается и декрементируется счётчик пустых бакетов empty_visits. Когда он дойдёт до нуля, управление будет передано главному потоку и он сможет опять обрабатывать пользовательские запросы.
Завершение перехеширования. После копирования проверяем, что все данные перенесены, и если да присваиваем ht_table[0] ht_table[1].

Что вызывает итерацию перехеширования

cron. В cron перехешируется основная таблица kv-хранилища и таблица expired. Перехеширование происходит пачками по 100 бакетов с ограничением - 16мс на БД на каждую из двух хештаблиц. Больше баз на инстансе - больше работы на перехеширование.

for (j = 0; j < dbs_per_call; j++) {
...
kvstoreTryResizeDicts(db->keys, CRON_DICTS_PER_DB);
kvstoreTryResizeDicts(db->expires, CRON_DICTS_PER_DB);
…
}

любой доступ к бакету: добавление ключа, удаление ключа,... Перед операцией сначала вызывается _dictRehashStep, который перехеширует бакет и далее доступ идёт уже к ht_table[1]. Под капотом dictRehash, количество бакетов в параметре для переноса строго 1 - тот, к которому обращаемся.

Метрики перехеширования

Какие инструменты за исключением полулегального DEBUG есть, чтобы простучаться снаружи к метрикам связанным с хеш-таблицами. Их немного:

INFO

mem_overhead_db_hashtable_rehashing: дополнительное потребление памяти на перехеширование по всем БД.

MEMORY STATS

- db.dict.rehashing.count: число БД в процессе перехеширования ( Redis 7.4+)

- dbXXX: Для каждой таблицы расчет занимаемых метаданных (overhead.hashtable.main and overhead.hashtable.expires, respectively) are reported in bytes. Дополнительное потребление памяти: hashtable(память для хештаблицы) + dictEntry(**для записи отношений** каждой пары) + redisObject(Описание различных типов данных) для main и hashtable + dictEntry для expired

- overhead.db.hashtable.lut: размер массива хештаблиц(ы) (прим. с учётом миграции from -> to) при перехешировании (Redis 7.4+)

- overhead.db.hashtable.rehashing: дополнительное потребление памяти для проходящего перехеширования(Redis 7.4+)

- db.dict.rehashing.count: Количество хеш-таблиц в настоящее время находящиеся в процессе перехеширования (Redis 8.0+)

К примеру на старте main и expired имеют по 312 байт “на старте” и на каждый ключ растут по 40 и 24 байта соответственно (а почему меньше? см. замечание про union v в структуре dictEntry). Когда ключей сотни миллионов может быть существенно при расчёте объёма хранения.

Дизайн hash-таблиц в redis