Wawancara System Design: Mendesain Proximity Service untuk Tempat Terdekat

Masalah dan Ruang Lingkup

Rancang layanan pencarian tempat terdekat berskala global. Katalog berisi 50 juta restoran, toko, dan fasilitas umum. Pengguna memberikan posisi saat ini, radius dari 500 meter hingga 50 kilometer, kategori, dan filter jam buka, kemudian menerima 20 hasil terdekat. Lalu lintas pencarian mencapai puncak 200.000 permintaan per detik. Pembuatan, pemindahan, dan penutupan tempat mencapai puncak 100 pembaruan per detik. Latensi baca harus tetap di bawah 150 milidetik pada p99.

Masalah ini memperlakukan tempat sebagai entitas statis yang jarang berubah. Lokasi pengemudi, kurir, atau teman yang diperbarui detik demi detik, pencocokan (matching), dan penugasan eksklusif merupakan bagian dari sistem lokasi dinamis yang berbeda. Jarak berarti jarak geografis di atas permukaan bumi. Waktu rute, personalisasi, dan lelang iklan berada di luar cakupan inti. Semua angka dan SLO merupakan asumsi wawancara.

Masalah utamanya adalah kueri radius dua dimensi. B-tree normal pada garis lintang (latitude) dan garis bujur (longitude) tidak dapat langsung melompat ke setiap baris di dalam lingkaran kueri. Pola yang direkomendasikan pertama-tama menggunakan indeks spasial atau grid diskrit untuk membuat superset kandidat, kemudian menghitung jarak eksak, memfilter, mengurutkan, dan memotong (truncate). Kecocokan sel hanyalah filter kasar; berada di sel yang sama atau sel tetangga tidak membuktikan bahwa suatu tempat berada di dalam radius.

Apa yang Dievaluasi Pewawancara

Sinyal pertama adalah mendefinisikan kebenaran (correctness) sebelum komponen. Setiap hasil harus berada di dalam radius, lolos filter, dan muncul dalam urutan deterministik terdekat lebih dahulu. Candidate set harus mencakup tempat-tempat di seberang batas sel, dan jarak eksak harus memverifikasi hasil kasar tersebut. Melakukan kueri hanya pada geohash pengguna akan melewatkan bisnis yang berjarak puluhan meter di seberang batas sel yang arbitrer.

Sinyal kedua adalah memilih indeks berdasarkan pola pembaruan. Bisnis statis dapat dimulai dengan PostGIS GiST, R-tree, atau indeks jarak bawaan database. Ketika lalu lintas baca dan perutean global memerlukannya, tempat dapat dipetakan ke dalam sel H3, S2, atau geohash. Sekadar mengatakan “gunakan Redis GEO” tidak menjelaskan cakupan lingkaran, resolusi, hot spot, atau jarak eksak.

Sinyal ketiga adalah mengenali ketimpangan spasial (spatial skew). Lautan dan sel pedesaan hampir kosong, sementara satu sel di pusat kota bisa sangat padat (hot). Rentang lintang-bujur yang seragam tidak menghasilkan shard yang seragam. Desain yang baik merutekan berdasarkan prefiks spasial kasar, membagi sel yang padat, dan menambahkan replika untuk sel yang sering dibaca. Kueri radius besar melintasi banyak shard, sehingga satu pencarian tidak selalu dapat diasumsikan hanya mengenai satu node.

Terakhir, paginasi, konsistensi, dan kegagalan harus selaras. Untuk paginasi jarak, koordinat pengguna, filter, versi katalog, jarak terakhir, dan ID tempat adalah bagian dari kontrak kursor. Pembaruan atau shard timeout dapat mengubah set hasil. Jawaban yang kuat menyatakan semantik snapshot atau best-effort dan membuat hasil parsial dapat dikenali.

Pertanyaan untuk Diklarifikasi Sebelum Menjawab

