Sharding

Sharding adalah teknik memecah satu kumpulan data besar ke beberapa node yang disebut shard, sehingga kapasitas penyimpanan dan tulisan tidak lagi dibatasi oleh satu mesin. Topik ini membahas kapan sharding diperlukan, peran shard key terhadap distribusi dan routing, masalah hotspot, perbandingan hash modulo dengan consistent hashing, dan biaya resharding. Sebuah simulasi Python memperbandingkan banyaknya kunci yang berpindah pada kedua strategi, dan demo interaktif memperlihatkan perpindahan tersebut secara langsung.

Kapan sharding diperlukan#

Replikasi menambah salinan data, tetapi setiap follower tetap menyimpan data secara utuh, dan tulisan tetap bertumpu pada satu leader. Bila ukuran data melampaui penyimpanan satu mesin, atau throughput tulis melampaui kemampuan satu node, salinan tambahan tidak lagi menyelesaikan masalahnya. Pada titik itu data harus dipecah, dan sharding adalah bentuk pemecahannya, yaitu partisi horizontal yang menempatkan subset baris pada node yang berbeda.

Angkanya mudah dikonkretkan. Arsip pembacaan sensor dengan 5 TB data tidak muat pada node berpenyimpanan 1 TB, berapa pun follower ditambahkan, karena setiap follower menyalin kelima terabyte itu secara utuh. Demikian pula beban tulis 50.000 permintaan per detik tidak berkurang dengan replikasi, karena setiap tulisan tetap dikerjakan oleh satu leader yang sama.

Tiap shard dapat direplikasi tersendiri, sehingga arsitektur lengkapnya berupa sekelompok kecil node untuk setiap shard. Pemecahan ini tidak gratis. Query yang menyentuh beberapa shard harus digabung hasilnya, transaksi lintas shard menjadi mahal, dan pekerjaan pemeliharaan bertambah banyak. Karena itu sharding diambil setelah scaling vertikal, caching, dan replikasi benar-benar dimanfaatkan, bukan sebagai langkah pertama.

Shard key dan pola akses#

Shard key adalah kolom yang menentukan penempatan setiap baris atau dokumen pada sebuah shard. Router menghitung penempatan dari nilai shard key, sehingga query yang menyertakan shard key langsung diarahkan ke satu shard, sedangkan query tanpa shard key harus dikirim ke seluruh shard lalu hasilnya digabungkan. Pola kedua disebut scatter-gather, dan biayanya membesar seiring bertambahnya jumlah shard.

Penempatan baris ke shard ada dua keluarga besar. Penempatan berbasis rentang menyimpan baris dengan kunci yang berdekatan pada shard yang sama, sehingga query rentang menjadi efisien, tetapi kunci yang menaik terus memusatkan tulisan baru pada satu shard. Penempatan berbasis hash menyebar nilai kunci ke shard secara merata, tetapi query rentang tidak lagi terarah ke satu shard. Pilihan keduanya diturunkan dari pola query yang paling sering terjadi, bukan dari selera.

Contoh konkret membuat pertimbangannya lebih mudah. Pada aplikasi catatan, pengenal pengguna adalah kandidat shard key yang sehat bila hampir setiap query membaca catatan milik satu pengguna. Sebaliknya, bila query harian lebih sering menyaring menurut waktu, shard key pengenal pengguna membuat query waktu menjadi scatter-gather, dan pilihan tersebut perlu ditimbang ulang.

Hotspot#

Hotspot adalah ketimpangan beban yang membuat satu shard menerima permintaan jauh lebih banyak daripada shard lainnya. Penyebabnya hampir selalu kunci yang tidak menyebar. Kunci yang menaik terus, misalnya waktu pencatatan atau pengenal yang bertambah otomatis, membuat semua tulisan baru jatuh pada shard terakhir bila penempatannya berbasis rentang. Kunci dengan ketimpangan alami juga berbahaya, misalnya satu sensor suhu yang jauh lebih sering dibaca daripada ribuan sensor lainnya, sebab semua pembacaan atas nilai tersebut menumpuk pada shard yang sama.

Ketimpangan ditangani sebelum mengakar. Ketimpangan harus terlihat dahulu, dan cara melihatnya adalah membandingkan metrik permintaan per shard secara berkala. Ketimpangan yang tumbuh perlahan biasanya berasal dari kunci yang menaik, sedangkan ketimpangan yang muncul mendadak biasanya berasal dari satu kunci yang mendadak panas. Kunci yang menaik dapat dihash terlebih dahulu sebelum penempatannya dihitung, sehingga tulisan baru menyebar kembali. Kunci yang panas dapat dibelah menjadi beberapa kunci dengan akhiran berbeda, sehingga bebannya terbagi ke beberapa shard, dan shard yang tetap panas dapat dipecah lagi secara mandiri tanpa menunggu pengaturan ulang yang menyeluruh.

