Masalah autocomplete yang paling menipu adalah saat metrik rata-rata terlihat sehat, tetapi pengguna tetap mengeluh timeout sporadis dan hasil yang terasa lambat. Dalam banyak sistem, akar masalahnya bukan pada throughput global, melainkan pada tail latency: request di p95 atau p99 yang meledak ketika prefix tertentu memicu scan panjang, cache miss tinggi, dan hot key yang membebani CPU.

Pada artikel ini, kita membahas studi kasus debug autocomplete lambat di backend untuk dataset sangat besar. Fokusnya bukan pada teori umum, melainkan pada gejala nyata, langkah investigasi, root cause yang sering muncul, dan perbaikan bertahap: dari struktur prefix index, strategi cache, sampai verifikasi pasca-fix agar p99 benar-benar turun, bukan hanya rata-rata yang terlihat bagus.

Gejala yang Terlihat di Produksi

Kasus yang dibahas biasanya memiliki pola seperti ini:

  • Rata-rata latensi endpoint autocomplete masih terlihat cepat.
  • Namun p95 dan terutama p99 melonjak tajam pada jam sibuk.
  • Timeout hanya terjadi sesekali, sehingga sulit direproduksi di lingkungan pengembangan.
  • CPU backend atau database spike saat prefix populer dicari banyak pengguna.
  • Query tertentu melakukan scan jauh lebih panjang dibanding prefix lain.
  • Cache hit ratio menurun justru untuk traffic tertinggi.
  • Hasil autocomplete kadang tidak konsisten untuk prefix populer karena timeout, fallback, atau race condition saat refresh cache.

Contoh pola request yang sering bermasalah:

  • Prefix pendek seperti a, co, pro.
  • Prefix dengan cardinality sangat tinggi, misalnya jutaan kandidat.
  • Prefix yang menjadi hot key karena dicari sangat sering.

Jika autocomplete terlihat cepat untuk prefix panjang tetapi lambat untuk prefix pendek yang populer, curigai desain index dan cache lebih dulu sebelum menyalahkan jaringan atau web server.

Mengapa Rata-rata Menipu dan p99 Lebih Penting

Autocomplete adalah endpoint interaktif. Pengguna merasakan respons per ketikan, bukan nilai rata-rata seluruh sistem. Satu request yang lambat di momen salah bisa terasa seperti aplikasi macet, meskipun 90% request lainnya cepat.

Karena itu, metrik berikut lebih relevan daripada sekadar average latency:

  • p50: baseline normal.
  • p95/p99: mengungkap outlier yang memicu pengalaman buruk.
  • timeout rate: efek langsung ke pengguna.
  • cache hit ratio per prefix bucket: apakah cache efektif untuk prefix populer.
  • CPU time per request: apakah bottleneck di compute, bukan I/O semata.
  • rows scanned / keys examined: indikator query tidak selektif.
  • allocation rate dan GC pressure: penting bila service membuat banyak objek sementara.

Sistem autocomplete yang buruk sering punya p50 bagus tetapi p99 buruk karena sebagian kecil prefix memicu jalur eksekusi yang sangat mahal. Prefix pendek adalah tersangka utama, terutama bila implementasi hanya mengandalkan pencarian prefix match di struktur data yang tidak cocok dengan distribusi data.

Langkah Investigasi yang Praktis

1. Pecah latensi per panjang prefix dan prefix populer

Jangan lihat endpoint sebagai satu angka agregat. Kelompokkan metrik berdasarkan:

  • panjang prefix: 1 karakter, 2 karakter, 3 karakter, dan seterusnya,
  • prefix spesifik yang paling sering diminta,
  • sumber hasil: database langsung, cache, atau fallback.

Sering kali Anda akan menemukan pola seperti ini:

  • prefix panjang: stabil, latensi rendah, cache efektif,
  • prefix pendek: scan besar, cache miss tinggi, CPU melonjak.

2. Aktifkan tracing per request

Untuk request autocomplete, trace sederhana sangat membantu:

request_id=abc123
prefix=co
prefix_len=2
cache_lookup_ms=1.2
cache_hit=false
db_query_ms=187
rows_scanned=850000
rows_returned=10
sort_ms=21
serialization_ms=3
alloc_mb=18

