Как работает consistent hashing и зачем нужны виртуальные узлы?

**Проблема hash % N.** Ключ k идёт на сервер hash(k) mod N. Добавили сервер — N сменился, и ключ остаётся на месте, только если hash mod N = hash mod (N+1): это примерно 1/(N+1) ключей. Остальные переезжают. Для кэша это мгновенный промах почти по всем ключам и удар по базе; для хранилища — перенос почти всех данных.

Кольцо. Пространство хешей (например, 0…2³²−1) замыкается в кольцо. Каждый узел хешируется в точку на кольце. Ключ хешируется в точку и принадлежит первому узлу, встреченному по часовой стрелке. Поиск — бинарный поиск по отсортированному списку точек, O(log N).

• добавление узла — он забирает ключи только у соседа на дуге перед собой; переезжает около 1/(N+1) ключей;
• удаление — его ключи уходят следующему узлу.

Виртуальные узлы. С одной точкой на сервер дуги получаются разной длины — один сервер может получить в разы больше ключей. И при падении узла вся его нагрузка достаётся одному соседу. Решение — каждому серверу сотню-две точек (хешируем server#1, server#2, …). Дуги усредняются, разброс падает до нескольких процентов, а ключи упавшего узла расходятся по всем остальным. Веса — пропорциональное число точек.

Где используется: распределённые кэши (клиенты memcached, Redis Cluster использует 16384 фиксированных слота — разновидность того же подхода), Cassandra и DynamoDB (токены), балансировка с привязкой (Envoy ring hash, nginx hash ... consistent), CDN.

Альтернативы:

• rendezvous (HRW) — для ключа считаем hash(key, server) для всех серверов и берём максимум. Равномерно без виртуальных узлов, но O(N) на ключ;
• jump consistent hash (Google) — O(log N), без памяти, но серверы только нумеруются и удаляются с конца;
• Maglev — таблица поиска для L4-балансировщиков;
• фиксированные слоты (Redis Cluster, Kafka-партиции): много слотов, слоты переносятся между узлами — переезд явный и управляемый.

Bounded load — ограничение: узел не берёт больше (1 + ε) от средней нагрузки, лишнее уходит следующему по кольцу. Спасает от горячих ключей и неравномерности.

import bisect, hashlib

def h(s): return int(hashlib.md5(s.encode()).hexdigest()[:8], 16)

class Ring:
    def __init__(self, nodes, vnodes=150):
        self.points = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
        self.keys = [p for p, _ in self.points]

    def node(self, key):
        i = bisect.bisect(self.keys, h(key)) % len(self.keys)
        return self.points[i][1]