Hash modulo dan consistent hashing#

Strategi penempatan paling sederhana adalah hash modulo, yaitu sisa bagi hash kunci dengan jumlah shard. Cara ini sederhana dan sebarannya merata, tetapi harganya muncul ketika jumlah shard bertambah. Secara teori sekitar $N/(N+1)$ kunci berpindah shard ketika jumlah shard naik dari $N$ menjadi $N+1$, karena sisa bagi hampir semua kunci ikut berubah.

Strategi kedua adalah consistent hashing. Kunci dan node virtual dipetakan ke titik pada cincin berhash, dan sebuah kunci dimiliki node virtual pertama yang berada di arah jarum jam darinya. Ketika satu shard baru bergabung, hanya kunci yang jatuh pada busur milik shard baru yang berpindah, sehingga teorinya sekitar $1/(N+1)$ kunci yang berpindah. Node virtual, yaitu beberapa titik cincin untuk satu shard, menjaga sebaran tetap merata ketika jumlah shard masih kecil.

Simulasi berikut menempatkan 40 kunci dengan kedua strategi, kemudian menambah satu shard dan menghitung banyaknya kunci yang berpindah.

"""Simulasi hash modulo dan consistent hashing.

Dua strategi penempatan kunci dibandingkan ketika jumlah shard bertambah
dari empat menjadi lima:

- Hash modulo: posisi shard = sisa bagi hash kunci dengan jumlah shard.
- Consistent hashing: kunci dipetakan ke node virtual pertama pada cincin
  berhash yang berada di arah jarum jam darinya.

Bagian yang diperbandingkan adalah banyaknya kunci yang berpindah shard
setelah satu shard baru ditambahkan.
"""

import hashlib

NAMA_KUNCI = [f"kunci-{i:02d}" for i in range(1, 41)]
VIRTUAL_PER_SHARD = 100  # jumlah node virtual untuk setiap shard


def h32(teks: str) -> int:
    """Hash deterministik 32-bit berbasis blake2b."""
    return int.from_bytes(hashlib.blake2b(teks.encode(), digest_size=4).digest(), "big")


def shard_modulo(kunci: str, jumlah_shard: int) -> int:
    """Penempatan hash modulo: sisa bagi hash kunci dengan jumlah shard."""
    return h32(kunci) % jumlah_shard


def buat_cincin(jumlah_shard: int) -> list[tuple[int, int]]:
    """Posisi node virtual pada cincin 32-bit, terurut menaik."""
    posisi: list[tuple[int, int]] = []
    for shard in range(jumlah_shard):
        for v in range(VIRTUAL_PER_SHARD):
            titik = h32(f"shard-{shard}-v{v}")
            posisi.append((titik, shard))
    posisi.sort()
    return posisi


def shard_cincin(kunci: str, cincin: list[tuple[int, int]]) -> int:
    """Penempatan consistent hashing: node pertama pada arah jarum jam."""
    h = h32(kunci)
    for titik, shard in cincin:
        if titik >= h:
            return shard
    return cincin[0][1]


cincin_lama = buat_cincin(4)
cincin_baru = buat_cincin(5)

total = len(NAMA_KUNCI)
pindah_modulo = sum(shard_modulo(k, 4) != shard_modulo(k, 5) for k in NAMA_KUNCI)
pindah_cincin = sum(
    shard_cincin(k, cincin_lama) != shard_cincin(k, cincin_baru) for k in NAMA_KUNCI
)
daftar_modulo = [k for k in NAMA_KUNCI if shard_modulo(k, 4) != shard_modulo(k, 5)]
daftar_cincin = [
    k for k in NAMA_KUNCI if shard_cincin(k, cincin_lama) != shard_cincin(k, cincin_baru)
]

print(f"Kunci yang diuji: {total}")
print()
print(f"Hash modulo, 4 -> 5 shard       : {pindah_modulo} kunci berpindah ({pindah_modulo / total:.0%})")
print(f"  kunci yang berpindah: {', '.join(daftar_modulo)}")
print()
print(f"Consistent hashing, 4 -> 5 shard: {pindah_cincin} kunci berpindah ({pindah_cincin / total:.0%})")
print(f"  kunci yang berpindah: {', '.join(daftar_cincin)}")

Kunci yang diuji: 40

