Vad är consistent hashing?

Question

Accepted Answer

**Consistent hashing** är en teknik för att distribuera data över noder (servrar) som **minimerar omfördelning när noder läggs till eller tas bort** — till skillnad från enkel hashing, som mappar om de flesta nycklar när antalet noder ändras. Det är viktigt för distribuerade cacheminnen, databaser och lastfördelning.

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

## Hur consistent hashing fungerar

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

## Virtuella noder och användningsområden

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

## Varför det är viktigt

Att förstå consistent hashing är värdeful kunskap på seniornivå eftersom det är en **fundamental teknik för att distribuera data i dynamiska distribuerade system**, används i många verkliga system, och är därför viktig för design av distribuerade system.

Problemet det löser är verkligt och viktigt: **enkel hashing** (`hash(key) % N`) orsakar att **de flesta nycklar omkartläggs när antalet noder ändras** (att lägga till eller ta bort en server förflyttar nästan all data — vilket orsakar massiv dataförflyttning eller cacheinvalidering), vilket gör det dåligt för dynamiska distribuerade system där noder läggs till och tas bort. **Consistent hashing** löser detta genom att mappa både noder och nycklar på en **hash ring** (där en nyckel tillhör den första noden medurs), så att **att lägga till eller ta bort en nod endast förflyttar en liten del av nycklarna** (de i ett ring-segment, ≈ K/N) snarare än de flesta — vilket minimerar omfördelning och störning när noduppsättningen ändras.

Att förstå detta — hur ringen fungerar och varför den minimerar nyckelförflyttning — är den viktigaste insikten.

Att förstå **virtuella noder** (att mappa varje fysisk nod till många ring-punkter för jämn fördelning, undvika den ojämna belastning som få eller dåligt placerade noder orsakar, och hantera heterogen kapacitet) återspeglar hur consistent hashing fungerar bra i praktiken.

Att förstå **användningsområdena** — distribuerade cacheminnen (att lägga till/ta bort cachenoder utan massinvalidering), distribuerade databaser (Cassandra, DynamoDB-partitionering av data) och lastbalanserare — klargör dess betydelse, eftersom det används i många verkliga, välanvända system.

Consistent hashing är en klassisk, viktig teknik för distribuerade system som ofta förekommer i diskussioner om systemdesign.

Eftersom att distribuera data över en dynamisk uppsättning noder (med minimal störning när noder ändras) är ett vanligt behov i distribuerade system och consistent hashing löser det (där enkel hashing misslyckas helt), och eftersom det används i verkliga system (distribuerade cacheminnen och databaser) och förståelse för det återspeglar kunskap om distribuerade system, är förståelse för consistent hashing värdeful kunskap på seniornivå — en fundamental teknik för datadistribution i dynamiska distribuerade system, används i många verkliga cacheminnen och databaser, löser nyckelomfördelningsproblemet med enkel hashing, och är ett klassiskt distribuerat-system-koncept som återspeglar den djup som förväntas för seniorrollen när man designar distribuerade system.