Location-Based Services (Maps / Nearby)
Problem statement
Store billions of moving points (drivers, users), answer geo queries (nearby, geofence enter/exit), and serve routing / ETA with fresh traffic.
How it works
- Writes: append location updates to stream keyed by
object_id. - Reads: geohash / quadtree / R-tree structures; Redis GEO for “nearby in radius”.
- Routing: precomputed graph + live traffic overlay from probe data or partner feeds.
Analogy: Fish in an aquarium with a grid overlay: asking “fish within 1 foot of the castle” is a radius query on tracked positions.
High-level design
Rendering diagram…
Components explained — this design
| Component | What it is | Why we use it here |
|---|---|---|
| Ingestion API | Authenticates devices; accepts batched GPS points. | Validates device certs / tokens; rate limits malicious uploaders. |
| Kinesis / PubSub | Streaming ingest buffer. | Absorbs spiky mobile uploads; decouples write burst from index update speed. |
| Redis GEO / PostGIS | Spatial indexes for radius queries. | Redis GEO for massive concurrent “nearby” queries; PostGIS when you need polygons + SQL joins. |
| Nearby API | Composes results + ranking + safety filters. | Applies business rules (blocked users) not expressible purely in geo index. |
| Route service (OSRM/Valhalla) | Road-graph shortest path / ETA. | Separates heavy graph algorithms from lightweight geo radius lookup. |
| Traffic tiles CDN | Cached traffic speed overlays. | Reduces calls to paid map APIs; TTL matches freshness needs. |
Shared definitions: 00-glossary-common-services.md
Low-level design
Ingestion
- Batching on device (every N seconds or N meters moved) to save battery and cost.
- Amazon Location Service / Google Maps APIs vs self-host OSRM tradeoff: ops vs accuracy.
Storage patterns
| Pattern | Tool | Use |
|---|---|---|
| Radius nearby | Redis GEO | Real-time drivers |
| Complex polygons | PostGIS | Delivery zones |
| Global low-latency | DynamoDB + geohash PK | Check-ins |
Geofencing
- Stream processing (Flink / Kinesis Analytics) evaluates polygon contains on each update; emits GeofenceEntered events to SNS.
Privacy
- Snap-to-road optional; blur precision for social apps; TTL on location history.
E2E: “drivers within 2km”
Rendering diagram…
Tricky parts
| Problem | Solution |
|---|---|
| Boundary effects at poles / date line | Use proper CRS; tests around antimeridian |
| Skewed density (airports) | Adaptive grid or H3 hex indexing |
| Stale locations | TTL + confidence score in response |
Caveats
- Regulatory: India Map policy, China GCJ-02 offset — legal basemap provider required.
- Battery: geofencing OS APIs (iOS Region Monitoring) better than constant GPS upload.
H3 / S2
- Uber H3 or Google S2 for uniform hex bins — great for surge aggregation and heatmap tiles.