Design a ride-hailing dispatch system with surge pricing

Questions first. One city or many? Which products: solo rides only, or pooled rides and scheduled rides too? How often do drivers report a location, and how stale may a position be before we ignore it? Is surge a rider-visible multiplier quoted before the request? Is there a regulatory cap on it? What should the rider see while waiting: the nearest cars on a map, an estimate, or only a spinner?

Scope I will assume: solo rides, one request at a time per rider, per-area surge shown as a quote before confirmation, drivers pinging every 4 seconds. Out of scope: pooling, payments, driver payouts, map routing internals (I treat the estimate service as a black box that returns travel time).

Planning figures for the exercise, not facts about any company.

• Requests: 5 million trips a day, 5 × 12 = about 60 a second on average, 300 a second at a 5x peak.
• Driver pings: 500,000 online drivers, one ping each 4 s: 500,000 ÷ 4 = 125,000 writes a second. That is 25x the 5,000 a second one relational primary takes, so locations live in memory, sharded. At 100 B a ping, 125,000 × 100 B = 12.5 MB a second.
• Latest positions: 500,000 × 100 B = 50 MB, so write rate, not memory, is the constraint. Over 16 nodes that is 125,000 ÷ 16 = about 7,800 writes a second each.
• Matching lookups: 300 requests × 7 cells (own plus 6 neighbours) = 2,100 reads a second. Trivial.
• Nearby-cars map: 100,000 riders refreshing every 5 s is 20,000 reads a second, at the 20,000 line, so serve it from a per-cell snapshot cache with a 2 to 3 s TTL.
• Surge: 50,000 cells a minute is about 830 updates a second. Small.
• Offers: at a 50% accept rate, 2 offers per trip on average, so about 2 × 15 s = 30 s of waiting on average if every decline runs to the timeout.

The location stream is the load, not matching: shard it in memory by cell, keep trips on a separate consistent store, and keep each city in one region (coast to coast is 60 to 70 ms).

1. Location service. Drivers send (driver_id, lat, lng, heading, ts) over a persistent connection. The service maps the point to a cell id in a hierarchical grid (hexagons, S2 cells or geohash all work) and writes into an in-memory store sharded by cell, with each driver's entry carrying a TTL of about 15 s so a silent driver drops out. When a driver crosses a cell boundary, the old cell entry is removed. A copy of every ping goes to a log for analytics and replay; the in-memory store is rebuilt from fresh pings in a few seconds after a node loss, so no durable write is on the hot path.
2. Shard layout. Shard by a coarser parent cell, not the fine cell, so a rider's cell and its neighbours usually sit on one node. Without this a lookup fans out to up to 7 shards. Use consistent hashing with virtual nodes so adding a node moves a fraction of cells.
3. Driver state. A separate small store keyed by driver_id: available, offered (with an offer id and lease expiry), on_trip, offline. Changes are compare-and-set: available to offered only if the state is still available.
4. Trip store. Relational, sharded by trip_id: trips(trip_id, rider_id, driver_id, state, quote_id, price_minor, version). The rider's app sends a request id and the trip id is derived from it, so a retry lands on the same shard and row and never creates a second trip.

Request path. The rider asks for a quote: the surge service reads the multiplier for the pickup cell and returns it with a quote_id valid for about 2 minutes, stored with the price. The rider confirms with that quote id. Dispatch for that cell reads the cell and its ring of neighbours, drops drivers whose last ping is older than about 10 s, takes the 5 to 10 nearest by straight-line distance, asks the estimate service for road travel time, and ranks by it. It then offers the trip to the best driver with a 15 s timeout via a compare-and-set to offered. Accept moves the driver to on_trip and the trip to ASSIGNED, each as a conditional update. A decline or timeout releases the lease and moves to the next candidate. After a few misses, widen the ring.

Surge. Request events and available-driver counts are keyed by cell and aggregated in one-minute tumbling windows by a stream job. Raw ratio of demand to supply is noisy, so the multiplier uses a smoothed ratio (average with the previous window and the neighbouring cells), is rounded to steps of 0.1, is capped, and only moves by a limited amount per window so riders do not see wild swings. The result is written to a key-value store as surge:{cell} with a TTL of about 2 minutes, so a dead stream job makes the surge expire to 1.0 instead of freezing a high price.

Hard problem 1: double assignment. Two requests can pick the same nearby driver at the same instant. The compare-and-set on the driver record means one wins and the other simply moves to its next candidate. Location data is allowed to be eventually consistent (a few seconds stale is fine); the assignment decision is not.

Hard problem 2: hot cells. A stadium emptying makes one cell carry thousands of requests while neighbouring shards idle. Split hot cells to a finer resolution dynamically, and let the dispatch tier move cell ownership between nodes. Hashing cannot fix this because the load really is in one place.

• Nearest-first vs batched matching. Greedy nearest-first answers instantly but can strand a far rider. Collecting requests for a couple of seconds and solving an assignment across all riders and drivers uses supply better but adds delay. Pick greedy to start; flip to batching in dense areas where many requests per cell arrive every second.
• One offer at a time vs several at once. Sequential offers never waste a driver's attention but average about 30 s to a match at a 50% accept rate if declines run to the timeout. Offering to three at once is faster and burns offers. Pick sequential; flip to parallel offers when supply is thin and the first accept matters more than fairness.
• Fine vs coarse surge cells. Fine cells track a block-level shortage but flicker and invite drivers to game boundaries. Coarse cells are stable but price unfairly across a large area. Pick medium cells with smoothing from neighbours; flip finer where data is dense and the price is stable.
• Memory-only locations vs a durable store. In-memory loses state on a node failure but recovers within a few ping intervals, and it handles 125,000 writes a second cheaply. A durable store protects nothing you need. Pick memory with a log copy; flip only if a feature needs location history in the request path.

• Writing driver pings to the main database. 125,000 a second is 25x its write limit.
• Skipping the spatial index, or naming one without the resolution trade-off or the hot-cell problem.
• Letting two requests take one driver, with no compare-and-set or lease.
• Using stale positions. No TTL means an offline driver is offered trips.
• Surge as a raw ratio. Noisy, uncapped, no TTL, and re-quoted after the rider has already seen a price.
• Global dispatch across regions, ignoring round-trip times.
• Demanding strong consistency everywhere instead of only on assignment.
• Never saying how a stalled stream job fails, so a stuck surge value persists.