Co je konzistentní hashování?

Question

Accepted Answer

**Konzistentní hashování** je technika pro distribuci dat mezi uzly (servery), která **minimalizuje opětovnou distribuci při přidávání nebo odebírání uzlů** — na rozdíl od jednoduchého hashování, které přemapuje většinu klíčů při změně počtu uzlů. Je důležité pro distribuované mezipaměti, databáze a distribuci zátěže.

## Problém s jednoduchým hashováním

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

## Jak konzistentní hashování funguje

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

## Virtuální uzly a aplikace

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

## Proč je to důležité

Rozmíšení konzistentního hashování je cenná znalost pro senior level, protože jde o **základní techniku pro distribuci dat v dynamických distribuovaných systémech**, která se používá v mnoha reálných systémech, a proto je důležitá pro návrh distribuovaných systémů.

Problém, který řeší, je reálný a důležitý: **jednoduché hashování** (`hash(key) % N`) způsobuje **přemapování většiny klíčů při změně počtu uzlů** (přidání nebo odebrání serveru přesune téměř všechna data — způsobuje masivní pohyb dat nebo znevalidnění mezipaměti), což je pro dynamické distribuované systémy, kde se uzly přidávají a odebírají, nepoužitelné. **Konzistentní hashování** to řeší mapováním jak uzlů tak klíčů na **hashovací kruh** (kde klíč patří prvnímu uzlu ve směru hodinových ručiček), takže **přidání nebo odebrání uzlu přemapuje pouze malou část klíčů** (ty v jednom segmentu kruhu, ≈ K/N) místo většiny — minimalizuje opětovnou distribuci a narušení při změně sady uzlů.

Rozmíšení toho — jak kruh funguje a proč minimalizuje pohyb klíčů — je klíčová myšlenka.

Rozmíšení **virtuálních uzlů** (mapování každého fyzického uzlu na mnoho bodů na kruhu pro rovnoměrnou distribuci, vyhýbání se nerovnoměrné zátěži, kterou způsobuje málo nebo špatně umístěných uzlů, a zvládání heterogenní kapacity) odráží, jak se konzistentní hashování v praxi funguje dobře.

Rozmíšení **aplikací** — distribuované mezipaměti (přidávání/odebírání uzlů mezipaměti bez masivního znevalidnění), distribuované databáze (Cassandra, DynamoDB dělí data) a load balancery — objasňuje jeho důležitost, protože se používá v mnoha reálných, často používaných systémech.

Konzistentní hashování je klasická, důležitá technika distribuovaných systémů, která se často objevuje v diskuzích o návrhu systémů.

Proto, že distribuce dat mezi dynamickou sadu uzlů (s minimálním narušením při změně uzlů) je běžná potřeba v distribuovaných systémech a konzistentní hashování ji řeší (kde jednoduché hashování selhává), a protože se používá v reálných systémech (distribuovaných mezipamětech a databázích) a jeho pochopení odráží znalost distribuovaných systémů, je porozumění konzistentnímu hashování cenná znalost pro senior level — základní technika pro distribuci dat v dynamických distribuovaných systémech, kterou používají mnohé reálné mezipaměti a databáze, řeší problém opětovného mapování klíčů u jednoduchého hashování, a je to klasický koncept distribuovaných systémů odrážející hloubku očekávanou pro senior role navrhující distribuované systémy.