Под капотом Redis: Хеш таблица (часть 1)

Если вы знаете, почему после выполнения `hset mySey foo bar` мы потратим не менее 296 байт оперативной памяти, почему инженеры instagram не используют строковые ключи, зачем всегда стоит менять hash-max-ziplist-entries/hash-max-ziplist-val и почему тип данных, лежащий в основе hash это и часть list, sorted set, set — не читайте. Для остальных я попробую об этом рассказать. Понимание устройства и работы хеш таблиц в Redis критически важно при написания систем, где важна экономия памяти.

О чём эта статья — какие расходы несёт Redis на хранения самого ключа, что такое ziplist и dict, когда и для чего они используются, сколько занимают в памяти. Когда hash хранится в ziplist, когда в dicth и что нам это даёт. Какие советы из модных статей об оптимизации Redis не стоит воспринимать всерьёз и почему.

Хочу сразу попросить прощения за то, что разбил материал на две статьи. Закончив часть о словаре, я понял, что вторая часть — про ziplist, получается немногим меньше первой. В итоге, после тестов на коллегах, принял решение разбить её на две части.

Сначала нам потребуется разобраться с тем, как работают отдельные структуры, которые лежат в основе Hashes. Затем посчитаем затраты на хранение данных. Вам будет проще понимать материал, если вы уже знаете что такое redisObject и как Redis хранит строки.

Есть некая путаница, в том, что структура hashes воспринимается как хеш таблица. Под капотом есть отдельный тип dict, который представляет собой настоящую хеш таблицу. Сама же структура hashes гибрид из dict и ziplist. Нам потребуется большое вступление о том, как устроены и работают хеш таблицы. Показав статью без этого материала нескольким свои коллегами убедился, что без него всё становится более запутанным.

В Redis вы управляете тем, каким внутренним типом данных будет представлен конкретный hash ключ. Переменная hash-max-ziplist-entries определяет максимальное количество элементов в hash при котом можно использовать кодировку REDIS_ENCODING_ZIPLIST. Например, при hash-max-ziplist-entries = 100 ваш hash будет представлен как ziplist, пока в нём будет менее 100 элементов. Как только элементов станет больше, он будет конвертирован в REDIS_ENCODING_HT (dict). Аналогично работает hash-max-ziplist-val — пока длина любого значения любого отдельного поля в hash не превышает hash-max-ziplist-val будет использоваться ziplist. Параметры работают в паре — внутреннее представление из ziplist в dict случится как только будет превышен любой из них. По умолчанию, любой hash всегда имеет кодировку ziplist.

Словари (dict) — ключевая структура Redis. Не только для hashes, но и для list, zset, set. Это основная структура, которая используется в Redis для хранения любых связок данных вида ключ — значение. Словари в Redis — это классическая хеш таблица, которая поддерживает операции вставки, замены, удаления, поиска и получения случайного элемента. Всю реализацию словарей можно найти в dict.h и disc.c в исходниках Redis.

У любой хеш таблицы есть ряд параметров, критически важных для понимания эффективности её работы и выбора правильной реализации. Помимо важной для любой структуры данных алгоритмической сложности это так же ряд факторов, которые напрямую зависят от условий использования. В этом ключе особенно интересны коэффициент заполнения(fill factor) и стратегия изменения размера. Последний особенно важен в любой системе, работающей в реальном времени, так как любая из имеющихся теоретических реализаций всегда ставит вас перед выбором — тратить много оперативной памяти или процессорного времени. Redis использует так называемое инкриментарное изменение размера(incremental resizing). Хотя есть предложения попробовать и linear hashing, monotonic keys, consistent hashing, resizing by copying в зависимости от специфики хеша.

Реализация инкриментарного изменения размера (функции dictRehashMilliseconds, dictRehash в dict.c), сводится к тому, что:

1. При изменении размера таблицы, мы выделяем новую хеш таблицу заведомо большую чем уже имеющаяся (и не меняем старую). Как и со строками, Redis станет удваивать количество слотов в новой таблице. Вместе с этим, любой запрашиваемый размер (включая первоначальный) всегда будет выровнен вверх до ближайшей степени двойки. Например, вам нужно 9 слотов, выделено будет — 16. Минимальная граница для новой таблицы определяется константой этапа компиляции DICT_HT_INITIAL_SIZE (по умолчанию 4, определена в dict.h).
2. Во время каждой операции чтения/записи заглядываем в обе таблицы.
3. Все операции вставки осуществляем только в новую таблицу.
4. При любой операции перемещаем n элементов из старой таблицы в новую.
5. Удаляем старую таблицу, если все элементы перенесены.

