Kehendak Soalan dan Konteks Berkenaan
Reka bentuk perkhidmatan bahagian belakang (backend) yang mengembalikan 10 cadangan pertanyaan teratas untuk awalan (prefix) yang ditaip. Andaikan 50 juta pengguna aktif harian, 10 carian setiap pengguna setiap hari, lima permintaan cadangan setiap carian, 150,000 permintaan sesaat pada waktu puncak, sasaran kependaman p99 50 ms, sasaran penyegaran populariti 15 minit, dan sasaran penyingkiran dasar satu minit.
Ini adalah andaian temu duga, bukan fakta pengeluaran yang diukur. Reka bentuk asas menyajikan cadangan populariti tanpa nama mengikut lokaliti (locale). Komponen pelayar, pembetulan ejaan, pelengkapan semantik dan pemperibadian bagi setiap pengguna berada di luar skop awal. Perkhidmatan ini tidak boleh mendedahkan pertanyaan yang jarang berlaku atau tidak dibenarkan semata-mata kerana ia muncul dalam log.
Ini ialah masalah reka bentuk sistem kerana kerja terasnya merangkumi pengingesan peristiwa, pemeringkatan, pembinaan indeks tak boleh ubah (immutable), penyajian dalam talian, tingkah laku cache dan shard, serta penerbitan yang selamat. Komponen autocomplete bahagian hadapan (frontend) boleh menggunakan API ini, manakala Trie hanyalah salah satu representasi indeks tempatan yang mungkin.
Perkara yang Dinilai oleh Penemu Duga
Jawapan yang kukuh terlebih dahulu memisahkan laluan pembelajaran yang berat beban tulisnya (write-heavy) daripada laluan penyajian yang berat beban bacanya (read-heavy). Mengimbas log mentah atau mengisih calon pada setiap ketukan kekunci tidak dapat memenuhi sasaran kependaman ekor (tail-latency) yang ketat. Pengagregatan, pemeriksaan kelayakan, penyederhanaan dan kebanyakan pemeringkatan harus berlaku sebelum permintaan tiba; laluan dalam talian melakukan carian awalan terikat dan mengembalikan senarai kecil.
Isyarat kedua ialah penaakulan kuantitatif. Andaian harian membayangkan 2.5 bilion permintaan: 50 juta kali 10 kali lima. Ini adalah kira-kira 28,900 permintaan sesaat secara purata, jadi puncak 150,000 yang dinyatakan adalah kira-kira lima kali ganda faktor puncak. Pada anggaran respons 1 KB, muatan respons puncak adalah sekitar 150 MB/s sebelum overhed protokol dan replikasi. Pengiraan ini memacu sasaran replikasi, cache dan ujian beban; ia tidak cuba mengagak saiz memori tanpa mengukur indeks yang dikodkan.
Isyarat ketiga ialah ketepatan penerbitan. Indeks yang dibina sebahagiannya atau dihalakan secara tidak konsisten boleh mengembalikan hasil yang hilang atau diperingkatkan secara berbeza. Calon yang kukuh membina artifak tak boleh ubah yang berversi, mengesahkannya, memuatkannya bersebelahan dengan versi lama, mengaktifkan penghalaan secara atomik dan mengekalkan versi baik sebelumnya untuk pengunduran (rollback).
Akhir sekali, populariti tidak sama dengan kelayakan. Log carian boleh mengandungi data peribadi, manipulasi dan teks berbahaya. Ambang kekerapan minimum, kawalan pengekalan, isyarat antirasuah/antipenyalahgunaan, penyederhanaan sebelum penerbitan dan laluan penolakan kecemasan yang lebih pantas adalah sebahagian daripada ketepatan sistem.
Soalan untuk Dijelaskan Sebelum Menjawab
- Apakah yang diwakili oleh sesuatu cadangan? Pelengkapan pertanyaan, entiti produk dan destinasi navigasi memerlukan sumber calon dan ciri pemeringkatan yang berbeza. Reka bentuk asas mengembalikan rentetan pertanyaan yang lengkap.
- Padanan manakah yang diperlukan? Carian awalan sahaja membolehkan indeks awalan tersusun yang padat. Padanan sisipan (infix), kabur (fuzzy) atau semantik menambah penjana calon dan menjadikan belanjawan dalam talian lebih sukar dihadkan.
- Sejauh manakah setiap perubahan perlu segar? Populariti boleh bertolak ansur dengan andaian 15 minit; penyingkiran dasar memerlukan satu minit. Ini membawa kepada indeks asas berversi ditambah lapisan penolakan (deny layer) yang disegarkan secara bebas.
- Adakah hasil bersifat global atau diperibadikan? Hasil global boleh dicache secara meluas. Pemperibadian mengurangkan perkongsian cache dan menambah persetujuan, pemadaman serta kependaman pengambilan ciri. Ia dikecualikan pada peringkat awal.
- Bagaimanakah lokaliti dan penormalan ditakrifkan? Case folding, skrip, aksen dan sempadan perkataan berbeza mengikut lokaliti. Indeks dan pertanyaan mesti menggunakan dasar penormalan berversi yang sama.
- Apakah yang berlaku untuk awalan kosong dan satu aksara? Ia menerima trafik yang sangat tinggi (hot) dan boleh mendedahkan trend yang luas. Sistem asas mengembalikan senarai lokaliti yang dikurasi untuk input kosong dan senarai yang dikira lebih awal untuk satu aksara.
- Apakah keperluan keselamatan dan privasi? Keperluan ini menentukan pengekalan log, ambang pengagregatan, aliran kerja penyemak, penyimpanan serantau dan sama ada calon dibenarkan memasuki indeks.
Rangka Kerja Jawapan 30 Saat
“Saya akan membahagikan sistem kepada laluan pembinaan luar talian dan laluan carian dalam talian yang terikat. Peristiwa carian masuk ke dalam strim, dinormalkan dan diagregatkan mengikut lokaliti dan tetingkap masa, kemudian melepasi get kekerapan, penyalahgunaan, privasi dan penyederhanaan. Tugas pemeringkatan menulis calon teratas ke dalam indeks awalan berversi. Selepas pengesahan, replika penyajian memuatkan versi tak boleh ubah dan suis penghalaan beralih secara atomik. Permintaan dalam talian menormalkan awalan, menyemak cache awalan hangat (hot-prefix), menghala ke shard lokaliti dan awalan, menggunakan lapisan penolakan pantas dan mengembalikan sepuluh hasil. Saya akan menentukan kapasiti daripada puncak 150,000, memecahkan awalan hangat apabila diperlukan, menyimpan indeks sebelumnya untuk pengunduran (rollback), dan mengukur kependaman p99, liputan, ingatan keselamatan (safety recall), kadar versi lapuk dan kualiti pemeringkatan.”
Perbincangan Terperinci Langkah demi Langkah
Langkah 1: Terbitkan belanjawan dan kontrak
Gunakan API baca idempoten yang kecil:
GET /v1/suggestions?prefix=iph&locale=en-US&limit=10
200 {
"suggestions": [
{ "text": "iphone charger", "id": "q_7f2" }
],
"indexVersion": "2026-07-19T17:30Z"
}Kepitkan limit, hadkan panjang awalan yang dinormalkan, tolak lokaliti yang tidak disokong dan jangan sekali-kali menerima pemberat pemeringkatan daripada klien. ID legap yang stabil menyokong analitik tanpa menganggap teks paparan sebagai pengecam. indexVersion menjadikan respons versi lapuk atau bercampur dapat diperhatikan.
Pengiraan harian 2.5 bilion memberikan purata kira-kira 28,900 QPS. Puncak 150,000 yang diberikan ialah sasaran kapasiti. Jika satu respons adalah sekitar 1 KB, menyajikan 150 MB/s memerlukan replika serantau dan pengangkutan termampat. Kapasiti cache dan RAM indeks masih memerlukan sampel pengeluaran: sirikan artifak representatif, ukur bait bagi setiap awalan dan entri top-K, kemudian tambahkan replikasi dan ruang tambahan (headroom). Mendarab saiz nod Trie yang diagak dengan bilangan calon akan menghasilkan ketepatan palsu.
Langkah 2: Bina calon tanpa menerbitkan log mentah
Klien memancarkan peristiwa carian selesai dengan ID pertanyaan, lokaliti yang dinormalkan, konteks kasar, cap masa, isyarat hasil dan kunci pelaku jangka pendek yang memelihara privasi yang hanya digunakan untuk pengagregatan terikat. Perkhidmatan pengingesan mengesahkan skema dan menggugurkan bot yang jelas sebelum strim tambah-sahaja (append-only). Pengagregatan bertetingkap mengira bilangan pelaku unik dan isyarat kualiti; pengecam pengguna mentah tidak sekali-kali menjadi sebahagian daripada kunci cadangan.
Saluran paip calon menggunakan ambang pengguna unik minimum, kawalan kadar dan penyalahgunaan, peraturan privasi dan pengekalan, serta pengelasan dasar. Ia kemudian memperingkatkan calon yang layak menggunakan gabungan populariti yang didokumentasikan, susutan kebaharuan (recency decay), kualiti hasil dan peraturan editorial. Pemberat yang tepat dipelajari dan diuji; ia bukan pemalar sejagat. Simpan calon yang ditolak dan alasannya dalam stor audit terhad, bukan dalam indeks penyajian.
Pemeringkatan daripada klik yang diperhatikan boleh mengukuhkan apa sahaja yang telah dipaparkan. Gunakan pertimbangan perkaitan luar talian dan eksperimen terkawal di samping penglibatan, serta pantau liputan cadangan, kadar tanpa hasil, aduan dan kepekatan pendedahan. Penyederhanaan patut dilakukan sebelum pembinaan indeks kerana cadangan yang diperoleh daripada log secara automatik boleh menghasilkan semula teks yang berbahaya atau berat sebelah.
Langkah 3: Jelmakan indeks awalan terikat
Bagi setiap cadangan yang layak, hasilkan awalan di bawah penormalan peka lokaliti yang sama seperti yang digunakan dalam talian. Simpan hanya senarai teratas yang terikat bagi setiap awalan—contohnya, 20 calon terbaik apabila API mengembalikan 10—supaya carian dan penapisan kekal terikat. Calon tambahan membolehkan penyahduplikasian dan penyingkiran kecemasan tanpa perlu menyusuri subpokok.
Trie atau transduser keadaan terhingga (finite-state transducer) boleh mewakili awalan yang dikongsi; jadual nilai kunci tersusun yang dikunci oleh lokaliti ditambah awalan adalah lebih mudah dari segi operasi dan mungkin dimampatkan dengan baik. Buat pilihan selepas menanda aras saiz artifak, masa pembinaan, p99 carian dan aliran kerja kemas kini. Pencadang pelengkapan (completion suggester) Elasticsearch menggambarkan pertukaran yang sama: carian awalan pantas menggunakan struktur dalam memori yang mahal untuk dibina, dan pemberat serta konteks mempengaruhi pemeringkatan dan penapisan.
Skop asas ialah pelengkapan awalan tepat. Pelengkapan kabur (fuzzy) ialah penjana berasingan kerana pengembangan jarak suntingan mengubah ingatan (recall), kos CPU dan analisis keselamatan. Ia tidak sepatutnya berkongsi janji kependaman yang sama secara senyap.
Langkah 4: Terbitkan versi tak boleh ubah dengan selamat
Setiap binaan mempunyai tera air input, versi penormalan, versi pemeringkat, versi dasar, checksum dan masa penciptaan. Pengesahan menyemak skema, kiraan calon, frasa ujian yang dilarang, pengasingan lokaliti, pemutus seri deterministik, sampel carian, saiz artifak dan kependaman pada replika yang dimuatkan.
Replika memuatkan indeks tak boleh ubah yang baharu di samping indeks yang aktif. Laporan kesihatan mengesahkan checksum dan pertanyaan representatifnya. Satah kawalan kemudian menukar versi aktif secara atomik untuk kumpulan shard. Semasa pelancaran, permintaan kekal dipautkan pada satu versi; hasil bercampur diukur. Simpan versi baik sebelumnya sehingga versi baharu melepasi tetingkap kanari, kemudian undurkan penghalaan jika kependaman, keselamatan atau liputan merosot.
Binaan yang gagal atau lewat tidak akan menggantikan indeks yang sihat. Kesegaran ialah SLO, bukan kebenaran untuk menerbitkan artifak yang tidak sah.
Langkah 5: Pastikan laluan dalam talian kekal pendek
Permintaan melepasi pengehadan kadar, penormalan, resolusi lokaliti dan cache awalan hangat yang tepat. Penghala memilih shard awalan dan replika. Replika melakukan satu carian indeks, mengalih keluar entri dalam set penolakan pantas, menyahduplikasi ID yang stabil dan mengembalikan 10 entri pertama. Tiada pertanyaan log mentah, pengagregatan teragih atau pengisihan penuh yang dibenarkan pada laluan ini.
Kunci cache termasuk lokaliti, awalan dinormalkan, had, versi dasar dan versi indeks aktif. Ini menghalang respons pemeringkatan atau dasar lama daripada kekal selepas pengaktifan. Awalan kosong dan satu aksara dikira lebih awal secara berasingan kerana trafik dan set calonnya luar biasa luas. Pengecaman negatif boleh melindungi awalan yang tidak wujud, tetapi TTL-nya tidak boleh menyembunyikan cadangan yang baru layak melebihi sasaran kesegaran.
Langkah 6: Pemecahan (sharding) untuk lokaliti dan awalan hangat
Pecahkan mengikut lokaliti terlebih dahulu, kemudian mengikut julat awalan atau cincangan (hash) beberapa aksara pertama yang dinormalkan. Pembahagian julat mengekalkan lokaliti tetapi mencipta shard hangat; pencincangan tulen mengimbangi beban tetapi mungkin memerlukan metadata penghalaan tambahan. Penghala praktikal memiliki peta berversi dari julat awalan ke shard dan boleh membahagikan julat hangat seperti satu aksara pertama yang popular tanpa membina semula julat yang tidak berkaitan.
Replikasi setiap shard merentasi domain kegagalan dan hala ke replika tempatan yang sihat. Rekod QPS setiap awalan, kadar hit cache, CPU shard, p99 carian dan bait indeks. Menambah replika menyelesaikan beban baca; membelah atau mengasingkan julat hangat menyelesaikan ketidakseimbangan beban (skew). Jika shard tidak tersedia, kembalikan versi yang dicache dengan metrik kesegaran eksplisit atau senarai kosong—jangan sekali-kali cadangan daripada lokaliti lain.
Langkah 7: Penuhi dua jam kesegaran
Indeks asas dibina semula setiap 15 minit. Tindanan trend terkini yang kecil boleh mengagregatkan tetingkap yang lebih pendek dan menggabungkan set terikat dengan calon asas, tetapi ia mesti melepasi get privasi dan keselamatan yang sama. Jika tindanan itu gagal, sajikan indeks asas baik yang terakhir daripada menjadikan keseluruhan titik akhir tidak tersedia.
Penyingkiran dasar menggunakan set penolakan yang diedarkan secara berasingan dengan sasaran satu minit. Replika penyajian menapis ID yang ditolak selepas carian, dan kunci cache menyertakan versinya. Binaan asas seterusnya mengalih keluarnya secara kekal. Reka bentuk dua jam ini mengelakkan pembinaan semula artifak yang besar untuk penyingkiran kecemasan sambil mengekalkan penerbitan asas yang deterministik.
Langkah 8: Sahkan pemeringkatan, keselamatan dan operasi
Ujian beban memainkan semula taburan panjang awalan dan lokaliti yang diperhatikan pada 150,000 QPS puncak, termasuk awalan satu aksara hangat, pemulaan cache sejuk (cold-cache), kehilangan replika dan pengaktifan versi. Pastikan p99 di bawah 50 ms pada sempadan perkhidmatan, kadar ralat terikat, tiada checksum bercampur bagi setiap respons dan pemulihan tanpa thundering herd.
Penilaian luar talian meliputi perkaitan top-K, liputan, kadar duplikasi, ketepatan lokaliti, ingatan kandungan terlarang dan kestabilan antara versi. Eksperimen dalam talian menggunakan pelengkapan carian dan kualiti hasil hiliran dengan kawalan keselamatan untuk kadar tiada hasil, kependaman, aduan dan kepekatan pendedahan. Kadar klik yang lebih tinggi sahaja tidak mencukupi kerana kedudukan paparan mempengaruhi klik.
Latih tubi operasi termasuk kelompok peristiwa beracun, binaan yang gagal, artifak bersaiz besar, shard hangat, set penolakan lapuk, pelancaran replika separa dan regresi pemeringkat. Setiap amaran harus dipetakan kepada tindakan yang selamat: tahan pengaktifan, kembali ke versi baik terakhir, asingkan tindanan, belah julat atau aktifkan peraturan penolakan kecemasan.
Contoh Jawapan Berkualiti Tinggi
“Saya akan mulakan dengan pelengkapan awalan tanpa nama yang khusus untuk lokaliti dan sepuluh hasil. Daripada 50 juta pengguna, sepuluh carian dan lima permintaan bagi setiap carian, saya mendapat 2.5 bilion permintaan sehari, purata kira-kira 28,900 QPS. Saya akan merancang kapasiti untuk puncak 150,000 yang dinyatakan dan mengukur saiz indeks bersiri dan bukannya mengagak memori Trie.
Laluan data dan laluan penyajian adalah berasingan. Peristiwa carian selesai memasuki strim. Pengagregatan menghasilkan bilangan pengguna unik, kebaharuan dan isyarat kualiti hasil. Calon melepasi get kekerapan minimum, penyalahgunaan, privasi dan penyederhanaan sebelum pemeringkat menulis senarai teratas terikat bagi setiap awalan yang dinormalkan. Setiap artifak merekodkan tera air data, penormalan, pemeringkat dan versi dasarnya.
Replika penyajian memegang versi indeks tak boleh ubah. Mereka memuatkan dan mengesahkan versi baharu di samping versi lama, kemudian penghalaan bertukar secara atomik dan boleh diundurkan (rollback). Permintaan menormalkan awalan dan lokaliti, menyemak cache berversi, menghala ke shard awalan, melakukan satu carian, menggunakan set penolakan pantas dan mengembalikan sepuluh hasil. Julat satu aksara yang hangat mendapat cache khusus dan boleh dibahagikan secara bebas.
Pembinaan semula asas memenuhi sasaran 15 minit. Tindanan trend kecil yang dikawal boleh meningkatkan kebaharuan, manakala penyingkiran kecemasan menggunakan lapisan penolakan satu minit; mana-mana satu daripadanya boleh gagal tanpa merosakkan pangkalan baik yang terakhir. Saya akan menguji taburan awalan sebenar pada 150,000 QPS dan menjejaki p99, kesegaran, kadar hit cache, herotan shard, perkaitan, kebocoran lokaliti, ingatan keselamatan dan masa pengunduran.”
Kesilapan Biasa
- Membuat pertanyaan dan mengisih log mentah pada setiap ketukan kekunci → beban kerja meningkat mengikut sejarah dan menjadikan kependaman ekor tidak dapat diramalkan → kira lebih awal senarai top-K terikat dan pastikan carian dalam talian terikat secara malar.
- Memanggil struktur data itu sekadar “Trie” dan berhenti di situ → ini mengabaikan pemeringkatan, penerbitan, pemecahan (sharding), keselamatan dan pemulihan → huraikan kedua-dua kitaran hayat pembinaan dan penyajian serta tanda aras representasi data.
- Menganggar RAM daripada saiz nod rekaan → pengekodan dan perkongsian awalan menentukan bait sebenar → sirikan data representatif dan ukur saiz artifak serta kependaman carian.
- Mengecam (caching) hanya mengikut awalan → versi lokaliti, dasar dan indeks akan bocor atau mengekalkan hasil yang salah → masukkan setiap versi yang mempengaruhi hasil ke dalam kunci.
- Menerbitkan di tempat asal (in-place) → pembaca memerhati data separa atau bercampur → bina artifak tak boleh ubah, sahkan, muatkan bersebelahan dan aktifkan secara atomik.
- Menggunakan populariti sebagai satu-satunya peraturan kelayakan → teks peribadi yang jarang berlaku, dimanipulasi atau berbahaya boleh muncul → gunakan ambang pengguna unik, get antipenyalahgunaan, privasi dan penyederhanaan.
- Membina semula segala-galanya untuk penyingkiran kecemasan → tarikh akhir keselamatan bergantung pada tugas kelompok yang besar → edarkan lapisan penolakan pantas dan alih keluar secara kekal dalam binaan asas seterusnya.
- Menganggap kadar klik lalu sebagai perkaitan saksama → kedudukan yang dipaparkan mempengaruhi klik → gabungkan eksperimen terkawal dengan pertimbangan luar talian dan metrik keselamatan.
Soalan Susulan dan Maklum Balas
Soalan susulan 1: Bagaimanakah anda akan menambah padanan kabur (fuzzy matching)?
Kekalkan carian awalan tepat sebagai penjana pertama yang murah. Cetuskan penjanaan kabur hanya selepas panjang minimum atau apabila liputan tepat adalah rendah, hadkan jarak suntingan dan bilangan calon, serta gabungkan melalui satu pemeringkat dan dasar penyederhanaan. Tanda aras jarak peka Unicode dan input bermusuhan kerana pengembangan kabur meningkatkan CPU dan boleh mendapatkan semula varian yang sensitif terhadap dasar.
Soalan susulan 2: Bagaimanakah anda akan menambah pemperibadian?
Campurkan set calon peribadi kecil yang dibenarkan selepas mengambil calon global. Cache kekal global sehingga sempadan tersebut; respons akhir menjadi berskop pengguna dan tidak boleh memasuki cache kongsi. Tentukan persetujuan, pengekalan, pemadaman, pengecualian pertanyaan sensitif, tamat masa ciri dan sandaran global sahaja sebelum menambah ciri pemeringkatan.
Soalan susulan 3: Bagaimana jika satu lokaliti tidak lagi muat dalam memori?
Bahagikan julat awalannya menggunakan bait dan QPS yang diukur, kemudian kemas kini peta penghalaan berversi. Simpan awalan hangat peringkat teratas pada replika khusus dan benarkan julat sejuk menggunakan indeks yang dipetakan memori atau indeks jauh jika p99-nya masih memenuhi belanjawan. Imbang semula mengikut versi artifak supaya pembaca tidak bergantung pada penghijrahan kunci di tempat asal (in-place).
Soalan susulan 4: Bagaimanakah anda menyokong berita terkini dalam masa beberapa saat?
Jangan memendekkan keseluruhan binaan asas secara membuta tuli. Tambahkan tindanan penstriman yang dihadkan dengan ketat dengan sumber calon yang dipercayai, ambang kelayakan yang tinggi, penyederhanaan serta-merta, TTL dan suis pemati (kill switch). Gabungkannya dengan hasil asas di bawah belanjawan calon yang tetap. Jika kesegaran atau tera air dasarnya lapuk, buang tindanan dan sajikan asas baik yang terakhir.
Soalan susulan 5: Bagaimanakah anda memadamkan pertanyaan selepas permintaan privasi?
Alih keluar atau letakkan tombstone pada peristiwa mentah yang layak dan agregat mengikut model data, tambah ID cadangan pada lapisan penolakan pantas, batalkan entri cache yang terjejas melalui versi dasar dan bina semula artifak asas daripada input yang diperbetulkan. Audit masa penyebaran merentasi wilayah tanpa mencatat teks sensitif itu lagi.