Design a Ride Dispatch & Matching System
A Staff-level walkthrough of a real-time dispatch system that matches riders to drivers across millions of concurrent candidates — trading greedy speed against batch-optimal total pickup time, with geospatial indexing, ETA-based scoring, and driver-fairness controls. Follow it top to bottom, or jump to any step.
Requirements
Functional Requirements
- Driver-rider matching: Find optimal driver for each ride request
- Geospatial indexing: Efficiently query nearby available drivers
- ETA-optimized matching: Minimize pickup time (not just straight-line distance)
- Batch matching: Simultaneously match multiple riders to multiple drivers
- Fairness: Don't starve drivers who are slightly further away
- Driver queuing: FIFO queues at airports and high-demand venues
Non-Functional Requirements
- Latency: Match within 15 seconds; driver sees offer within 5 seconds
- Scale: 500 matches/second peak; 5M concurrent drivers to search
- Accuracy: ETA-based matching (not just distance) reduces pickup time by 20%
Architecture
Deep dives
WHERE STAFF IS WONDeep Dive 1: Batch Matching (Hungarian Algorithm)
Problem with greedy matching: Rider A arrives, gets matched to nearest Driver X. 2 seconds later, Rider B arrives — Driver X would have been closer to B, and Driver Y closer to A. Greedy matching produces sub-optimal total pickup time.
Batch matching solution:
1. Collect ride requests in 2-second batches
2. For each batch: build bipartite graph (riders ↔ drivers)
3. Edge weights: ETA from driver to rider
4. Solve assignment problem: minimize total ETA across all matches
5. Algorithm: Hungarian algorithm O(n³) or auction algorithm
Impact: 10-15% reduction in average pickup time vs greedy matching.
When to batch vs greedy:
- Dense areas (downtown, airport): Batch (many riders + drivers → optimization matters)
- Sparse areas (suburbs): Greedy (few options, batch adds unnecessary delay)
Deep Dive 2: Fairness and Driver Starvation
Problem: Driver A is 3 min from every rider. Driver B is 2 min. B always wins → A starves.
Fairness score: Track each driver’s idle time and completed trips per hour.
Higher fairness score = driver has been idle → boost their matching priority.
Airport queue: Drivers enter virtual FIFO queue on arrival. Dispatched strictly in order (with vehicle type matching). Prevents circling and ensures fairness.
Deep Dive 3: ETA vs Distance for Matching
Why ETA, not distance?: Driver A is 2km away but across a river (10 min drive). Driver B is 3km away but on the same road (4 min drive). Distance says A is closer. ETA correctly picks B.
Implementation: For top 10 candidate drivers, call ETA Service (routing engine with real-time traffic). Cache: driver-to-rider ETAs are short-lived (valid for ~30 seconds), so not heavily cached.
Tradeoff: ETA computation for 10 candidates per ride = 10 routing calls. At 500 rides/sec = 5000 ETA calls/sec. Mitigation: pre-compute ETA matrix for active drivers in hot zones every 30 seconds.
Bottlenecks & tradeoffs
Monitoring
- Match rate: % of requests matched in < 30s — alert if < 85%
- Average pickup ETA: Track by city and hour
- Driver decline rate: Alert if > 30% (ride offers aren't appealing)
- Fairness distribution: Gini coefficient of trips/driver — alert if too skewed
- Batch matching computation time: Alert if > 1 second
Rubric — Senior vs Staff
Want more breakdowns like this?
Join free early access for upcoming RAG, LLM eval, agents, and AI infrastructure walkthroughs.