Dari trace seperti ini, Anda bisa cepat melihat di mana waktu habis. Jika rows_scanned tinggi tetapi hasil hanya 10 item, masalahnya bukan jumlah hasil, melainkan selektivitas pencarian.

3. Profil query yang lambat

Periksa query untuk prefix populer. Bentuk query yang tampak sederhana bisa sangat mahal:

SELECT term, score
FROM suggestions
WHERE term LIKE :prefix || '%'
ORDER BY score DESC
LIMIT 10;

Query di atas bisa berjalan baik untuk dataset kecil, tetapi pada dataset sangat besar ada beberapa risiko:

  • Index hanya membantu sebagian, lalu database tetap harus memeriksa terlalu banyak kandidat.
  • ORDER BY score DESC memaksa sort di himpunan kandidat besar.
  • Prefix pendek menghasilkan cardinality buruk sehingga planner memilih rencana yang mahal.

Yang perlu diperiksa dari database engine apa pun adalah konsep yang sama:

  • berapa banyak row atau key yang diperiksa,
  • apakah terjadi sort besar di memori atau disk,
  • apakah planner salah mengestimasi jumlah kandidat,
  • apakah index yang dipakai benar-benar sesuai dengan pola akses.

4. Periksa cache bukan hanya hit ratio global

Hit ratio global bisa menyesatkan. Cache mungkin efektif untuk prefix panjang, tetapi gagal total untuk prefix populer yang justru paling penting. Lihat:

  • hit ratio per panjang prefix,
  • hit ratio untuk top-N prefix paling sering diminta,
  • eviction rate,
  • TTL efektif versus pola traffic,
  • jumlah concurrent recomputation untuk key yang sama.

Jika prefix populer seperti co sering miss, maka cache Anda kemungkinan salah desain, bukan sekadar kurang kapasitas.

5. Ambil profil CPU dan memori di service

Bila query sebenarnya sudah lumayan cepat tetapi p99 tetap buruk, cek sisi aplikasi:

  • apakah request membangun daftar kandidat besar lalu baru dipotong 10 teratas,
  • apakah normalisasi string dilakukan berulang-ulang,
  • apakah ada alokasi objek besar per request,
  • apakah garbage collection atau allocator contention muncul saat traffic tinggi.

Autocomplete sering terlihat sederhana, tetapi manipulasi string, deduplikasi, sort, dan serialisasi bisa menjadi mahal pada jalur panas.

Akar Masalah yang Paling Sering Muncul

Struktur prefix index tidak tepat

Masalah klasiknya adalah mengandalkan pencarian prefix di index yang tidak didesain untuk mengambil top-k secara cepat. Misalnya, data memang bisa dicari dengan prefix, tetapi untuk mendapatkan 10 saran terbaik sistem masih harus memindai sangat banyak kandidat lalu menyortirnya.

Gejalanya:

  • prefix pendek sangat mahal,
  • rows scanned jauh lebih besar daripada rows returned,
  • latensi memburuk seiring pertumbuhan dataset.

Intinya, prefix lookup dan ranking lookup sering perlu dipikirkan bersama. Jika index hanya bagus untuk menemukan kandidat tetapi tidak untuk mengambil kandidat terbaik, p99 akan tetap buruk.

Cardinality buruk pada prefix pendek

Prefix seperti a atau co memiliki banyak kandidat. Bahkan jika engine mampu melakukan range scan, jumlah item yang harus dilalui tetap besar. Ini bukan bug planner semata; memang struktur datanya terlalu padat untuk prefix tersebut.

Semakin besar dataset, semakin mahal prefix pendek kecuali Anda memiliki precomputed structure atau strategi pembatasan yang eksplisit.

Hot key pada cache

Prefix populer sering menjadi hot key. Ironisnya, key ini bisa tetap menjadi sumber latensi jika:

  • TTL terlalu pendek sehingga sering diregenerasi,
  • banyak worker menghitung ulang key yang sama secara paralel,
  • payload cache terlalu besar sehingga deserialisasi mahal,
  • cache tier tunggal menjadi bottleneck.

