Консистентное хеширование

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

История

Концепция консистентного хеширования была впервые предложена Дэвидом Каргером (David Karger) и его коллегами из Массачусетского технологического института (MIT) в 1997 году в работе «Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web». Изначально алгоритм разрабатывался для решения проблемы кэширования в распределённых веб-системах, где динамическое изменение состава серверов (выход из строя, добавление новых) приводило к лавинообразному сбросу кэша. Позднее метод был популяризирован и широко внедрён в практику такими системами, как распределённое хранилище Amazon Dynamo (2007) и система управления конфигурациями Apache Cassandra, а также в кэширующих прокси-серверах, например, в проекте Memcached.

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

Хеш-кольцо

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

Определение владельца

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

Добавление и удаление узлов

• Добавление узла: Новый узел помещается на кольцо в соответствии со своим хешем. Он «перехватывает» часть ключей, которые ранее принадлежали узлу, следующему за ним по часовой стрелке. Ключи, принадлежащие другим узлам, не затрагиваются.
• Удаление узла: При выходе узла из строя или его удалении все ключи, которые были закреплены за ним, переходят к следующему узлу по часовой стрелке. Остальные узлы и их ключи остаются неизменными.

Таким образом, при изменении состава кластера перераспределяется только 1/N часть всех ключей (где N — общее число узлов), что является ключевым преимуществом перед модульным хешированием, где перераспределяется почти 100% ключей.

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

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

• Сгладить неравномерность распределения, особенно при малом количестве физических узлов.
• Обеспечить более плавное перераспределение нагрузки при добавлении или удалении узла, так как нагрузка снимается или добавляется не целиком, а порциями, соответствующими виртуальным узлам.

Применение

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

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

Распределённые базы данных

В системах управления базами данных, построенных на принципах распределённого хранения (NoSQL), консистентное хеширование используется для шардирования (разделения данных на части). Примеры:

• Apache Cassandra — использует консистентное хеширование для распределения данных по узлам кластера, обеспечивая высокую доступность и масштабируемость.
• Amazon DynamoDB — внутренняя реализация Dynamo (на которой основан DynamoDB) использует этот алгоритм для балансировки нагрузки.
• Project Voldemort — распределённое хранилище ключ-значение от LinkedIn.

Системы управления конфигурациями

Некоторые системы, такие как Consul (в части распределения сессий) и etcd, используют консистентное хеширование для распределения нагрузки на запросы к распределённому хранилищу конфигураций.

Сети доставки контента (CDN)

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

Преимущества и недостатки

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

• Минимальное перераспределение: При изменении числа узлов перераспределяется только часть ключей, прямо пропорциональная доле изменённых узлов.
• Масштабируемость: Легко добавлять и удалять узлы без полной остановки системы.
• Децентрализация: Не требует единого диспетчера или координатора для принятия решений о распределении.
• Устойчивость к сбоям: Выход одного узла не приводит к каскадному отказу всей системы.

Недостатки

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

Сравнение с другими методами

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

• Алгоритм консистентного хеширования лёг в основу работы распределённой хеш-таблицы (DHT), используемой в пиринговых сетях (например, в протоколе BitTorrent).
• В 2014 году консистентное хеширование было усовершенствовано в проекте Amazon DynamoDB+ для поддержки «горячих» ключей (ключей с очень высокой частотой запросов).
• Некоторые реализации (например, в библиотеке libketama для Memcached) используют алгоритм, основанный на консистентном хешировании, который был разработан инженерами компании Last.fm.

Источники

• 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.
• Lakshman, A., & Malik, P. «Cassandra: A Decentralized Structured Storage System.» ACM SIGOPS Operating Systems Review, 2010.
• Официальная документация Apache Cassandra: «Partitioners» (раздел о консистентном хешировании).
• Документация Memcached: «Consistent Hashing» (раздел о распределении ключей).