В случае с Redis, n — это количестве ключей, которые успел перенести сервер за 1 миллисекунду с шагов 1000. Иными словами, 1 шаг рехешинга — это не менее 1000 элементов. Это важно, поскольку при использовании ключей с длинными строковыми значениями такая операция может значительно превышать 1 мс, вызывая зависание сервера. Дополнительный аспект — большое пиковое потребление памяти при рехешинге таблицы, остро проявляющее себя на хешах с больших количеством «длинных» ключей. При расчётах мы будет рассматривать таблицы вне хеширования, помня, однако, что если в нашей ноде Redis есть большая таблица, есть высокая вероятность отказа от обслуживания при невозможности изменить её размер. Например, если вы арендуете бюджетный Redis на heroku(всего 25 мб памяти).

Коэффициент заполнения (константа dict_force_resize_ratio равна по умолчанию 5) определяет степень разреженности в словаре и то, когда Redis начнёт процесс удвоения размера текущего словаря. Текущее значение коэффициента заполнения определяется как отношение общего числа элементов в хеш таблице к числу слотов. Иными словами, если у нас всего 4 слота и 24 элемента (распределённых между ними) Redis примет решение об удвоении размера (24 / 4 > 5). Подобная проверка происходит при каждом обращении к любому ключу словаря. Если количество элементов станет равным или превысит число слотов — Redis так же попытается удвоить количество слотов.



Каждый словарь построен вокруг использования трех структур — dict, dictht и dictEntry. Dict — корневая структура, в её поле ht хранится от 1 до 2 (во время решенга) таблиц dictht с перечнем слотов. В свою очередь dictht хранит связанный список из dictEntry. Каждый dictEntry хранит в себе указатель на ключ и значение (в виде указателя или double/uint64_t/int64_t). Если вы используете в качестве значение число — dictEntry будет хранить число, храните строку — будет сохранён указатель на redisObject с sds строкой на борту.

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

1. С помощью хеширующей функции находится нужный слот (для поиска слота в настоящее время используется хеширующая функция MurMur2).
2. Все значения слота перебираются один за одним (связный список), сравнивая ключи.
3. Выполняется запрашиваемая операция над dictEntry (с ключом и значением)

В справке к HSET или HGET написано, что это операции выполняемые за О(1). Верьте с осторожностью: большую часть времени ваш hset будет занимать O(n). В больших таблицах (более 1000 элементов) с активной записью hget так же будет занимать O(n).

Ответ на вопрос сколько памяти будет использовано на самом деле, зависит от операционной системы, компилятора, типа вашего процесса и используемого аллокатора(в redis по умолчанию jemalloc). Все дальнейшие расчёты я привожу для redis 3.0.5 собранном на 64 битном сервере под управлением centos 7.

Теперь можно поcчитать, сколько памяти потратится при вызове `hset mySet foo bar`. Оверхед на создание пустого словаря:

• dictEntry: 3 * size_of(pointer)
  
• dictht: 3 * size_of(unsigned longs) + size_of(pointer) = 24 + size_of(pointer)
  
• dict: 2 * size_of(dictht) + 2 * size_of(int) + 2 * size_of(pointer) = 56 + 4 * size_of(pointer)
  

Если собрать всё вместе, то получаем формулу для вычисления приблизительных накладных расходов для хранения n элементов:

	56 + 2 * size_of(pointer) + 3 * next_power(n) * size_of(pointer) 
	-------------------------    -------------------------------------
	      |	                                      |
              ` dict + dictht                    `dictEntry  

Эта формула не учитывает расходы на хранение самого ключа и значения. Ключ всегда представляет собой sds строку в redisObject. Значение, в зависимости от типа может быть строкой sds или нативными числами (целыми или с плавающей точкой). Проверим для `hset mySet foo bar`, помня про то, что минимальное количество слотов (dictEntry) в новом словаре равно DICT_HT_INITIAL_SIZE(4):

56 + 2 * 8 + 3 * 4 * 8 = 168 + 2 * 56 = 280 байт (будет выровнено до 296 байт).

Проверяем:

config set hash-max-ziplist-entries 0
+OK
config set hash-max-ziplist-value 1
+OK
hset mySet foo bar
:1
debug object mySet
+Value at:0x7f44894d6340 refcount:1 encoding:hashtable serializedlength:9 lru:5614464 lru_seconds_idle:6

Что при этом показывает info memory? Он покажет вам, что потрачено 320 байт. На 24 байта больше, чем мы ожидали. Эта память — расходы на выравнивание при выделении памяти.

Как при этом был сохранён сам ключ mySet и как Redis находит наш hash по этому имени? В самом сердце Redis лежит структура redisDb (redis database representation, в redis.h). Она содержит единый словарь dict для всех ключей. Точно такой же, о котором рассказывалось выше. Это важно, так как даёт представление о расходах на хранение базы ключей и даст нам основу для понимания советов о том, что в одном экземпляре не стоит хранить много простых ключей.

