Design Ride Matching

What are we designing? A system that, when a rider requests a ride, finds the nearest available drivers, broadcasts a ride offer to them, accepts the first response, and tracks the trip through pickup -> dropoff -> payment. The system must do this within ~5 seconds end-to-end (rider sees driver assigned), at the scale of a major city (50K concurrent drivers, 100K ride requests per hour).

The defining challenges are (1) geospatial indexing — how to find the K nearest drivers to a point without scanning all drivers, (2) the dispatch protocol — how to broadcast an offer and accept exactly one driver, and (3) supply-demand balancing — surge pricing to incentivize drivers to high-demand areas.

Functional requirements.

• A rider requests a ride at location (lat, lng) for destination (lat, lng).
• System finds the nearest K available drivers (default K=3-5).
• System broadcasts a ride offer to those drivers; first to accept wins.
• If no driver accepts within N seconds, expand the search radius and retry.
• Once a driver accepts, the rider sees driver details + ETA.
• System tracks trip state: requesting -> matched -> en_route -> pickup -> in_trip -> dropoff -> payment -> completed.
• Driver app updates location every 4 seconds; rider app updates every 4s during trip.

Non-functional requirements.

• Dispatch latency: < 5 s from request to driver-assigned (most of this is human decision time).
• Nearest-driver query latency: < 100 ms p99.
• Driver position freshness: < 5 s lag (we know roughly where every driver is in real time).
• Throughput: 100K ride requests/hour = ~30/sec peak in a city; 50K concurrent driver positions updated every 4s = 12K updates/sec.
• Availability: 99.99% (lost rides = lost revenue + bad UX).

Non-goals. No route optimization (Google Maps API), no fare calculation (separate service), no fraud detection.

Capacity estimation.

Driver position updates. 50K concurrent drivers in a city, position every 4s = 12.5K updates/sec. In a country with 10 cities = ~125K updates/sec. Each update ~50 bytes (driver_id, lat, lng, heading, speed, status) = ~6 MB/sec ingest — trivial.

Ride requests. 100K/hour peak in a big city = ~30/sec. Each request triggers a nearest-driver query (~50 ms) + a broadcast to ~5 drivers + ~3s of human decision time. Broadcast = 150 messages/sec to drivers — trivial via WebSocket.