Hash modulo, 4 -> 5 shard       : 33 kunci berpindah (82%)
  kunci yang berpindah: kunci-01, kunci-02, kunci-03, kunci-04, kunci-05, kunci-06, kunci-07, kunci-08, kunci-09, kunci-11, kunci-13, kunci-14, kunci-15, kunci-16, kunci-17, kunci-18, kunci-19, kunci-21, kunci-22, kunci-23, kunci-24, kunci-25, kunci-26, kunci-28, kunci-29, kunci-30, kunci-32, kunci-34, kunci-35, kunci-36, kunci-38, kunci-39, kunci-40

Consistent hashing, 4 -> 5 shard: 7 kunci berpindah (18%)
  kunci yang berpindah: kunci-12, kunci-23, kunci-24, kunci-26, kunci-27, kunci-31, kunci-39

Pada 40 kunci yang diuji, hash modulo memindahkan 33 kunci, sedangkan consistent hashing hanya memindahkan 7 kunci. Kedua angka mendekati batas teorinya, yaitu 80 persen dan 20 persen. Selisih ini menentukan besarnya pekerjaan migrasi data setiap kali kapasitas ditambah, dan itulah alasan banyak sistem terdistribusi menggunakan consistent hashing atau variasinya. Variasi yang lazim adalah slot berhash dengan jumlah tetap, misalnya 16384 slot pada Redis Cluster, sehingga penambahan node hanya berarti memindahkan sebagian slot tanpa mengubah rumus penempatan kunci.

Demo berikut memperlihatkan perpindahan kunci secara langsung. Tekan tombol Tambah shard beberapa kali, amati sel merah yang menandai kunci yang berpindah, lalu bandingkan kolom hash modulo dengan kolom consistent hashing.

Biaya resharding#

Resharding adalah mengubah pembagian data antarshard, baik karena jumlah shard bertambah, berkurang, maupun karena shard key diganti. Operasi ini termasuk yang paling mahal pada lapisan data. Data lama harus disalin ke shard baru sambil sistem terus melayani trafik, tulisan yang masuk selama migrasi ditulis ganda agar tidak hilang, rute pembagian diganti tanpa memutus klien, dan indeks pada shard baru dibangun ulang. Bila shard key ikut diganti, hampir seluruh baris berpindah karena penempatan dihitung ulang dari nol.

Biaya tersebut ditekan dengan antisipasi sejak awal. Jumlah shard dipilih lebih banyak daripada kebutuhan hari ini, misalnya sepuluh shard logis untuk dua node, sehingga penambahan kapasitas cukup dengan memindahkan shard tanpa mengubah rumus penempatan. Sistem terdistribusi modern menyediakan migrasi slot atau resharding daring yang memperkecil gangguannya, tetapi kemampuan itu tidak menghapus biaya penyalinan datanya.

Kesalahan umum#

Tiga kesalahan berikut paling sering muncul ketika sharding baru dirancang.

• Menggunakan waktu atau pengenal yang menaik sebagai shard key pada penempatan berbasis rentang. Semua tulisan baru menumpuk pada satu shard, gejalanya sering baru muncul setelah berbulan-bulan, dan perbaikannya adalah menghash kunci atau menambah komponen pengacak.
• Memilih shard key yang jarang muncul pada query harian. Kebanyakan query menjadi scatter-gather, biayanya membesar seiring jumlah shard, dan perbaikannya adalah memindahkan shard key ke kolom yang menyertai mayoritas query, misalnya pengenal pengguna pada data catatan pengguna.
• Memulai dengan jumlah shard yang sama dengan jumlah node saat ini. Penambahan kapasitas pertama langsung memicu resharding, dan perbaikannya adalah memulai dengan shard logis yang lebih banyak daripada node fisiknya, misalnya agar mampu menampung data dua hingga tiga kali ukuran hari ini.
• Mengabaikan pemantauan keseimbangan antarshard setelah sistem berjalan. Distribusi yang merata pada awalnya tidak menjamin merata selamanya, dan perbaikannya adalah memantau ukuran serta beban tiap shard secara berkala.

Ringkasan#

• Sharding memecah data ke beberapa node ketika replikasi saja tidak lagi menambah kapasitas tulis dan penyimpanan.
• Shard key menentukan distribusi dan routing, sehingga query tanpa shard key menjadi scatter-gather dan kunci yang tidak menyebar memicu hotspot.
• Consistent hashing membatasi perpindahan kunci saat jumlah shard bertambah, berbeda dengan hash modulo yang memindahkan hampir semua kunci.
• Resharding mahal, sehingga jumlah shard awal yang berlebih dan shard key yang lentur dipilih sejak desain.

Referensi#

• Sharding Introduction and Architecture — MongoDB — Dokumentasi resmi sharding MongoDB, termasuk pemilihan shard key serta strategi rentang dan hash.
• Scale with Redis Cluster — Redis — Dokumentasi resmi Redis Cluster yang membagi data ke 16384 hash slot dengan CRC16.