Давайте посмотрим, что пишут в статье хранение сотен миллионов простых ключей. Если вам нужно хранить много пар ключ-значение не используйте строковые ключи, используйте хеш таблицы.
Гист с тестом из статьи instagram, мы напишем на LUA, чтобы не потребовалось для проверки ничего кроме запущенного Redis:

flushall
+OK
info memory
$225
# Memory
used_memory:508408

eval "for i=0,1000000,1 do redis.call('set', i, i) end" 0   
$-1
info memory
$226
# Memory
used_memory:88578952

Для хранения 1,000,000 целочисленных ключей нам потребовалось чуть больше 88 мб. Теперь сохраним те же данные в хеш таблицу, равномерно распределяя ключи между 2000 хеш таблиц:

flushall
+OK
info memory
$227
# Memory
used_memory:518496

eval "for i=0,1000000,1 do local bucket=math.floor(i/500); redis.call('hset', bucket, i, i) end" 0
$-1
info memory
$229
# Memory
used_memory:104407616

Для хранения тех же данных с целочисленными полями мы затратили чуть больше 103 мб. Однако, стоит нам попытаться сохранить скажем 10,000,000 ключей ситуация резко измениться, а именно ~970 мб против ~165 мб (и все они в накладных расходах на хранение в системной хеш таблице ключей). В целом правило «если у вас сотни миллионов ключей, не используйте строковые ключи» — правда.

Давайте рассмотрим ещё один аспект. Очень часто описывая оптимизации такого вида, подразумевается что вы имеете много ключей вида сущность: идентификатор (например `set username:4566 RedisMan`) и предлагают перейти к использованию хеш таблиц
bucket:id идентификатор значение (например `hset usernames:300 4566 RedisMan`). Важно понимать, что тут происходит частичная подмена понятий — sds строка `username:4566`превращается в поле-ключ 4566 с кодировкой REDIS_ENCODING_INT. Это означает, что вместо sds строки в redisObject стали использовать число, тем самым минимальные 32 байта на sds строку(после выравнивания jemalloc) превратились в 4 байта.

Давайте форсируем кодировку хеш таблиц в ziplist:

config set hash-max-ziplist-entries 1000                                           
+OK
config set hash-max-ziplist-value 1000000
+OK
flushall
+OK
eval "for i=0,1000000,1 do local b=math.floor(i/500); redis.call('hset', 'usernames:' ..b, i, i) end" 0
$-1
info memory
$228
# Memory
used_memory:16816432

На хранение наших данных ушло всего 16 мб или 72 мб экономии(в 5 раз меньше) c моим примером на 1,000,000 ключей. Заманчиво? К объяснению перейдём во второй части статьи.

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

• Используйте числовые имена ключей, значений, полей в хеш таблицах везде, где это возможно. Не используйте префиксы/постфиксы.
• При проектировании систем, активно использующих Redis, исходите из принципа: одна совокупность требований к данным — один Redis. Хранить разнородные данные сложно из-за настроек hash-max-ziplist-entries/hash-max-ziplist-value и разграничению ключей без префиксов.
• Заменяя простые ключи на группы хеш таблиц, помните о том, что ваша оптимизация работает при количестве ключей от миллиона и выше.
• Если в вашем экземпляре миллионы и сотни миллионов ключей — вы несёте огромные расходы на хранение их в системном словаре и перерасход памяти на резерв системного словаря. Скажем, для 100 млн ключей это составит порядка 2,5 гб только на сам системный dict без учёта ваших данных.
• Если вы проходите под значения hash-max-ziplist-entries/hash-max-ziplist-value и ваши данные хранятся в ziplist, вместо dict вы можете получить экономию памяти, выраженную в сотнях процентов. И заплатите за это высоким использованием CPU. Об этом далее.
  

Оглавление:

• Под капотом Redis: Строки
  
• Под капотом Redis: Хеш таблица (часть 1)
  
• Под капотом Redis: Хеш таблица (часть 2) и Список
  

Материалы, использованные при написании статьи:

• redis.io/topics/memory-optimization
  
• Back To Basics: Hashtables Part 2 by Karl Seguin
  
• en.m.wikipedia.org/wiki/Hash_table
• Redis Internal Data Structure: Dictionary by Wei Jin
• Исходники Redis 3.0.5
• Великолепный ответ на stackexchange о скорости и проблемах с коллизиями в разных алгоритмах хеширования
• github.com/sripathikrishnan/redis-rdb-tools/wiki/Redis-Memory-Optimization
• instagram-engineering.tumblr.com/post/12202313862/storing-hundreds-of-millions-of-simple-key-value