• Apakah lokasi bersifat statis atau terus bergerak? Puncak 100 pembaruan per detik mendukung caching dan pengindeksan asinkron. Entitas yang bergerak membutuhkan kesegaran data yang lebih ketat, indeks yang dioptimalkan untuk penulisan, dan konsistensi pencocokan.
• Apakah "terdekat" berarti jarak geografis atau waktu tempuh? Desain ini menggunakan jarak geografis. Waktu tempuh membutuhkan graf jalan dan layanan ETA terpisah, yang biasanya diterapkan pada candidate set kasar yang kecil.
• Haruskah hasilnya lengkap, atau 20 kandidat perkiraan dapat diterima? Masalah ini memerlukan pemfilteran radius yang benar dan 20 terdekat yang deterministik di antara tempat-tempat yang terindeks. Sel hanya boleh menghasilkan kandidat.
• Seberapa segar status buka harus diperbarui? Lokasi dan kategori dapat mentoleransi propagasi dalam skala menit. Jika penutupan sementara membutuhkan pembaruan dalam hitungan detik, simpan dalam overlay terpisah dengan TTL pendek daripada memberikan satu janji campuran pada katalog statis.
• Apakah deep pagination diperlukan? Pencarian terdekat biasanya hanya membutuhkan beberapa halaman. Desain ini membatasi sesi hasil pada 100 tempat. Mengekspor setiap hasil dalam jarak 50 kilometer membutuhkan API asinkron atau penjelajahan regional.
• Bolehkah kegagalan lintas-shard mengembalikan data parsial? API eksplorasi dapat mengembalikan partial=true dengan wilayah yang hilang. Pemanggil yang ketat dapat gagal dan mencoba lagi. Data parsial tidak boleh disajikan sebagai set terdekat yang lengkap.

Jawaban 30 Detik

“Saya akan memisahkan jalur penulisan katalog dari jalur pencarian. Catatan tempat berversi masuk ke katalog source-of-truth dan memperbarui indeks spasial secara asinkron. Setiap tempat menyimpan koordinat eksak, sel perutean kasar, dan sel resolusi pencarian. Kueri memvalidasi radius dan filternya, lalu menggunakan cakupan H3, S2, geohash atau indeks jarak PostGIS untuk memperoleh superset kandidat. Layanan ini menghitung jarak sferis eksak, memfilter, dan mengurutkan berdasarkan (distance, place_id) sebelum mengambil 20 data.

Prefiks kasar merutekan ke shard. Sel padat dapat dipecah, dan kueri lintas-sel mengunjungi sejumlah shard terbatas secara paralel sebelum penggabungan top-k global. Kunci cache mencakup sel, bucket radius, filter, dan versi katalog; pemindahan berversi membatalkan sel lama dan baru. Kursor mengikat kueri asli dan snapshot katalog. Saya akan memverifikasi batas sel, garis penanggalan, kutub, kota padat, relokasi, shard timeout, dan cache basi sambil mengukur kebenaran dan p99.”

Pembahasan Mendalam Langkah demi Langkah

Langkah 1: Tetapkan API, model, dan invarian

API menerima radius terbatas, koordinat valid, filter yang disetujui, dan ukuran halaman kecil. Respons mencakup jarak yang dihitung, versi katalog, kelengkapan, dan kursor kelanjutan.

GET /v1/places/nearby?lat=&lng=&radius_m=&category=&open_at=&limit=&cursor=

Place {
  place_id, lat, lng, search_cell, routing_cell,
  category, status, hours_version, location_version, updated_at
}

Cursor {
  query_hash, catalog_version, last_distance_m, last_place_id
}

Pertahankan empat invarian: setiap hasil memenuhi radius dan filter; pembuatan kandidat tidak boleh menghilangkan titik di dalam lingkaran; urutan akhir adalah (distance_m, place_id); dan versi lokasi lama tidak dapat menimpa versi baru. Koordinat menggunakan satu sistem referensi yang dinyatakan, menolak rentang yang tidak valid, dan menggunakan meter secara internal.

Langkah 2: Pilih indeks spasial paling sederhana yang memenuhi target

