The system design question
Drivers' phones send their GPS position every few seconds while they're online. Design the system that takes in those updates and lets other services ask where a driver is right now, or which drivers are in a certain area. Assume millions of drivers around the world.
Agree on the scope (5 minutes)
Say up front what you're covering.
| We'll design | We'll skip |
|---|---|
| Taking in location updates from driver phones | Matching riders with drivers |
| Looking up one driver's latest position | ETAs and routing |
| Finding drivers in an area | Long-term location history analysis |
| Live updates for a rider watching their driver | Maps and road data |
Then agree on what "good" means:
- Fresh: the position we hand out should be a few seconds old at most.
- Fast reads: an area search should come back in tens of milliseconds, since matching waits on it.
- Handles the load: millions of drivers sending updates all the time, with big peaks on Friday nights.
- Okay to lose a little: if we drop one update, the next one's a few seconds away. Nobody needs every single point.
Rough numbers (5 minutes)
These are assumptions, but reasonable ones: 5 million drivers online at a peak around the world, each sending an update every 4 seconds, and each update about 200 bytes on the wire.
- ~1.25M
- updates per second at a peak
- ~250 MB/s
- of incoming data
- ~500 MB
- to hold every driver's latest position
- ~5 TB
- a day if we kept every point
| Question | Rough math | What it means |
|---|---|---|
| How many updates? | 5 million ÷ 4 seconds | About 1.25 million writes a second, way too many for one database |
| How big is the live data? | 5 million × about 100 bytes | Half a gigabyte. Fits in memory on a few machines with room to spare |
| How much history? | About 50 billion points a day × 100 bytes | Around 5 TB a day, so history goes to cheap storage in batches |
| How many open connections? | 5 million ÷ about 50K per server | Around 100 servers just to hold connections |
The overall design (10 minutes)
- The driver app sends its position, the time it was taken, and the driver's status over a connection it keeps open.
- A gateway server checks the update makes sense and drops it onto a stream, split up by region.
- Location store machines read their region's part of the stream and overwrite each driver's latest position in memory, plus which map cell they're in.
- Other services, like matching, ask the store for a single driver or for everyone in an area.
- A separate consumer reads the same stream and writes batches of history to cheap storage for later analysis.
What the apps need to do
| Action | Who does it | What's sent |
|---|---|---|
| Send location | Driver app | Driver ID, latitude, longitude, the phone's timestamp, heading, speed and status |
| Get a driver's position | Internal services | Driver ID, and we return the position and how old it is |
| Find drivers in an area | Internal services | A point and a radius, plus filters like status or car type |
| Watch a driver | Trip service, for the rider's app | Driver ID, and we push each new position as it arrives |
What we store and where
| Data | Where it goes | Why |
|---|---|---|
| Latest position per driver | In memory, split by region | Changes every few seconds, and it's fine to lose |
| Drivers in each map cell | In memory, next to the positions | Area searches need to be quick |
| The raw stream of updates | A message stream, kept a day or so | Lets the store rebuild itself and feeds history |
| Location history | Cheap file storage, written in batches | Analytics and disputes, nobody reads it live |
Step 1: Taking in a million updates a second (10 minutes)
Writing every update to a normal database is where most people get stuck, and you don't need to. Each update makes the last one useless, so the job is really just overwriting one small record per driver.
Driver apps hold a connection open to a gateway server. The gateway does cheap checks, like is this driver logged in and is the point on Earth, and puts the update on a message stream. The stream soaks up spikes and lets us add more readers later without touching the phones.
Split the stream by region, so every update for one area lands on the same partition. A location store machine reads one or more partitions and keeps their drivers in memory. That's sharding by region, and it means an area search almost always hits one machine.
Cutting down the writes
Phones can help. A parked driver doesn't need to send every 4 seconds, so the app can slow down when it isn't moving and speed up when it is. You can also batch on the gateway and only pass on the newest point per driver every second.
Step 2: Answering "who's in this area?" (10 minutes)
Searching by latitude and longitude with a normal index is slow, because you need a range on two columns at once. Instead, cut the map into cells, like hexagons about 1 km across, and keep a list of drivers in each cell. That's geospatial indexing.
When an update comes in, work out the driver's cell. If it's the same as before, just overwrite the position. If they've moved into a new cell, take them out of the old cell's list and add them to the new one. Most updates don't change cells, so most writes are cheap.
For an area search, find the cells that cover the circle, grab every driver in them, throw out anyone we haven't heard from in 30 seconds, and filter by exact distance. That's a few hundred drivers to check at most, which is quick.
- Busy downtown areas: use smaller cells there, so one cell doesn't hold thousands of drivers.
- A search that crosses a region border: the store asks the neighboring region's machine too and merges the results.
- One driver by ID: keep a small lookup from driver ID to region, so you know which machine to ask.
Step 3: Stale, late and lost updates (10 minutes)
Phones go through tunnels and send updates late, or in bursts. Every update carries the time the phone took it, and the store ignores anything older than what it already has. Otherwise a late point could jump a driver back down the road.
Each driver's record has a last-heard time. If it's more than about 30 seconds old, area searches skip them, and after a few minutes we drop them from the cell lists. A phone dying can't leave a ghost driver on the map.
If a store machine dies, a standby takes over its partitions and replays the last minute of the stream. Within a few seconds, everyone's sent a fresh update anyway, so it refills on its own. This is a place where eventual consistency is fine: a slightly old position isn't a bug.
Keeping history without slowing anything down
History is a separate reader on the same stream. It groups updates into files every few minutes and writes them to cheap storage. If it falls behind, nothing live cares.
Choices you should be able to defend
| We chose | Instead of | Because | We'd reconsider if |
|---|---|---|---|
| Latest position in memory | Writing every update to a database | We only need the latest spot, and it's out of date in seconds | We had to answer 'where was this driver at 3:02' instantly, which is a different store |
| Split by region | Split by driver ID | Area searches stay on one machine | Regions got really uneven, then we'd split big cities further |
| A stream between gateway and store | Gateways writing to the store directly | Absorbs spikes, and history and other readers come for free | The extra hop's delay mattered, which it rarely does |
| Fixed hexagon cells | A tree that adapts to density | Simple to build and to explain | Cells in dense areas got too crowded even after shrinking them |
What could go wrong (5 minutes)
| What happens | What we do about it |
|---|---|
| A store machine dies | A standby takes its partitions, replays recent updates, and fresh ones fill it within seconds |
| A gateway server dies | Phones reconnect to another gateway, and we lose a few seconds of updates |
| The stream falls behind | Positions get older. Alert on how far behind it is and add store machines |
| A driver's phone goes quiet | They drop out of searches after 30 seconds, and off the lists after a few minutes |
| A phone sends bad GPS | The gateway drops points that jump impossibly far from the last one |
| A huge event floods one area | Shrink the cells there and move that area to its own machine |
Follow-up questions (5 minutes)
How would you show a rider their driver moving smoothly?
Push each new position to the rider's app as it arrives, and let the app animate between points. The app can also snap the point to the road so it doesn't look like the car's driving through buildings.
What if we needed the last 24 hours of a driver's path quickly?
Add a second store keyed by driver and time, fed from the same stream, keeping a day of points. It's a separate read path, so it can't slow down live searches.
How do you handle drivers that cross between regions a lot?
When a driver's cell belongs to a different region, the old region forwards them and drops its copy. Overlap the borders a little so searches near the edge still work.
How the 60 minutes add up
| Minutes | What you're doing |
|---|---|
| 0–5 | Agree on what you're building |
| 5–10 | Rough numbers |
| 10–20 | Draw the overall design |
| 20–30 | Taking in a million updates a second |
| 30–40 | Answering "who's in this area?" |
| 40–50 | Stale, late and lost updates |
| 50–55 | What could go wrong |
| 55–60 | Follow-up questions |
Key concepts used here
- Geospatial indexingFind what's nearby with map grids like geohashes and H3.
- Message queues and event streamsKeep services from depending on each other, and handle traffic spikes.
- Sharding and consistent hashingSplit data across machines and keep it balanced.
- Consistency and the CAP theoremWhat happens when copies of your data can't agree.
Further reading
We wrote this sample answer ourselves.
Practice Loop is independent and isn't affiliated with or endorsed by Uber.