Design a Location-Based Service

Problem Statement

Design a location-based service (like Google Places or Yelp Nearby) that indexes millions of points of interest (POIs), supports fast proximity search ("restaurants within 2 km"), handles real-time location updates from moving entities (drivers, delivery riders), and supports geofencing (trigger actions when a user enters/exits a zone).

Requirements

Functional

• Index 200M+ POIs with latitude, longitude, category, and attributes
• Proximity search: find the K nearest POIs within a radius, filtered by category
• Real-time location tracking: ingest location updates from 5M moving entities every 5 seconds
• Geofencing: define zones and trigger webhooks when tracked entities enter/exit

Non-Functional

• Latency: Proximity search <100ms for static POIs, <200ms including moving entities
• Freshness: Moving entity locations reflected in queries within 5 seconds
• Scale: 200M POIs, 5M active moving entities, 100K proximity queries/second
• Accuracy: Results accurate to within 10 meters

Core Architecture

1. GeoHash Index (Static POIs) -- POIs are indexed using GeoHash strings (base32-encoded, precision level 6 = ~1.2 km cells). Stored in Redis as sorted sets keyed by GeoHash prefix. A proximity query converts the center point to a GeoHash, identifies the 9 neighboring cells (to handle edge cases), and queries all 9 cells. Results are filtered by exact distance and sorted by proximity.

2. QuadTree (Moving Entities) -- A distributed in-memory QuadTree partitions the world into adaptive cells. Dense areas (cities) have smaller cells; sparse areas (oceans) have larger cells. Each leaf node holds up to 500 entities. Location updates re-insert the entity into the correct leaf. The QuadTree is sharded by geographic region across multiple nodes.

3. Geofence Evaluation Engine -- Stores geofence polygons in PostgreSQL with PostGIS. When a location update arrives for a tracked entity, the engine checks if the new position is inside any active geofence using PostGIS ST_Contains. To avoid checking every geofence, a spatial index (R-tree) narrows candidates to geofences overlapping the entity's GeoHash cell.

4. Location Ingestion Pipeline -- Receives location updates via a lightweight UDP/MQTT endpoint (lower overhead than HTTP for high-frequency updates). Writes to Kafka, consumed by: (a) the QuadTree updater, (b) the geofence evaluator, and (c) a Cassandra store for location history.

Database Choice

Redis with GEO commands for static POI proximity queries -- GEORADIUS returns results in <1ms for up to 10K nearby POIs. In-memory QuadTree for moving entities -- the entire QuadTree for a city fits in ~2 GB of RAM. PostgreSQL + PostGIS for geofence polygon storage and evaluation. Cassandra for location history (write-heavy: 5M updates every 5 seconds = 1M writes/second, partitioned by entity_id).

Key API Endpoints

GET /api/v1/nearby?lat=37.77&lng=-122.42&radius_m=2000&category=restaurant&limit=20
  -> Returns: \{ pois: [\{ id, name, lat, lng, distance_m, rating, category \}] \}

POST /api/v1/locations/update
  -> Body: \{ entity_id: "D-123", lat: 37.7750, lng: -122.4195, timestamp: ... \}

POST /api/v1/geofences
  -> Body: \{ name: "Downtown Zone", polygon: [[lat, lng], ...], webhook_url: "https://...", events: ["enter", "exit"] \}

Scaling Insight

GeoHash-based sharding solves the data distribution problem elegantly. Assign each Redis node a range of GeoHash prefixes (e.g., node 1 handles prefixes "9q8y*", node 2 handles "9q8z*"). Since GeoHash preserves spatial locality (nearby locations share prefixes), a proximity query typically hits only 1-2 nodes (the target cell and its neighbors). This is far more efficient than random sharding, which would require querying every node for every proximity search.

Key Tradeoffs

Original DosiBridge notes for Design a Location-Based Service

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study Design a Location-Based Service is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Core Entity: For Design a Location-Based Service, decide the core entity before choosing tools; otherwise the design looks clean but fails when location changes.
• Read/Write Path: For Design a Location-Based Service, decide the read/write path before choosing tools; otherwise the design looks clean but fails when based changes.
• Contention Point: For Design a Location-Based Service, decide the contention point before choosing tools; otherwise the design looks clean but fails when service changes.
• Abuse Path: For Design a Location-Based Service, decide the abuse path before choosing tools; otherwise the design looks clean but fails when location changes.
• Recovery Workflow: For Design a Location-Based Service, decide the recovery workflow before choosing tools; otherwise the design looks clean but fails when based changes.

Design a Location-Based Service correctness boundary

For this problem, separate the user-visible action from background work. The correctness boundary is the smallest state transition that must not be duplicated, lost, or reordered. Naming that boundary makes the solution more original than a stock API/database/cache template.

Design a Location-Based Service scaling bottleneck

The first bottleneck should be described in the language of this system: a hot timeline, a contested seat, a busy wallet ledger, a media-processing queue, or a search index update delay. That bottleneck decides which component deserves the deepest interview discussion.

Production review question

If Design a Location-Based Service suddenly receives 10x traffic, which entity becomes contested first, and what queue, lock, shard, or cache protects that entity without hiding correctness bugs?

Practical metric to track

Track location-service health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For Design a Location-Based Service, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.

Sources

• Design a Location-Based Service -- Reference
• Source: System-Design-Overview