Versi pertama dapat menggunakan database relasional dengan indeks spasial. Kueri radius menggunakan bentuk batas (bounding shape) yang dapat diindeks untuk memperkecil set data, lalu menggunakan fungsi jarak eksak untuk memfilternya. Dokumentasi resmi earthdistance secara eksplisit menyatakan bahwa kotak yang dapat diindeks berisi beberapa titik di luar jarak great-circle yang diminta, sehingga pemeriksaan jarak kedua diperlukan. Aturan superset-kandidat ini independen dari vendor mana pun.

Ketika satu topologi database tidak dapat menangani lalu lintas baca global atau perutean spasial eksplisit diperlukan, enkoder setiap tempat ke dalam sel H3, S2, atau geohash dengan resolusi tetap. Ubah lingkaran kueri menjadi sekumpulan sel penutup, baca inverted list dari setiap sel, lakukan deduplikasi, dan lakukan pemurnian. Hierarki H3 mengubah resolusi secara efisien, tetapi penahanan geografis di seluruh sel induk dan anak memiliki masalah perkiraan. Verifikasi titik-ke-titik eksak tetap menentukan penyertaan.

Satu resolusi tetap menciptakan masalah yang berlawanan: sel besar memperbanyak kandidat, sementara sel kecil membuat kueri 50 kilometer menghitung terlalu banyak sel. Pilih dari sekumpulan kecil resolusi yang telah ditentukan sebelumnya berdasarkan radius dan lakukan prakomputasi tingkat tersebut untuk setiap tempat, atau rutekan radius besar melalui indeks yang lebih kasar. Amplifikasi kandidat, fanout, dan uji beban p99 digunakan untuk memilih tingkatan tersebut.

Langkah 3: Eksekusi pencarian kandidat dan top-k global

Layanan kueri mengubah lingkaran menjadi sel kandidat, mencakup setiap sel yang berpotongan dan bukan hanya bagian tengahnya. Layanan ini membaca ID tempat dan koordinat yang telah difilter kasar dari setiap sel secara paralel di bawah batas waktu keseluruhan dan anggaran per-shard. Layanan ini menduplikasi berdasarkan place_id, menghitung jarak geografis eksak, menghapus titik di luar lingkaran, dan menerapkan filter otorisasi, status, dan kategori.

Setiap shard dapat mengembalikan top k lokalnya, tetapi pemotongan (truncation) memerlukan pembuktian. Jika setiap shard mengurutkan berdasarkan jarak akhir yang sama dan mengembalikan setidaknya k global, item k+1 dari suatu shard tidak dapat masuk ke dalam top k global. Agregator menggabungkan dengan max heap berukuran k. Beban kerja bersifat linier terhadap kandidat yang dikembalikan, dengan memori penggabungan O(k).

Radius yang besar atau pusat kota yang padat dapat menghasilkan terlalu banyak kandidat. Layanan menetapkan anggaran kandidat tetapi tidak boleh memotong secara diam-diam dan mengklaim keakuratan. Layanan dapat memilih grid yang lebih halus, mendorong pemfilteran kategori ke bawah (push-down), memperluas dalam bentuk cincin hingga 20 hasil ditemukan dan jarak minimum yang mungkin dari setiap wilayah yang belum dicari melebihi hasil ke-20 saat ini, atau mengembalikan error batas sumber daya secara eksplisit.

Langkah 4: Rencanakan sharding, hot spot, dan kapasitas

Petakan direktori sel ke shard dengan routing_cell kasar, alih-alih melakukan sharding acak berdasarkan place_id, yang akan mem-broadcast setiap kueri spasial. Layanan direktori memelihara tabel perutean dan epoch. Kueri menggunakan satu epoch dan mencoba lagi jika terjadi perubahan perutean sehingga pemecahan sel tidak menciptakan celah data.

Jika satu catatan indeks pencarian termasuk ID, koordinat, bidang filter, dan overhead diperkirakan berukuran 128 hingga 256 byte, 50 juta catatan membutuhkan sekitar 6 hingga 12 GiB sebelum replikasi, beberapa resolusi, dan overhead database. Besaran ini dapat dipartisi dan dilayani oleh node yang dioptimalkan untuk pembacaan, tetapi ini tidak membuktikan bahwa database tertentu pasti akan memenuhi target.

