Design a Real-Time Ride-Sharing Dispatch & Matching Engine (Uber / Lyft)
A real-time geospatial dispatch system matches riders with the most optimal nearby drivers using 64-bit H3 hexagonal indexing and 2-second batch optimization, minimizing city-wide pickup ETA and driver idle time.
Live Architecture Studio
Edit components, modify labels, add databases, or redraw connections directly on this canvas:
Loading Uber Dispatch Engine Blueprint...
Mounting vector diagram elements, nodes, and capacity metrics
Loading Uber Dispatch Engine Blueprint...
Mounting vector diagram elements, nodes, and capacity metrics
1. Problem & Challenge
Millions of mobile drivers stream continuous noisy GPS coordinates every 4 seconds. When a rider requests a trip, the platform cannot simply pick the nearest straight-line car; it must calculate real road route ETAs, traffic, and match supply and demand globally without race conditions.
2. Core Building Blocks & Responsibilities
👉 Desliza la tabla para ver roles y responsabilidades| Component | Role | Plain-English Explanation |
|---|---|---|
| Mobile Telemetry Ingestion | GPS Stream Entry | Receives 1.25M GPS pings/sec over gRPC/HTTP2, applying Kalman filters to remove urban skyscraper reflection noise. |
| Map-Matching Stream (Flink) | Road Snapping | Runs Hidden Markov Models (HMM) over Kafka streams to snap raw coordinates directly to valid road network segments. |
| H3 Hexagonal Spatial Index | In-Memory Geo Grid | Partitions Earth into uniform hexagons (Resolution 8: ~460m radius). Hexagons have identical neighbor distances, eliminating coordinate distortion. |
| DISCO Dispatch Matcher | Marketplace Optimizer | Collects ride demand and driver supply in 2-second micro-batches, solving the Bipartite Matching Problem with the Hungarian algorithm. |
| Routing & ETA Engine | Contraction Hierarchies | Computes real road-network driving distance and duration in <15ms instead of naive Euclidean straight-line distance. |
3. Step-by-Step Request Flow
Driver Pings Location
Driver mobile app transmits location every 4s to the Ingestion Gateway.
Kafka Stream & Map Snapping
Apache Flink snaps latitude/longitude to the road vector graph and converts coordinates into a 64-bit H3 cell index.
In-Memory Cell Update
Driver ID is updated in the in-memory H3 grid cluster (Ringpop/Redis), maintaining active supply state.
Rider Requests Trip
DISCO scans neighboring k-ring hexagons, runs batch matching over a 2-second window, and dispatches the optimal driver.
4. Architectural Trade-offs
Hexagonal Grid (H3) vs Square Geohashes
Chosen: H3 Hexagonal Hierarchical Index
Rationale: Square cells have two types of neighbors (edges at distance 1, corners at distance 1.414). Hexagons have 6 identical neighbors at uniform distance 1, making radius search and surge diffusion symmetric.
Greedy First-Match vs 2-Second Batch Window
Chosen: 2-Second Batch Window
Rationale: Greedy matching assigns the closest car immediately, leaving subsequent riders stranded. 2-second batching reduces average city-wide pickup ETA by 20%.
Interview Tip
Explain why the entire global driver supply state fits in memory: 5M active drivers at 500 bytes per record is only ~2.5 GB of RAM. The challenge is not storage size, but ingestion throughput (1.25M writes/sec) and map-matching.
Explore Related System Blueprints
TinyURL Shortener
A URL shortener converts a long link (like a 100-character article URL) into a compact 7-character key (like tinyurl.com/xyz123) and redirects visitors in under 15 milliseconds.
API Rate Limiter
A rate limiter acts as a digital bouncer at the door of your API, ensuring each client stays within their allowed request limits (e.g. 100 requests per minute) and blocking abusive traffic.
Video Streaming CDN
Streaming high-definition video to millions of smart TVs and mobile phones requires breaking large 10GB video files into tiny 5-second chunks, encoding each into 20 different resolutions, and caching them right inside local ISP networks.
Stripe Payments Ledger
A resilient financial payments architecture guarantees strict consistency (CP system) using cryptographic idempotency reservation, double-entry balanced postings, and sharded balance locks.
Figma Multiplayer Engine
A real-time multiplayer document engine uses stateful sticky session routing and server-authoritative operational ordering to sync 2D scene graphs across worldwide collaborators without locking.
Twitter Timeline & Feed
A timeline generation system balances high write amplification against fast sub-50ms reads by pushing tweets to followers of regular accounts, while pulling and merging celebrity tweets on-demand.