Что такое консистентное хеширование (consistent hashing) и какую проблему оно решает?

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

Проблема обычного хеширования:

Представьте, что у вас N серверов, и вы распределяете данные по ним с помощью формулы server_index = hash(key) % N. Если вы добавите новый сервер (N+1), то почти все ключи поменяют свой сервер назначения, так как изменился делитель. Это приведет к массовой миграции данных и огромной нагрузке на систему.

Как работает консистентное хеширование (аналогия с кольцом):

1. Создается хеш-кольцо: Представьте себе окружность со значениями от 0 до 2^32-1.
2. Узлы размещаются на кольце: Каждый сервер хешируется (например, по IP-адресу), и его хеш-значение определяет его позицию на этом кольце.
3. Ключи размещаются на кольце: Для каждого ключа данных также вычисляется хеш, который определяет его позицию на кольце.
4. Определение сервера: Чтобы найти, на каком сервере должен храниться ключ, мы находим позицию ключа на кольце и движемся по часовой стрелке до тех пор, пока не встретим первый узел. Этот узел и будет отвечать за данный ключ.

Преимущество:

Когда новый узел добавляется на кольцо, он забирает на себя только часть ключей от своего соседа по часовой стрелке. Аналогично, при удалении узла его ключи переходят к следующему за ним соседу. В обоих случаях затрагивается минимальное количество ключей, а не вся система.

Пример реализации на Go:

package main

import (
    "fmt"
    "hash/crc32"
    "sort"
)

// ConsistentHash представляет наше хеш-кольцо
type ConsistentHash struct {
    nodes map[uint32]string // Хеш узла -> имя узла
    keys  []uint32          // Отсортированные хеши узлов
}

// AddNode добавляет узел (сервер) на кольцо
func (ch *ConsistentHash) AddNode(node string) {
    hash := crc32.ChecksumIEEE([]byte(node))
    ch.nodes[hash] = node
    ch.keys = append(ch.keys, hash)
    // Поддерживаем ключи отсортированными для быстрого поиска
    sort.Slice(ch.keys, func(i, j int) bool { return ch.keys[i] < ch.keys[j] })
}

// GetNode находит узел для заданного ключа
func (ch *ConsistentHash) GetNode(key string) string {
    if len(ch.keys) == 0 {
        return ""
    }
    hash := crc32.ChecksumIEEE([]byte(key))

    // Ищем первый узел, чей хеш больше или равен хешу ключа
    idx := sort.Search(len(ch.keys), func(i int) bool { return ch.keys[i] >= hash })

    // Если такого узла нет (ключ "заворачивается" на начало кольца)
    if idx == len(ch.keys) {
        idx = 0
    }

    return ch.nodes[ch.keys[idx]]
}

func main() {
    ch := &ConsistentHash{nodes: make(map[uint32]string)}
    ch.AddNode("server-1")
    ch.AddNode("server-2")
    ch.AddNode("server-3")

    fmt.Printf("Ключ 'user:100' находится на: %sn", ch.GetNode("user:100"))
    fmt.Printf("Ключ 'article:55' находится на: %sn", ch.GetNode("article:55"))
}

Где используется: Распределенные кеши (Redis, Memcached), шардирование баз данных (Cassandra, DynamoDB), балансировщики нагрузки.