Hot key tidak selalu terlihat sebagai cache miss besar. Kadang hit terjadi, tetapi biaya pengambilan dan decoding tetap cukup tinggi untuk merusak p99.

Alokasi memori berlebih di jalur request

Autocomplete yang membangun banyak string sementara, objek hasil, atau array besar dapat meningkatkan pressure pada allocator dan garbage collector. Gejala yang sering muncul:

  • CPU spike tanpa peningkatan query time yang setara,
  • latensi memburuk saat traffic paralel naik,
  • profil menunjukkan banyak waktu habis di copy, alloc, atau GC.

Strategi cache yang salah

Beberapa strategi cache terlihat masuk akal tetapi buruk untuk autocomplete skala besar:

  • TTL sama untuk semua prefix: prefix panas dan dingin diperlakukan identik.
  • Cache hanya hasil akhir: padahal bottleneck ada pada retrieval kandidat dasar yang berulang.
  • Cache prefix terlalu pendek tanpa batas ukuran: memori cepat habis.
  • Cache write-through untuk semua key: overhead tinggi untuk key yang tidak pernah dipakai lagi.

Contoh Pola Implementasi yang Menyebabkan p99 Buruk

Misalkan service melakukan langkah berikut:

  1. Cek cache hasil autocomplete untuk prefix.
  2. Jika miss, query semua kandidat yang cocok dengan prefix.
  3. Normalisasi dan filter hasil di aplikasi.
  4. Sort berdasarkan skor/popularitas.
  5. Ambil 10 teratas dan simpan ke cache.

Pseudocode-nya kira-kira seperti ini:

function autocomplete(prefix, limit = 10):
    key = "ac:" + normalize(prefix)
    cached = cache.get(key)
    if cached != null:
        return cached

    candidates = db.query(
        "SELECT term, score FROM suggestions WHERE term LIKE ?",
        [prefix + "%"]
    )

    filtered = []
    for c in candidates:
        if isValid(c.term):
            filtered.append(c)

    result = sortDesc(filtered, by = score).take(limit)
    cache.set(key, result, ttl = 60)
    return result

Kode ini mudah dipahami, tetapi buruk untuk prefix populer karena:

  • mengambil terlalu banyak kandidat,
  • sort dilakukan setelah kandidat terkumpul,
  • cache miss memicu kerja berat penuh,
  • tidak ada perlindungan terhadap stampede pada key panas.

Perbaikan Bertahap yang Realistis

1. Batasi ruang masalah: bedakan strategi untuk prefix pendek dan panjang

Jangan perlakukan semua prefix sama. Prefix pendek hampir selalu perlu strategi khusus. Contoh kebijakan praktis:

  • Untuk panjang 1-2 karakter, gunakan struktur precomputed.
  • Untuk panjang menengah, gunakan index prefix yang lebih selektif.
  • Untuk panjang lebih besar, query langsung bisa cukup.

Ini bekerja karena distribusi biaya tidak linear. Prefix pendek memiliki fan-out besar, sehingga optimasi khusus memberi dampak paling besar pada p99.

2. Ganti dari scan kandidat besar ke precomputed top-k per prefix tertentu

Jika ada prefix yang sangat populer atau sangat padat, simpan langsung daftar top-k hasil untuk prefix tersebut. Bukan berarti semua prefix harus dimaterialisasi; pilih subset yang paling mahal atau paling sering dipakai.

Contoh struktur sederhana:

prefix_topk = {
  "a":  [top 10 item],
  "co": [top 10 item],
  "com": [top 10 item]
}

Keuntungan:

  • latensi baca sangat rendah,
  • tidak perlu sort di jalur request,
  • p99 turun drastis untuk prefix yang sebelumnya paling mahal.

Trade-off:

  • memori meningkat,
  • pipeline update menjadi lebih kompleks,
  • perlu kebijakan refresh bila ranking berubah.

Ini adalah contoh jelas pertukaran memori vs latensi. Untuk endpoint interaktif, trade-off ini sering masuk akal selama dataset precomputed dibatasi secara cerdas.

3. Pakai struktur index yang selaras dengan akses top-k

Jika tetap mengandalkan database atau storage engine, desain index harus mempertimbangkan dua hal sekaligus:

  • bagaimana mencari prefix dengan cepat,
  • bagaimana mendapatkan kandidat terbaik tanpa scan besar.

Dalam praktiknya, ini bisa berarti:

  • memisahkan storage antara dictionary mentah dan view top-k,
  • menyimpan skor/ranking yang sudah siap diakses,
  • menghindari query yang mengharuskan sort besar setelah prefix match.

Jika query Anda masih memerlukan scan ratusan ribu item untuk mengembalikan 10 hasil, index belum cocok dengan pola akses sebenarnya.

4. Tambahkan proteksi cache stampede

Untuk prefix panas, gunakan teknik seperti:

  • single-flight: hanya satu worker yang boleh menghitung ulang key tertentu,
  • request coalescing: request lain menunggu hasil yang sama,
  • stale-while-revalidate: sajikan data lama sebentar sambil refresh di belakang layar,
  • jitter TTL: hindari expiry serentak.

Pseudocode sederhana:

function getAutocomplete(prefix):
    key = "ac:" + prefix
    cached = cache.get(key)
    if cached != null:
        return cached

    return singleFlight(key, function():
        cached2 = cache.get(key)
        if cached2 != null:
            return cached2

        result = buildResult(prefix)
        cache.set(key, result, ttlWithJitter())
        return result
    )

Ini tidak mempercepat query dasar, tetapi mencegah ledakan kerja paralel yang sering menjadi penyebab p99 buruk saat cache miss massal terjadi.

5. Kurangi alokasi di jalur panas

Optimasi yang sering efektif:

  • normalisasi prefix sekali di awal,
  • hindari membangun daftar kandidat penuh jika hanya butuh top-k,
  • gunakan struktur heap kecil untuk top-k daripada sort seluruh kandidat,
  • hindari serialisasi payload yang berlebihan.

Contoh ide top-k tanpa sort penuh:

heap = new MinHeap(limit)
for candidate in streamCandidates(prefix):
    if heap.size < limit:
        heap.push(candidate)
    else if candidate.score > heap.min().score:
        heap.replaceMin(candidate)

return heap.toSortedDescList()

Jika kandidat tetap besar, ini belum menyelesaikan masalah utama. Namun setidaknya biaya sort dan memori menjadi lebih terkendali.

6. Terapkan pembatasan eksplisit untuk prefix ekstrem

Terkadang keputusan produk dan teknis harus bertemu. Misalnya:

  • autocomplete baru aktif setelah 2 atau 3 karakter,
  • prefix 1 karakter hanya memakai daftar populer statis,
  • query untuk prefix terlalu pendek tidak selalu mengakses dataset penuh.

Ini bukan kelemahan desain; justru sering menjadi keputusan yang paling rasional ketika biaya prefix sangat pendek tidak sebanding dengan manfaatnya.

Contoh Arsitektur Perbaikan yang Lebih Stabil

Berikut pola arsitektur yang sering lebih sehat untuk skala besar:

  1. Data mentah suggestion disimpan di storage utama.
  2. Pipeline offline atau nearline membangun prefix top-k index untuk prefix tertentu.
  3. Endpoint membaca dari cache atau store in-memory untuk prefix panas.
  4. Untuk prefix panjang yang lebih selektif, fallback ke query langsung yang sudah dioptimalkan.
  5. Ranking dan normalisasi dilakukan di luar jalur request sebisa mungkin.

Pseudocode keputusan baca:

function autocomplete(prefix, limit = 10):
    p = normalize(prefix)

    if len(p) <= 2:
        return prefixTopKStore.get(p) or []

    cached = cache.get("ac:" + p)
    if cached != null:
        return cached

    result = querySelectiveIndex(p, limit)
    cache.set("ac:" + p, result, ttlWithJitter())
    return result

Pola ini bekerja karena jalur paling mahal dipindahkan dari request time ke precomputation time. Anda membayar biaya memori dan kompleksitas update agar tail latency turun.

Trade-off Memori vs Latensi

Tidak ada optimasi gratis. Pada autocomplete skala besar, keputusan utama biasanya adalah seberapa banyak memori atau storage tambahan yang rela Anda gunakan untuk menurunkan p99.

