Design Typeahead Suggestion

Prompt latihan

1. Problem Statement, Functional Requirements, and Scale Assumptions

   Tentukan ruang lingkup sistem saran typeahead: penyelesaian query berbasis prefix saat pengguna mengetik, mengembalikan saran terurut dari indeks yang telah dibangun sebelumnya. Kecualikan secara eksplisit halaman hasil full-text search, koreksi ejaan, saran pencarian gambar, dan input suara dari desain awal. Nyatakan asumsi skala awal (volume query, ukuran korpus, target latensi yang diharapkan) sebelum mengusulkan komponen apa pun.

2. Non-Functional Requirements

   Tentukan NFR utama: latensi saran per keystroke (target <100ms end-to-end termasuk jaringan), ketersediaan (kotak pencarian tidak boleh pernah memblokir saat outage layanan saran), latensi update indeks (seberapa cepat query trending baru muncul di saran), dan kualitas relevansi. Bedakan antara kebutuhan kritis-latensi (pengiriman saran per-keystroke) dan eventually-consistent (pipeline update indeks).

3. Quantitative Analysis

   Estimasikan QPS API saran puncak (pencari aktif harian × keystroke rata-rata per sesi pencarian × amplifikasi jam-puncak), ukuran indeks saran di memori (jumlah prefix unik × byte per entri daftar saran), dan volume event analitik dari klik-tayang saran. Turunkan rasio baca:tulis untuk indeks prefix (banyak baca per update indeks) dan nilai kemampuan-cache lookup prefix teratas.

4. API Design

   Tentukan operasi API untuk mengambil saran berdasarkan sebuah prefix (termasuk parameter untuk konteks pengguna, locale, dan batas hasil), mencatat klik-tayang saran untuk analitik, dan API internal untuk rebuild indeks atau update inkremental. Sertakan bentuk response (teks saran, label tampilan, skor rank), perilaku debounce di klien, dan kasus error (saran kosong, indeks tidak tersedia).

5. High-Level Design

   Usulkan komponen utama: debounce sisi-klien, suggestion API service, indeks prefix (trie atau inverted index), cache in-memory untuk prefix panas, ranking service (popularitas global + sinyal personalisasi), dan pipeline analitik untuk umpan balik. Telusuri sebuah request dari keystroke ketiga pengguna melalui debounce, panggilan API, pengecekan cache, lookup indeks, ranking, dan response. Identifikasi dari mana saran berasal untuk pengguna cold-start (ranking global) vs. pengguna kembali (re-ranking terpersonalisasi).

6. Additional High-Level Design Prompts

   Bahas tiga area desain lanjutan: (1) Injeksi saran trending, bagaimana query trending real-time (dari satu jam terakhir event pencarian) dipadukan ke saran popularitas-global tanpa membangun ulang seluruh trie; (2) Pencegahan penyalahgunaan, bagaimana saran query yang menyinggung atau berbahaya difilter dari indeks (blocklist, klasifier ML, supresi berbasis-ambang); (3) A/B testing algoritma ranking, bagaimana model ranking berbeda (popularitas global, terpersonalisasi, trending-boosted) disajikan ke cohort pengguna berbeda tanpa men-deploy beberapa salinan indeks.

7. Deep Dives

   Deep dive ke tiga area: (1) Trie vs. inverted index untuk lookup prefix, bandingkan footprint memori (trie menyimpan pohon prefix penuh di memori; inverted index menggunakan token edge n-gram yang disimpan di indeks standar), performa query prefix (trie: traversal O(panjang prefix); inverted index: lookup O(log n) pada prefix ter-tokenisasi), biaya update (trie: penambahan node in-place; inverted index: re-indexing dokumen), dan pendekatan hybrid (trie untuk prefix top-K panas yang disajikan dari memori, inverted index untuk long tail); (2) Personalisasi, bagaimana riwayat pencarian pengguna diberi bobot bersama frekuensi query global, injeksi query trending dengan faktor decay kesegaran, sinyal kontekstual (lokasi, waktu hari, bahasa), dan A/B testing model ranking saran tanpa menyajikan indeks terpisah per cohort; (3) Tokenisasi multi-bahasa, teks CJK (Tionghoa, Jepang, Korea) tidak memiliki batas kata spasi sehingga memerlukan segmentasi level-karakter atau tokenisasi berbasis-kamus, normalisasi diakritik (caFe → cafe, naïve → naive) memungkinkan pencocokan tak-sensitif-aksen, query campuran-aksara (Indonesia + Inggris) memerlukan deteksi aksara per-token dan routing stemmer per-bahasa.

8. Final Review Handoff Readiness

   Ringkas keputusan desain end-to-end: struktur data indeks yang dipilih (trie, inverted index, atau hybrid) beserta justifikasi, strategi lapisan cache untuk prefix panas, model ranking (popularitas global + sinyal personalisasi), pendekatan injeksi trending, dan rencana dukungan multi-bahasa. Soroti dua pertanyaan terbuka terbesar yang tersisa (trade-off latensi update indeks vs. kesegaran, dan batas privasi personalisasi) dan berikan rencana rollout untuk meluncurkan dengan saran global dulu, lalu menambahkan personalisasi secara bertahap.

Preview solusi

Merancang Typeahead Suggestion, Solusi Referensi 1. Scope dan Non-Goals Dalam scope: Prefix-based query completion yang mengembalikan suggestion ter-rank ketika pengguna mengetik. Pengguna melihat hingga 10 suggestion setelah 100–200 ms waktu idle mengetik (debounce). Suggestion berasal dari index query populer yang telah dibangun sebelumnya, dipersonalisasi…