Practice/Google/Design a Real-time Traffic Monitoring System
Design a Real-time Traffic Monitoring System
System DesignMust
Problem Statement
Design a city-scale traffic monitoring platform that ingests GPS data from millions of vehicles and road sensors, computes real-time traffic speeds for every road segment, and pushes live congestion updates to map clients. The system powers the colored overlay (green, yellow, red) that drivers see on mapping applications to make routing decisions.
The primary challenge is processing a firehose of GPS pings — each vehicle reports its position every few seconds — and translating raw latitude/longitude coordinates into per-road-segment speed estimates with minimal delay. You must map-match each GPS point to the correct road segment (a non-trivial geospatial problem given GPS inaccuracy), aggregate speeds across all vehicles on that segment within a recent time window, and detect transitions between free-flow and congested states.
The system must also push updates efficiently to millions of connected map clients. Not every client needs every road segment update — only segments visible in the user's current viewport should be pushed. This requires a spatial subscription model that minimizes unnecessary data transfer while keeping the map overlay fresh.
Key Requirements
Functional
- GPS ingestion -- Accept high-frequency position reports from millions of vehicles and IoT road sensors
- Per-segment speed computation -- Calculate average and percentile speeds for each road segment within sliding time windows
- Congestion classification -- Classify each road segment into traffic tiers (free-flow, moderate, heavy, standstill) based on computed speeds relative to historical baselines
- Push-based client updates -- Deliver traffic state changes to map clients in near real-time, filtered to the user's visible map area
Non-Functional
- Scalability -- Handle tens of millions of GPS pings per second during peak commute hours
- Latency -- Traffic state changes should reach affected map clients within 10 seconds of the underlying speed change
- Accuracy -- Speed estimates should be within 10% of ground truth for road segments with sufficient probe coverage
- Availability -- The system must remain operational during infrastructure failures, with graceful degradation (showing slightly stale data) rather than outage
What Interviewers Focus On
Based on real interview experiences, these are the areas interviewers probe most deeply:
1. GPS Map-Matching and Geospatial Indexing
Raw GPS coordinates are noisy and do not inherently correspond to road segments. Interviewers want to understand how you resolve this.
Hints to consider:
- How do you efficiently find candidate road segments near a GPS point using a geospatial index (geohash, S2 cells, R-tree)?
- What is map-matching, and how does using a sequence of GPS points (rather than a single point) improve accuracy?
- How do you handle GPS drift near highway overpasses, tunnels, or parallel roads?
- How do you partition the road network geographically so that map-matching can be parallelized?
2. Stream Processing for Speed Aggregation
Computing per-segment speeds from raw GPS data in real time requires a well-designed streaming pipeline.
Hints to consider:
- After map-matching, how do you estimate a vehicle's speed on a specific segment from consecutive GPS pings?
- What window size and slide interval give a good balance between freshness and statistical significance?
- How do you handle segments with very few probes — do you fall back to historical averages?
- How does Flink's keyed state help you maintain per-segment aggregation windows?
3. Spatial Subscription and Push Updates
Pushing updates to millions of clients efficiently requires filtering by geographic relevance.
Hints to consider:
- How do you model a client's visible viewport as a set of geospatial tiles or cells?
- When a segment's traffic state changes, how do you determine which clients are subscribed to that region?
- What protocol do you use for push delivery — WebSockets, Server-Sent Events, or periodic polling with short intervals?
- How do you handle the thundering herd when a major road transitions from green to red and millions of clients need the update?