System design practice

Ride Matching

medium geo caching write-heavy resilience

100k location updates per second into a geo store, not a database.

Solve it in your browser Read the lesson first

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

Use these use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.

Scale

Constraints

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.

Start designing

Lesson · 12 min read

Learn it: Ride Matching #

Ride matching: a live map of 400,000 moving drivers #

What you'll learn #

The problem, explained #

The dispatch core of a ride-hailing app like Uber or Lyft, with two kinds of users:

The non-functional requirements:

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:

Back-of-the-envelope #

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
FlowRateKind of operation
Location updates100k rpsoverwrite one key per driver
Geo searches (every ride request)2k rpsread: nearest within 3 km
Trips created (95% of requests)1.9k rpsdurable, strongly consistent insert
Offers to drivers1.9k rpsasync 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.

Concepts #

Geospatial indexing #

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.

IndexHow it worksStrength
GeohashInterleaves 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
QuadtreeSplits 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.

Ephemeral state versus the record #

Positions and trips look like "driver data", but they have opposite needs:

Driver positionTrip
Write rate100k/s1.9k/s
Value of old datanone after a few secondsbilled and audited for years
On lossthe next update in 4 s fixes itmoney and trust lost
Consistencylatest winstwo 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]   x2
live   "Live state" [Redis]      x3 "Latest value per key, overwritten"
record "Records"    [PostgreSQL] x2 "Durable, strongly consistent"
app -> live   : SET
app -> record : SQL

Asynchronous hand-off with a queue #

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 publishes RideOffered 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] x2
events "Events" [Kafka]    x2
worker "Worker" [Service]  x2
user   -> api
api    -> events : produce
events -> worker : consume

usecase "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.

Designing it step by step #

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).

Common mistakes #

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:

In the interview #

Separate the two kinds of state, and justify each store by its numbers.

Likely follow-ups:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems