Ответ
Консистентное хеширование — это алгоритм, который используется в распределённых системах для минимизации перемещения данных при добавлении или удалении серверов (узлов).
Проблема, которую решает
Представьте, у вас есть 4 сервера и вы распределяете данные по ключу, используя простую формулу hash(key) % 4. Если вы добавите пятый сервер (N=5), то формула изменится на hash(key) % 5. В результате почти все ключи поменяют свое местоположение, и придется переместить огромное количество данных. Консистентное хеширование решает эту проблему.
Как это работает (принцип "хеш-кольца")
- Создается кольцо: Представьте себе абстрактное числовое кольцо (например, от 0 до 2^32 - 1).
- Размещаются серверы: Каждый сервер хешируется и помещается в соответствующую точку на этом кольце.
- Размещаются ключи: Каждый ключ данных также хешируется и помещается на это же кольцо.
- Определяется владелец: Чтобы найти, на каком сервере хранить ключ, мы движемся от точки ключа по часовой стрелке до тех пор, пока не встретим первый сервер. Этот сервер и будет хранить данные.
Ключевые преимущества
- Минимальное перераспределение: При добавлении нового сервера на кольцо, только ключи, находящиеся между ним и предыдущим сервером, меняют своего «владельца». То же самое при удалении. Это главное преимущество.
- Горизонтальное масштабирование: Легко и с минимальными издержками добавлять и удалять узлы.
- Сглаживание нагрузки: Для более равномерного распределения данных используются «виртуальные узлы» (virtual nodes) — один физический сервер может быть представлен несколькими точками на кольце.
Где используется
- Базы данных: Cassandra, Riak, DynamoDB.
- Кеширование: Memcached, Redis Cluster.
- Балансировщики нагрузки и сети доставки контента (CDN).