Design a Ride-Hailing System

Problem Design a ride-hailing system: riders request a ride from a pickup to a drop location, nearby available drivers are matched, the trip is tracked live, and a fare is computed at the end.

Functional requirements

• Rider requests a ride with pickup + destination; sees an ETA and price estimate up front.
• Match a nearby available driver; handle accept / reject / timeout and re-offer.
• Track the trip live on both apps through Requested → Accepted → In Progress → Completed.
• Compute the fare (base + distance + time + surge) and charge at completion.
• Handle cancellation by either party and mid-trip disconnects.

Non-functional requirements

• ~5M drivers, ~100M riders, ~20M trips/day → ~230 trips/sec average, ~1,000/sec at peak.
• ~1M drivers online concurrently at peak pinging every 4 s ≈ 250k location writes/sec.
• Nearby-driver query p99 < 100 ms; match offer delivered to a driver in < 2 s.
• Location freshness on the rider's map < 5 s.
• Trip state and payment must be durable and exactly-once; location data can be lossy.

Key components

• Location service: ingests driver GPS pings through a queue, writes the current position to an in-memory geo store, and publishes to a regional pub/sub so only interested subscribers receive updates.
• Geospatial index: geohash / S2 cells / quadtree over online drivers, supporting "drivers within radius R of point P".
• Matching service: on a request, queries the geo-index, ranks candidates (proximity, ETA over the road network, driver idle time, acceptance rate), offers with a timeout, and falls through to the next candidate.
• Trip service: owns the trip state machine, persisted in a store sharded by trip_id, emitting state events.
• Pricing service: fare computation plus a surge service tracking demand/supply imbalance per zone on a short rolling window.
• Notification/streaming layer (WebSocket) pushing driver location and trip state to the apps.

Deep dives / trade-offs

• Geo-indexing choice: geohash is simple and prefix-searchable but has edge effects — two nearby points can sit in different cells, so you must query neighbouring cells. Quadtrees adapt to density (dense cities vs empty highways) but are costlier to update at 250k writes/sec. S2 gives uniform-ish cells on a sphere. The write rate, not the read rate, usually decides this.
• Matching policy: nearest-driver minimizes pickup ETA but starves drivers on the edge and can churn a driver's position. Least-idle-driver is fairer and improves retention but raises average pickup time. Batched matching over a few seconds beats greedy on global efficiency at the cost of latency.
• Location scale: batch pings, do not persist every ping to durable storage, keep the hot position in memory with TTL, and regionally partition pub/sub — a rider in Delhi must not subscribe to a global stream.
• Straight-line vs road-network ETA: haversine distance is cheap and wrong; a routing engine with live traffic is accurate and expensive. Discuss using haversine to prefilter candidates and routing only for the shortlist.
• Disconnects: driver app loses network mid-trip — how do you distinguish "offline" from "trip abandoned", and how does the client reconcile state on reconnect (event replay from last-seen sequence number)?
• Surge: computing multipliers per zone creates cliff effects at zone boundaries and can oscillate; discuss smoothing and hysteresis.