Pada 200.000 QPS dan rata-rata ilustratif fanout enam pembacaan sel, backend menangani sekitar 1,2 juta pembacaan sel per detik. Caching dan batch read harus mengurangi operasi. Tambahkan replika berdasarkan beban baca dan pecah sel padat menjadi sel anak. Menggabungkan sel yang jarang penduduknya hanya mengubah penyimpanan dan perutean; cakupan geometris tetap mengontrol kebenaran.

Langkah 5: Buat penulisan, cache, dan konsistensi konvergen

Setelah validasi kepemilikan, layanan tempat memperbarui catatan sumber dan menaikkan location_version. Peristiwa perubahan (change event) berisi sel lama, sel baru, dan versi. Konsumen indeks menulis versi baru ke dalam sel baru sebelum menghapus sel lama. Operasi baca melakukan deduplikasi berdasarkan versi, membuat pemutaran ulang (replay) aman dan mencegah penghapusan yang tertunda memenangkan data basi. Perpindahan lintas-shard mengekspos jeda indeks terbatas dan menyatu berdasarkan versi alih-alih memerlukan transaksi terdistribusi seketika.

Gunakan dua lapisan cache: ID sel-ke-kandidat dan objek tempat lengkap. Kunci kandidat mencakup versi indeks, sel, kategori, dan bucket status. Cache respons akhir juga harus menyertakan bucket koordinat, bucket radius, filter, dan versi katalog, sehingga biasanya memiliki hit rate lebih rendah. Pembaruan membatalkan sel lama dan baru, sementara TTL pendek membatasi peristiwa pembatalan yang hilang.

Jika open_at berubah setiap menit, jangan membersihkan seluruh cache spasial setiap menit. Cache kandidat statis dan aturan buka, lalu evaluasi aturan pada saat kueri dijalankan. Penutupan sementara berada dalam overlay segar yang kecil. Dengan demikian, perubahan status buka tidak perlu membangun ulang indeks geografis.

Langkah 6: Tentukan semantik paginasi dan kegagalan

Kursor melakukan hash pada koordinat, radius, filter, dan catalog_version, lalu menyimpan (distance_m, place_id) terakhir. Panggilan halaman berikutnya menolak parameter kueri yang berbeda. Jika snapshot berumur pendek didukung, panggilan tersebut membaca versi katalog yang sama. Sebaliknya, API best-effort mendokumentasikan bahwa pembaruan bersamaan dapat membuat duplikasi atau kelalaian dan membiarkan klien melakukan deduplikasi ID.

Setiap shard menerima batas waktu yang lebih pendek dari target end-to-end 150 milidetik. Setelah satu shard mengalami batas waktu (timeout), respons tidak dapat disebut sebagai 20 terdekat global karena shard yang hilang mungkin berisi tempat yang lebih dekat. API eksplorasi dapat mengembalikan partial=true, sel yang hilang, dan kursor percobaan ulang. Klien yang ketat menerima hasil tidak tersedia yang jelas. Circuit breaking mengisolasi shard yang gagal, bukan seluruh indeks global.

Penerapan regional harus memprioritaskan replika baca lokal lengkap atau partisi geografis. Kebijakan lintas batas mengatur metadata tempat dan audit, bahkan koordinat bisnis publik memerlukan sumber yang sah. Failover hanya boleh menggunakan wilayah dengan indeks yang cukup segar dan harus mengembalikan as_of; failover tidak boleh beralih ke pemindaian tabel katalog penuh selama insiden berlangsung.

Langkah 7: Verifikasi dengan counterexample geometris dan kegagalan

Untuk data uji kecil, gunakan jarak eksak brute-force sebagai oracle. Hasilkan titik dan lingkaran acak lalu bandingkan set hasilnya. Targetkan tepi dan sudut sel, garis bujur positif dan negatif 180 derajat, wilayah kutub, titik tepat pada radius, koordinat duplikat, hasil nol, posisi seri 20 dan 21, serta relokasi lintas sel. Pastikan tidak ada false negative, tidak ada titik di luar radius, dan pemecahan seri (tie-breaking) yang stabil.

