Worked Example 15.3 · 3 of 15

Design Uber's matching system

📖 8 min read · 12 sections · May 2026

Asked at: Uber Lyft DoorDash Swiggy

The setup

"Design the core of Uber: matching a rider to a nearby driver, then tracking the trip in real time. Don't worry about payments, ratings, or surge pricing — focus on dispatch and live location tracking. Scale: 100M rides/month, peak 100K concurrent rides."

This problem tests three things: (1) geospatial query at scale, (2) real-time stream of location updates from many sources, (3) race condition handling in concurrent matching. It's also a good lens on regional sharding because the data is naturally geographic.

Clarifying questions

Question	Story answer
Geospatial precision required for matching?	~100m for matching; 1m for live tracking once trip starts.
Match latency target?	< 5 sec from rider request to driver assigned.
How often are driver locations updated?	Every 4-5 sec while on duty.
Single city or global?	Designed for global; partitioned per region; no cross-region matching.
How does a match actually work? First accept? Closest driver?	Offer to nearest available driver; they have 10 sec to accept; if decline/timeout, offer to next nearest.
Surge pricing factor?	Out of scope this session.

Capacity estimation

Drivers on duty (global, peak): ~1M
Driver location updates: 1M × 1 update / 4 sec = 250K writes/sec
But sharded by region (e.g., 200 cities): ~1,250 writes/sec per city — trivial

Rider requests (peak): 100K rides/min = ~1,700/sec
Per region: ~10-100/sec for major cities; nominal otherwise

Match-time computation: find K nearest available drivers
Active rides being tracked: 100K concurrent × 4 location updates / sec
= 400K location updates/sec for tracking purposes
With pub/sub for rider apps: similar fan-out scale

Design Decision 1: Geospatial index — geohash, S2, or H3?

The central technical challenge: given a rider's location, find the K nearest available drivers efficiently. Naive O(N) computation is impossible at scale.

Approach	How	Tradeoff
2D R-tree / kd-tree	Spatial tree with explicit lat/lng	Hard to update at high write rates (drivers move every 4 sec); locks during rebuild; single-machine bottleneck
Geohash	Encode lat/lng as a string with prefix-locality property (nearby points share prefixes)	Simple; great for sharding; cells are rectangular and distort near poles. Boundary effects at cell edges (a driver 5m on the other side of a cell boundary is "far" in geohash terms).
Google S2	Spherical cells; more uniform than rectangular	More accurate than geohash for global apps; library is heavy
Uber H3	Hexagonal cells; hierarchical; designed for this use case	Best uniformity; neighbor cells are predictable; widely adopted for ride-hailing

