Что такое согласованное хеширование?

Question

Accepted Answer

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

## Проблема с простым хешированием

```text
Simple approach: node = hash(key) % N  (N = number of nodes)
  ✗ when N CHANGES (add/remove a node), N changes → MOST keys remap to different nodes →
    massive data movement / cache invalidation (almost everything moves!)
→ adding/removing a server causes huge disruption → bad for dynamic distributed systems.
```

## Как работает согласованное хеширование

```text
Map both NODES and KEYS onto a HASH RING (a circle of hash values):
  → a key belongs to the FIRST node clockwise from it on the ring
  → adding/removing a node only affects keys in ONE segment of the ring (its neighbors) →
    only a SMALL fraction of keys move (≈ K/N, not most of them)
→ minimal redistribution when nodes change → much better for dynamic systems.
```

## Виртуальные узлы и применение

```text
✓ VIRTUAL NODES → each physical node maps to MANY points on the ring → EVEN distribution
  (avoids uneven load from few nodes/uneven placement) → handles heterogeneous capacity
USES:
  → distributed CACHES (e.g. memcached clusters) — add/remove cache nodes without mass
    invalidation
  → distributed DATABASES (Cassandra, DynamoDB) — partition data across nodes
  → load balancers; any system distributing data/load across a changing set of nodes
```

## Почему это важно

Понимание согласованного хеширования — это ценное знание уровня senior, так как это **фундаментальная техника для распределения данных в динамических распределённых системах**, используется во многих реальных системах, поэтому это важно для проектирования распределённых систем.

Проблема, которую оно решает, реальна и важна: **простое хеширование** (`hash(key) % N`) вызывает **переопределение большинства ключей при изменении количества узлов** (добавление или удаление сервера перемещает почти все данные — вызывает массивное перемещение данных или инвалидацию кэша), что делает его неподходящим для динамических распределённых систем, где узлы добавляются и удаляются. **Согласованное хеширование** решает эту проблему, отображая как узлы, так и ключи на **хеш-кольцо** (ключ принадлежит первому узлу по часовой стрелке), поэтому **добавление или удаление узла перемещает только небольшую часть ключей** (те, что в одном сегменте кольца, ≈ K/N) вместо большинства — минимизируя перераспределение и нарушения при изменении набора узлов.

Понимание этого — как работает кольцо и почему оно минимизирует перемещение ключей — это ключевое понимание.

Понимание **виртуальных узлов** (отображение каждого физического узла на множество точек кольца для равномерного распределения, избежание неравномерной нагрузки, вызванной несколькими или плохо расположенными узлами, и обработка разнородной ёмкости) отражает, как согласованное хеширование хорошо работает на практике.

Понимание **применения** — распределённые кэши (добавление/удаление узлов кэша без массовой инвалидации), распределённые базы данных (Cassandra, DynamoDB разбивают данные на разделы) и балансировщики нагрузки — уточняет его важность, так как оно используется во многих реальных, широко распространённых системах.

Согласованное хеширование — это классическая, важная техника распределённых систем, часто появляющаяся в обсуждениях проектирования систем.

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