Design Google Maps

Prompt latihan

1. Problem Statement, Functional Requirements, and Scale Assumptions

   Tentukan ruang lingkup platform pemetaan dan navigasi: pengguna melihat peta (tile yang merender jalan, landmark, medan), mencari tempat (alamat, POI) dan mendapat petunjuk arah (routing turn-by-turn antara dua titik), serta menerima update lalu lintas real-time yang memengaruhi ETA rute. Kecualikan secara eksplisit: pembuatan tile peta (ingestion citra satelit, kartografi), routing transit (jadwal bus/kereta bawah tanah), peta offline, manajemen listing bisnis, Street View, dan Indoor Maps. Nyatakan asumsi skala: total request tile peta per detik, total pencarian tempat per hari, sesi navigasi turn-by-turn aktif saat puncak, dan unggahan GPS probe per detik dari perangkat.

2. Non-Functional Requirements

   Tentukan NFR utama: latensi tile peta (tile harus dirender dalam 100ms pada persentil ke-99, strategi caching apa yang memungkinkan ini pada skala global?), latensi komputasi rute (petunjuk turn-by-turn harus dikembalikan dalam 1–2 detik, algoritma routing mana yang memungkinkan ini pada graph dengan 100 juta+ node jalan?), frekuensi update ETA (seberapa sering pengguna yang bernavigasi harus menerima ETA yang direvisi akibat perubahan lalu lintas, setiap 30 detik? hanya saat perubahan signifikan?), dan throughput tulis GPS probe (jutaan perangkat mengunggah lokasi setiap 5 detik, strategi tulis apa yang menghindari kelebihan beban sistem?).

3. Quantitative Analysis

   Estimasikan QPS tile peta puncak (DAU × tile per tampilan peta × render-ulang per sesi × pengali puncak), total storage tile peta (level zoom 0–20, di mana setiap level melipatempatkan jumlah tile), laju tulis GPS probe (1 miliar perangkat × unggah setiap 5s = 200 juta tulis/detik, bagaimana ini ditangani?), QPS komputasi rute, dan cache hit rate CDN. Identifikasi penyajian tile sebagai operasi dominan dengan selisih beberapa orde besaran di atas routing, membenarkan arsitektur penyajian tile yang terpisah dari backend routing/navigasi.

4. API Design

   Tentukan operasi API untuk: mengambil tile peta berdasarkan koordinat zoom/x/y (GET /tiles/{z}/{x}/{y}.png, skema URL slippy map tile standar), mencari tempat berdasarkan query teks dan bounding box, menghitung petunjuk arah antara dua titik lat/lon dengan waktu keberangkatan opsional, mengambil update ETA real-time untuk sesi navigasi aktif, dan mengunggah GPS probe (unggah batch lokasi perangkat). Bahas bagaimana skema URL tile memungkinkan edge caching CDN, dan bagaimana response rute mengkodekan instruksi turn-by-turn dan geometri polyline.

5. High-Level Design

   Usulkan komponen utama: tile serving CDN (penyajian tile statis via CDN global, tanpa mengenai origin untuk tile ter-cache), tile origin (menghasilkan dan menyimpan tile peta pra-render di object storage), routing service (menghitung petunjuk shortest-path menggunakan graph jalan), traffic service (mengagregasi data GPS probe menjadi estimasi kecepatan link, memberi makan graph routing dengan bobot real-time), place search service (mengindeks POI dengan pencarian geospasial + teks), dan pipeline ingestion GPS probe (menangani unggahan perangkat throughput-tinggi). Jelaskan pemisahan statis vs. dinamis: tile bersifat statis dan di-cache CDN; rute dan ETA bersifat dinamis dan dihitung saat request.

