Partitioning dan Sharding

Satu node tidak lagi sanggup menyimpan sekaligus memproses tabel pesanan TokoKita yang bertambah miliaran baris per tahun. Partitioning memecah masalah tersebut dengan membagi dataset menjadi potongan-potongan bernama partition; ketika setiap potongan ditempatkan di node terpisah, potongan tersebut disebut shard. Pembagian yang rata membuat tiap node hanya mengerjakan sebagian data sehingga kapasitas dan throughput tumbuh mengikuti jumlah node. Chapter ini membahas dua strategi pembagian, jebakan skew yang membuat pembagian timpang, dan cara menekan biaya rebalancing saat cluster membesar.

Dua Strategi Pembagian Data #

Range partitioning membagi data menurut rentang nilai kunci, misalnya pesanan 2024-01 di shard pertama dan 2024-02 di shard berikutnya. Rentang membuat query berbasis rentang menjadi murah karena cukup menyentuh beberapa shard, tetapi rentang yang tidak rata (bulan ramai versus bulan sepi) menghasilkan shard berukuran timpang.

Hash partitioning menghitung nilai hash dari kunci lalu menentukan shard dari hasil hash tersebut, misalnya hash(kunci) % jumlah_shard. Distribusi hasil hash yang merata membuat ukuran shard seimbang tanpa peduli pola data; konsekuensinya, data yang bersebelahan logis tersebar ke shard mana saja sehingga query rentang harus menyentuh semua shard.

Jebakan Skew: Kunci yang Tidak Beragam #

Hash hanya meratakan distribusi bila kuncinya beragam. Simulasi berikut membandingkan dua pilihan kunci pada 24 pesanan yang sama: kunci kota yang didominasi Jakarta, dan kunci order_id yang unik. Keduanya dihitung dengan MD5 agar hasilnya stabil antar eksekusi — berbeda dari fungsi bawaan hash() yang nilainya berubah tiap proses.

"""Distribusi record ke shard: skew akibat kunci panas, lalu rebalancing
modulo-N vs consistent hashing."""
import hashlib
from bisect import bisect, insort

RUANG = 2 ** 32  # ukuran ruang hash ring


def posisi_hash(nilai):
    """Hash stabil (MD5) dipetakan ke ruang 0..RUANG-1."""
    return int(hashlib.md5(nilai.encode()).hexdigest(), 16) % RUANG


def shard_modulo(kunci, n_shard):
    return posisi_hash(kunci) % n_shard


# 24 pesanan TokoKita: kolom kota timpang (16 dari Jakarta)
pesanan = [
    ("ORD-001", "jakarta"), ("ORD-002", "jakarta"), ("ORD-003", "jakarta"),
    ("ORD-004", "jakarta"), ("ORD-005", "jakarta"), ("ORD-006", "jakarta"),
    ("ORD-007", "jakarta"), ("ORD-008", "jakarta"), ("ORD-009", "jakarta"),
    ("ORD-010", "jakarta"), ("ORD-011", "jakarta"), ("ORD-012", "jakarta"),
    ("ORD-013", "jakarta"), ("ORD-014", "jakarta"), ("ORD-015", "jakarta"),
    ("ORD-016", "jakarta"), ("ORD-017", "bandung"), ("ORD-018", "bandung"),
    ("ORD-019", "surabaya"), ("ORD-020", "surabaya"), ("ORD-021", "medan"),
    ("ORD-022", "medan"), ("ORD-023", "denpasar"), ("ORD-024", "makassar"),
]


def hitung_distribusi(fungsi_kunci, label, n_shard=3):
    hitung = {f"shard-{i}": 0 for i in range(n_shard)}
    for pid, kota in pesanan:
        hitung[f"shard-{shard_modulo(fungsi_kunci(pid, kota), n_shard)}"] += 1
    print(f"{label}: " + ", ".join(f"{s}={n}" for s, n in hitung.items()))
    return hitung


print("Distribusi 24 pesanan ke 3 shard:")
dist_kota = hitung_distribusi(lambda pid, kota: kota, "kunci = kota")
dist_id = hitung_distribusi(lambda pid, kota: pid, "kunci = order_id")
maks = max(dist_kota.values())
print(f"skew kunci kota: shard terpanjang menampung {maks}/24 pesanan "
      f"({maks / 24:.0%} beban pada satu shard)")

kunci_uji = [f"kunci-{i:03d}" for i in range(100)]


