Two hundred thousand drivers are moving around a city, and every one of their phones reports
where it is every four seconds. A rider opens the app and wants to see the nearest cars.
Thirty seconds later they want exactly one of those cars, promised to them and to nobody else.
Report. Every four seconds each driver app sends its position over a connection it keeps open.
Look at the two halves of that picture. They are two different systems sharing a screen:
The driver half (driver app, gateway, geo index) takes fifty thousand location updates a
second, and it is allowed to lose all of them, because a fresh one arrives four seconds later.
The rider half (rider API, matching, trip store) handles about a thousand ride requests a
second, and it is never allowed to lose one, because a trip is money and a legal record.
driver half, 50,000/sa new position every 4 s,the old one is overwrittenrider half, 1,000/strip t_9f31rider 4471, q_71a2in_progresskeptone durable row per trip,never allowed to lose
Most candidates design the driver half and hand wave the rider half. The rider half is where
the interview is.
The real Uber
This page builds the core of a ride hailing app like Uber: tracking moving drivers, finding the nearest ones, and giving exactly one of them to a rider. The numbers and choices below are interview assumptions, not Uber's own. Where the page says what Uber really does, it says so by name.
Ask about the matching before you ask about the map. Finding nearby points on a map is a
solved problem with a known answer. Deciding which driver gets which rider is where the real
decisions are. Each row below settles one line of the design.
You ask
They say
What it settles
How many drivers are online, and how often do they report position?
A couple of hundred thousand in a large city, every four seconds.
Fifty thousand writes a second into whatever holds locations. That number alone rules out a relational table with a spatial index and pushes you to an in memory grid.
How fresh does a driver location have to be for matching?
Within a few seconds.
Location is soft state. It can live in memory, be lost on restart and rebuild itself in four seconds, which removes durability from the hottest write path in the system.
Can two riders be matched to the same driver?
Never.
A serialisation point per driver, and an offer that locks the driver while they decide. This is the hard requirement, and it is not solved by the geospatial index.
What happens if a driver ignores the request?
Move to the next one, within seconds.
Offers with a short timeout and automatic reassignment, so the matching state machine has a timer in it. It also means a rider is waiting while you try three drivers in sequence.
Does the price change while the rider is looking?
It is quoted up front and honoured.
A pricing service that reads supply and demand per area on a slow loop, and a quote that is frozen into the trip. Recomputing at accept time is how you get a support ticket.
Is a trip record allowed to be lost?
Absolutely not. It is money and it is a legal record.
Two different storage systems with two different guarantees. Locations are disposable, trips are durable and transactional, and confusing the two is the most common mistake in this design.
Location writes a day if you stored them4.3 billion
50,000 writes/sec
against a working set that fits in the memory of one laptop
Those two numbers together are the design. 24MB of live state means the whole city fits in memory, and 50,000 writes a second means you must never touch a disk to record one. The moment somebody suggests persisting every location update, ask what reads it.
Read the last two rows together. Fifty thousand writes a second sounds huge, but the whole
city's live state is about 24 megabytes, smaller than a few phone photos. That pairing
is the design: everything fits in memory, and nothing on the hot path ever touches a disk.
every second: 50,000 to 1,000for every50 location writesinto memory1 ride requestinto a database
The number people get wrong
Candidates size storage for location history and end up designing a time series
database. Nothing in the matching path ever reads a location older than a few seconds.
Keep the live position in memory, and if the business wants trip traces for analytics,
publish them to a log the matching system never queries (the difference between a queue and a
log is in queue vs pub/sub vs event stream). Two
systems, two lifetimes.