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

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

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

Согласованное хэширование основано на представлении всех возможных значений хэш-функции (например, от 0 до 2³²−1) в виде абстрактного кольца (хэш-кольца). Каждый узел системы (сервер) и каждый ключ данных отображаются в точку на этом кольце с помощью одной и той же хэш-функции (например, SHA-1 или MD5). Для определения того, какой узел отвечает за конкретный ключ, используется правило: ключ назначается первому узлу, встречающемуся при движении по кольцу по часовой стрелке от точки хэша ключа.

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

1. Хэширование узлов: Каждый физический узел (сервер) хэшируется и помещается на кольцо. Например, для сервера с идентификатором «server1» вычисляется хэш h(«server1»), который становится его позицией.
2. Хэширование ключей: Каждый ключ данных (например, имя файла или идентификатор записи) также хэшируется, и его позиция на кольце определяется как h(ключ).
3. Поиск ответственного узла: Начиная от позиции ключа, кольцо обходится по часовой стрелке до тех пор, пока не будет найден первый узел. Этот узел и становится владельцем данного ключа. Если ключ оказывается после последнего узла, поиск продолжается с начала кольца.

Пример

Предположим, на кольце расположены три узла: A, B и C. Ключ K1 хэшируется в точку между A и B. По часовой стрелке первым встречается узел B, поэтому K1 назначается на B. Ключ K2, хэшированный в точку после C, назначается на A (первый узел при переходе через ноль).

Свойства и преимущества

Минимальное перераспределение

Основное преимущество согласованного хэширования — устойчивость к изменению состава узлов. При добавлении нового узла D на кольцо только ключи, которые ранее принадлежали узлу, следующему за D по часовой стрелке, перераспределяются на D. В среднем, при добавлении или удалении одного узла из N узлов, переназначению подлежит лишь 1/N часть всех ключей. В модульном хэшировании при изменении N перераспределяются все ключи.

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

В базовой реализации возможна неравномерная загрузка узлов, если хэш-функция распределяет узлы на кольце неравномерно. Для решения этой проблемы применяются виртуальные узлы (англ. virtual nodes, vnodes). Каждый физический узел представляется на кольце несколькими виртуальными копиями (например, 100–200 штук), каждая со своим хэшем. Это сглаживает распределение и позволяет более равномерно распределять нагрузку между узлами, а также учитывать разную производительность (более мощные узлы могут иметь больше виртуальных узлов).

Отказоустойчивость

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

История

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

Практическое распространение технология получила после того, как в 2000-х годах её начали использовать крупные интернет-компании. В 2004 году компания Akamai Technologies применила согласованное хэширование для своей сети доставки контента (CDN). В 2006 году система распределённого кэширования Memcached в версии с поддержкой libketama (библиотека, реализующая согласованное хэширование) стала стандартом для многих проектов.

Применение

Согласованное хэширование является ключевым компонентом многих современных распределённых систем:

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

• Memcached (с использованием библиотеки libketama) — одна из первых и наиболее известных реализаций. Позволяет добавлять и удалять серверы кэша без сброса всего кэша.
• Redis Cluster — использует модифицированное согласованное хэширование (слоты хэшей) для распределения данных по 16384 слотам, каждый из которых закреплён за определённым узлом.

Базы данных

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

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

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

Пиринговые сети

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

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

• HAProxy — поддерживает алгоритм согласованного хэширования для привязки сессий пользователей к определённым серверам (sticky sessions).

Реализации

Существует несколько известных реализаций алгоритма:

• libketama — библиотека на C, первоначально разработанная для Memcached. Реализует согласованное хэширование с использованием MD5 и виртуальных узлов.
• Jump consistent hash — алгоритм, предложенный Google в 2014 году. Он не использует кольцо, а вычисляет назначение ключа на узел через итеративный процесс, обеспечивая равномерное распределение и минимальное перераспределение. Однако он не поддерживает произвольное добавление узлов (только последовательное увеличение числа узлов).
• Rendezvous hashing (HRW — Highest Random Weight) — альтернативный алгоритм, который для каждого ключа вычисляет вес для каждого узла и выбирает узел с максимальным весом. Он также обеспечивает минимальное перераспределение, но требует O(N) операций для каждого ключа, что может быть дорого при большом количестве узлов.

Критика и ограничения

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

Источники

• 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.
• Lamping, J., Veach, E. «A Fast, Minimal Memory, Consistent Hash Algorithm.» arXiv:1406.2294, 2014.