Uji beban secara terpisah mencakup wilayah kosong, kota normal, dan titik padat yang ekstrem. Ukur fanout sel, amplifikasi kandidat, komputasi jarak eksak, rasio hit cache, p95/p99 shard, waktu penggabungan, dan p99 end-to-end. Skenario kegagalan mencakup replika sel yang lambat, perubahan routing-epoch, pembatalan yang hilang, replay konsumen, perpindahan lintas-shard yang terinterupsi, dan failover regional.

Luncurkan dengan shadow query. Kirim sampel lalu lintas kecil ke indeks baru dan implementasi lama yang tepercaya, lalu bandingkan set 20 teratas, urutan, jarak, dan tingkat kehilangan data. Peningkatan latensi tidak dapat menjadi alasan atas terjadinya false negative; melewatkan tempat terdekat yang benar adalah kegagalan kebenaran indeks.

Contoh Jawaban yang Kuat

“Pertama-tama saya membatasi ruang lingkup ini pada pengambilan tempat statis, bukan pencocokan pengemudi yang bergerak. Katalog tempat menyimpan koordinat eksak dan versi lokasi monotonik, lalu memancarkan peristiwa ke indeks spasial. Pembacaan tidak mengurutkan seluruh tabel dengan ekspresi lintang-bujur. Pembacaan mengubah lingkaran menjadi sel-sel yang menutupinya secara penuh. Saya dapat memulai dengan indeks spasial PostGIS dan memperkenalkan H3, S2, atau geohash ketika lalu lintas global membutuhkan perutean spasial eksplisit. Sel hanya memfilter secara kasar; jarak geografis eksak menentukan inklusi, diikuti oleh pengurutan stabil pada jarak dan ID tempat.

Sel kasar merutekan ke shard. Sel padat dipecah dan sel yang sering dibaca mendapatkan replika. Kueri membaca shard terbatas secara paralel, masing-masing mengembalikan top-k lokal, dan agregator menghasilkan top-k global. Kandidat berlebih memicu pemfilteran yang lebih selektif atau ekspansi cincin, bukan pemotongan diam-diam. Kandidat sel dan objek tempat di-cache dengan versi indeks. Pemindahan membatalkan kedua sel, dan versi lokasi membuat replay konvergen.

Kursor mengikat koordinat, radius, filter, versi katalog, dan jarak/ID tempat terakhir. Shard timeout berarti hasil terdekat global tidak dapat dibuktikan, sehingga API eksplorasi menandai respons parsial dan menyebutkan sel yang hilang sementara API yang ketat mengembalikan kegagalan. Untuk verifikasi, jarak brute-force adalah oracle-nya. Perbandingan acak dan kasus uji terarah pada tepi sel, garis penanggalan, kutub, seri, pemindahan, dan perubahan perutean membuktikan kebenaran sebelum uji beban kota padat dan uji kegagalan membuktikan p99 150 milidetik.”

Kesalahan Umum

• Hanya mengueri geohash pusat → lingkaran yang melintasi tepi sel akan kehilangan tetangga dekat → baca setiap sel yang berpotongan dan verifikasi jarak eksak.
• Memperlakukan sel tetangga sebagai bagian dalam radius → sudut sel yang jauh mungkin melebihi radius → gunakan grid untuk kandidat dan jarak sferis untuk inklusi.
• Melakukan sharding secara acak berdasarkan ID tempat → setiap kueri terdekat di-broadcast secara global → rutekan berdasarkan prefiks spasial kasar, lalu pecah atau replikasi sel yang padat.
• Menggunakan satu resolusi paling halus → presisi radius kecil menghasilkan ledakan fanout pada radius besar → gunakan beberapa tingkat terkontrol yang dipilih dari pengukuran.
• Melakukan caching berdasarkan koordinat saja → radius, kategori, atau versi katalog saling mengontaminasi → sertakan kontrak kueri lengkap dan versi dalam kunci cache.
• Menghapus sebelum menambahkan saat pemindahan → kegagalan konsumen menghapus tempat untuk sementara waktu → tulis versi baru terlebih dahulu, hapus sel lama kemudian, dan lakukan deduplikasi berdasarkan versi.
• Menyebut respons sebagai “20 terdekat” setelah shard timeout → shard yang hilang mungkin berisi hasil yang lebih dekat → tandai data parsial atau gagalkan permintaan yang ketat.
• Hanya menguji data pusat kota yang padat → bug batas wilayah, kutub, dan wilayah renggang tetap tersembunyi → gunakan brute-force oracle, property test, dan counterexample geometris yang terarah.

