Apakah consistent hashing?

Question

IT Interview Practice · Accepted Answer

**Consistent hashing** ialah teknik untuk mengagihkan data merentasi nod (pelayan) yang **meminimumkan pengagihan semula apabila nod ditambah atau dialih keluar** — tidak seperti hashing ringkas, yang memetakan semula kebanyakan kunci apabila bilangan nod berubah. Ia penting untuk cache teragih, pangkalan data, dan pengagihan beban.

## Masalah dengan hashing ringkas

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

## Bagaimana consistent hashing berfungsi

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

## Virtual node dan penggunaan

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

## Mengapa ia penting

Memahami consistent hashing merupakan pengetahuan peringkat senior yang bernilai kerana ia merupakan **teknik asas untuk mengagihkan data dalam sistem teragih yang dinamik**, digunakan dalam banyak sistem sebenar, jadi ia penting untuk reka bentuk sistem teragih.

Masalah yang diselesaikannya adalah nyata dan penting: **hashing ringkas** (`hash(key) % N`) menyebabkan **kebanyakan kunci dipetakan semula apabila bilangan nod berubah** (menambah atau mengalih keluar pelayan memindahkan hampir semua data — menyebabkan pergerakan data atau cache invalidation yang besar-besaran), menjadikannya teruk untuk sistem teragih yang dinamik di mana nod ditambah dan dialih keluar. **Consistent hashing** menyelesaikan ini dengan memetakan kedua-dua nod dan kunci ke atas **hash ring** (dengan kunci milik nod pertama mengikut arah jam), supaya **menambah atau mengalih keluar nod hanya memindahkan sebahagian kecil kunci** (yang berada dalam satu segmen ring, ≈ K/N) dan bukannya kebanyakan — meminimumkan pengagihan semula dan gangguan apabila set nod berubah.

Memahami perkara ini — bagaimana ring berfungsi dan mengapa ia meminimumkan pergerakan kunci — merupakan pandangan utama.

Memahami **virtual node** (memetakan setiap nod fizikal ke banyak titik ring untuk taburan sekata, mengelakkan beban tidak sekata yang disebabkan oleh nod yang sedikit atau penempatan yang lemah, dan mengendalikan kapasiti heterogen) mencerminkan bagaimana consistent hashing berfungsi dengan baik dalam amalan.

Memahami **penggunaan** — cache teragih (menambah/mengalih keluar nod cache tanpa cache invalidation besar-besaran), pangkalan data teragih (Cassandra, DynamoDB membahagikan data), dan load balancer — menjelaskan kepentingannya, kerana ia digunakan dalam banyak sistem sebenar yang digunakan secara meluas.

Consistent hashing merupakan teknik sistem teragih klasik yang penting yang kerap muncul dalam perbincangan system design.

Memandangkan mengagihkan data merentasi set nod yang dinamik (dengan gangguan minimum apabila nod berubah) merupakan keperluan lazim dalam sistem teragih dan consistent hashing menyelesaikannya (di mana hashing ringkas gagal teruk), dan memandangkan ia digunakan dalam sistem sebenar (cache dan pangkalan data teragih) dan memahaminya mencerminkan pengetahuan sistem teragih, memahami consistent hashing merupakan pengetahuan peringkat senior yang bernilai — teknik asas untuk pengagihan data dalam sistem teragih yang dinamik, digunakan dalam banyak cache dan pangkalan data sebenar, menyelesaikan masalah pengagihan semula kunci pada hashing ringkas, dan konsep sistem teragih klasik yang mencerminkan kedalaman yang dijangkakan untuk peranan senior yang mereka bentuk sistem teragih.

Masalah dengan hashing ringkas

Bagaimana consistent hashing berfungsi

Virtual node dan penggunaan

Mengapa ia penting

Soalan berkaitan