Storage. Trip records: 100K trips/day/city = ~3M trips/month. Each trip ~1KB metadata + GPS breadcrumb stream (~100KB). ~300GB/month per city. Driver location history is ephemeral (we don't need to store every position update forever — keep last 24h for analytics, then aggregate).

Memory. Live driver positions: 50K drivers x 100 bytes (id, lat, lng, status, last_update) = 5 MB. Trivially fits in a single Redis geo-index.

APIs.

# Driver app -> server (every 4s)
POST /v1/drivers/location
  { lat, lng, heading, speed }
  -> { status: ok }

# Rider requests a ride
POST /v1/rides
  { pickup: {lat,lng}, dropoff: {lat,lng}, ride_type }
  -> { ride_id, status: "searching" }

# Server pushes ride offers to drivers via WebSocket
WS /v1/drivers/events  ->  { type: "ride_offer",
                              ride_id, pickup, dropoff, est_fare, ttl_sec }

# Driver accepts
POST /v1/rides/:id/accept
  -> { status: "matched", rider_info: {...} }
  -> other drivers get "ride_cancelled" event

# Trip state machine
POST /v1/rides/:id/state  { state: "pickup" | "in_trip" | "dropoff" | ... }

The WebSocket to drivers is the spine — every driver with the app open holds a WS connection. The server can push ride offers, cancellations, and rider ETA updates instantly. Long-poll is the fallback; mobile carriers' NAT timeouts are typically 30s, so we send keepalives every 25s.

Data model.

Live driver positions (Redis GEO index, one key per city):

GEOADD drivers:nyc {lng} {lat} {driver_id}
GEORADIUS drivers:nyc {lng} {lat} 3 km ASC COUNT 10

Redis GEO wraps a geohash-sorted set; GEORADIUS returns drivers sorted by distance in O(log N + K). 50K drivers in one city = sub-millisecond query.

Rides (sharded SQL by ride_id):

rides (
  id PK, rider_id, driver_id, status, pickup_geo, dropoff_geo,
  fare, surge_multiplier, created_at, accepted_at, completed_at,
  INDEX (status, created_at),
  INDEX (driver_id, created_at),
  INDEX (rider_id, created_at)
)

Trip breadcrumbs (time-series store, e.g. Cassandra or TimescaleDB):

trip_breadcrumbs (ride_id, ts, lat, lng, speed, heading,
                  PRIMARY KEY (ride_id, ts))

Driver state (Redis hash, ephemeral):

driver:{id}  -> { status: "available" | "in_ride" | "offline",
                 current_ride_id, last_ping_at }

Critical invariant: a driver appears in drivers:nyc GeoSet only when status = available. The moment they accept a ride, they're ZREM'd from the available set so other riders' queries don't see them.

Deep dive: geospatial indexing — geohash and quadtree.

A naive SELECT * FROM drivers ORDER BY distance LIMIT 5 scans every driver — O(N). With 50K drivers per city at 30 queries/sec = 1.5M scans/sec = death. We need an index that lets us ask: 'give me the K nearest points to (lat, lng)'.

Geohash. Encode (lat, lng) as a base-32 string. The longer the string, the smaller the cell. dr5reg is a Manhattan block; dr5regw3 is a building. Points in the same geohash cell are physically close. To find nearby drivers: query all drivers in dr5reg* (the cell + 8 neighbors for boundary effects). O(log N + K).

Pro: simple, prefix-friendly (B-tree index works), easy to shard by geohash prefix. Con: cells near the equator and poles have different shapes (longitude lines converge); need 8-neighbor queries to handle boundary cases.

Quadtree. Recursively subdivide a 2D area into 4 quadrants until each leaf holds <= K points. To find K nearest: descend to the leaf containing the query point, expand to siblings and parent if needed. Used by Uber's internal geospatial index for years.

Pro: adaptive — dense cities get finer subdivisions than rural areas; natural K-NN. Con: tree mutations are non-trivial when points move (drivers move constantly), so quadtrees need rebuilding or complex updates.

Redis GEO wraps a geohash-sorted set — the practical choice. GEORADIUS in O(log N + K). 50K points in one key, ~5 microsecond query. Production systems use Redis GEO as the hot path, with quadtrees only for offline analytics.

Sharding by city. Each city is its own drivers:{city} Redis key — geographic isolation, no need to share across regions. A driver crossing city limits re-registers in the new city's set.

Deep dive: the dispatch protocol and atomic claim.

When the rider requests a ride, we find K=3-5 nearest drivers and broadcast a ride_offer to each. The challenge: only ONE driver should accept — multiple drivers accepting the same ride is the classic race condition.

Atomic claim via SET NX. When a driver accepts, the Dispatch Service does SET ride:{id}:accepted_driver {driver_id} NX EX 600 (set if not exists, expire in 10 min). Returns 1 = this driver won the ride; returns 0 = another driver beat them. This is a Redis atomic primitive — no two drivers can simultaneously win.

Fallback on no-accept. If no driver accepts within 8 seconds, the offer TTLs out for all drivers. The Dispatch Service expands the search radius (3km -> 5km -> 8km) and retries. After 3 retries with no accept, the ride is cancelled and the rider is told "no drivers available".

Driver acceptance rate. Drivers ignore offers for many reasons — wrong direction, low fare, break time. Real-world acceptance rate is ~30-50%. This is why we broadcast to 3-5 drivers, not 1: we want P(at least one accepts) > 90% in 8 seconds.

Surge pricing. When demand exceeds supply (e.g. 5 PM rush hour, rainy Friday), the system raises the fare multiplier. Goal: (a) incentivize more drivers to log on (supply), (b) reduce ride requests (demand) until they balance. The surge factor is computed per geohash cell every minute based on (requests per available driver). Cap surge at e.g. 3x to avoid PR disasters. Surge multiplier is shown to the rider before they confirm the ride.

Trip state machine. A ride has states: searching -> matched -> en_route (driver heading to pickup) -> arrived -> in_trip -> dropoff -> payment_processing -> completed. Cancellations are possible in searching and en_route (with different cancellation fees). Each transition is a state machine guarded by validation (can't go from completed back to in_trip). Persisted in the rides table status column; subscribers (fare service, notification service, analytics) react to transitions.

Bottlenecks and failure modes.

• Hot geohash cell. A concert ends; 10K riders in one cell request simultaneously. Mitigation: surge pricing kicks in within 1 min; cap concurrent ride-offers per driver (a driver should not get >1 offer at a time).

• Driver position flood. 50K drivers x 1 update/4s = 12.5K writes/sec into Redis. Mitigation: Redis handles 100K+ writes/sec easily; batch updates from mobile gateway (coalesce within 1s).

• WebSocket connection count. 50K concurrent WS connections per city = 50K file descriptors per gateway. Mitigation: horizontal scale gateways; use sticky LB on driver_id for connection affinity; send keepalives every 25s to beat carrier NAT.

• Race condition on accept. Two drivers accept the same ride simultaneously. Mitigation: atomic SET NX on Redis; losers get ride_cancelled via WS.

• Zombie drivers. A driver's phone dies but the server hasn't noticed (last_ping_at < 30s ago). They still appear in drivers:nyc. Mitigation: a reaper that ZREM's drivers with last_ping_at > 30s; we don't offer rides to drivers whose last_ping is stale.

• Redis geo index failure. If Redis dies, all matching stops. Mitigation: Redis cluster with replicas + Sentinel failover; degrade to a DB-backed quadtree (slower) as fallback.

• Driver GPS drift. A stationary driver's GPS reports slightly different positions each ping, causing churn. Mitigation: snap to road (snap GPS to nearest road segment via a road network); hysteresis on position (only update if moved > 30m).

• Surge feedback loop. Too-aggressive surge causes riders to cancel and wait; demand then drops too far; surge cuts; demand spikes again. Mitigation: damp surge updates (exponential moving average); cap surge change per minute.

Scaling strategy and trade-offs.

Per-city isolation. Each city is a self-contained deployment: own Redis cluster, own matching service, own rides DB shard. A failure in NYC doesn't affect SF. Cross-city trips (rare) handled by state migration.

Driver position sharding. Redis GEO is single-key (one set per city). 50K drivers per city is fine; if a city had 1M drivers we'd shard by geohash prefix (drivers:nyc:dr5*). Most cities are fine with a single key.

Read replicas for ride status. Riders check ride status frequently ("where's my driver?"); this is read-heavy. Master for writes, replicas for reads.

Multi-AZ. Redis cluster across 3 AZs with replicas. Rides DB across 3 AZs. WebSocket gateway stateless — any gateway can serve any driver (but we use sticky LB for connection reuse).

Trade-offs made explicit.

• We chose Redis GEO over a custom quadtree — gained simplicity and operational maturity, lost adaptive subdivision (denser cities don't get finer cells). For 50K drivers per cell, fine.
• We chose broadcast-to-K with first-accept-wins over central assignment — gained human decision (drivers can decline bad rides) and resilience, lost optimal global matching (we could have picked the truly-nearest driver but they might be heading home).
• We chose per-minute surge updates — gained predictability, lost responsiveness to sudden demand spikes.
• We chose 4s position update interval — gained low bandwidth and Redis load, lost fine-grained position (driver ETA can be off by a few seconds).
• We chose atomic SET NX for accept — gained simplicity and correctness under races, lost the ability to do batch assignment (could optimize globally with a Hungarian-algorithm batch dispatcher — Uber research did this, but ops complexity).

Mental model. Think of Design Ride Matching as a deliberate boundary in a system. The boundary exists because something becomes harder to manage when everything is done in one place: latency, scale, failure isolation, consistency, cost, or team ownership. The useful question is not “what does Design Ride Matching mean?” but “what pressure makes this boundary worth introducing, and what new failure mode does it create?”

Numerical lens: write down traffic, payload size, read/write ratio, peak multiplier and durability target before choosing a component. The numbers should justify the architecture.

Answer this without notes: When would you choose Design Ride Matching, and when would you intentionally avoid it? Mention at least one bottleneck it addresses, one failure mode it introduces, and one alternative. Then quantify the workload you are designing for.

Numerical sanity check

Back-of-the-envelope reasoning beats fake precision. State your traffic, payload, concurrency and growth assumptions explicitly, then calculate enough to know whether the current architecture is orders of magnitude away from the target.