Согласованное и рандеву хеширование
Согласованное хеширование (Consistent hashing) — это специальная техника хеширования в компьютерных науках, которая обладает важным свойством: при изменении размера хеш-таблицы требуется перераспределить в среднем только n/m ключей, где n — количество ключей, а m — количество слотов.
Основные особенности
- Эффективность при масштабировании: В отличие от традиционных хеш-таблиц, где изменение количества слотов приводит к перераспределению почти всех ключей, согласованное хеширование минимизирует количество перемещаемых данных.
- Распределение нагрузки: Техника равномерно распределяет ключи кэша по шардам, даже если некоторые шарды выходят из строя или становятся недоступными.
Применение
Согласованное хеширование широко используется в распределенных системах, особенно в:
- Распределенных кэшах
- Системах хранения данных (например, Amazon Dynamo)
- Сетях доставки контента (CDN)
- Балансировке нагрузки
Принцип работы
- Ключи и серверы отображаются на виртуальную окружность (обычно от 0 до 2π).
- Каждый ключ назначается ближайшему серверу по часовой стрелке.
- При добавлении или удалении сервера перераспределяются только ключи, попадающие в его сегмент.
Преимущества
- Минимизация перераспределения данных при изменении количества серверов.
- Улучшение масштабируемости и отказоустойчивости распределенных систем.
Согласованное хеширование стало ключевой технологией для многих современных распределенных систем, обеспечивая эффективное распределение данных и нагрузки
Рандеву-хеширование (Rendezvous hashing) или хеширование с наибольшим случайным весом (HRW) — это алгоритм, позволяющий клиентам достичь распределенного соглашения о выборе k вариантов из n возможных. Этот метод часто применяется в распределенных системах для назначения объектов серверам или прокси.
Основные особенности
- Простота: Алгоритм концептуально прост и легок в реализации.
- Минимальное нарушение: При добавлении или удалении узла перераспределяются только объекты, связанные с этим узлом.
- Равномерное распределение: Обеспечивает равномерное распределение объектов по узлам.
- Поддержка взвешивания: Позволяет учитывать разную мощность узлов.
Принцип работы
- Для каждого объекта и каждого узла вычисляется хеш-значение.
- Объект назначается узлу с наибольшим хеш-значением.
- При изменении набора узлов пересчитываются только затронутые объекты.
Применение
Рандеву-хеширование используется во многих реальных системах, включая:
- Балансировщик нагрузки GitHub
- Распределенная база данных Apache Ignite
- Файловое хранилище Tahoe-LAFS
- Pub/sub платформа Twitter EventBus
Преимущества перед согласованным хешированием
- Более простая концепция и реализация
- Не требует предварительных вычислений или хранения токенов
- Обеспечивает простое решение для распределенного k-соглашения
Рандеву-хеширование становится все более популярным в современных распределенных системах благодаря своей простоте, эффективности и гибкости
| Характеристика | Согласованное хеширование | Рандеву-хеширование |
|---|---|---|
| Год изобретения | 1997 | 1996 |
| Сложность | Более сложный | Проще |
| Метод отображения | Отображает узлы и ключи на кольцо хеширования | Вычисляет хеш-значения для каждой пары ключ-узел |
| Размещение объектов | По часовой стрелке на хеш-кольце | Выбирает узел с наибольшим хеш-значением |
| Балансировка нагрузки | Хорошая, но могут быть горячие точки | В целом лучше, более равномерная |
| Масштабируемость | Хорошо масштабируется при инкрементных изменениях | Менее масштабируемо, пересчитывает все хеши |
| Предварительные вычисления токенов | Требует предварительного вычисления и хранения токенов | Не требует предварительных вычислений токенов |
| Сложность добавления/удаления узлов | O(K/N + log N) | O(n) для базовой реализации |
| Перераспределение ключей | Минимальное перемещение ключей | Объекты перераспределяются на оставшиеся узлы |
| Реальное использование | Cassandra, Couchbase | GitHub Load Balancer, Apache Ignite, Twitter EventBus |
