Pengantar

Ketika sebuah aplikasi berkembang, satu server sering kali tidak lagi cukup untuk menangani seluruh permintaan pengguna. Data dan traffic kemudian perlu didistribusikan ke beberapa server agar sistem dapat tetap cepat, stabil, dan mudah dikembangkan.

Salah satu tantangan dalam sistem terdistribusi adalah menentukan server mana yang harus menangani sebuah data atau request.

Pendekatan sederhana seperti modulo hashing memang dapat digunakan. Namun, metode tersebut memiliki masalah ketika jumlah server berubah. Penambahan atau penghapusan satu server dapat menyebabkan sebagian besar data harus dipetakan ulang.

Di sinilah Consistent Hashing menjadi penting.

Consistent hashing merupakan teknik untuk mendistribusikan key ke sejumlah node dengan tujuan meminimalkan jumlah key yang harus berpindah ketika node ditambahkan atau dihapus. Konsep ini diperkenalkan dalam penelitian Karger dan rekan-rekannya pada 1997 untuk membantu sistem caching terdistribusi menghadapi perubahan node dan beban jaringan (dikutip dari: https://doi.org/10.1145/258533.258660).

Teknik tersebut kemudian menjadi konsep penting dalam berbagai sistem terdistribusi, termasuk sistem caching, distributed storage, dan load balancing.

Apa Itu Consistent Hashing?

Pengertian Consistent Hashing

Consistent hashing adalah teknik hashing yang memetakan data dan server ke sebuah ruang hash yang sama.

Berbeda dengan hashing biasa yang langsung menggunakan hasil hash untuk menentukan server, consistent hashing menggunakan konsep hash ring atau lingkaran hash.

Setiap server ditempatkan pada posisi tertentu di ring berdasarkan hasil hash identitas server.

Key atau objek yang ingin disimpan juga di-hash dan ditempatkan pada ring yang sama.

Server yang bertanggung jawab kemudian ditentukan berdasarkan posisi key dan aturan pencarian node berikutnya pada ring.

baca juga : Cross-Site Request Forgery (CSRF): Cara Kerja Serangan dan Strategi Efektif untuk Melindungi Web

Mengapa Hashing Biasa Menjadi Masalah?

Contoh Modulo Hashing

Misalnya terdapat tiga server:

Server A
Server B
Server C

Sistem dapat menggunakan:

server = hash(key) % 3

Dengan cara tersebut, key akan didistribusikan ke salah satu dari tiga server.

Masalah muncul ketika server baru ditambahkan.

Misalnya:

Sebelumnya:
hash(key) % 3

Setelah server ditambahkan:
hash(key) % 4

Karena pembagi berubah dari 3 menjadi 4, hasil pemetaan banyak key juga berubah.

Akibatnya, sebagian besar data dapat dianggap berpindah server.

Masalah Data Remapping

Bayangkan terdapat 1 juta key yang tersebar pada tiga server.

Kemudian administrator menambahkan satu server baru.

Pada hashing berbasis modulo, perubahan jumlah node dapat membuat banyak key mendapatkan hasil hash yang berbeda.

Konsekuensinya dapat berupa:

  • Cache menjadi banyak miss.
  • Data perlu dipindahkan.
  • Traffic jaringan meningkat.
  • Beban server menjadi tidak stabil.
  • Proses rebalancing menjadi mahal.

Dalam sistem berskala besar, efek tersebut dapat menjadi masalah serius.

Cara Kerja Hash Ring

Membuat Ring

Consistent hashing menggunakan ruang hash yang dianggap berbentuk lingkaran.

Contohnya:

                 0
            ┌─────────┐
         270│         │90
            │  HASH   │
            │  RING   │
         180└─────────┘

Nilai hash memiliki rentang tertentu, misalnya:

0 → 2³² - 1

Setelah mencapai nilai maksimum, ruang hash kembali ke nilai 0.

Karena itu, struktur tersebut disebut ring.

Menempatkan Server pada Ring

Setiap server di-hash terlebih dahulu.

Misalnya:

hash(Server-A) → 20
hash(Server-B) → 100
hash(Server-C) → 200

Ring kemudian memiliki node:

20  → Server A
100 → Server B
200 → Server C

Server tidak lagi ditentukan menggunakan operasi modulo secara langsung.

Menempatkan Key pada Ring

Key juga di-hash.

Misalnya:

hash(user:1001) → 50
hash(user:1002) → 130
hash(user:1003) → 250

Kemudian sistem mencari server berikutnya searah jarum jam.

Contohnya:

Key 50
   ↓
Server B pada posisi 100

Maka:

user:1001 → Server B

Sedangkan key dengan posisi 130 akan menuju Server C pada posisi 200.

Apa yang Terjadi Jika Server Ditambahkan?

Inilah keunggulan utama consistent hashing.

Misalnya awalnya terdapat:

Server A
Server B
Server C

Kemudian:

Server D

ditambahkan ke ring.

Server D hanya mengambil sebagian rentang key yang sebelumnya menjadi tanggung jawab node berikutnya.

Artinya, tidak seluruh key harus dipetakan ulang.

Secara sederhana:

Sebelum:

A → B → C → A

Setelah D ditambahkan:

A → B → D → C → A

Hanya sebagian key yang terdampak.

Apa yang Terjadi Jika Server Dihapus?

Hal yang sama berlaku ketika node dihapus.

Misalnya:

A → B → D → C

Jika D gagal:

A → B → C

Key yang sebelumnya diarahkan ke D dapat dialihkan ke node berikutnya sesuai aturan ring.

Dengan demikian, perubahan topology tidak menyebabkan seluruh key harus dihitung ulang.

Consistent Hashing dan Minimal Data Movement

Salah satu alasan utama consistent hashing digunakan adalah minimal data movement.

Ketika node ditambahkan atau dihapus, hanya sebagian key yang perlu berpindah.

Hal ini sangat berguna pada sistem dengan:

  • Banyak server.
  • Jutaan atau miliaran key.
  • Distributed cache.
  • Distributed database.
  • Object storage.
  • Load balancing.

Amazon menjelaskan bahwa sistem Dynamo menggunakan consistent hashing sebagai bagian dari mekanisme partitioning untuk mendistribusikan data pada lingkungan distributed storage yang sangat besar (dikutip dari: https://www.amazon.science/publications/dynamo-amazons-highly-available-key-value-store).

Virtual Nodes atau VNodes

Mengapa Virtual Node Dibutuhkan?

Consistent hashing dasar dapat menghasilkan distribusi yang kurang merata.

Misalnya:

Server A → 10% data
Server B → 60% data
Server C → 30% data

Kondisi tersebut tidak ideal karena Server B menerima beban jauh lebih besar.

Untuk mengatasinya, banyak sistem menggunakan virtual nodes atau vnodes.

Cara Kerja Virtual Nodes

Daripada menempatkan satu server sebagai satu posisi pada ring, satu server dapat memiliki banyak posisi.

Contohnya:

Server A
 ├── A1
 ├── A2
 ├── A3
 └── A4

Server B
 ├── B1
 ├── B2
 ├── B3
 └── B4

Semua virtual node tersebut ditempatkan pada posisi berbeda di ring.

Dengan jumlah posisi yang lebih banyak, distribusi key dapat menjadi lebih merata.

baca juga : Kernel Samepage Merging (KSM): Cara Linux Menghemat Memori dengan Berbagi Halaman yang Identik

Keuntungan Virtual Nodes

Virtual nodes memberikan beberapa manfaat:

  • Distribusi data lebih merata.
  • Mengurangi risiko hotspot.
  • Mempermudah rebalancing.
  • Mendukung server dengan kapasitas berbeda.
  • Memudahkan pengelolaan cluster.

Pada sistem yang heterogen, jumlah virtual node dapat disesuaikan dengan kapasitas masing-masing server.

Server yang memiliki resource lebih besar dapat diberikan lebih banyak virtual node.

Consistent Hashing untuk Distributed Cache

Contoh Penggunaan

Distributed cache merupakan salah satu penggunaan populer consistent hashing.

Misalnya sebuah aplikasi memiliki:

Cache-01
Cache-02
Cache-03
Cache-04

Setiap request memiliki cache key:

user:10001
product:5001
session:abc123

Key tersebut di-hash untuk menentukan cache server yang bertanggung jawab.

Jika satu cache server ditambahkan, hanya sebagian key yang perlu diarahkan ke server baru.

Hal tersebut dapat membantu mengurangi cache invalidation dan cache miss besar-besaran akibat perubahan topology.

Consistent Hashing pada Distributed Database

Consistent hashing juga dapat digunakan untuk membagi data ke beberapa node database.

Misalnya:

User ID
   ↓
Hash
   ↓
Partition
   ↓
Database Node

Ketika node baru ditambahkan, sebagian data dapat dipindahkan secara bertahap ke node tersebut.

Namun, implementasi database modern biasanya memiliki mekanisme tambahan untuk replication, partitioning, rebalancing, dan consistency.

Karena itu, consistent hashing sebaiknya dipahami sebagai salah satu komponen dari arsitektur distributed system, bukan solusi tunggal untuk seluruh masalah database.

Consistent Hashing vs Hashing Biasa

Aspek Hashing Biasa Consistent Hashing
Struktur Hash function Hash ring
Penentuan node Biasanya modulo Posisi pada ring
Tambah node Banyak key dapat berubah Relatif sedikit key berubah
Hapus node Banyak key dapat berubah Sebagian key terdampak
Rebalancing Bisa mahal Lebih efisien
Cocok untuk Sistem sederhana Sistem terdistribusi

Perbedaan paling penting terletak pada bagaimana sistem menangani perubahan jumlah node.

Consistent Hashing vs Range Partitioning

Consistent Hashing

Data didistribusikan berdasarkan hasil hash.

Kelebihannya adalah distribusi dapat lebih merata dan perubahan node dapat dilakukan dengan relatif sedikit perpindahan key.

Range Partitioning

Data dibagi berdasarkan rentang tertentu.

Contohnya:

A–F → Node 1
G–L → Node 2
M–R → Node 3
S–Z → Node 4

Range partitioning dapat berguna ketika query berdasarkan rentang sangat penting.

Namun, distribusi dapat mengalami hotspot jika data tidak tersebar secara merata.

Kelebihan Consistent Hashing

Mengurangi Data Movement

Penambahan atau penghapusan node tidak menyebabkan seluruh data harus dipindahkan.

Cocok untuk Sistem Dinamis

Teknik ini cocok untuk cluster yang jumlah nodenya dapat berubah.

Mendukung Skalabilitas

Node baru dapat ditambahkan secara bertahap untuk meningkatkan kapasitas sistem.

Membantu Distribusi Beban

Dengan penggunaan virtual nodes yang tepat, key dapat tersebar lebih merata.

Kekurangan Consistent Hashing

Distribusi Tidak Selalu Sempurna

Consistent hashing dasar dapat menghasilkan distribusi yang tidak merata.

Virtual nodes dapat membantu mengatasi masalah tersebut, tetapi tetap membutuhkan konfigurasi yang tepat.

Implementasi Lebih Kompleks

Dibandingkan modulo hashing sederhana, consistent hashing membutuhkan struktur ring dan mekanisme pengelolaan node.

Rebalancing Tetap Diperlukan

Walaupun data movement lebih kecil, penambahan atau penghapusan node tetap dapat menyebabkan sebagian data berpindah.

Hot Key Tetap Menjadi Masalah

Jika satu key menerima traffic sangat tinggi, consistent hashing tidak otomatis menyelesaikan masalah tersebut.

Misalnya:

product:viral

menjadi sangat populer.

Semua request dapat tetap mengarah ke node yang sama.

Karena itu, masalah hot key membutuhkan strategi tambahan seperti replication, caching, request coalescing, atau load distribution.

Contoh Sederhana Implementasi

Secara konseptual, algoritma consistent hashing dapat dibuat seperti berikut:

1. Buat hash ring
2. Hash setiap server
3. Masukkan server ke ring
4. Hash setiap key
5. Cari node pertama searah jarum jam
6. Kirim key ke node tersebut

Pseudocode sederhananya:

hashRing.add(hash(serverA))
hashRing.add(hash(serverB))
hashRing.add(hash(serverC))

position = hash(key)

server = hashRing.findNext(position)

Dalam implementasi nyata, sistem membutuhkan struktur data yang efisien untuk melakukan pencarian node.

Contoh Perubahan Cluster

Misalnya terdapat empat node:

Node A
Node B
Node C
Node D

Kemudian Node E ditambahkan.

Dengan consistent hashing, Node E hanya mengambil sebagian rentang key dari node yang berada setelah posisi E pada ring.

Berbeda dengan pendekatan:

hash(key) % N

yang dapat mengubah hasil pemetaan hampir seluruh key ketika nilai N berubah.

Monitoring Consistent Hashing

Penerapan consistent hashing tetap membutuhkan monitoring.

Beberapa metrik yang dapat diperhatikan antara lain:

  • Distribusi key per node.
  • CPU usage.
  • Memory usage.
  • Request per node.
  • Cache hit ratio.
  • Data movement.
  • Rebalancing duration.
  • Hot partition.
  • Hot key.
  • Network traffic.

Jika satu node menerima traffic jauh lebih besar dibandingkan node lain, kemungkinan terdapat masalah distribusi atau workload yang tidak seimbang.

Best Practice Menggunakan Consistent Hashing

Gunakan Virtual Nodes

Virtual nodes dapat membantu meningkatkan distribusi key dan mengurangi ketidakseimbangan antar-node.

Gunakan Hash Function yang Tepat

Hash function sebaiknya menghasilkan distribusi yang baik sehingga key tidak terkonsentrasi pada area tertentu.

Monitor Distribusi Beban

Jangan hanya melihat jumlah key. Perhatikan juga traffic dan ukuran data.

Satu node mungkin memiliki jumlah key yang sama dengan node lain, tetapi traffic yang jauh lebih tinggi.

Rencanakan Rebalancing

Penambahan node tetap dapat menyebabkan data berpindah.

Pastikan proses rebalancing tidak membebani jaringan atau storage secara berlebihan.

Perhatikan Hot Key

Consistent hashing tidak otomatis menyelesaikan hot key.

Gunakan strategi tambahan jika terdapat key yang menerima traffic sangat tinggi.

baca juga : LLMNR & NBT-NS Poisoning: Ancaman Name Resolution yang Sering Terabaikan di Jaringan Windows

Kesimpulan

Consistent Hashing merupakan teknik penting dalam desain sistem terdistribusi untuk mendistribusikan key atau data ke banyak node dengan meminimalkan perpindahan data ketika topology cluster berubah.

Konsep utamanya menggunakan hash ring, di mana server dan key ditempatkan pada ruang hash yang sama. Ketika sebuah node ditambahkan atau dihapus, hanya sebagian key yang perlu dipetakan ulang.

Keuntungan tersebut membuat consistent hashing cocok untuk berbagai kebutuhan, seperti distributed cache, distributed storage, database partitioning, dan load balancing.

Penggunaan virtual nodes dapat membantu meningkatkan distribusi data dan mengurangi risiko satu server menerima beban yang terlalu besar. Namun, teknik ini tetap memiliki keterbatasan, seperti hotspot, hot key, dan kebutuhan rebalancing.

Dengan memahami cara kerja hash ring, virtual nodes, data movement, dan karakteristik workload, consistent hashing dapat digunakan sebagai salah satu fondasi untuk membangun sistem terdistribusi yang lebih scalable, fleksibel, dan efisien.

Related Posts: