System Design · Interview Prep

Geospatial Service: dari Teori sampai Jawaban Interview

Geospasial bukan sekadar peta. Ini fondasi ride hailing dan food delivery. Di balik pertanyaan “apa yang ada di dekat titik X” ada masalah scaling berat. Di versi ini tiap sub-materi punya simulasi yang bisa kamu mainkan langsung.

1. Kenapa Ini Fondasi Semua Domain

Tanpa location service: tidak ada driver terdekat, ETA, ongkir berbasis jarak, surge pricing, atau geofence bandara. Hampir semua fitur inti bergantung padanya.

Dua karakter yang membuatnya unik:

• Read spasial. Bukan lookup by ID, tapi “semua driver dalam radius 2 km”. B-tree biasa tidak membantu karena data 2 dimensi tidak punya urutan linear alami.
• Write berat dan bergerak. Driver mengirim ping tiap 2-5 detik. Data ini terus di-overwrite, bukan write-once read-many. Cache dan indeks tradisional dirancang untuk kebalikannya.

Tips interview: jelaskan dua karakter ini sebelum menyebut H3 atau Geohash. Kalau langsung lompat ke nama teknologi, kamu terdengar hafalan.

2. Problem Statement dan Requirement

Functional: nearby search (N terdekat, urut jarak), location update tiap 2-5 detik, geofencing (titik dalam polygon), reverse geocoding (koordinat ke alamat).

Non-functional: p99 query < 50-100 ms; puluhan sampai ratusan ribu QPS; freshness (ping > 15 detik dianggap tidak tersedia); availability tinggi (service mati berarti tidak ada order); accuracy (jangan miss driver dekat hanya karena beda cell).

Dilema inti: data bergerak cepat tidak cocok di DB relasional yang dioptimasi untuk data statis, sementara data statis (merchant) butuh query kaya. Solusinya memisahkan keduanya, dan itu benang merah seluruh artikel ini.

3. Teori Dasar: Bumi Bukan Bidang Datar

Jarak. Untuk jarak pendek dalam kota, Euclidean setelah proyeksi cukup. Untuk akurasi, pakai Haversine (jarak di permukaan bola, R ≈ 6371 km). Cukup sebut namanya dan alasannya di interview.

Scan itu mustahil. Solusinya spatial index: kelompokkan titik berdekatan ke bucket, periksa hanya bucket sekitar user. Analogi: kode pos. Kamu tidak scan semua rumah di Indonesia, cukup cari prefix kodenya.

4. Spatial Indexing Mendalam

Geohash

Lat/lng di-encode jadi string; prefix sama berarti berdekatan. Panjang 5 ≈ 4.9 km, 6 ≈ 1.2 × 0.6 km, 7 ≈ 153 m. Mudah disimpan di Redis/KV, nearby jadi range scan prefix. Kelemahan: masalah batas cell. Dua titik berjarak 10 m bisa punya prefix berbeda total, jadi query wajib cek 8 tetangga. Bentuk cell juga terdistorsi menjauhi ekuator.

Quadtree

Bagi ruang jadi 4 kuadran, bagi lagi yang terlalu padat. Adaptif: kecil di Jakarta Pusat, besar di pinggiran. Tapi untuk driver bergerak, tree harus terus di-rebalance dan sulit didistribusikan ke banyak server. Bagus untuk data statis, jarang jadi pilihan utama untuk driver.

S2 (Google)

Permukaan bola diproyeksikan ke 6 sisi kubus, tiap sisi diurutkan dengan Hilbert Curve yang menjaga locality (titik dekat tetap dekat di urutan kurva). Cell hirarkis (1 cell jadi 4 anak) dan ukurannya relatif seragam. Kekuatan utamanya covering: polygon bandara diubah jadi daftar cell S2, lalu geofencing jadi lookup. Kekurangannya kurva belajar (level, cell id, covering). Pilih S2 kalau kasus utamamu geofencing dan region query.

H3 (Uber)

Grid hexagon hirarkis: 122 cell dasar, tiap hexagon pecah jadi 7 anak. Keunggulan: 6 tetangga berjarak sama dari pusat, sedangkan di grid kotak tetangga diagonal lebih jauh. Ini membuat k-ring (ambil tetangga sejauh K langkah) elegan: jumlah cell = 1 + 3K(K+1), yaitu 7, 19, 37, ... Smoothing untuk surge dan heatmap juga terlihat natural. Kekurangan: parent-child tidak nested sempurna, dan ada 12 pentagon (distorsi kecil) di level dasar.

R-tree dan PostGIS

Index klasik DB: objek dibungkus Minimum Bounding Rectangle, lalu dikelompokkan jadi tree. Query paling kaya (polygon, intersection, join spasial: “merchant dalam kecamatan ini”). Tapi tiap update lokasi mengubah tree, jadi mahal untuk write tinggi. Keputusan: merchant/POI/zona di PostGIS, driver bergerak jangan.

Redis GEO

Sorted set dengan geohash 52-bit. Cepat, cocok untuk MVP. Dua masalah di skala besar: satu key per kota jadi hot key, dan tidak ada TTL per member. Solusi: shard per cell (satu key per hexagon) dan simpan timestamp ping di sorted set terpisah untuk dibersihkan berkala. Catatan: GEORADIUS sudah deprecated sejak Redis 6.2, pakai GEOSEARCH.

GEOADD geo:h3:8828308281fffff 106.8456 -6.2088 driver:42
ZADD seen:h3:8828308281fffff 1767000000 driver:42      # score = ts ping
GEOSEARCH geo:h3:8828308281fffff FROMLONLAT 106.8456 -6.2088 BYRADIUS 3 km ASC COUNT 20
ZREMRANGEBYSCORE seen:h3:8828308281fffff -inf (now-15)  # buang yang stale

// Go (uber/h3-go v4)
cell, _ := h3.LatLngToCell(h3.LatLng{Lat: -6.2088, Lng: 106.8456}, 8)
cells, _ := h3.GridDisk(cell, 1) // pusat + 6 tetangga = 7 cell

5. Arsitektur: dari Ping sampai Hasil

Write path: driver ping (WebSocket/HTTP) → Ingestion Service validasi → Kafka → Location Indexer update index in-memory. Update bersifat kondisional: masih di cell sama berarti cukup update posisi (murah); pindah cell berarti hapus dari cell lama dan tambah ke cell baru (mahal). Histori ke Cassandra/BigQuery secara batch/async, bukan di critical path.

Read path (2 langkah): (1) lat/lng user jadi cell id (H3 res 8-9 atau Geohash 7), ambil cell + k-ring, mulai K=1 dan expand ke K=2 kalau kandidat < 20. Cepat tapi kasar. (2) Hitung Haversine hanya untuk ratusan kandidat, urutkan, buang yang stale atau sedang trip. Jangan pernah Haversine ke 500 ribu driver.

6. Keputusan Desain Kunci

• Shard by cell, bukan driver ID. By ID: query nearby harus fan-out ke semua shard. By cell: hanya 1-3 shard. Harga yang dibayar: hotspot (SCBD jam makan siang). Solusi: split cell adaptif, lalu sebar sub-cell dengan consistent hashing.
• Driver in-memory, merchant di disk. Bukan karena in-memory lebih keren, tapi karena karakter datanya beda.
• Jangan tulis tiap ping ke DB. Buffer, batch, atau update index hanya saat pindah cell.
• Staleness adalah fitur. TTL membuang ping lama. Lebih baik tampilkan driver sedikit stale daripada query lambat: trade-off availability vs consistency yang wajib kamu sebut.
• Reverse geocoding dan geofencing di-precompute. Reverse geocoding = lookup cell ke alamat. Geofencing: ray casting untuk polygon sederhana, S2 covering untuk skala besar.

7. Edge Case yang Sering Ditanyakan

Driver melintasi batas cell/shard. Tiga teknik: expand search (selalu cek tetangga), dual write singkat dengan TTL pendek saat pindah cell (tidak ada window driver “hilang”), dan overlap buffer di batas. Jawaban terbaik: kombinasi expand search + dual write dengan TTL. Coba di simulasi Geohash di atas: centang “cek tetangga” dan driver langsung ketemu.

Hotspot. Satu cell bisa berisi 10 ribu driver (bandara, stasiun jam pulang). Split adaptif ke resolusi lebih halus, dan sampling untuk query di cell super padat (tidak perlu scan semua).

Driver offline mendadak. Aplikasi mati tidak mengirim “saya offline”. Andalkan TTL, jangan tunggu sinyal eksplisit. Klik tombol “Matikan 6 driver” di simulasi dan lihat mereka memudar.

Tambahan: GPS jitter/loncatan (validasi kecepatan maksimal wajar, abaikan ping tidak masuk akal), ping out-of-order (tolak jika timestamp lebih lama dari yang tersimpan), dan failover shard (replika in-memory, rebuild dari Kafka dengan replay beberapa menit terakhir).

8. Studi Kasus: 500k Driver, 100k QPS

Write = 500.000 / 3 ≈ 166k write/s, jadi PostgreSQL dengan R-tree langsung jebol. Read: tiap query cek 7 cell dan hitung Haversine untuk ~100-200 kandidat. Data inti hanya ~50 byte × 500k ≈ 25 MB. Yang berat throughput, bukan storage. Ubah angka di bawah:

Desain: shard by H3 res 7/8 (res 8 ≈ 0.74 km², cocok untuk kota); in-memory index per shard; Query Service stateless di belakang load balancer (autoscale); Kafka sebagai buffer spike ping; fallback ke shard tetangga atau cache terakhir bila satu shard mati. Jawaban yang diharapkan bukan “pakai Redis GEO”, tapi “Redis GEO ter-shard per H3 cell, TTL 15 detik, expand k-ring”.

9. Cheat Sheet 1 Menit

1. Clarify: skala, radius, freshness, data statis atau bergerak.
2. High level: pisahkan data bergerak (in-memory per cell) dan statis (PostGIS).
3. Index: H3/S2 untuk skala besar, Geohash/Redis GEO untuk MVP; sebut boundary dan hotspot.
4. Flow: write tidak langsung ke DB; read 2 langkah (prune by cell, rank by Haversine).
5. Scale: hitung write rate, shard by cell, TTL, penanganan batas cell.

10. Latihan dan Jawaban