For this design: pick H3 (or geohash for simplicity in interview — they're conceptually similar). Uber actually built H3 specifically for this problem and open-sourced it.

Why hexagons over squares: every hexagon's 6 neighbors are equidistant from its center. With squares, diagonal neighbors are farther than edge neighbors. This matters for "find drivers within radius R" — fewer false positives at the boundary.

Design Decision 2: Regional sharding

A driver in Mumbai is never matched to a rider in Tokyo. The dataset is naturally partitionable by geography. Each region's geo-index is its own service instance.

What's a "region"? Typically a city or sub-city. Small enough that the in-memory index fits comfortably; large enough that cross-region matching is rare. Uber's actual partition size is finer (neighborhoods or sectors); this design uses city as a simplification.

Each region's matching service:

Runs in a single AZ (or per-AZ instances with shared state for HA)
Holds an in-memory geo-index of available drivers in that region
Accepts location updates from drivers in that region
Accepts ride requests from riders in that region
Performs match computations

The boundary problem: a driver near the edge of a region might be the best match for a rider just inside a neighboring region. Two approaches: (a) ignore this — region edges are rare; the next-best driver within the same region is fine; (b) cross-region peek: query the neighbor region for drivers within radius R of the boundary. Production likely does (b) for high-density boundaries.

Design Decision 3: In-memory or persistent index?

Location data is high-write, ephemeral (we don't care about a driver's location 2 minutes ago). In-memory is the right call.

Storage	Fit
In-memory (custom) or Redis with GEO commands	Best — sub-ms operations, easy update; loses state on restart but rebuilds from incoming updates within seconds
Postgres with PostGIS	Workable; latency higher; updates more expensive; not designed for 250K writes/sec
Cassandra	Possible but spatial queries are awkward

Decision: Redis with GEO commands per region, or a custom in-memory H3 index. Redis GEO supports GEOADD (write driver location), GEORADIUS (find drivers within radius). Custom in-memory gives lower latency but more engineering. For the interview, Redis is the simpler defensible choice.

Async backup: every minute, snapshot the index to a durable store (just in case region service needs to rebuild from cold start). On recovery, snapshot is loaded; recent updates from the update stream replay.

The architecture

Driver app ──── periodic location update (every 4s) ────► [Location Update Service]
                                                                ↓
                                                  Route by region (which H3 cell?)
                                                                ↓
                                                  Per-region matching service
                                                  - in-memory geo-index (Redis GEO)
                                                  - records (driver_id, lat, lng, status)
                                                  
Rider app ──── ride request (pickup_lat, pickup_lng) ──► [Dispatch Service]
                                                                ↓
                                                  Route to region's matching service
                                                                ↓
                                                  Query nearest K available drivers
                                                                ↓
                                                  Apply business rules (vehicle type, ratings)
                                                                ↓
                                                  Offer to driver #1 (10-sec accept window)
                                                                ↓
                                                  If decline/timeout → offer to driver #2
                                                                ↓
                                                  Match → trip starts
                                                  
Trip live tracking:
   Driver location updates flow to per-trip pub/sub channel
   Rider app subscribes to that trip's channel
   Real-time location streamed to rider

Cross-examination round 1: location update throughput

Interviewer: 1M drivers × 0.25 updates/sec = 250K writes/sec to your location service. Walk me through the path of a single update.

Driver app sends HTTP POST (or sustained WSS frame) every 4 sec with (driver_id, lat, lng, timestamp, status). Hits an edge gateway. Gateway determines the driver's region (by lat/lng) and routes the update to that region's matching service. The matching service: (1) authenticates, (2) updates the in-memory geo-index (Redis GEO write or custom), (3) async writes to a durable log (Kafka) for analytics and recovery. The hot path is the in-memory index update — single-digit ms. 250K updates/sec across 200 regions = ~1,250/sec/region. Trivial per shard.

Follow-up: What if a driver's GPS jumps wildly (urban canyon, signal loss)?
A: Server-side validation. Reject updates where implied speed exceeds plausible (300 km/h between consecutive reports). Use Kalman filtering or simpler dead-reckoning to interpolate gaps. Client-side: smooth GPS readings before sending. Don't trust the GPS sensor blindly.

Follow-up: A driver crosses a region boundary mid-shift. What happens?
A: Each location update is independently routed by current lat/lng. The previous region's index has a stale entry for this driver — gets cleaned up via TTL (e.g., 30 sec TTL on entries; if no fresh update arrives, remove). New region now has the driver. Brief inconsistency window of a few seconds; acceptable because matching latency is also a few seconds.

Cross-examination round 2: match concurrency

Interviewer: 1000 ride requests come in at the same time in the same neighborhood. Will they match to the same driver?

Drivers can only be matched to one request at a time. The matching service maintains driver status: available, offered, matched, on_trip. Match flow: (1) find nearest K available drivers, (2) lock the chosen driver (status: offered) via atomic compare-and-swap, (3) push notification to that driver, (4) if they accept within 10 sec → status: matched; if decline/timeout → status: available again, try next driver. The atomic CAS prevents two simultaneous requests from both offering to the same driver — first to CAS wins; second sees the driver is taken and falls through to next-nearest.

Follow-up: Walk me through the race: two ride requests, both nearest-driver is Alice. Both find Alice in their query. Both try to offer.
A: Atomic CAS on Alice's status row in Redis. Request 1 does SET available → offered NX (only if currently available). Request 1 succeeds; status flips to offered. Request 2 attempts the same CAS; fails (already offered). Request 2 sees Alice unavailable; queries again for next-nearest; offers to Bob. Two riders end up with different drivers; no double-offer.

Follow-up: What if Alice declines after 10 seconds? Request 1's rider has been waiting.
A: Status flips back to available. Match service re-queries for nearest available, offers to next driver. Rider sees "looking for driver..." until match completes. UX shows progress: "found driver Alice... declined... trying again." If multiple declines exhaust the local driver pool, expand search radius progressively.

Cross-examination round 3: live tracking

Interviewer: Now the rider's in the car. They want to see the driver moving on the map in real time. Plus the driver needs turn-by-turn nav. Design.

The driver's location updates (still 4 sec cadence) now also publish to a per-trip pub/sub channel (Redis Pub/Sub or Kafka topic, partitioned by trip_id). The rider's app subscribes to that trip channel via WSS. As the driver moves, the rider sees the marker update on the map. Same pattern as messaging: pub/sub fan-out for location to the trip's subscribers (typically just the rider, but could include support/family).

Follow-up: What's the latency from driver-side GPS to rider-app render?
A: Driver GPS → driver app: ~1 sec. Driver app → server: ~100-500ms (mobile network). Server → rider app: ~100-500ms via WSS. Total: 1.5-3 sec. That's why you smooth the marker animation client-side — predict driver's path between updates so the marker moves smoothly rather than jumping.

Failure mode analysis

Failure	Mitigation
Region's matching service crashes	Replica failover (drivers and riders briefly see "service unavailable"). In-memory index rebuilds from Kafka log replay on the new node (~30 sec for full rebuild).
Redis GEO degraded	Match latency up; partial outage in that region. Drivers continue to receive updates; matching queues briefly until Redis recovers.
Driver app loses connectivity mid-trip	Location updates pause; trip remains active (no auto-cancel). When connectivity resumes, app catches up. Rider sees frozen marker but can still see ETA from last known.
Sudden surge (10× normal traffic in a region)	Match queue backs up. Riders see "longer wait"; the system continues operating but slower. Auto-scaling brings up more match service instances within minutes.

Takeaway

Geospatial matching at scale is a specialized problem. The naive "compute distance from rider to every driver" is O(N) per request and dies above a few thousand drivers. Spatial indexes (geohash, H3, R-tree) bring it to O(log N) or O(K) with hierarchical structures. Sharding by geography removes the global-state problem. The interesting parts are the surrounding systems: location-update throughput, match fairness, race conditions in concurrent offers, and the live-tracking subsystem that's effectively a streaming database. Uber's H3 (open-sourced) is worth reading independently as a specialized data structure paper.

The deeper insight: when your data has natural geographic distribution, your architecture should reflect that. Don't try to make a globally-coordinated system when you can have N independent regional systems with no cross-region dependencies. The architecture mirrors the problem.