Što je konzistentno heširanje?

Question

Accepted Answer

**Konzistentno heširanje** je tehnika za distribuciju podataka među čvorovima (serverima) koja **minimizira redistribuciju kada se čvorovi dodaju ili uklanjaju** — za razliku od jednostavnog heširen ja, koje ponovno mapira većinu ključeva kada se broj čvorova promijeni. Važno je za distribuirane cache-eve, baze podataka i distribuciju opterećenja.

## Problem s jednostavnim heširenjem

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

## Kako konzistentno heširanje funkcionira

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

## Virtualni čvorovi i primjena

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

## Zašto je to važno

Razumijevanje konzistentnog heširanje je vrijedna znanja na razini seniora jer je to **fundamentalna tehnika za distribuciju podataka u dinamičkim distribuiranim sustavima**, korištena u mnogim stvarnim sustavima, pa je važna za dizajn distribuiranih sustava.

Problem koji rješava je pravi i važan: **jednostavno heširanje** (`hash(key) % N`) uzrokuje da se **većina ključeva ponovno mapira kada se broj čvorova promijeni** (dodavanje ili uklanjanje servera premješta gotovo sve podatke — što uzrokuje masivno premještanje podataka ili invalidaciju cache-a), što ga čini neprikladnim za dinamičke distribuirane sustave gdje se čvorovi dodaju i uklanjaju. **Konzistentno heširanje** rješava to mapiranjem i čvorova i ključeva na **heš prsten** (gdje ključ pripada prvom čvoru u smjeru kazaljke na satu), tako da **dodavanje ili uklanjanje čvora premješta samo mali dio ključeva** (one u jednom segmentu prstena, ≈ K/N) umjesto većine — minimizirajući redistribuciju i poremetnje kada se skup čvorova promijeni.

Razumijevanje toga — kako prsten funkcionira i zašto minimizira pomicanje ključeva — je ključni uvid.

Razumijevanje **virtualnih čvorova** (mapiranje svakog fizičkog čvora na mnoge točke prstena za ujednačenu distribuciju, izbjegavajući neujednačeno opterećenje koje uzrokuju nekoliko ili loše postavljenih čvorova, te rukovanje heterogenim kapacitetom) odražava kako konzistentno heširanje dobro funkcionira u praksi.

Razumijevanje **primjena** — distribuirani cache-evi (dodavanje/uklanjanje cache čvorova bez masovne invalidacije), distribuirane baze podataka (Cassandra, DynamoDB particioniranje podataka) i load balanceri — pojašnjava njegovu važnost, jer se koristi u mnogim stvarnim, široko korištenim sustavima.

Konzistentno heširanje je klasična, važna tehnika distribuiranih sustava koja se često pojavljuje u raspravama o dizajnu sustava.

Budući da je distribucija podataka preko dinamičkog skupa čvorova (s minimalnom poremećajem kada se čvorovi promijene) česta potreba u distribuiranim sustavima i konzistentno heširanje je rješava (gdje jednostavno heširanje neuspješno), te budući da se koristi u stvarnim sustavima (distribuirani cache-evi i baze podataka) i razumijevanje toga odražava znanje o distribuiranim sustavima, razumijevanje konzistentnog heširanje je vrijedna znanja na razini seniora — fundamentalna tehnika za distribuciju podataka u dinamičkim distribuiranim sustavima, korištena u mnogim stvarnim cache-evima i bazama podataka, rješavajući problem redistribucije ključeva jednostavnog heširanje, te klasičan koncept distribuiranih sustava koji odražava dubinu očekivanu za senior uloge pri dizajniranju distribuiranih sustava.