Konteks Pertanyaan dan Batasan
Desain layanan backend yang mengembalikan 10 saran kueri teratas untuk awalan (prefix) yang diketik. Asumsikan 50 juta pengguna aktif harian, 10 pencarian per pengguna per hari, lima permintaan saran per pencarian, beban puncak 150.000 permintaan per detik, target latensi p99 50 ms, target pembaruan popularitas 15 menit, dan target penghapusan kebijakan satu menit.
Ini adalah asumsi wawancara, bukan fakta produksi terukur. Desain dasar melayani saran popularitas anonim yang spesifik per lokal (locale). Komponen browser, koreksi ejaan, pelengkapan semantik, dan personalisasi per pengguna berada di luar cakupan awal. Layanan tidak boleh mengekspos kueri langka atau kueri terlarang hanya karena kueri tersebut muncul di log.
Ini adalah masalah desain sistem karena pekerjaan intinya mencakup penyerapan event, pemeringkatan, pembuatan indeks yang tidak dapat diubah (immutable), penyajian online, perilaku cache dan shard, serta publikasi yang aman. Komponen autocomplete frontend dapat mengonsumsi API ini, sementara Trie hanyalah salah satu representasi indeks lokal yang memungkinkan.
Hal yang Dievaluasi oleh Pewawancara
Jawaban yang kuat pertama-tama memisahkan jalur pembelajaran yang berat beban tulisnya (write-heavy) dari jalur penyajian yang berat beban bacanya (read-heavy). Memindai log mentah atau mengurutkan kandidat pada setiap penekanan tombol tidak akan mampu memenuhi target tail-latency yang ketat. Agregasi, pemeriksaan kelayakan, moderasi, dan sebagian besar pemeringkatan harus terjadi sebelum permintaan tiba; jalur online melakukan pencarian prefix yang dibatasi dan mengembalikan daftar kecil.
Sinyal kedua adalah penalaran kuantitatif. Asumsi harian menyiratkan 2,5 miliar permintaan: 50 juta dikali 10 dikali lima. Itu sekitar 28.900 permintaan per detik rata-rata, sehingga beban puncak 150.000 yang disebutkan kira-kira merupakan faktor puncak lima kali lipat. Pada estimasi respons 1 KB, payload respons puncak adalah sekitar 150 MB/s sebelum overhead protokol dan replikasi. Perhitungan ini mendorong target replikasi, cache, dan uji beban; perhitungan ini tidak berpura-pura menentukan ukuran memori tanpa mengukur indeks yang dienkode.
Sinyal ketiga adalah kebenaran publikasi. Indeks yang dibangun sebagian atau dirutekan secara tidak konsisten dapat mengembalikan hasil yang hilang atau diperingkat secara berbeda. Kandidat yang kuat membangun artefak terversi yang tidak dapat diubah (immutable), memvalidasinya, memuatnya berdampingan dengan versi lama, mengaktifkan perutean secara atomik, dan mempertahankan versi bagus sebelumnya untuk rollback.
Terakhir, popularitas tidak sama dengan kelayakan. Log pencarian dapat berisi data pribadi, manipulasi, dan teks berbahaya. Ambang batas frekuensi minimum, kontrol retensi, sinyal anti-penyalahgunaan, moderasi sebelum publikasi, dan jalur penolakan darurat yang lebih cepat adalah bagian dari kebenaran sistem.
Pertanyaan untuk Diklarifikasi Sebelum Menjawab
- Apa yang direpresentasikan oleh saran? Pelengkapan kueri, entitas produk, dan tujuan navigasi memerlukan sumber kandidat dan fitur pemeringkatan yang berbeda. Desain dasar mengembalikan string kueri lengkap.
- Pencocokan apa saja yang diperlukan? Pencarian hanya-prefix memungkinkan indeks prefix berurutan yang ringkas. Pencocokan infix, fuzzy, atau semantik menambahkan generator kandidat dan membuat anggaran online lebih sulit dibatasi.
- Seberapa segar setiap perubahan harus terjadi? Popularitas dapat mentolerir asumsi 15 menit; penghapusan kebijakan membutuhkan satu menit. Hal ini mengarah pada indeks dasar terversi ditambah lapisan penolakan (deny layer) yang diperbarui secara independen.
- Apakah hasilnya bersifat global atau dipersonalisasi? Hasil global dapat di-cache secara masif. Personalisasi mengurangi pembagian cache dan menambah persetujuan (consent), penghapusan, serta latensi pengambilan fitur. Ini dikecualikan pada awalnya.
- Bagaimana lokal dan normalisasi didefinisikan? Case folding, aksara, aksen, dan batas kata berbeda menurut lokal. Indeks dan kueri harus menggunakan kebijakan normalisasi terversi yang sama.
- Apa yang terjadi untuk prefix kosong dan satu karakter? Karakter-karakter ini sangat sering diakses (hot) dan dapat mengungkap tren luas. Sistem dasar mengembalikan daftar lokal yang dikurasi untuk input kosong dan daftar yang telah dihitung sebelumnya untuk satu karakter.
- Apa persyaratan keselamatan dan privasinya? Persyaratan ini menentukan retensi log, ambang agregasi, alur kerja peninjau, penyimpanan regional, dan apakah seorang kandidat boleh masuk ke dalam indeks.
Kerangka Kerja Jawaban 30 Detik
“Saya akan membagi sistem menjadi jalur pembangunan offline dan jalur pencarian online yang dibatasi. Event pencarian masuk ke stream, dinormalisasi dan diagregasi berdasarkan lokal dan jendela waktu, lalu melewati gerbang frekuensi, penyalahgunaan, privasi, dan moderasi. Pekerjaan pemeringkatan menulis kandidat teratas ke dalam indeks prefix terversi. Setelah validasi, replika penyaji memuat versi yang tidak dapat diubah (immutable) dan perutean beralih secara atomik. Permintaan online menormalisasi prefix, memeriksa cache prefix populer (hot-prefix), merutekan ke shard lokal dan prefix, menerapkan lapisan penolakan cepat, dan mengembalikan sepuluh hasil. Saya akan menentukan kapasitas dari puncak 150.000, membagi prefix populer saat dibutuhkan, menyimpan indeks sebelumnya untuk rollback, dan mengukur latensi p99, cakupan, recall keselamatan, tingkat versi basi, dan kualitas pemeringkatan.”
Pembahasan Mendalam Langkah demi Langkah
Langkah 1: Turunkan anggaran dan kontrak API
Gunakan API baca idempoten yang ringkas:
GET /v1/suggestions?prefix=iph&locale=en-US&limit=10
200 {
"suggestions": [
{ "text": "iphone charger", "id": "q_7f2" }
],
"indexVersion": "2026-07-19T17:30Z"
}Batasi limit, batasi panjang prefix yang dinormalisasi, tolak lokal yang tidak didukung, dan jangan pernah menerima bobot pemeringkatan dari klien. ID buram (opaque ID) yang stabil mendukung analitik tanpa memperlakukan teks tampilan sebagai pengenal. indexVersion membuat respons versi basi atau versi campuran dapat diamati.
Perhitungan 2,5 miliar harian menghasilkan rata-rata sekitar 28.900 QPS. Puncak 150.000 yang diberikan adalah target kapasitas. Jika satu respons kira-kira 1 KB, melayani 150 MB/s memerlukan replika regional dan transportasi terkompresi. Kapasitas cache dan RAM indeks tetap memerlukan sampel produksi: serialisasikan artefak representatif, ukur byte per prefix dan entri top-K, lalu tambahkan replikasi dan headroom. Mengalikan tebakan ukuran node Trie dengan jumlah kandidat akan menghasilkan presisi semu.
Langkah 2: Bangun kandidat tanpa memublikasikan log mentah
Klien memancarkan event pencarian selesai dengan ID kueri, lokal ternormalisasi, konteks kasar, stempel waktu, sinyal hasil, dan kunci aktor sementara yang menjaga privasi yang hanya digunakan untuk agregasi terbatas. Layanan penyerapan memvalidasi skema dan membuang bot yang jelas sebelum stream append-only. Agregasi berbasis jendela menghitung jumlah aktor unik dan sinyal kualitas; pengenal pengguna mentah tidak pernah menjadi bagian dari kunci saran.
Pipeline kandidat menerapkan ambang batas minimum pengguna unik, kontrol laju dan penyalahgunaan, aturan privasi dan retensi, serta klasifikasi kebijakan. Pipeline ini kemudian memeringkat kandidat yang memenuhi syarat menggunakan kombinasi terdokumentasi dari popularitas, peluruhan kebaruan (recency decay), kualitas hasil, dan aturan editorial. Bobot pastinya dipelajari dan diuji; bobot tersebut bukan konstanta universal. Simpan kandidat yang ditolak dan alasannya di penyimpanan audit terbatas, bukan di indeks penyajian.
Pemeringkatan dari klik yang diamati dapat memperkuat apa pun yang sudah ditampilkan sebelumnya. Gunakan penilaian relevansi offline dan eksperimen berpagar (guarded experiments) bersamaan dengan engagement, serta pantau cakupan saran, tingkat tanpa hasil, keluhan, dan konsentrasi paparan. Moderasi harus dilakukan sebelum pembuatan indeks karena saran otomatis yang diturunkan dari log dapat mereproduksi teks yang berbahaya atau bias.
Langkah 3: Materialisasikan indeks prefix yang dibatasi
Untuk setiap saran yang memenuhi syarat, hasilkan prefix di bawah normalisasi sadar-lokal yang sama dengan yang digunakan secara online. Simpan hanya daftar teratas yang dibatasi per prefix—misalnya, 20 kandidat terbaik saat API mengembalikan 10—sehingga pencarian dan pemfilteran tetap terikat batasnya. Kandidat ekstra memungkinkan deduplikasi dan penghapusan darurat tanpa menelusuri subtree.
Trie atau finite-state transducer dapat merepresentasikan prefix bersama; tabel key-value terurut dengan kunci lokal ditambah prefix lebih sederhana secara operasional dan dapat dikompresi dengan baik. Pilih setelah melakukan benchmark pada ukuran artefak, waktu pembangunan, p99 pencarian, dan alur kerja pembaruan. Completion suggester milik Elasticsearch mengilustrasikan trade-off yang sama: pencarian prefix yang cepat menggunakan struktur dalam-memori yang mahal untuk dibangun, dan bobot serta konteks memengaruhi pemeringkatan dan pemfilteran.
Cakupan dasar adalah pelengkapan prefix yang tepat (exact). Pelengkapan fuzzy adalah generator terpisah karena perluasan edit-distance mengubah recall, biaya CPU, dan analisis keselamatan. Fitur ini tidak boleh secara diam-diam berbagi janji latensi yang sama.
Langkah 4: Publikasikan versi yang tidak dapat diubah dengan aman
Setiap build memiliki watermark input, versi normalisasi, versi ranker, versi kebijakan, checksum, dan waktu pembuatan. Validasi memeriksa skema, jumlah kandidat, frasa uji yang dilarang, isolasi lokal, pemecahan seri deterministik (deterministic tie-breaking), sampel pencarian, ukuran artefak, dan latensi pada replika berbeban.
Replika memuat indeks baru yang tidak dapat diubah di samping indeks yang sedang aktif. Laporan kesehatan mengonfirmasi checksum dan kueri representatifnya. Control plane kemudian secara atomik mengubah versi aktif untuk suatu grup shard. Selama peluncuran, permintaan tetap terikat pada satu versi; hasil campuran diukur. Simpan versi bagus sebelumnya hingga versi baru melewati jendela canary, lalu lakukan rollback perutean jika latensi, keselamatan, atau cakupan mengalami penurunan kualitas (regresi).
Pembangunan yang gagal atau terlambat tidak menggantikan indeks yang sehat. Kesegaran data adalah sebuah SLO, bukan izin untuk memublikasikan artefak yang tidak valid.
Langkah 5: Jaga agar jalur online tetap pendek
Permintaan melewati rate limiting, normalisasi, resolusi lokal, dan cache prefix populer yang tepat. Router memilih shard prefix dan replika. Replika melakukan satu kali pencarian indeks, menghapus entri dalam himpunan penolakan cepat, mendeduplikasi ID stabil, dan mengembalikan 10 entri pertama. Tidak ada kueri log mentah, agregasi terdistribusi, atau pengurutan penuh yang boleh berada di jalur ini.
Kunci cache mencakup lokal, prefix ternormalisasi, batas (limit), versi kebijakan, dan versi indeks aktif. Hal ini mencegah respons pemeringkatan atau kebijakan lama tetap ada setelah aktivasi. Prefix kosong dan satu karakter dihitung secara terpisah sebelumnya karena lalu lintas dan himpunan kandidatnya sangat luas. Negative caching dapat melindungi prefix yang tidak ada, tetapi TTL-nya tidak boleh menyembunyikan saran yang baru memenuhi syarat melebihi target kesegaran.
Langkah 6: Sharding untuk lokalitas dan prefix populer
Partisi pertama-tama berdasarkan lokal, lalu berdasarkan rentang prefix atau hash dari beberapa karakter pertama yang dinormalisasi. Partisi rentang menjaga lokalitas tetapi menciptakan shard populer (hot shard); hashing murni menyeimbangkan beban tetapi mungkin memerlukan metadata perutean tambahan. Router praktis memiliki peta terversi dari rentang prefix ke shard dan dapat membagi rentang populer seperti satu karakter pertama yang populer tanpa membangun kembali rentang yang tidak terkait.
Replikasi setiap shard di seluruh domain kegagalan dan rutekan ke replika lokal yang sehat. Catat QPS per-prefix, rasio hit cache, CPU shard, p99 pencarian, dan byte indeks. Menambahkan replika menyelesaikan beban baca; membagi atau mengisolasi rentang populer menyelesaikan ketimpangan beban (skew). Jika shard tidak tersedia, kembalikan versi yang di-cache dengan metrik kesegaran eksplisit atau daftar kosong—jangan pernah mengembalikan saran dari lokal lain.
Langkah 7: Penuhi dua siklus waktu kesegaran data
Indeks dasar dibangun kembali setiap 15 menit. Overlay tren terkini yang kecil dapat mengagregasi jendela yang lebih pendek dan menggabungkan kumpulan terbatas dengan kandidat dasar, tetapi harus melewati gerbang privasi dan keselamatan yang sama. Jika overlay tersebut gagal, sajikan indeks dasar terakhir yang bagus daripada membuat seluruh endpoint tidak tersedia.
Penghapusan kebijakan menggunakan himpunan penolakan yang didistribusikan secara terpisah dengan target satu menit. Replika penyaji memfilter ID yang ditolak setelah pencarian, dan kunci cache menyertakan versinya. Pembangunan dasar berikutnya menghapusnya secara permanen. Desain dua siklus ini menghindari pembangunan ulang artefak besar untuk penghapusan darurat sambil tetap mempertahankan publikasi dasar yang deterministik.
Langkah 8: Validasi pemeringkatan, keselamatan, dan operasi
Uji beban memutar ulang distribusi panjang prefix dan lokal yang diamati pada puncak 150.000 QPS, termasuk prefix satu karakter yang populer, pemulaian cache dingin (cold-cache startup), kehilangan replika, dan aktivasi versi. Pastikan p99 di bawah 50 ms pada batas layanan, tingkat kesalahan yang terbatas, tidak ada checksum campuran per respons, dan pemulihan tanpa thundering herd.
Evaluasi offline mencakup relevansi top-K, cakupan, tingkat duplikasi, kebenaran lokal, recall konten terlarang, dan stabilitas antar versi. Eksperimen online menggunakan penyelesaian pencarian dan kualitas hasil downstream dengan batasan pengaman (guardrails) untuk tingkat tanpa hasil, latensi, keluhan, dan konsentrasi paparan. Tingkat klik yang lebih tinggi saja tidak cukup karena posisi tampilan memengaruhi klik.
Latihan operasional mencakup batch event yang teracuni (poisoned), build yang gagal, artefak yang terlalu besar, hot shard, himpunan penolakan basi, peluncuran parsial replika, dan regresi ranker. Setiap peringatan (alert) harus dipetakan ke tindakan yang aman: tunda aktivasi, kembali ke versi bagus terakhir, isolasi overlay, bagi rentang, atau aktifkan aturan penolakan darurat.
Contoh Jawaban Berkualitas Tinggi
“Saya akan mulai dengan pelengkapan prefix anonim yang spesifik per lokal dan sepuluh hasil. Dari 50 juta pengguna, sepuluh pencarian, dan lima permintaan per pencarian, saya mendapatkan 2,5 miliar permintaan per hari, sekitar 28.900 rata-rata QPS. Saya akan merencanakan kapasitas untuk beban puncak 150.000 yang dinyatakan dan mengukur ukuran indeks yang diserialisasi daripada menebak memori Trie.
Jalur data dan jalur penyajian dipisahkan. Event pencarian selesai masuk ke stream. Agregasi menghasilkan jumlah pengguna unik, kebaruan, dan sinyal kualitas hasil. Kandidat melewati gerbang frekuensi minimum, penyalahgunaan, privasi, dan moderasi sebelum ranker menulis daftar teratas yang dibatasi per prefix yang dinormalisasi. Setiap artefak mencatat watermark data, versi normalisasi, ranker, dan kebijakannya.
Replika penyaji menyimpan versi indeks yang tidak dapat diubah (immutable). Mereka memuat dan memvalidasi versi baru di samping versi lama, kemudian perutean beralih secara atomik dan dapat di-rollback. Permintaan menormalisasi prefix dan lokal, memeriksa cache terversi, merutekan ke shard prefix, melakukan satu pencarian, menerapkan himpunan penolakan cepat, dan mengembalikan sepuluh hasil. Rentang satu karakter yang populer mendapatkan cache khusus dan dapat dipecah secara independen.
Pembangunan ulang dasar memenuhi target 15 menit. Overlay tren kecil yang terpagar dapat meningkatkan kebaruan, sementara penghapusan darurat menggunakan lapisan penolakan satu menit; kegagalan pada salah satunya tidak akan merusak basis data terakhir yang bagus. Saya akan menguji distribusi prefix yang sebenarnya pada 150.000 QPS dan melacak p99, kesegaran, rasio hit cache, ketimpangan shard, relevansi, kebocoran lokal, recall keselamatan, dan waktu rollback.”
Kesalahan Umum
- Mengueri dan mengurutkan log mentah pada setiap penekanan tombol → beban kerja bertambah seiring bertambahnya riwayat dan membuat tail latency tidak dapat diprediksi → hitung sebelumnya daftar top-K yang dibatasi dan jaga agar pencarian online dibatasi secara konstan.
- Hanya menyebut struktur data sebagai “Trie” lalu berhenti → ini menghilangkan aspek pemeringkatan, publikasi, sharding, keselamatan, dan pemulihan → jelaskan siklus hidup pembangunan dan penyajian serta lakukan benchmark representasi data.
- Mengestimasi RAM dari ukuran node yang dikarang → pengodean dan pembagian prefix menentukan ukuran byte sebenarnya → serialisasikan data representatif dan ukur ukuran artefak serta latensi pencarian.
- Melakukan caching hanya berdasarkan prefix → versi lokal, kebijakan, dan indeks akan bocor atau mempertahankan hasil yang salah → sertakan setiap versi yang memengaruhi hasil ke dalam cache key.
- Menerbitkan secara in-place → pembaca akan melihat data parsial atau campuran → bangun artefak yang tidak dapat diubah (immutable), validasi, muat berdampingan, dan aktifkan secara atomik.
- Menggunakan popularitas sebagai satu-satunya aturan kelayakan → teks pribadi yang langka, dimanipulasi, atau berbahaya dapat muncul ke permukaan → terapkan ambang batas pengguna unik, gerbang anti-penyalahgunaan, privasi, dan moderasi.
- Membangun kembali semuanya untuk penghapusan darurat → tenggat waktu keselamatan menjadi bergantung pada batch job yang besar → distribusikan lapisan penolakan cepat dan hapus secara permanen pada pembangunan dasar berikutnya.
- Memperlakukan rasio klik-tayang (CTR) sebagai relevansi yang tidak bias → peringkat tampilan memengaruhi klik → gabungkan eksperimen berpagar dengan penilaian offline dan metrik keselamatan.
Pertanyaan Lanjutan dan Tanggapan
Pertanyaan lanjutan 1: Bagaimana Anda akan menambahkan pencocokan fuzzy?
Pertahankan pencarian prefix tepat (exact) sebagai generator pertama yang murah. Picu pembuatan fuzzy hanya setelah panjang minimum tercapai atau ketika cakupan exact rendah, batasi edit distance dan jumlah kandidat, serta gabungkan melalui satu ranker dan kebijakan moderasi. Lakukan benchmark pada distance yang sadar Unicode dan input adversarial karena perluasan fuzzy meningkatkan CPU dan dapat mengambil varian yang sensitif terhadap kebijakan.
Pertanyaan lanjutan 2: Bagaimana Anda akan menambahkan personalisasi?
Campurkan sejumlah kecil kumpulan kandidat pribadi yang diotorisasi setelah mengambil kandidat global. Cache tetap bersifat global hingga batas tersebut; respons akhir menjadi tercakup ke pengguna (user-scoped) dan tidak boleh masuk ke cache bersama. Tentukan persetujuan (consent), retensi, penghapusan, pengecualian kueri sensitif, batas waktu fitur (timeout), dan fallback khusus global sebelum menambahkan fitur pemeringkatan.
Pertanyaan lanjutan 3: Bagaimana jika satu lokal tidak lagi muat di memori?
Bagi rentang prefix-nya menggunakan byte dan QPS terukur, lalu perbarui peta perutean terversi. Pertahankan prefix populer tingkat atas pada replika khusus dan izinkan rentang dingin (cold ranges) menggunakan indeks yang di-memory-map atau indeks jarak jauh jika p99-nya masih memenuhi anggaran. Lakukan rebalancing berdasarkan versi artefak sehingga pembaca tidak pernah bergantung pada migrasi kunci in-place.
Pertanyaan lanjutan 4: Bagaimana Anda akan mendukung berita terkini (breaking news) dalam hitungan detik?
Jangan memperpendek seluruh pembangunan dasar secara membabi buta. Tambahkan overlay streaming yang dibatasi secara ketat dengan sumber kandidat tepercaya, ambang kelayakan tinggi, moderasi langsung, TTL, dan kill switch. Gabungkan dengan hasil dasar di bawah anggaran kandidat tetap. Jika kesegaran atau watermark kebijakannya basi, buang overlay dan sajikan indeks dasar terakhir yang bagus.
Pertanyaan lanjutan 5: Bagaimana Anda menghapus kueri setelah ada permintaan privasi?
Hapus atau beri tombstone pada event mentah yang memenuhi syarat dan agregat sesuai dengan model data, tambahkan ID saran ke lapisan penolakan cepat, batalkan entri cache yang terpengaruh melalui versi kebijakan, dan bangun kembali artefak dasar dari input yang telah dikoreksi. Audit waktu propagasi di seluruh wilayah tanpa mencatat kembali teks sensitif tersebut.