System Design Case Study
Ride matching
A rider opens the app after a late flight, pins pickup at the curb, and watches a car approach on the map. Underneath, millions of drivers stream locations every few seconds while must finish in under a second.
Ride matching is a local real-time marketplace. Keep fresh driver positions, match nearby supply, then track one from request through payment, without using stale pins.
Request → trip journey
Drivers update a geospatial index every ~3s.
GEORADIUS, rank, offer, timeout fallback.
Rider sees the car; ETA refreshes.
Fare, surge, capture, receipt.
Try it: ride matching in a geo cell
Riders and drivers update location in a geo index. Matching runs inside a city cell to keep latency local.
- Rider
- Dispatch
- Geo index
- Driver offer
- Trip start
- Offers
- 0
- Accepted
- 0
- Mode
- match
- Path hop
- 0
Locality
geo cellMatching scoped to a city/cell shard to bound search.
Offers
timeout0 offers, 0 accepts.
Failure
idle supplyEmpty cells should fail fast into pricing or expansion, not hang the rider.
Run match under normal supply or surge when the cell is empty.
What actually happens
The critical path is the . Drivers push lat/lng; the service stores them in a geospatial index ( / / GEOADD) and serves queries for matching. Shard by city so NYC peak hour does not drown SF.
ranks candidates by distance, , and rating, offers the top driver, and expands radius or applies when supply is thin. After accept, a (or poll fallback) streams positions on a trip channel.
Payments and history live in durable stores; live locations stay ephemeral with TTL so stale drivers drop out of the available set. A location update is an observation, not proof of availability. Store an observation timestamp and a monotonic device sequence so a delayed packet cannot replace a fresher position. Filter stale or implausible locations during candidate selection, and verify driver status again when assigning a trip. Historical location streams may be retained separately when needed, but they should not make an offline driver appear matchable.
How to choose the design moves
1. Is matching local? Search nearby supply using geographic partitions around the pickup area. Choose a durable trip owner based on the operating region and the product’s latency and residency rules; the rider’s account home region need not own an airport ride elsewhere. Keep that ownership stable through the trip or use an explicit handoff rather than allowing two regions to update it independently.
2. Is the position fresh? Heartbeats and timestamps filter stale drivers. Old pins must not win a match.
3. What if routing is slow? Match with approximate distance, then refresh after acceptance rather than blocking the whole match on perfect routing.
Simple rule of thumb
Treat Location Service as the heartbeat of the product: regional shards, geospatial indexes, matching timeouts, and resilient live tracking. Always reason about hot regions, stale positions, and surge feedback loops.
In simple terms: find nearby drivers fast, pick one carefully, then keep the map honest until payment settles.
Case-study upgrade
Ride Matching Math
Ride matching is a local, real-time state machine. The key is fresh location data, nearby candidate search, offer timeouts, and one accepted driver.
Assumptions and formulas
- Rides: 20M/day. Concurrent rides: 500K. Online drivers: 5M.
- Drivers send location every 3 seconds. Matching scans about 50 candidates/request.
- Location updates are small but extremely frequent and geographically skewed.
Concrete math
- Rides: 20M/day = 231 rides/sec average; 10x peak is 2.3K/sec.
- Active trip tracking: 500K rides / 3 sec = 167K updates/sec.
- Available driver pings: 5M drivers / 3 sec = 1.67M updates/sec.
- Ingress: 1.67M/sec x 120 bytes = about 200 MB/sec before protocol overhead.
- Matching: 2K requests/sec peak x 50 candidates = 100K candidate scores/sec; one hot city can dominate this.
Design decisions forced by numbers
- Shard by geography, not globally.
- Keep latest driver location in a TTL-backed geo index; stale drivers should not be offered.
- Use an offer state machine so duplicate accepts cannot create two trips.
Scaling to millions
- At 1M users: one regional geo index and simple dispatch workers are enough.
- At 10M users: split hot cities, add ETA services, and isolate matching from trip storage.
- At 100M+ users: add regional control planes, surge isolation, stale-position detection, and graceful fallback.
Readable flow
Interview follow-ups to expect
- How fresh must driver location be?
- What happens when two drivers accept at the same time?
- How do we degrade when ETA or pricing is stale?
Operational readiness checklist
After the math, explain how this capacity plan is measured, protected, launched, and evolved.
Observability
- Attach each capacity estimate to a dashboard metric: p99 latency, queue age, cache hit rate, shard skew, error rate, and freshness lag.
- Alert on rate-of-change and saturation, not only hard failures; backlogs and hot keys usually warn before an outage.
Security and abuse
- Budget for auth checks, rate limits, quota isolation, audit logging, privacy filters, and abuse-review side paths.
- Separate trusted internal events from user-controlled input so retries and backfills cannot bypass policy checks.
Degraded modes
- Define the fallback when a dependency is slow: stale cache, partial results, read-only mode, delayed async work, or admission control.
- Protect the invariant first; reduce freshness, personalization, or analytics quality before risking duplicate or corrupt state.
Testing and rollout
- Test average, peak, and hot-object traffic; include retry storms, cold caches, lagging workers, and regional dependency loss.
- Use canaries, shadow reads, dual-write validation, feature flags, and explicit rollback criteria for risky path changes.
Rollout, backfill, and runbooks
- Make migrations and backfills idempotent, resumable, rate-limited, and visible through progress and error metrics.
- Write the runbook before launch: owner, dashboards, paging thresholds, mitigation switches, replay steps, and repair commands.
10x evolution
- For ride matching math, state which number forces the next move: cache memory, shard count, write amplification, queue lag, egress, or failover reserve.
- Add the next layer only when the metric forces it: sharding, regional reads, async replay, hot-key isolation, or stricter backpressure.
Scope you should nail down
Product surface
- Rider requests ride (pickup, destination)
- Match with nearby available driver
- Real-time driver location tracking
- ETA for pickup and arrival; surge pricing
- Payments, ride history, mutual ratings
Scale targets
- ~100M users, ~20M rides/day
- Peak ~500K concurrent rides
- Location update every ~3s; match latency <1s
- High availability (~99.99%)
Capacity picture
APIs worth sketching
- POST /rides/request: requestRide(rider_id, pickup, destination)
- POST /rides/{id}/match: matchDriver(ride_id)
- POST /location: updateLocation(driver_id, lat, lng)
- GET /rides/{id}/eta: getETA(ride_id)
- POST /rides/{id}/complete: completeRide(ride_id)
- POST /rides/{id}/rate: rateRide(rider_id, driver_id, rating)
Core data model
Users
Drivers
Rides
Locations
Payments
Ratings
High-level architecture
Location service (critical path)
/
A spatial index narrows the drivers examined for a radius search. Geohashes encode cells whose shared prefixes often indicate proximity, but nearby coordinates can fall across a cell boundary. Query neighboring cells as needed and filter candidates by actual distance and freshness. A quadtree subdivides dense areas recursively, trading index structure and update cost against efficient spatial pruning.
In-memory geospatial
GEOADD updates a driver in a Redis geospatial index. performs a radius lookup whose cost depends on both index size and the number of candidates in the bounding area; it is not simply O(log N). Redis documents O(N + log M) for that command and supports GEOSEARCH for newer query designs. Bound radius and candidates, and shard dense operating areas so a busy airport cannot monopolize one index.
Geospatial commands sketch
// in-memory geospatial commands
GEOADD drivers:sf 37.7749 -122.4194 driver_123
GEORADIUS drivers:sf 37.77 -122.42 5 km WITHDIST
→ Returns drivers within 5km, sorted by distance
// Cell-based: partition by city (drivers:sf, drivers:nyc)Cell-based: Shard by city or geohash prefix. Each region has its own cache cluster. Reduces cross-shard queries.
Driver availability
Entering an available-driver index makes a driver a candidate, not an exclusive assignment. Offer acceptance should conditionally move the driver and trip from their expected states to assigned under one authority. A second dispatcher with an old availability result then loses the claim. On cancellation or completion, return the driver to availability only if the transition still owns that assignment and a sufficiently fresh location exists.
Matching, tracking, ETA, and surge
Matching flow
- Rider requests ride (pickup lat/lng)
- GEORADIUS: available drivers within radius (e.g., 5km)
- Rank by distance, ETA, driver rating
- Offer to top driver; timeout (~15s) → next driver
- Expand radius / notify wait / surge if empty
Real-time tracking
- for rider location stream
- Driver app pushes every ~3s to Location Service
- Pub/sub on channel ride:{ride_id}
- Polling fallback; batched GEOADD keeps the index fresh
Road network as a graph. Dijkstra or A* with traffic-weighted edges; contraction hierarchies for speed. ML + crowdsourced driver speeds improve segment predictions.
Surge pricing responds to a local imbalance between demand and available supply under a product-defined policy. Compute over a time window, smooth changes, and avoid tiny cell boundaries that create abrupt neighboring prices. Return a quote with its scope and validity before confirmation so the user understands the charge basis. Recompute future quotes as conditions change rather than silently changing an already accepted fare contract.
Surge pricing formula
surge_factor = f(demand_requests, available_drivers)
demand_requests = count(requests in last 5 min)
available_drivers = GEORADIUS countPartitioning and payment
- Location: shard by city/region (drivers:sf, drivers:nyc)
- User data: shard by user_id: rides, payments, ratings
- Rides: shard by ride_id or rider_id for history
A trip crossing geographic boundaries needs a stable authority for state transitions even while location routing follows the moving vehicle. Either retain the original trip-owning region until completion or transfer ownership with a versioned handoff. Reads can be served near the user, but two regions must not independently accept cancellation, completion, or reassignment from stale state. Explain this separately from where the rider’s profile is stored.
On complete: Pricing computes fare (distance × rate + surge). Payment charges with idempotency; split platform fee + driver payout. Webhooks confirm async; receipts via Notification Service; backoff on provider failures. Record the fare calculation inputs and payment operation before contacting the provider so a retry refers to the same trip charge. A timeout can mean the charge succeeded but the response was lost; query or retry using the original provider key. Keep rider payment, platform accounting, and driver payout as distinct states so a delayed payout cannot be mistaken for an unpaid trip.
Bottlenecks to call out
Location update storm
~1.7M updates/sec: batch, shard by region, scale the cache cluster.
Hot region
NYC/SF peak: more replicas and read scaling.
Matching latency
GEORADIUS + ranking <1s: precompute availability; cache hot zones.
WebSocket scale
Millions of connections: regional pools and horizontal scaling.
Takeaway
Ride-matching design is dominated by the Location Service: millions of updates per second need regional geospatial indexing, fast matching timeouts, and resilient real-time tracking.
Review the design
Location Service: in-memory GEOADD/GEORADIUS for spatial indexing. Shard by city/region. Critical path for matching.
Matching: GEORADIUS → rank by distance/ETA/rating → request top driver → timeout fallback.
Real-time: WebSocket for rider; driver pushes location; pub/sub broadcasts.
ETA: graph routing (Dijkstra/A*) + traffic data + ML.
Surge: dynamic pricing by supply/demand per zone.
Partition: location by region; user data by user_id. Cross-region rides handled via rider home region.
Compare a starting answer with a more complete design
A starting answer
Model riders, drivers, trips, location updates, matching, ETA, payments, and real-time trip tracking.
Developing the reasoning
Discuss region partitioning, location TTLs, stale driver filtering, matching timeouts, surge pricing feedback loops, ETA fallbacks, and trip state reconciliation.
Deeper walkthrough
ride matching deeper walkthrough
Ride hailing is a local real-time marketplace. The location stream, matching workflow, trip state machine, ETA service, and payment flow all interact.
Requirement refinements
Clarify ride types, driver availability, cancellation rules, surge pricing, scheduled rides, live tracking, and payments.
State the trip invariant: one active driver should own an accepted trip, and stale location should not be used for matching.
API design details
Use heartbeat and location update APIs with timestamps so stale driver positions can be filtered.
Model ride request, driver offer, accept, cancel, pickup, start, complete, and payment as explicit state transitions.
Data model and storage
Keep latest driver location in an ephemeral geo index with TTL and write raw location events to a stream for analytics.
Store trip state transitions in an event log so disputes and payment reconciliation can replay what happened.
Scaling strategy
Partition by city or geo region because matching is local and hot spots are geographically clustered.
Throttle low-value location pings during storms and prefer fresh nearby candidates for matching.
Reliability, recovery, and operations
If routing is slow, match with approximate distance and refresh ETA after acceptance.
Monitor location lag, match success rate, request-to-accept latency, ETA error, cancellation rate, and payment reconciliation lag.
Deepening reference
Ride Hailing: realistic production notes
Beginner mental model: Ride hailing is geo-indexed supply, demand matching, state machines, and real-time tracking.
Production scope: The location system dominates write volume. Matching must consider distance, ETA, driver status, fairness, cancellation, surge, and city-level partitioning.
Choose what the first version must guarantee
Start by deciding which ride hailing capabilities are essential. Describe the main read and write operations before choosing infrastructure. For each operation, identify the stored records it uses and the condition that makes its result correct. A fast response is useful only if it satisfies that condition.
Next, separate work the user must wait for from work that can finish later. Estimate requests per second, storage growth, and the busiest object or customer. Use those estimates to choose one bottleneck to investigate. The calculations below are example workloads with stated assumptions; they are not measured limits of a particular product.
Core flow to walk through
Driver location: ingest GPS ping, validate, update latest location in geo index with TTL.
Request ride: find nearby candidates, rank, offer to drivers, handle timeout and retry.
Trip state: requested, accepted, arrived, in_progress, completed, paid, cancelled.
Production readiness
Ride Hailing: ship, operate, and evolve
Now examine the same request flow during failures and deployments. Tie each operational control to the user behavior it protects.
Observability
Track ride hailing p95/p99 latency, error rate, saturation, and user-visible freshness separately for read, write, and async paths.
Alert on leading indicators such as queue age, hot-key skew, cache miss storms, reconciliation mismatches, and error-budget burn.
Security and abuse
Enforce authentication, authorization, rate limits, input validation, audit trails, and privacy checks at the service boundary.
Treat abuse controls as a first-class path: throttling, quota isolation, moderation hooks, revocation, and safe handling of sensitive data.
Degraded modes
Name what still works if cache, search, ranking, stream processing, object storage, or a regional dependency is slow.
Prefer stale-but-safe reads, partial results, async retry, admission control, and feature disablement over corrupting core state.
Testing and rollout
Load test average, peak, and hot-object traffic; add failure-injection for retries, timeouts, backlog growth, and dependency outages.
Ship with canaries, shadow reads or dual writes when useful, rollback switches, schema compatibility checks, and replay validation.
Runbooks
Document dashboards, paging thresholds, owner actions, rollback steps, data repair commands, and customer-impact language.
Keep backfills and replays idempotent, resumable, rate-limited, and observable so repair work does not create a second incident.
10x evolution
Say which metric forces the next architecture change: shard count, cache footprint, write amplification, queue lag, p99 latency, or regional failover reserve.
Evolve one bottleneck at a time: partition by access pattern, isolate hot tenants, regionalize reads, add replayable async pipelines, then harden multi-region behavior.
Hard parts worth deepening
Partition by region/city because rides are local.
Use short-lived driver location with TTL to avoid matching stale drivers.
Matching is a workflow with timeouts, not one database query.
ETA and surge are feedback loops that can change user and driver behavior.
Failure modes and recovery
Location ingest storm; throttle low-value pings and keep last-known location.
Driver accepts but app disconnects; heartbeat and reassign before pickup if needed.
Map/routing service is slow; fallback to approximate distance and cached ETA.
Payment capture fails after trip; keep trip complete and reconcile payment separately.
Signals to monitor
Location-update lag measures the age of the driver position used for matching. Compare it with ETA error, the difference between predicted and observed arrival, because a precise routing algorithm cannot correct an old location.
Match success and request-to-accept time describe whether a rider finds a driver promptly. Cancellation rate adds context: a quick match that is repeatedly cancelled may be worse than a slightly slower, reliable assignment.
| Choice | Best when | Cost |
|---|---|---|
| Nearest-driver match | You need a simple baseline. | May reduce fleet efficiency. |
| Batch/global optimization | Dense markets and high demand. | Adds decision latency. |
| In-memory geo index | Latest location queries are hot and ephemeral. | Durability comes from the event log, not the serving index. |
Try this scenario
Explain how matching changes when 10,000 users request rides after a concert ends.
Primary sources
- Uber Engineering: H3: geo indexing for matching.
- Google S2 Geometry: spatial cells for nearby search.
- Kafka Streams documentation: location event pipelines.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Design location ingestion, geo indexing, stale-state policy, matching/reservation, dispatch state, fairness, reconnects, and surge safeguards.
Explain the decision
Why use a hierarchical geo index for nearby-driver lookup?
Read the reasoning
It maps points to cells, supports neighbor expansion and resolution trade-offs, and partitions spatial work better than scanning coordinates.
Apply it to a production scenario
A driver accepts a trip, disconnects, and the rider retries. What prevents double assignment?
Read one approach
Use a conditional trip-state transition with lease/expiry, stable command ID, driver heartbeat semantics, and reconciliation before rematching.
Work through the numbers
Two million drivers send a 120-byte update every 4 seconds. Estimate raw ingest.
Read the worked calculation
500,000 updates/s and about 60 MB/s before protocol, indexes, replicas, and history.
Reason through a failure
What must dispatch preserve?
Read the recovery reasoning
At most one active driver reservation exists for a trip epoch, and stale drivers cannot accept after reassignment.