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

Practical Implementation for .NET Developers

In a .NET application, you would typically implement this pattern using the following approach:

ASP.NET Core setup: Create a service class that encapsulates the logic, register it with dependency injection, and inject it into your controllers or minimal API endpoints. The built-in DI container handles lifecycle management.

Entity Framework Core: For database interactions, EF Core provides the ORM layer. Use migrations for schema management and raw SQL for performance-critical queries. Consider Dapper for read-heavy paths where EF Core's overhead matters.

Azure integration: If deploying to Azure, leverage managed services — Azure Cache for Redis, Azure SQL, Azure Service Bus, Azure Cosmos DB. These eliminate operational overhead and provide built-in monitoring through Application Insights.

Testing: Use xUnit with Testcontainers for integration tests that spin up real databases in Docker. Mock external dependencies with NSubstitute. The WebApplicationFactory class lets you test your entire HTTP pipeline in-process.

Monitoring: Add Application Insights telemetry to track request latency, dependency calls, and custom metrics. Use structured logging with Serilog to make production debugging possible:

Log.Information("Processing order {OrderId} for {CustomerId}", orderId, customerId);

This gives you searchable, structured logs in Azure Monitor or Seq.

System-Specific Clarifying Questions

Before designing Location Based Service, ask questions specific to THIS system:

1. Who are the primary users? Understanding the user base shapes every technical decision — consumer apps have different requirements than enterprise B2B systems.
2. What is the read-to-write ratio? This determines whether you optimize for fast reads (caching, denormalization) or fast writes (write-ahead logs, async processing).
3. What is the geographic distribution? Users in one country vs. global users fundamentally changes your data replication and CDN strategy.
4. What is the acceptable latency? Some features need sub-100ms responses, others can tolerate seconds. This determines your caching and architecture strategy.
5. What is the consistency requirement? Some data (payments, inventory) needs strong consistency. Other data (social feeds, recommendations) can be eventually consistent.

Architecture Deep Dive

The architecture for Location Based Service should be designed around the specific access patterns of the system. Do not apply generic templates — every system has unique hotspots, bottlenecks, and scaling challenges.

Write Path: How does data enter the system? Is it bursty (event-driven, flash sales) or steady (sensor data, logs)? Bursty writes need queuing and backpressure. Steady writes can go directly to the database.

Read Path: How is data consumed? Is it fan-out (one write, many reads like social feeds) or point lookups (one read for specific data like user profiles)? Fan-out reads benefit from pre-computation and caching. Point lookups benefit from efficient indexing.

Hot Spots: Where are the bottlenecks? For Location Based Service, identify the component that will fail first under load and design mitigation strategies: caching, sharding, rate limiting, or async processing.

Sources

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