Ответ
Консистентное хеширование решает проблему минимизации перераспределения данных при добавлении или удалении узлов (серверов) в распределённой системе (например, в кластере кэша или базе данных).
Проблема без него (наивный подход):
При использовании простого хеширования вида hash(key) % N, где N — количество серверов, любое изменение N (добавление или удаление сервера) приводит к изменению результата для большинства ключей. Это вызывает массовое перемещение данных по всей системе, создавая огромную нагрузку.
Как работает консистентное хеширование:
- Хеш-кольцо: Вместо линейного распределения используется абстрактное кольцо (например, от 0 до 2^32 - 1).
- Размещение узлов: Каждый узел (сервер) хешируется и помещается в несколько точек на этом кольце (виртуальные ноды для более равномерного распределения).
- Размещение данных: Ключ данных также хешируется, и данные сохраняются на первом узле, который встречается на кольце при движении по часовой стрелке от точки хеша ключа.
Результат: При добавлении или удалении узла перераспределению подлежат только ключи, находящиеся в его зоне ответственности (в среднем K/N ключей), а не все данные в кластере.
Пример реализации на Go:
package main
import (
"fmt"
"hash/crc32"
"sort"
)
// Ring представляет хеш-кольцо
type Ring struct {
nodes []uint32 // Отсортированные хеши узлов
nodeMap map[uint32]string // Маппинг хеша на имя узла
}
// Get находит узел для заданного ключа
func (r *Ring) Get(key string) string {
hash := crc32.ChecksumIEEE([]byte(key))
// sort.Search находит первый узел, чей хеш >= хешу ключа
idx := sort.Search(len(r.nodes), func(i int) bool {
return r.nodes[i] >= hash
})
// Если мы вышли за пределы, возвращаемся к началу кольца
if idx == len(r.nodes) {
idx = 0
}
return r.nodeMap[r.nodes[idx]]
}Где используется: Распределенные базы данных (Cassandra, Riak), системы кэширования (Redis Cluster, Memcached), балансировщики нагрузки и CDN.