Pertanyaan dan Jawaban Lanjutan

Lanjutan 1: Mengapa tidak menggunakan PostGIS untuk seluruh sistem?

Ini adalah pilihan awal yang baik. Database spasial sudah menyediakan kandidat indeks dan fungsi jarak yang benar, sehingga tim dapat merilis sistem yang andal dengan lebih sedikit komponen. Perkenalkan discrete grid dan tier pencarian terpisah hanya setelah pengukuran lalu lintas, perutean global, isolasi hotspot, atau biaya menunjukkan bahwa topologi database tidak memenuhi target. Migrasi bayangan (shadow migration) harus membandingkan set hasil yang lengkap, bukan hanya latensi.

Lanjutan 2: Bagaimana Anda membuktikan penutup sel tidak akan melewatkan tempat di dalam lingkaran?

Gunakan operasi penutup lingkaran atau poligon dari pustaka daripada menebak jumlah tetangga. Penutup tersebut mungkin menyertakan sel ekstra, tetapi harus menyertakan setiap sel yang berpotongan dengan lingkaran. Jarak eksak akan menghapus false positive setelahnya. Bandingkan dengan full-scan oracle pada lingkaran acak, sudut sel, garis penanggalan, dan area kutub. Adanya false negative akan memblokir perilisan.

Lanjutan 3: Bagaimana jika kueri 50 kilometer mencakup ribuan sel halus?

Beralihlah ke tingkat yang lebih kasar yang telah dihitung sebelumnya agar jumlah sel tetap terbatas, lalu andalkan filter yang didorong ke bawah dan pemurnian eksak. Ekspansi cincin dapat berhenti setelah 20 hasil ditemukan dan jarak minimum yang mungkin dari setiap wilayah yang belum dikunjungi melebihi hasil ke-20 saat ini. Jika permintaan radius besar masih melebihi anggaran sumber dayanya, tolak permintaan tersebut atau jadikan asinkron daripada mencari lebih sedikit data secara diam-diam.

Lanjutan 4: Bagaimana sistem ini diubah menjadi pencocokan pengemudi terdekat?

Masalahnya berubah secara mendasar. Lokasi pengemudi membutuhkan penulisan dan kedaluwarsa dalam hitungan detik, indeks yang dipartisi berdasarkan kota atau sel, serta perlindungan terhadap pembaruan yang tidak berurutan dan pengemudi hantu (ghost drivers). Setelah pengambilan kandidat, pemeringkatan membutuhkan ETA, status, dan keadilan. Penugasan akhir membutuhkan pembaruan kondisional berversi atau pemilik tunggal untuk mencegah dispatch ganda; indeks spasial yang eventually consistent tidak dapat memesan pengemudi.

Lanjutan 5: Akankah status buka menit demi menit menciptakan badai pembatalan cache?

Pisahkan kandidat spasial statis dari status dinamis. Cache sel menyimpan ID, lokasi, dan kategori. Node kueri mengevaluasi aturan buka untuk open_at, sementara penutupan sementara berasal dari overlay segar yang kecil. Hanya perubahan lokasi atau kategori yang membatalkan cache kandidat spasial. Pantau kesegaran overlay dan kembalikan status tidak diketahui atau degradasi yang disetujui bisnis saat overlay tidak tersedia.