Apa itu consistent hashing?

Question

IT Interview Practice · Accepted Answer

**Consistent hashing** adalah teknik untuk mendistribusikan data di seluruh node (server) yang **meminimalkan redistribusi ketika node ditambahkan atau dihapus** — berbeda dengan simple hashing, yang memetakan ulang sebagian besar kunci ketika jumlah node berubah. Ini penting untuk distributed caches, databases, dan load distribution.

## Masalah dengan simple 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.
```

## Cara kerja consistent hashing

```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 nodes 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 ini penting

Memahami consistent hashing adalah pengetahuan tingkat senior yang berharga karena ini adalah **teknik fundamental untuk mendistribusikan data dalam dynamic distributed systems**, digunakan dalam banyak sistem nyata, sehingga penting untuk desain distributed system.

Masalah yang dipecahkannya adalah nyata dan penting: **simple hashing** (`hash(key) % N`) menyebabkan **sebagian besar kunci dipetakan ulang ketika jumlah node berubah** (menambahkan atau menghapus server memindahkan hampir semua data — menyebabkan pergerakan data besar-besaran atau cache invalidation), membuatnya sangat buruk untuk dynamic distributed systems di mana node ditambahkan dan dihapus. **Consistent hashing** memecahkan ini dengan memetakan kedua node dan kunci ke **hash ring** (dengan kunci milik node pertama searah jarum jam), sehingga **menambahkan atau menghapus node hanya memindahkan sebagian kecil kunci** (kunci di satu segmen ring, ≈ K/N) daripada sebagian besar — meminimalkan redistribusi dan gangguan ketika set node berubah.

Memahami ini — bagaimana ring bekerja dan mengapa itu meminimalkan pergerakan kunci — adalah insight kunci.

Memahami **virtual nodes** (memetakan setiap physical node ke banyak ring points untuk distribusi yang merata, menghindari beban yang tidak merata yang disebabkan oleh beberapa atau node yang ditempatkan dengan buruk, dan menangani kapasitas heterogen) mencerminkan bagaimana consistent hashing bekerja dengan baik dalam praktik.

Memahami **penggunaan** — distributed caches (menambahkan/menghapus cache nodes tanpa invalidasi massal), distributed databases (Cassandra, DynamoDB partisi data), dan load balancers — memperjelas pentingnya, karena digunakan dalam banyak sistem nyata yang banyak digunakan.

Consistent hashing adalah teknik distributed-systems klasik dan penting yang sering muncul dalam diskusi system design.

Karena mendistribusikan data di seluruh dynamic set dari nodes (dengan gangguan minimal ketika nodes berubah) adalah kebutuhan umum dalam distributed systems dan consistent hashing memecahkannya (di mana simple hashing gagal dengan buruk), dan karena digunakan dalam sistem nyata (distributed caches dan databases) dan memahaminya mencerminkan pengetahuan distributed-systems, memahami consistent hashing adalah pengetahuan tingkat senior yang berharga — teknik fundamental untuk distribusi data dalam dynamic distributed systems, digunakan dalam banyak caches dan databases nyata, memecahkan masalah key-redistribution dari simple hashing, dan konsep distributed-systems klasik yang mencerminkan kedalaman yang diharapkan untuk peran senior yang merancang distributed systems.

Masalah dengan simple hashing

Cara kerja consistent hashing

Virtual nodes dan penggunaan

Mengapa ini penting

Pertanyaan terkait