Saat layak menambah memori

  • traffic tinggi dan endpoint berada di jalur interaktif,
  • prefix panas relatif terbatas dan dapat diidentifikasi,
  • ranking tidak berubah setiap detik,
  • biaya timeout ke pengguna lebih mahal daripada biaya RAM tambahan.

Saat perlu hati-hati dengan precompute besar-besaran

  • jumlah prefix unik sangat besar,
  • ranking berubah sangat sering,
  • memori terbatas,
  • ada banyak bahasa atau normalisasi kompleks yang memperbanyak jumlah key.

Pendekatan praktis biasanya bukan mematerialisasi semua prefix, melainkan:

  • top prefix berdasarkan traffic,
  • prefix dengan cardinality terburuk,
  • prefix pendek sampai panjang tertentu,
  • hasil top-k yang ukuran payload-nya kecil dan stabil.

Debugging Tips untuk Hasil yang Tidak Konsisten

Selain lambat, prefix populer kadang menghasilkan hasil yang berubah-ubah. Beberapa penyebab yang patut dicek:

  • cache berisi snapshot dari waktu berbeda sementara ranking terus berubah,
  • beberapa node memiliki state atau dataset yang belum sinkron,
  • request timeout memicu fallback ke sumber data lain dengan urutan berbeda,
  • sort tidak deterministik saat skor sama,
  • normalisasi input berbeda antara jalur cache dan jalur database.

Perbaikan yang sering membantu:

  • tetapkan tie-breaker deterministik pada ranking,
  • samakan pipeline normalisasi,
  • beri versi pada data cache bila ada perubahan format atau ranking model,
  • catat source-of-truth hasil pada log untuk request yang menyimpang.

Checklist Verifikasi Pasca-Fix

Setelah melakukan perubahan, jangan berhenti di pengujian lokal. Gunakan checklist berikut:

Metrik latensi

  • p50, p95, dan p99 turun, bukan hanya average.
  • Latency breakdown menunjukkan waktu terbesar sudah hilang dari jalur request.
  • Timeout rate menurun pada prefix pendek dan prefix panas.

Metrik query dan storage

  • Rows scanned atau keys examined turun signifikan untuk prefix terburuk.
  • Sort besar di database berkurang atau hilang.
  • Fallback ke query mahal makin jarang terjadi.

Metrik cache

  • Hit ratio naik khusus untuk top prefix, bukan hanya global.
  • Stampede berkurang saat key panas expired.
  • Eviction tidak menghapus key penting terlalu cepat.

Metrik aplikasi

  • CPU per request turun pada traffic yang sama.
  • Allocation rate dan GC pressure menurun.
  • Tidak ada lonjakan memori yang tidak terkendali akibat precompute atau cache baru.

Konsistensi hasil

  • Urutan hasil stabil untuk input yang sama.
  • Normalisasi input menghasilkan key cache yang konsisten.
  • Jalur fallback tidak menghasilkan ranking yang berbeda tanpa alasan jelas.

Uji operasional

  • Lakukan load test yang meniru distribusi prefix nyata, bukan data acak seragam.
  • Uji skenario expiry serentak dan restart node.
  • Pastikan pipeline pembaruan prefix index tidak tertinggal terlalu jauh.

Penutup

Debug autocomplete lambat hampir selalu soal distribusi biaya yang tidak merata. Rata-rata bisa terlihat aman, tetapi p99 rusak karena sebagian kecil prefix memicu scan panjang, cardinality buruk, hot key, dan alokasi memori berlebih. Jika endpoint Anda timeout secara sporadis pada dataset besar, mulailah dari observasi yang tepat: pecah latensi berdasarkan prefix, lihat rows scanned, profil cache per key panas, lalu cek biaya CPU dan memori di jalur request.

Perbaikan terbaik biasanya bukan satu trik tunggal. Anda perlu kombinasi prefix index yang sesuai, precomputed top-k untuk kasus terburuk, cache dengan perlindungan stampede, dan pembatasan eksplisit untuk prefix ekstrem. Biayanya adalah memori dan kompleksitas update, tetapi hasilnya adalah sistem autocomplete yang bukan hanya cepat di rata-rata, melainkan stabil di p99.