Sharding dan consistent hashing: membagi data ke banyak node
Range vs hash partitioning, hot partition, resharding, lalu kenapa ring consistent hashing + virtual node membuat penambahan node murah
Sebelumnya, lesson 0009 menangani beban baca dengan index dan read replica. Replica menyalin seluruh data, jadi tidak menolong kalau yang jenuh adalah write atau ukuran data melebihi satu server. Jawabannya membagi data: setiap node menyimpan sebagian. Ini anak tangga yang mahal, jadi lesson ini juga membahas kapan belum perlu.
hash(key) mod N buruk saat resharding, dan bagaimana consistent hashing dengan virtual node memindahkan data seminimal mungkin.
1. Partitioning: range vs hash
Partitioning membagi satu tabel besar menjadi bagian-bagian. Kalau bagian-bagian itu berada di server berbeda, namanya sharding (satu bagian = satu shard). Kolom yang menentukan sebuah baris masuk ke shard mana disebut shard key (partition key). Dua cara utama:
- Range partitioning. "The table is partitioned into 'ranges' defined by a key column or set of columns, with no overlap between the ranges", misalnya per rentang tanggal atau ID. [1] Bigtable memakai cara ini lintas mesin: rentang row key dibagi menjadi tablet, "the unit of distribution and load balancing", dan "reads of short row ranges are efficient and typically require communication with only a small number of machines." Tablet otomatis dipecah saat tabel tumbuh, masing-masing kira-kira 100–200 MB secara default. [2]
- Hash partitioning. Partisi dipilih dari hash shard key; PostgreSQL mendefinisikannya dengan "a modulus and a remainder for each partition". [1] Data tersebar rata, tapi query rentang (mis. "order bulan ini") harus bertanya ke semua shard.
| Range | Hash | |
|---|---|---|
| Query rentang | murah (sedikit shard) | mahal (semua shard) |
| Sebaran beban | rawan timpang (data terbaru di satu shard) | rata untuk key yang banyak |
| Contoh shard key | created_at, user_id berurutan | hash(user_id) |
Hot partition
Hot partition (hot spot) adalah shard yang menerima beban jauh di atas yang lain. Penyebab klasik: range partitioning per tanggal (semua write hari ini ke shard terakhir),
atau satu key yang sangat populer (akun selebriti) di hash partitioning. Dynamo mengandalkan banyaknya key: desainnya mengasumsikan bahwa walau akses timpang, "there are enough keys in the popular end of the distribution so that the load of handling popular keys can be spread across the nodes uniformly through partitioning." [3]
Satu key tunggal yang terlalu panas tidak bisa dibagi oleh partitioning; obatnya di level lain (cache untuk read, memecah key untuk write, mis. counter#1..#10).
Shard key menentukan semuanya
Pilih shard key dari query yang dominan, supaya query itu cukup ke satu shard: chat dibagi per conversation_id, data tenant per tenant_id.
Query lintas shard (JOIN, agregasi global, transaksi yang menyentuh dua shard) menjadi mahal atau harus dikerjakan di aplikasi.
Latihan 1 — Partitioning
Jawab tanpa scroll ke atas. Soal yang sama akan muncul lagi, diacak, di review 0019.
Kuis di lesson ini adalah feedback cepat, bukan bukti penguasaan; yang dicatat hanya hasil review 0019.
2. Resharding dan consistent hashing
Resharding adalah memindahkan data saat jumlah shard berubah. Dengan shard = hash(key) mod N, mengubah N dari 4 ke 5 memindahkan hampir semua key.
Paper Karger et al. menggambarkan masalah yang sama untuk cache: dengan hash klasik, "When the range of the hash function … changed, almost every item would be hashed to a new location. Suddenly, all cached data is useless". [4]
Consistent hashing adalah fungsi hash yang "changes minimally as the range of the function changes." [4]
Cara kerjanya menurut Dynamo: output hash diperlakukan sebagai "fixed circular space or 'ring'". Node dan key di-hash ke ring yang sama; sebuah key disimpan di node pertama yang ditemui searah jarum jam. "The principle advantage of consistent hashing is that departure or arrival of a node only affects its immediate neighbors and other nodes remain unaffected." [3] Dengan N node, menambah satu node rata-rata hanya memindahkan sekitar 1/(N+1) key, bukan hampir semuanya.
Virtual node
Ring dasar punya masalah: "the random position assignment of each node on the ring leads to non-uniform data and load distribution." Dynamo memakai varian dengan virtual node: "instead of mapping a node to a single point in the circle, each node gets assigned to multiple points in the ring." Keuntungannya: saat node mati, "the load handled by this node is evenly dispersed across the remaining available nodes"; node baru menerima "a roughly equivalent amount of load from each of the other available nodes"; dan jumlah virtual node per server bisa disesuaikan dengan kapasitasnya. [3]
Latihan 2 — Consistent hashing
Jawab tanpa scroll ke atas.
3. Kapan tidak perlu
- Sinyal yang membenarkan sharding. Write throughput sudah melewati kapasitas satu leader setelah index, tuning, dan scale vertical; atau total data tidak lagi muat di satu server terbesar yang wajar. Beban baca saja bukan sinyal sharding (itu read replica atau cache, lesson 0009 dan modul Caching).
- Biaya dan risiko. Query dan transaksi lintas shard, JOIN yang pindah ke aplikasi, resharding yang memindahkan data saat sistem hidup, hot partition kalau shard key salah, dan operasional N database. Shard key hampir mustahil diganti nanti.
- Alternatif lebih murah. Index dan query yang benar, scale vertical, arsip data lama, dan partitioning di satu server (PostgreSQL declarative partitioning). Untuk partitioning itu pun dokumentasi PostgreSQL mengingatkan bahwa manfaatnya "will normally be worthwhile only when a table would otherwise be very large", dengan patokan kasar "the size of the table should exceed the physical memory of the database server." [1] Untuk 1.000 user aktif harian, sharding adalah over-engineering.
Kalimat untuk interview: "Satu database cukup untuk angka ini. Kalau write melewati kapasitas satu leader setelah scale vertical, saya shard per user_id dengan consistent hashing supaya penambahan node hanya memindahkan sebagian kecil data."
Latihan lisan — Ucapkan dengan suara keras
Pasang timer dan jawab dengan suara keras, seolah sedang interview. Jangan buka jawaban contoh sebelum selesai.
"Data Anda tidak lagi muat di satu database. Bagaimana Anda membaginya, dan apa yang terjadi saat Anda menambah node?" (60 detik)
Bandingkan dengan jawaban contoh dan checklist-nya
"Pertama saya pastikan memang perlu: write atau ukuran data sudah melewati satu server setelah index dan scale vertical; kalau hanya read, replica atau cache cukup. Lalu pilih shard key dari query dominan, misalnya user_id, supaya sebagian besar query cukup ke satu shard. Range partitioning bagus untuk query rentang tapi rawan hot partition, misalnya semua write hari ini ke shard terakhir; hash partitioning menyebar rata tapi query rentang harus ke semua shard. Untuk penempatan saya pakai consistent hashing, bukan hash mod N, karena mod N memindahkan hampir semua key saat N berubah. Di ring, node baru hanya mengambil key dari tetangganya. Dengan virtual node, setiap server punya banyak titik di ring, jadi beban rata dan saat node mati bebannya tersebar ke banyak node. Biayanya: query lintas shard mahal dan shard key sulit diganti."
Checklist: apakah Anda menyebut…
- range vs hash partitioning beserta trade-off-nya (query rentang vs sebaran rata)?
- shard key dipilih dari query dominan, query lintas shard mahal?
- hot partition: penyebab dan penanganannya?
hash mod Nmemindahkan hampir semua key saat resharding?- consistent hashing (ring, hanya tetangga terdampak) + virtual node untuk sebaran rata?
- membenarkan sharding dengan angka atau metrik (write/ukuran data melewati satu server setelah tuning)?
Lulus jika minimal 4 dari 6.
Berikutnya, lesson 0011: data sekarang tersebar dan direplikasi di banyak node. Apa yang terjadi saat jaringan antar node putus? CAP, PACELC, dan consistency model.
Istilah: GLOSSARY.md (bagian "Data") · Indeks: semua lesson System Design
Ada yang belum jelas? Tanyakan ke saya (agent) di terminal, misalnya: "bagaimana memilih shard key untuk aplikasi multi-tenant dengan tenant yang sangat besar?", "bagaimana resharding dilakukan tanpa downtime?", atau "berapa virtual node per server yang masuk akal?"
Sumber: [1] PostgreSQL docs: Table Partitioning · [2] Chang et al. 2006, Bigtable: A Distributed Storage System for Structured Data (OSDI) · [3] DeCandia et al. 2007, Dynamo: Amazon's Highly Available Key-value Store (SOSP) · [4] Karger et al. 1997, Consistent Hashing and Random Trees (STOC)