System design: match riders with nearby drivers

A rider asks for a trip. Find a driver close by and offer it to them. If they say no, try the next one. And a driver can never end up with two trips at once.

You can't design all of Uber in an hour, so say up front what you're covering.

Then agree on what "good" means:

• Fast: the first offer should go out within a couple of seconds.
• Correct: a driver can never be given two trips, and a trip can never get two drivers.
• Keeps running: one machine dying shouldn't stop people getting rides.
• Fresh enough: positions can be a few seconds old. Nobody will notice.

We're making these up, but they're reasonable. Say there are 1 million drivers online at a busy time, each sending their location every 5 seconds, and 10 million trips a day.

200K

location updates per second

~100 MB

to hold every driver's latest position

~120

trip requests per second, on average

~600

trip requests per second at a peak

A few more quick ones are worth doing, because they shape the design:

1. Every driver's app sends its location every few seconds.
2. A rider requests a trip. We save it and put it in a queue.
3. A matching worker grabs the trip and looks up nearby drivers.
4. The worker reserves the closest driver and offers them the trip.
5. If they accept, we're done. If not, the worker tries the next driver.

What the apps need to do

What we store and where

We only keep each driver's latest position, and we keep it in memory. A position is old news in a few seconds, so there's no point carefully saving every update to disk.

To search by location, split the map into a grid of cells about 1 km across, and keep a list of available drivers for each cell. That's geospatial indexing. When a location update comes in, we do three things:

1. Work out which cell the driver is in now.
2. If they've crossed into a new cell, take them off the old list and add them to the new one.
3. Save their position and the time we heard from them.

Most updates don't change a driver's cell, so most of them are a quick overwrite. Only available drivers go on the cell lists. As soon as someone's reserved or on a trip, they come off, so they won't show up in searches.

200,000 updates a second is a lot for one machine, so we split the data across a few machines. Splitting by city is an easy place to start, since a rider and their nearby drivers are almost always in the same city. A huge city can get its own machines.

1. Work out which cell the rider's in.
2. Grab the drivers from that cell and the eight around it. The closest driver might be just over the line.
3. Throw out anyone we haven't heard from in the last 30 seconds, and anyone in the wrong kind of car.
4. Sort by distance and keep the closest five or so.
5. If nobody turns up, check a wider ring of cells, up to a limit.

Straight-line distance is fine to start. If you've got time, point out that the closest driver might be on the other side of a river, so you'd take that shortlist and rank it by estimated driving time. Doing that only for the top few keeps it cheap.

This is where most of your time should go. Two workers could pick the same driver for two different riders at the exact same moment. If a position's a little stale, nobody cares, but assignments have to be right. That's what people mean by consistency.

So we keep each driver's status in a relational database, and a worker reserves a driver with one update that basically says "mark this driver as reserved for this trip for the next 15 seconds, but only if they're still available."

The in-memory lists can be a moment behind, and that's fine. Worst case, a worker tries someone who just got reserved, the update fails, and it moves to the next driver. The database has the final say.

The steps for each trip

1. Try to reserve the first driver on the list. If someone beat you to it, move on.
2. Send the offer and give them 15 seconds.
3. If they accept, assign the trip and you're done.
4. If they say no or don't answer, release them and try the next one.
5. If the list runs out, search further out. After a couple of minutes, tell the rider we couldn't find anyone.

Keep track of where each trip is

A trip can also end as cancelled, or no driver found, and it can go from Offered back to Matching when a driver says no.

Don't make workers sit and wait

Our numbers said there could be 12,000 trips being matched at once, and each is mostly just waiting on a driver. If every worker sat there for 15 seconds, we'd need a huge number of them. So a worker sends the offer, saves the trip's status and a timer, and moves on to something else. When the driver answers or the timer runs out, a worker picks it back up.

Why bother with a queue?

We don't want the rider's request hanging while all this happens. A message queue holds onto each trip until a worker finishes with it, and it helps when everyone leaves a concert at once. A separate queue per city stops one busy city from holding up another.

Getting the offer to the driver

Each driver's app keeps a connection open to our servers, so offers show up right away. If that doesn't work, fall back to a push notification. Riders can have the same kind of connection, or check every few seconds, to see when a driver's been found.

Small things that are easy to miss

• The rider taps twice: the app sends a unique request ID, so the second tap gets the same trip back.
• The rider cancels during matching: check the trip's status before each new offer, and release any reserved driver.
• The driver goes offline during an offer: the 15-second timer handles it, same as no answer.

That 15-second expiry is doing a lot of work. Every reservation ends on its own, so a crash can't leave a driver stuck forever. Because the trip's status is saved, whichever worker picks it up knows exactly where things stand.

What about a rider near the edge of a city?

The nearby cells might live on another city's machines. When a search reaches a border, ask both.

How would you make matches better than just closest driver?

Sometimes it's better to wait a second or two, gather a batch of riders and drivers in an area, and find the best overall pairing. It's slower for any single rider, but cuts total pickup time.

What if we expand to the whole world?

Run this setup separately in each region, so riders and drivers talk to servers near them. Trips rarely cross regions, which makes that pretty clean.

How would you read a heavy dashboard of live trips?

Keep it away from the database doing the matching. Copy changes somewhere else, and add caching for things that get read a lot.

• Geospatial indexingFind what's nearby with map grids like geohashes and H3.
• 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.
• Relational vs non-relational databasesPick a database based on how you'll actually use it.
• Message queues and event streamsKeep services from depending on each other, and handle traffic spikes.
• Caching strategiesMake reads faster, and figure out what to do when data changes.
• Real-time deliveryPush updates to users the moment they happen, with WebSockets and friends.

We wrote this sample answer ourselves. If you want to see how Uber has described parts of its real systems:

• Uber Engineering: H3 geospatial index
• Uber Engineering: Ringpop and tracking driver locations

Practice Loop is independent and isn't affiliated with or endorsed by Uber.