Согласованное хеширование

Согласованное хеширование (англ. consistent hashing) — это алгоритм распределения данных по множеству узлов (серверов, кэшей, баз данных), обеспечивающий минимальное перемещение данных при изменении состава узлов (добавлении или удалении). Относится к классу хеш-функций и используется в распределённых системах для балансировки нагрузки, кэширования и шардирования.

Принцип работы

В отличие от классического модульного хеширования (где ключ отображается на узел по формуле hash(key) % N, где N — число узлов), согласованное хеширование использует кольцевую структуру (хеш-кольцо). Каждый узел и каждый ключ отображаются на точки на кольце с помощью хеш-функции (например, SHA-1 или MD5). Ключ назначается на ближайший по часовой стрелке узел.

Хеш-кольцо

Хеш-кольцо представляет собой числовое пространство от 0 до 2^m - 1, где m — разрядность хеша (обычно 32 или 64 бита). Хеш-функция отображает как узлы, так и ключи на это пространство. Кольцо замыкается: после максимального значения следует минимальное.

Алгоритм назначения

1. Вычислить хеш ключа — получить точку на кольце.
2. Найти на кольце первый узел, чья хеш-позиция больше или равна хешу ключа (движение по часовой стрелке).
3. Если такой узел не найден (хеш ключа больше хеша всех узлов), ключ назначается на первый узел кольца (минимальный хеш).

Пример

Пусть на кольце расположены узлы A (хеш 10), B (хеш 50), C (хеш 100). Ключ с хешем 30 назначается на узел B (ближайший по часовой стрелке). Ключ с хешем 120 назначается на узел A (замыкание кольца).

История

Концепция согласованного хеширования впервые была предложена в 1997 году Дэвидом Кагером, Томом Левинсоном, Томасом Моссом и Эриком Брюером в статье «Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web». Алгоритм был разработан для решения проблемы кэширования в распределённых веб-системах, где добавление или удаление сервера приводило к массовому перераспределению ключей.

В 2001 году алгоритм был популяризирован в системе распределённого хранения данных Amazon Dynamo, а затем в проектах с открытым исходным кодом, таких как Apache Cassandra, Redis Cluster и Riak. В 2007 году в системе Amazon Dynamo была предложена модификация с использованием виртуальных узлов для улучшения балансировки.

Преимущества

• Минимальное перемещение данных: при добавлении или удалении узла перераспределяется только часть ключей, пропорциональная доле кольца, занимаемой узлом. В среднем перемещается K/N ключей, где K — общее число ключей, N — число узлов.
• Масштабируемость: добавление и удаление узлов происходит без полной реорганизации данных.
• Децентрализация: не требует центрального координатора для распределения ключей.
• Устойчивость к сбоям: при выходе узла из строя его нагрузка равномерно распределяется между соседними узлами.

Недостатки

• Неравномерное распределение: при малом числе узлов или неравномерном хешировании возможна концентрация ключей на одном узле. Для решения используется введение виртуальных узлов (vNodes).
• Сложность реализации: требует корректной обработки граничных случаев (замыкание кольца, пустое кольцо).
• Зависимость от хеш-функции: плохая хеш-функция может привести к неравномерному распределению.

Модификации

Виртуальные узлы (vNodes)

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

Взвешенное согласованное хеширование

Узлам назначаются веса, пропорциональные их ёмкости (например, объём памяти или процессорная мощность). Виртуальные узлы распределяются пропорционально весам.

Jump consistent hashing

Алгоритм, предложенный в 2014 году Джоном Лэмпингом и Эриком Вичем, обеспечивает равномерное распределение без использования кольца. Работает за O(log N) и не требует памяти для хранения виртуальных узлов. Используется в системах Google.

Rendezvous hashing (HRW)

Альтернативный алгоритм, в котором для каждого ключа вычисляется хеш со всеми узлами, и выбирается узел с максимальным значением. Обеспечивает минимальное перемещение данных, но требует O(N) вычислений на ключ.

Применение

Распределённое кэширование

Системы кэширования, такие как Memcached и Redis Cluster, используют согласованное хеширование для распределения ключей между серверами. При добавлении нового сервера перераспределяется только часть кэша, что минимизирует потери данных.

Шардирование баз данных

В распределённых базах данных (Cassandra, DynamoDB, Riak) согласованное хеширование используется для распределения данных по шардам. Каждый шард отвечает за диапазон хешей на кольце.

Балансировка нагрузки

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

Распределённые файловые системы

В системах типа Amazon S3, Google Cloud Storage и Ceph согласованное хеширование используется для распределения объектов по узлам хранения.

Реализации

• libketama: библиотека на C, реализующая согласованное хеширование с виртуальными узлами. Используется в Memcached.
• ConsistentHashRing: встроенная реализация в Apache Cassandra.
• Redis Cluster: использует собственную реализацию с 16384 слотами (виртуальные узлы).
• JumpHash: реализация jump consistent hashing на различных языках.

Критика

Основная критика согласованного хеширования связана с неравномерностью распределения при малом числе узлов. Для решения этой проблемы требуется введение большого количества виртуальных узлов, что увеличивает накладные расходы на память. Альтернативные алгоритмы (jump consistent hashing, rendezvous hashing) предлагают лучшую равномерность, но имеют свои ограничения по производительности или масштабируемости.

Интересные факты

• Согласованное хеширование лежит в основе распределённой хеш-таблицы (DHT), используемой в пиринговых сетях (например, BitTorrent, Kademlia).
• Алгоритм используется в системе управления конфигурациями etcd (разработка компании CoreOS, США) для распределения ключей между узлами.
• В 2020 году в проекте Apache Cassandra была предложена модификация с использованием «ленивого» перераспределения ключей для снижения нагрузки при добавлении узлов.

Источники

• Karger, D., et al. «Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.» Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997.
• DeCandia, G., et al. «Dynamo: Amazon’s Highly Available Key-value Store.» Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles, 2007.
• Lamping, J., Veach, E. «A Fast, Minimal Memory, Consistent Hash Algorithm.» arXiv:1406.2294, 2014.
• Thaler, D., Ravishankar, C. V. «A Name-Based Mapping Scheme for Rendezvous.» IEEE/ACM Transactions on Networking, 1998.
• Официальная документация Apache Cassandra, Redis Cluster, Memcached.