Design Uber (Ride-Sharing)
The core challenge is real-time geospatial matching at scale — finding nearby drivers fast, handling millions of location updates per second, and pricing under surge demand.
1. Requirements
- · Rider requests a ride (pickup + dropoff location)
- · Match rider with a nearby available driver
- · Real-time driver location tracking on the map
- · Dynamic (surge) pricing and ETA estimation
- · Trip lifecycle: requested → accepted → in-progress → completed
- · Payments and ratings after trip completion
- · 10M daily active riders, 1M active drivers
- · Driver app pings location every 4 sec
- · 5M ride requests/day
- · Peak concentration: rush hour in dense cities
- · Location update QPS dominates over ride-request QPS
2. Estimation
3. Core Challenge: Geospatial Indexing
"Find all available drivers within 2km of the rider" is a spatial range query — a plain SQL table scan or B-Tree index on (lat, lng) can't do this efficiently since neither column alone is sorted by proximity.
Encodes (lat, lng) into a base32 string — nearby locations share a common prefix. Store drivers in Redis sorted by geohash prefix; query = prefix range scan.
Recursively subdivides the map into 4 quadrants until each cell has few enough drivers. Dense areas (city centers) get finer cells; sparse areas stay coarse.
Uber's actual approach (simplified): a hierarchical hexagonal grid (similar to Google's S2 / Uber's own H3 library) that divides the world into hexagonal cells at multiple resolutions. Driver locations are bucketed by cell ID; matching expands outward ring-by-ring (search current cell → neighboring rings) until enough drivers are found.
4. Architecture
5. Database Choices & Rationale
| Data | Storage | Why |
|---|---|---|
| Live driver locations | Redis (GEO / sorted sets, in-memory) | Sub-ms reads/writes at 250K updates/sec. Only latest position matters — no durability needed. |
| Trip records | PostgreSQL / MySQL (sharded by trip_id or region) | Needs ACID for payment-linked state transitions (requested → completed → paid). |
| Location history (analytics) | Cassandra / data lake (S3 + Parquet) | High write volume, append-only, time-series. Used for ETA model training, not live queries. |
| Driver/rider profiles | PostgreSQL | Relational data with strong consistency needs (ratings, payment methods). |
| Surge pricing state | Redis counters per geo-cell | Needs fast read/write of demand/supply ratio, recomputed every ~1 minute per cell. |
| ETA / routing | Dedicated routing service (graph-based, e.g. OSRM-like) | Shortest path over road graph — specialized algorithm (contraction hierarchies), not a generic DB. |
6. Bottlenecks & Solutions
Shard the geo-index by region/cell range across multiple Redis nodes. Each shard owns a set of cells — writes route by cell_id hash. Use write-behind buffering (batch updates every 1-2s) instead of writing every single ping.
Dynamically subdivide hot cells into finer sub-cells (quadtree-style) so matching doesn't scan thousands of drivers per lookup. Apply surge pricing to naturally throttle demand.
Atomic compare-and-swap on driver status in Redis (Lua script: check-and-set 'available' -> 'matched' atomically) or a distributed lock per driver_id with short TTL.
Fallback to periodic polling (every 5s) if WebSocket drops. Store the last N location updates server-side (short TTL) so a reconnecting client can catch up immediately instead of waiting for the next push.
7. Key Trade-offs Summary
| Decision | Option A | Option B | Chosen & Why |
|---|---|---|---|
| Geo-indexing | Quadtree | Geohash / H3 grid | Hex grid (H3-like) — uniform neighbor lookups, easy ring expansion |
| Location storage | Durable DB | In-memory (Redis) | Redis — only latest position matters, needs sub-ms writes at huge QPS |
| Matching strategy | Global optimal assignment | Greedy nearest-first with timeout | Greedy — near-optimal is fine, users need a match in seconds, not a perfect one |
| Live trip updates | Polling | WebSocket push | WebSocket — lower latency, less wasted bandwidth than polling every few seconds |
| Consistency (trip state) | Eventual | Strong (ACID) | Strong — trip/payment state must never be ambiguous or double-charged |
| Surge computation | Real-time exact | Periodic approximation (~1 min) | Periodic — exact real-time recompute isn't worth the cost; riders tolerate slightly stale surge |
8. Follow-up Questions
A: Divide the map into geo-cells and maintain rolling demand (open ride requests) and supply (available drivers) counters per cell in Redis, recomputed on a fixed interval (e.g. every 30-60s) rather than per-request. The multiplier for a cell is looked up (O(1)) at request time instead of computed fresh.
A: Trip service uses a heartbeat/timeout: if no location update for the active trip_id in N seconds, flag the trip as 'connection lost' and notify the rider, but don't cancel immediately — allow a grace period for reconnection before escalating to support/cancellation.
A: Driver state transitions must be atomic: use a Redis Lua script (or DB row-level lock) to compare-and-swap status from 'available' to 'pending_match' — only one matching request can win the race; the loser retries with the next candidate driver.
A: Partition the entire system by geographic region (e.g. by city or country) — each region has its own matching service instance and geo-index shard, since a rider in Bangalore never needs to be matched with a driver in São Paulo. This keeps each shard's working set small and localized.