Hva er konsistent hashing?

Question

Accepted Answer

**Konsistent hashing** er en teknikk for å distribuere data på tvers av noder (servere) som **minimerer omfordeling når noder legges til eller fjernes** — i motsetning til enkel hashing, som remapper de fleste nøkler når antallet noder endres. Det er viktig for distribuerte cacher, databaser og lastfordeling.

## Problemet med enkel hashing

```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.
```

## Hvordan konsistent hashing fungerer

```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.
```

## Virtuelle noder og bruksområder

```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
```

## Hvorfor det er viktig

Å forstå konsistent hashing er verdifull kunnskap på seniornivå fordi det er en **fundamental teknikk for å distribuere data i dynamiske distribuerte systemer**, brukt i mange virkelige systemer, så det er viktig for design av distribuerte systemer.

Problemet det løser er realt og viktig: **enkel hashing** (`hash(key) % N`) gjør at **de fleste nøkler remappes når antallet noder endres** (å legge til eller fjerne en server flytter nesten alle data — forårsaker massiv databevegelse eller cache-invalidering), noe som gjør det dårlig for dynamiske distribuerte systemer hvor noder blir lagt til og fjernet. **Konsistent hashing** løser dette ved å mappe både noder og nøkler på en **hash-ring** (med en nøkkel som tilhører den første noden med klokken), slik at **å legge til eller fjerne en node bare flytter en liten brøkdel av nøklene** (de i ett ring-segment, ≈ K/N) i stedet for de fleste — noe som minimerer omfordeling og forstyrrelse når nodene endres.

Å forstå dette — hvordan ring-en fungerer og hvorfor den minimerer nøkkelbevegelse — er den viktige innsikten.

Å forstå **virtuelle noder** (kartlegge hver fysisk node til mange ring-punkter for jevn fordeling, unngå ujevn last som få eller dårlig plasserte noder forårsaker, og håndtere heterogen kapasitet) reflekterer hvordan konsistent hashing fungerer godt i praksis.

Å forstå **bruksområdene** — distribuerte cacher (legge til/fjerne cache-noder uten masse invalidering), distribuerte databaser (Cassandra, DynamoDB partisjonerer data), og lastbalanserere — klargjør dens betydning, siden det brukes i mange virkelige, mye brukte systemer.

Konsistent hashing er en klassisk, viktig teknikk for distribuerte systemer som hyppig dukker opp i diskusjoner om systemdesign.

Siden å distribuere data på tvers av et dynamisk sett av noder (med minimal forstyrrelse når noder endres) er et vanlig behov i distribuerte systemer og konsistent hashing løser det (hvor enkel hashing mislykkes dårlig), og siden det brukes i virkelige systemer (distribuerte cacher og databaser) og forståelse av det reflekterer kunnskap om distribuerte systemer, er forståelse av konsistent hashing verdifull kunnskap på seniornivå — en fundamental teknikk for datadistribusjon i dynamiske distribuerte systemer, brukt i mange virkelige cacher og databaser, løser nøkkelomfordelingproblemet med enkel hashing, og er et klassisk distribuert-systemer-konsept som reflekterer dybden som forventes for seniorroller som designer distribuerte systemer.