Consistent Hashing: Kenapa Menambah Server Tak Mengacak Semua

Bayangkan Anda punya 4 server cache dan jutaan data yang tersebar di antaranya. Cara paling sederhana membagi data adalah hash(key) % 4. Sederhana, cepat, merata. Masalah baru muncul saat Anda menambah satu server: tiba-tiba hampir semua data pindah tempat, cache jadi kosong serentak, dan database di belakangnya kebanjiran permintaan. Consistent hashing lahir untuk mencegah bencana ini.

1. Masalah dengan `hash(key) % N`

Dengan modulo, server tujuan sebuah key bergantung pada N — jumlah server. Begitu N berubah dari 4 ke 5, pembaginya berubah, dan nyaris semua key dipetakan ke server yang berbeda.

Seberapa parah? Mari ukur: 100.000 key, pindah dari 4 ke 5 server.

import hashlib

def h(s):
    return int(hashlib.md5(str(s).encode()).hexdigest(), 16)

keys = [f"key{i}" for i in range(100_000)]
pindah = sum((h(k) % 4) != (h(k) % 5) for k in keys)
print(f"{pindah / len(keys) * 100:.0f}% key pindah server")
# 80% key pindah server

80%. Empat dari lima data harus ditarik ulang hanya karena menambah satu mesin. Untuk sistem cache, ini artinya badai cache miss.

2. Ide intinya: sebuah cincin

Consistent hashing membuang % N. Sebagai gantinya, bayangkan semua nilai hash disusun melingkar — sebuah ring dari 0 sampai nilai hash maksimum, lalu kembali ke 0.

Setiap server ditempatkan di titik tertentu pada ring (berdasarkan hash namanya).
Setiap key juga dipetakan ke sebuah titik pada ring.
Sebuah key ditangani oleh server pertama yang ditemui bila kita berjalan searah jarum jam dari posisi key itu.

Key dipetakan ke server terdekat searah jarum jam pada ring

Setiap key berjalan searah jarum jam sampai bertemu server. Menambah server S5 hanya “merebut” key pada potongan busur antara S5 dan server sebelumnya — sisanya tak tersentuh.

3. Kenapa ini jauh lebih hemat

Inilah keajaibannya: ketika sebuah server baru masuk ke ring, ia hanya menyisip di satu titik. Ia cuma mengambil alih key yang berada di busur antara dirinya dan server sebelumnya. Semua key lain tetap di tempatnya.

Akibatnya, menambah server ke dalam kelompok berisi N server hanya memindahkan kira-kira:

Bandingkan: modulo memindahkan ~N/(N+1) (hampir semua), consistent hashing hanya ~1/(N+1) (jatah adilnya saja).

4. Virtual nodes: menjaga beban tetap merata

Ada satu masalah tersisa. Kalau tiap server hanya punya satu titik di ring, posisinya acak — bisa jadi satu server kebagian busur raksasa sementara yang lain kebagian remah. Bebannya timpang.

Solusinya virtual nodes: tiap server fisik ditaruh di banyak titik di ring (misalnya 100–200 titik). Dengan banyak potongan kecil yang tersebar, beban tiap server jadi rata, dan saat server ditambah/dihapus, perpindahan key pun lebih mulus.

5. Simulasi lengkap

import hashlib, bisect
from collections import Counter

def h(s):
    return int(hashlib.md5(str(s).encode()).hexdigest(), 16)

class HashRing:
    def __init__(self, vnodes=100):
        self.vnodes = vnodes
        self.ring = []          # daftar (posisi, server), terurut
        self.positions = []

    def add(self, server):
        for v in range(self.vnodes):
            self.ring.append((h(f"{server}#{v}"), server))
        self.ring.sort()
        self.positions = [p for p, _ in self.ring]

    def get(self, key):
        i = bisect.bisect(self.positions, h(key)) % len(self.positions)
        return self.ring[i][1]

keys = [f"key{i}" for i in range(100_000)]
ring = HashRing(vnodes=100)
for s in ["s1", "s2", "s3", "s4"]:
    ring.add(s)

before = {k: ring.get(k) for k in keys}
ring.add("s5")                      # tambah satu server
after = {k: ring.get(k) for k in keys}

pindah = sum(before[k] != after[k] for k in keys)
beban = sorted(round(v / len(keys) * 100, 1) for v in Counter(after.values()).values())
print(f"pindah saat +1 server : {pindah / len(keys) * 100:.1f}%")
print(f"beban per server (%)  : {beban}")

Keluarannya:

pindah saat +1 server : 17.1%
beban per server (%)  : [17.1, 18.9, 20.6, 21.5, 22.0]

Hanya 17% key yang pindah (mendekati jatah ideal 1/5 = 20%), dan kelima server berbagi beban dengan rata. Bandingkan dengan 80% milik modulo.

Modulo memindahkan 80% key, consistent hashing hanya sekitar 17%

Tanpa virtual nodes, perpindahan memang kecil tapi beban timpang (dari 3% sampai 30%). Dengan virtual nodes, beban merata dan perpindahan tetap sekitar jatah adilnya.

6. Di mana ini dipakai

Consistent hashing bukan teori belaka — ia menyangga banyak sistem terdistribusi nyata:

Memcached klien (mis. ketcon/ketama) untuk sharding cache.
Cassandra dan Amazon DynamoDB untuk menyebar data antar node.
CDN dan load balancer untuk mengarahkan permintaan ke server yang konsisten.

Semuanya butuh satu hal yang sama: bisa menambah atau kehilangan node tanpa harus mengocok ulang seluruh data.

Penutup

hash(key) % N sederhana, tapi mengubah N memindahkan hampir semua key.
Consistent hashing menaruh server dan key pada sebuah ring; menambah server hanya memindahkan ~1/(N+1) key.
Virtual nodes membuat beban tiap server merata.

Dari satu perubahan cara berpikir — dari “bagi sisa” menjadi “titik terdekat di lingkaran” — sebuah sistem bisa tumbuh dan menyusut dengan tenang, tanpa badai setiap kali satu mesin datang atau pergi.