6. Additional High-Level Design Prompts

   Bahas tiga area lanjutan: (1) Komputasi ulang rute selama navigasi, ketika pengemudi keluar dari rute atau kondisi lalu lintas berubah signifikan di tengah perjalanan, bagaimana dan kapan rute dihitung ulang? Siapa yang memulainya: klien atau server? Berapa anggaran latensi untuk re-route? (2) Pipeline pembuatan tile peta, tile dihasilkan sebelumnya pada level zoom 0–15 dari data geografis (OSM, citra satelit, jaringan jalan); pada level zoom tinggi (16–20) tile mungkin dihasilkan secara dinamis atau di-cache saat request pertama; jelaskan pipeline pembuatan tile offline; (3) Menangani noise GPS dalam data probe, GPS perangkat mentah memiliki akurasi ±15m dan jitter; bagaimana data probe di-map-match ke jaringan jalan (algoritma map-matching menempelkan lat/lon mentah ke segmen jalan terdekat) sebelum diagregasi menjadi kecepatan link?

7. Deep Dives

   Deep dive ke tiga area: (1) Algoritma routing pada skala besar, Dijkstra bekerja untuk graph kecil; untuk 100 juta+ node jalan, gunakan A* dengan heuristik (jarak Euclidean ke tujuan); untuk routing skala-benua, Contraction Hierarchies memproses graph terlebih dahulu dengan menambahkan edge 'shortcut' yang melewati node tidak penting, mengurangi waktu query dari O(V log V) menjadi milidetik; bidirectional Dijkstra (pencarian dari source dan destination secara bersamaan) memangkas ruang pencarian setengahnya; trade-off: Contraction Hierarchies memerlukan pra-pemrosesan offline berat saat jaringan jalan berubah; (2) Pipeline data lalu lintas, GPS probe dari 1 miliar perangkat mengunggah setiap 5s; pipeline: perangkat mem-batch 10 pembacaan dan mengunggah setiap 50s; Kafka meng-ingest stream probe; job stream processing (Flink/Spark Streaming) mengagregasi kecepatan per segmen jalan per window 1-menit; segmen jalan dipetakan ke edge graph; bobot edge diperbarui di graph routing; berapa lama sebelum kondisi lalu lintas baru tercermin di ETA: biasanya 1–3 menit; (3) Strategi caching tile, level zoom 0 (seluruh dunia, 1 tile) hingga level zoom 15 (jalan kota, ~1 miliar tile); tile di bawah zoom 13 bersifat statis dan di-cache CDN tanpa batas (jaringan jalan jarang berubah); tile pada zoom 14+ diperbarui saat jaringan jalan berubah; propagasi perubahan: saat jalan dibuka, tile yang terpengaruh pada semua level zoom di atas 13 diinvalidasi dan dihasilkan ulang.

8. Final Review Handoff Readiness

   Ringkas keputusan desain utama: penyajian tile CDN-first (tile disajikan dari edge, origin hanya saat miss), algoritma routing (Contraction Hierarchies untuk komputasi rute sub-detik), pipeline batching GPS probe (Kafka + stream processing, latensi lalu lintas 1–3 menit), invalidasi cache tile per level zoom, dan map-matching untuk kualitas probe. Soroti dua pertanyaan terbuka terbesar yang tersisa (frekuensi pemrosesan ulang Contraction Hierarchy, seberapa sering graph jalan dapat diperbarui sebelum overhead pra-pemrosesan menjadi terlalu tinggi, dan SLA kesegaran ETA, berapa lag yang dapat diterima antara penutupan jalan dan pengaruhnya terhadap ETA yang ditampilkan?) dan usulkan rollout bertahap: penyajian tile + pencarian dulu, lalu routing statis, lalu integrasi lalu lintas real-time.

Preview solusi

Solusi Referensi, Merancang Google Maps Core Insight Google Maps memiliki tiga subsistem yang secara fundamental berbeda yang sebaiknya dirancang secara independen: tile serving (statis, didominasi CDN), routing (CPU-intensive, jarang di-cache), dan real-time traffic (write throughput tinggi, stream processing). Menggabungkan ketiganya dalam satu desain serv…