Skalakan eksekusi query

Pertanyaan

Saat satu mesin nggak cukup, bagaimana query dieksekusi di banyak mesin tanpa membuat yang paling lambat menentukan seluruh respons?

Setelah baca ini, kamu bisa menghitung dampak fan-out pada tail latency, menjelaskan kenapa paginasi dalam itu mahal, dan membagi eksekusi jadi tahap retrieval dan ranking.

Prasyarat dan contoh

Kamu sudah paham inverted index, BM25 (M11.01, M11.02), serta partisi dan replika (M07, M08).

Indeks berisi 400 juta dokumen, sekitar 600 GB di disk. Satu mesin menjawab query dalam 200 ms pada indeks sekecil 20 GB tapi lebih dari 2 detik pada 600 GB karena cache halaman nggak lagi memuat bagian yang sering dipakai. Jadi indeks dibagi ke 30 shard sekitar 20 GB. Tiap query sekarang harus ke 30 mesin.

Mekanisme

1. Partisi menurut dokumen. Tiap shard memegang subset dokumen lengkap beserta inverted index miliknya sendiri. Dokumen ditempatkan lewat hash ID. Pilihan lain, partisi menurut term (satu shard memegang posting list term tertentu), membuat query multi-term harus memindahkan posting list besar antar mesin. Mesin pencarian umum memilih partisi menurut dokumen, karena penambahan dan penghapusan dokumen cuma menyentuh satu shard.

2. Scatter-gather.

1. Koordinator menerima query dan mengirimkannya ke semua shard.
2. Tiap shard menghitung top-k lokal dari dokumennya sendiri.
3. Koordinator menggabungkan 30 daftar menjadi top-k global (merge dari daftar terurut).
4. Koordinator mengambil isi dokumen (snippet) hanya untuk k hasil terakhir.

Pemisahan "cari id dan skor" dari "ambil isi" penting. Mengambil isi untuk semua kandidat memperbesar transfer puluhan kali lipat.

3. Tail latency akibat fan-out. Respons menunggu shard paling lambat. Misal p99 satu shard 50 ms, artinya 1% request ke shard itu lebih lambat dari 50 ms. Dengan 30 shard:

P(semua shard <= 50 ms) = 0,99^30 = 0,74

Jadi sekitar 26% query melewati 50 ms, padahal tiap shard "baik-baik saja" menurut p99-nya. Makin banyak shard, makin dominan ekor distribusi (M02).

Mitigasi:

• Hedged request. Kirim ulang ke replika lain jika shard belum menjawab dalam, misalnya, p95 latensinya. Biayanya sekitar 5% beban tambahan.
• Deadline dan hasil parsial. Setelah 150 ms, kembalikan hasil dari shard yang sudah menjawab dan tandai hasil sebagai tidak lengkap ("2 dari 30 shard terlambat").
• Shard secukupnya. Jangan memecah indeks lebih kecil dari yang diperlukan. Lebih banyak shard berarti lebih banyak fan-out.

4. Replika. Tiap shard punya beberapa salinan. Replika menambah throughput baca dan ketersediaan. Kalau satu salinan menangani 200 query per detik per shard dan target 1.000 query per detik, tiap shard butuh minimal 5 salinan. Kamu juga butuh replika untuk melewati kegagalan, jadi tambahkan margin.

5. Paginasi dalam. Untuk halaman ke-100 dengan 10 hasil per halaman, tiap shard harus mengirim 1.000 + 10 kandidat, bukan 10, karena hasil global bisa datang dari satu shard mana pun. Dengan 30 shard, koordinator menggabungkan 30 x 1.010 = 30.300 kandidat untuk 10 hasil. Pilihannya: batasi kedalaman (misalnya 1.000 hasil pertama), atau pakai cursor search_after berdasarkan skor dan ID hasil terakhir.

6. Dua tahap. Ranking mahal (model terlatih, fitur dari penyimpanan lain) nggak bisa dijalankan untuk jutaan kandidat.

Tahap 1: BM25 + filter  -> 1.000 kandidat    (murah, ratusan ribu dokumen/detik/inti)
Tahap 2: rerank          -> 100 teratas       (mahal, beberapa ms per dokumen)
Tahap 3: ambil snippet   -> 10 hasil tampil

Recall tahap 1 menjadi batas atas kualitas. Dokumen bagus yang nggak masuk 1.000 kandidat nggak akan diselamatkan oleh reranker terbaik.

Saat rancangan ini gagal

• Shard tidak seimbang. Satu tenant besar menumpuk di satu shard dan shard itu selalu paling lambat. Latensi seluruh sistem mengikutinya.
• Retry badai. Hedging tanpa batas menambah beban saat sistem sudah lambat, dan membuatnya makin lambat. Batasi hedge pada persentase kecil dari total request.
• Hasil parsial diam-diam. Kalau satu shard mati dan koordinator tetap menjawab tanpa memberi tahu, pengguna mengira dokumennya nggak ada. Sertakan metadata kelengkapan.
• Deep paging. Satu bot yang meminta halaman 5.000 membebani semua shard. Batasi kedalaman.
• Jumlah shard tetap. Mengubah jumlah shard berarti memindahkan dokumen. Rencanakan lebih awal, atau pakai shard lebih banyak dengan beberapa shard per mesin.

Contoh tandingan: indeks 8 GB dengan 50 query per detik berjalan nyaman di satu mesin dengan dua replika. Memecahnya jadi 4 shard hanya menambah fan-out dan tail latency tanpa keuntungan.

Latihan

Indeks dibagi 12 shard. Latensi p99 tiap shard 80 ms, dan target p99 pencarian 120 ms.

1. Berapa persen query yang melewati 80 ms jika semua shard dipanggil dan dianggap independen?
2. Untuk halaman 20 dengan 10 hasil per halaman, berapa kandidat yang digabungkan koordinator?
3. Sebutkan dua perubahan untuk menekan tail latency dan satu risikonya.

Lihat pembahasan+

1. Peluang semua shard di bawah 80 ms adalah 0,99^12 = 0,886. Jadi sekitar 11,4% query melewati 80 ms. Asumsi independen jarang benar, karena beban yang sama biasanya memengaruhi beberapa shard sekaligus, jadi anggap angka ini perkiraan bawah.

2. Halaman 20 butuh 20 x 10 = 200 kandidat per shard. Total 12 x 200 = 2.400 kandidat digabung untuk memilih 10 hasil.

3. (a) Deadline 120 ms dengan hasil parsial: p99 terjaga, risikonya hasil bisa kurang lengkap sehingga harus ditandai. (b) Hedged request setelah 60 ms ke replika lain: memotong ekor latensi, risikonya beban naik sekitar beberapa persen dan bisa memperparah saat sistem jenuh, jadi batasi rasio hedge.

Jawaban yang bagus menyebut angka, asumsi independensi, dan konsekuensi bagi pengguna.

Terkait

• Sebelumnya: M11.04 Jaga indeks tetap mutakhir.
• Lanjut ke M11.06 Evaluasi retrieval.
• Hedged request dan deadline berkaitan dengan retry yang aman di M03. Penempatan data lintas shard dan hot spot ada di M07.
• Rancangan D10 menggabungkan semua tahap ini. Belum tersedia.

Catatan

• Asumsi: partisi menurut dokumen, shard diperlakukan independen dalam perhitungan tail latency.
• Yang nggak dibahas: pemilihan kluster mesin, pemadatan (merge) segmen saat query berjalan, dan biaya cloud.
• Angka throughput dan latensi dalam contoh ilustratif. Ukur pada perangkat keras dan korpusmu.
• Terakhir ditinjau: 26 Oktober 2026.