Консистентное хеширование: стабильное размещение ключей при изменении состава узлов

Что это такое

Указанная документация Cassandra противопоставляет наивное хеширование — остаток от деления хеша ключа на число корзин — консистентному хешированию. При последнем каждый узел владеет одним или несколькими токенами на непрерывном хеш-кольце, ключ хешируется на это кольцо, а владельцем становится следующий узел при обходе в выбранном направлении. При изменении числа узлов перемещается лишь небольшая доля ключей. Если токен на узел один, а узлов мало, для нового узла нет позиции токена, сохраняющей баланс кольца; неравные диапазоны означают неравную нагрузку. Поэтому Cassandra следует статье Dynamo и назначает каждому физическому узлу несколько токенов — виртуальные узлы, — чтобы даже один добавленный узел забирал много небольших фрагментов у многих соседей.

Указанный модуль upstream в nginx предоставляет тот же выбор: обычный hash $key может перераспределить большинство ключей при удалении сервера, а hash $key consistent использует метод ketama, при котором перемещается лишь немного ключей. Указанная документация Envoy предлагает балансировщик на хеш-кольце и Maglev — табличный вариант с более быстрым поиском; она отмечает, что при удалении хостов Maglev перемещает больше ключей, чем кольцо.

Почему это важно

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

Как применять

• Выбирайте ключ хеширования с достаточным числом различных значений (идентификатор пользователя, арендатора, ключ кеша), а не, например, IP клиента за NAT.
• Используйте реализацию библиотеки или прокси. Настройте виртуальные узлы или размер таблицы для равномерной нагрузки на узлы и следите за долей каждого хоста (Envoy предоставляет метрики минимального и максимального числа записей на хост).
• Для репликации выбирайте следующие k различных физических узлов на кольце, пропуская виртуальные узлы той же машины и, по возможности, той же стойки или зоны.
• Продумайте перемещение данных при присоединении узла: новый владелец должен получить свой диапазон до начала обслуживания либо во время перехода обращаться за промахами к прежнему владельцу.
• Зафиксируйте хеш-функцию на весь срок работы развёртывания: её смена перераспределяет всё.

Подводные камни

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