Design the dispatch core of a ride-hailing app. Drivers' phones report where they are every few seconds; when a rider asks for a ride, the system finds the nearest free driver, creates the trip and offers it to that driver.
Functional requirements
Update location: an online driver's app sends its position (lat, lng, heading) every 4 seconds. Only the latest position matters.
Request ride: a rider asks for a ride from a pickup point. Model it with two scenarios:
"Matched": a free driver is within 3 km. The trip is created and stored, the rider gets 201 with the trip and the driver, and the driver receives the ride offer through a queue.
"No driver nearby": nobody is free within 3 km; the rider gets 404 and no trip is created.
Use these use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.
Scale
400k drivers online at peak, one update every 4 seconds: 100k rps of location updates.
Ride requests: 2k rps at peak; 5% of them find no driver.
Constraints
p99 of a location update under 50 ms; of a ride request under 300 ms.
Ride requests available 99.9% of the time.
A trip is never lost once the rider was told about it, and it lives in a database (it is billed and audited later).
Location updates are writes (GEOADD), and they must not reach the database: a relational database takes about 5k writes per second on its primary, and read replicas add no write capacity; only shards do, at the price of a whole cluster each.
The trip is the driver's lock: it is stored in a strongly consistent database (a relational one, not an eventually consistent NoSQL table), so two riders racing for one driver cannot both win.
The ride offer goes to the driver through a queue; the rider never waits for it.
Losing any single machine, including a node of the store that holds the driver locations, must not stop matching.
At most $10,000 / month.
What is given
problem.proschi declares the rider and the driver and holds the traffic, requirements and tests. Add the components, the connections and the two use cases.
How your design is checked
You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.
The dispatch core of a ride-hailing app like Uber or Lyft, with two kinds of users:
Drivers keep the app open while online, and every 4 seconds the phone reports its position (lat, lng, heading). That is the Update location use case. Only the newest position matters; matching needs no history.
Riders ask for a ride from a pickup point: Request ride, with two outcomes. "Matched": a free driver is within 3 km, so a trip is created and stored, the rider gets 201 with the trip and driver, and the driver gets the offer through a queue. "No driver nearby": nobody is free within 3 km, the rider gets 404, and no trip is created.
The non-functional requirements:
p99 (the latency 99% of requests beat) under 50 ms for a location update, 300 ms for a ride request.
Ride requests available 99.9% of the time.
A trip is never lost once the rider was told about it, and lives in a database (it is billed later). It also acts as the driver's lock (two riders must not get the same driver), so the store is strongly consistent.
The offer goes through a queue.
Losing any machine, a node of the location store included, must not stop matching.
At most $10,000 a month.
The given declares the two actors, the requirements, the tests and the traffic: 100k location updates a second and 2k ride requests a second, 5% of which find nobody. Everything else is yours.
The tests encode four ideas:
Location updates start at the driver, write a cache-kind store (the live map) before answering, and never call a database.
Every ride request searches the live map, does so before touching any database, and the "No driver nearby" case never reaches a database and answers 404.
A matched ride writes a strongly consistent database before answering 201.
The matched ride sends to a queue but never waits for it.
400k drivers ÷ 4 s = 100k writes a second. Ride requests are 2k a second, 50 times fewer. That asymmetry is the whole problem.
location writes
100k/s
geo searches
2k/s
trips and offers
1.9k/s
live-map nodes to survive a failure
3
gateway replicas at 70% busy
≈ 72
Flow
Rate
Kind of operation
Location updates
100k rps
overwrite one key per driver
Geo searches (every ride request)
2k rps
read: nearest within 3 km
Trips created (95% of requests)
1.9k rps
durable, strongly consistent insert
Offers to drivers
1.9k rps
async message
Could a relational database take the locations? The simulation's PostgreSQL takes 5k writes a second on its one primary; read replicas add no write capacity. 100k ÷ 5k = 20 shards at 100%, closer to 30 with headroom, each at least two replicas at $400. The bare minimum costs $16k a month, for data stale four seconds after it is written.
An in-memory geo store. Redis takes about 100k operations a second per node in the model; the store sees 100k updates + 2k searches ≈ 102k. Two nodes run at about 50% each, but "survive any node failure" re-runs the analysis with one node fewer: 102k against 100k, saturated. A third node keeps the two survivors below 100%.
The connection tier dominates the bill. Every update passes through whatever accepts driver connections. A service replica takes about 2k rps in the model: 100k ÷ 2k = 50 replicas at 100%, about 72 at 70%, and you want to stay below 70% with one lost, too. At $100 a replica, that is most of the $10k budget.
Trips. 1.9k inserts a second against one PostgreSQL primary (5k) is under 40%. A single primary with a replica for failover is enough; no sharding for this part.
Latency. A location update is load balancer → gateway → one GEOADD: about ten milliseconds on average, a p99 in the tens, under 50 ms if the gateways are not overloaded. A matched ride is load balancer → matching service → GEOSEARCH → INSERT → enqueue, and the response; the async enqueue counts its own hop, not what the consumer does later.
Separate indexes on lat and lng cannot answer "drivers within 3 km": a B-tree range-scans one dimension, not a circle. Geospatial indexes map 2D space onto something an ordinary index handles.
Index
How it works
Strength
Geohash
Interleaves the bits of latitude and longitude into a string. A shared prefix means the same rectangular cell, so "nearby" is "same prefix", plus neighbouring cells for edges.
Simple; fits any key-value store
Quadtree
Splits a square into four, recursively, until each leaf holds few points.
Adapts to density (tiny cells in Manhattan, huge in the desert); needs rebalancing as drivers move
S2 (Google)
Projects the sphere onto a cube and numbers cells along a space-filling curve: a 64-bit id per cell, at many resolutions. Uber's early dispatch used S2 cells to shard supply and demand.
Cells of nearly equal area anywhere on Earth; tight coverings of a circle
H3 (Uber, open source)
Hexagons, whose neighbours are all the same distance from the centre, so rings of nearby cells and smoothing are simpler than with squares.
Best for analytics and pricing over areas
Redis's GEO commands keep points in a sorted set scored by a 52-bit geohash; GEOSEARCH … BYRADIUS 3 km ASC returns members within a radius, nearest first. In an interview, name one index, explain cells plus neighbours, and move on.
Positions and trips look like "driver data", but they have opposite needs:
Driver position
Trip
Write rate
100k/s
1.9k/s
Value of old data
none after a few seconds
billed and audited for years
On loss
the next update in 4 s fixes it
money and trust lost
Consistency
latest wins
two riders must not get one driver
Positions go to an in-memory, overwrite-in-place store: one entry per driver, replaced by every update. Drivers who stop reporting must drop out; Redis cannot expire a single member of a geo set, so keep a last-seen time per driver and sweep stale members, or rotate sets by time bucket. Trips go to a durable, strongly consistent database, written before the rider hears back.
When not to split. If positions must be kept for compliance or route replay, also stream them to cheap storage asynchronously, but never make matching wait on that.
title"Hot state in memory, records in a database"app "App"[REST API] x2live "Live state"[Redis] x3 "Latest value per key, overwritten"record "Records"[PostgreSQL] x2 "Durable, strongly consistent"app -> live : SETapp -> record : SQL
The offer must reach the driver's phone, connected to some gateway node. Calling that gateway synchronously would make the rider wait for the push, and fail whenever the gateway is busy. Instead, the matching service publishesRideOffered d7 to a queue and answers the rider; a consumer delivers the offer to the driver's connection.
In Proschi, ->> is an asynchronous send: the hop counts once for the sender, but nothing after it delays the response.
Deep dive Fire and forget in Proschi
title"Fire and forget"user "User"[Actor]api "API"[REST API] x2events "Events"[Kafka] x2worker "Worker"[Service] x2user -> apiapi -> events : produceevents -> worker : consumeusecase"Do something" { user -> api : POST /things api ->> events : ThingHappened events ->> worker : ThingHappened api --> user : 202}
When not to use it. When the caller needs the result. The rider needs the trip id (from the database, synchronous), not proof the push was delivered.
1. Scope. You are designing matching, not pricing, ETAs, payments or the trip lifecycle. Confirm the update interval (4 s), the fleet size (400k online at peak), the search radius (3 km) and that a confirmed trip never disappears. Derive the 100k writes a second out loud: it shapes everything.
2. High level. Drivers keep a long-lived connection (a websocket) to a gateway tier behind a load balancer, which takes updates and pushes offers. Riders call a matching service over HTTPS. Three stores: the live map, the trips database, and a queue for offers. Draw both use cases as sequences.
3. Deep dive.
Where positions live. Count the naive design (UPDATE drivers SET lat, lng): dozens of database shards. Propose an in-memory geo index: GEOADD (overwrite one member, about a millisecond) and GEOSEARCH (radius, nearest first). Partition by city or geo cell when one node's memory or throughput runs out; the model spreads load evenly over replicas, so you only need enough of them.
Survive a failure. Show the n − 1 arithmetic. A lost node loses at most a few seconds of positions, restored by the next round of updates: why memory is acceptable here and not for trips.
Matching and the lock. Search, pick the nearest candidates, and insert the trip with a uniqueness rule on the driver's active trip, in a strongly consistent store, before responding. If another rider just got that driver, try the next candidate.
The offer. Publish to the queue with an async send; the gateway holding the driver's connection consumes and pushes.
Sizing. The gateways carry 100k updates a second and cost the most: size them to stay under about 70% busy with one replica lost, and no further. Everything else is small.
4. Wrap up. Mention what you skipped: drivers declining offers (timeouts, re-offer to the next driver), surge pricing by cell, batching riders and drivers for globally better matches instead of greedy nearest-first, and multi-region (cities are natural partitions).
Locations in the database (wrong/locations-in-database). The starter does this, and it feels natural: drivers are rows, so update the row. 100k writes a second land on a PostgreSQL primary built for 5k, which saturates and drags down both use cases. Caught by "Location updates are writes to the live map, never the database" and p99 of Update location < 50 ms.
Locations in a heavily sharded database (wrong/locations-in-sharded-database). The fix if you only look at utilisation: 22 shards. The writes fit, but at 93% busy the database still breaks both p99 limits, and it costs about $26k a month, over 2.5 times the budget, for data nobody needs to keep. Caught by the same flow test and cost ≤ $10,000/month.
The ride request waits for the offer queue (wrong/request-waits-for-offer-queue). A synchronous publish with an ack adds latency and couples the rider's success to the queue and, in real systems, often to the downstream push. Caught by "The driver's offer never holds up the rider".
Trips in an eventually consistent NoSQL table (wrong/trips-in-nosql). Scales nicely, but a lagging read can show a driver as free right after another rider got them: two trips for one driver. Caught by "Trips are stored strongly before the rider hears back".
Classic mistakes beyond the tests:
Two live-map nodes "for redundancy" that cannot carry the load alone after one fails.
Searching only the rider's own geohash cell and missing a driver 50 m away across the cell boundary.
Polling for offers from the driver app instead of pushing over the open connection.
Keeping every position forever in the hot store, instead of removing stale drivers and archiving asynchronously.
Separate the two kinds of state, and justify each store by its numbers.
Likely follow-ups:
A Redis node dies; what is lost? At most a few seconds of positions on that node; drivers resend within 4 s, and matching continues on the survivors (hence three).
How do you avoid offering one driver to two riders? The trip insert is the lock (a unique constraint on the driver's active trip, strongly consistent); the loser retries with the next candidate.
A driver ignores the offer. The offer carries a deadline; on timeout, release the driver and offer the trip to the next candidate.
How would you shard the live map at 10× scale? By region or by geo cell (geohash prefix, S2 or H3 cell), with searches fanning out to the neighbouring cells. Cities are natural boundaries.
Why not let the database's geo extension do it (PostGIS)? It answers the search well, but every update is still a durable write on a primary; the write rate, not the query, is the problem.
Alex Xu and Sahn Lam, System Design Interview – An Insider's Guide, Volume 2, chapters "Proximity Service" and "Nearby Friends" — geohash, quadtrees and moving-location updates in depth.