class RingKonsisten:
    """Consistent hashing ring dengan virtual node."""

    def __init__(self, node, jumlah_vnode=40):
        self.posisi = []  # daftar posisi ring yang selalu terurut
        self.pemilik = {}  # posisi ring -> nama node
        self.tambah(node, jumlah_vnode)

    def tambah(self, node, jumlah_vnode=40):
        for v in range(jumlah_vnode):
            p = posisi_hash(f"{node}#{v}")
            insort(self.posisi, p)
            self.pemilik[p] = node

    def shard(self, kunci):
        p = posisi_hash(kunci)
        indeks = bisect(self.posisi, p) % len(self.posisi)
        return self.pemilik[self.posisi[indeks]]


# Rebalancing cara 1: hash modulo N, jumlah shard 3 -> 4
lama = {k: shard_modulo(k, 3) for k in kunci_uji}
baru = {k: shard_modulo(k, 4) for k in kunci_uji}
pindah_modulo = sum(1 for k in kunci_uji if lama[k] != baru[k])

# Rebalancing cara 2: consistent hashing, jumlah node 3 -> 4
ring = RingKonsisten("node-1")
for node in ("node-2", "node-3"):
    ring.tambah(node)
sebelum = {k: ring.shard(k) for k in kunci_uji}
ring.tambah("node-4")
sesudah = {k: ring.shard(k) for k in kunci_uji}
pindah_ring = sum(1 for k in kunci_uji if sebelum[k] != sesudah[k])

print("\nRebalancing 100 kunci dari 3 ke 4 penyimpan:")
print(f"  hash modulo N      : {pindah_modulo} kunci berpindah ({pindah_modulo}%)")
print(f"  consistent hashing : {pindah_ring} kunci berpindah ({pindah_ring}%)")

Output yang Dihasilkan:

Distribusi 24 pesanan ke 3 shard:
kunci = kota: shard-0=18, shard-1=2, shard-2=4
kunci = order_id: shard-0=8, shard-1=9, shard-2=7
skew kunci kota: shard terpanjang menampung 18/24 pesanan (75% beban pada satu shard)

Rebalancing 100 kunci dari 3 ke 4 penyimpan:
  hash modulo N      : 71 kunci berpindah (71%)
  consistent hashing : 24 kunci berpindah (24%)

Mari kita telaah baris-baris kode di atas:

1. Baris 9-15 (posisi_hash dan shard_modulo): MD5 menghasilkan angka besar yang stabil, lalu operasi modulo menentukan shard; inilah rumus hash partitioning paling dasar.
2. Baris 31-36 (hitung_distribusi): setiap pesanan diarahkan ke shard menurut kunci yang dipilih, lalu jumlahnya dihitung per shard untuk melihat keseimbangan.
3. Baris 40-41 (dua pilihan kunci): lambda pertama memakai kota sebagai kunci, lambda kedua memakai order_id — satu baris perbedahan yang mengubah seluruh distribusi.
4. Baris 49-66 (RingKonsisten): setiap node menempati 40 virtual node di ring; kunci ditempatkan pada virtual node pertama yang ditemui searah jarum jam (bisect mencarinya pada daftar posisi yang terurut).
5. Baris 69-81 (dua cara rebalancing): cara pertama menghitung ulang hash % 3 menjadi hash % 4; cara kedua menambah node-4 ke ring lalu menghitung ulang pemilik tiap kunci.

Membaca Hasil: Skew dan Biaya Rebalancing #

Kunci kota menggumpalkan 75 persen pesanan pada satu shard karena keenam belas pesanan Jakarta memiliki kunci identik — hash berbeda tidak bisa menolong bila kuncinya sama. Node pemilik shard-0 menjadi hot partition: menampung 18 pesanan sementara dua shard lainnya hanya menampung 2 dan 4. Kunci order_id yang unik menghasilkan distribusi 8-9-7 yang mendekati rata. Karena itu, pemilihan kunci partition adalah keputusan desain terpenting: pilih kolom bernilai tinggi-kardinalitas dan tersebar merata.

Bagian rebalancing memperlihatkan masalah kedua. Dengan rumus modulo, menambah shard dari 3 ke 4 memindahkan 71 dari 100 kunci (71 persen) meski node lama semuanya masih hidup — hasil % 4 melewati posisi baru untuk sebagian besar kunci. Consistent hashing memindahkan 24 kunci saja, kurang lebih seperempat, sesuai teori: hanya kunci di antara node baru dan tetangganya yang berpindah. Virtual node menjaga pemerataan sekaligus membatasi wilayah yang berpindah. Pada cluster produksi, yang dipindahkan bukan 100 kunci melainkan terabyte data, sehingga selisih 71 persen berbanding 24 persen berubah menjadi perbedaan berjam-jam berbanding beberapa menit.

Pembagian data ke banyak shard menyelesaikan kapasitas, tetapi setiap shard kini berdiri sendiri: satu node berhenti berarti potongan data yang ditampungnya ikut tidak tersedia. Solusi berikutnya adalah menyimpan salinan tiap shard di beberapa node, pembahasan Chapter Replication.