Uber

What the interviewer is asking

"Design Uber" is a favorite system design question because its hard part is unusual. Storing trips is easy; the hard part is that a million phones report where they are every few seconds, and each ride request must find the nearest free driver without ever handing one driver two rides.

Below are the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• Ask for a ride from A to B.
• Match a driver: offer the ride to drivers nearby until one accepts.
• Watch each other live until pickup and during the trip.

Park the rest out loud: surge pricing, payments (a design of its own: the Payment System lesson), ratings, shared rides and rides booked for later. Arrival times come from a maps service (the Google Maps lesson).

2. Data: positions, trips, drivers and riders

record     fields
position   driver_id → lat, lng, time (replaced every 4 s)
trip       id, rider_id, driver_id, status, pickup, dropoff, route
driver     id, name, car, plate, status (available, reserved, on a trip)
rider      id, name, phone

A position is tiny and replaced every 4 seconds: only the newest one matters. A trip is written a few times and kept; drivers and riders change rarely. That decides where each is stored.

3. The API: a WebSocket per app

Half the traffic is the server speaking first: an offer for a driver, "3 min away" for a rider, the car moving on the map. Over plain HTTP the server can only answer, and polling mostly returns "nothing new", so each app keeps a WebSocket open (the Real-Time Updates lesson). The ride request is an ordinary call:

POST /rides  {"pickup": {"lat": 37.7749, "lng": -122.4194}, "dropoff": {…}}
→ 201 Created  {"ride": "r1", "status": "requested"}

Everything else is an event on the open connection (↑ up, ↓ down):

↑ {"type": "position", "lat": 37.7752, "lng": -122.4172}      every 4 s, driver app
↓ {"type": "offer", "ride": "r1", "pickup": {…}}               to one driver
↑ {"type": "accept", "ride": "r1"}
↓ {"type": "ride", "ride": "r1", "driver": "dee", "eta": "3 min"}
↓ {"type": "position", "driver": "dee", "lat": …, "lng": …}   to the rider

A light HTTP call every 4 seconds would work for positions too.

4. The busy path: location updates

A driver online for an hour sends 3,600 ÷ 4 = 900 positions; a rider sends one request per trip. So the busy path is the location updates: writes, not reads, unlike most systems. The second path that has to stay fast reads them: finding the drivers near a pickup.

5. The numbers

From the interviewer: 1 million drivers online at the busiest time, each sending a position every 4 seconds, and about 10 million rides a day. Say an update takes about 100 bytes. A day has 86,400 seconds; round it to 100,000.

what               working
updates            1 million ÷ 4 s = 250,000 writes a second
ride requests      10 million a day ÷ 100,000 s = 100 a second, about 500 at busy hours (5×)
data coming in     250,000 × 100 bytes = 25 MB a second
latest positions   1 million × 100 bytes = 100 MB
every update kept  250,000 × 100 bytes × 100,000 s ≈ 2.5 TB a day

Updates outnumber ride requests 500 to 1. The latest positions, 100 MB, fit in memory with room to spare; keeping every update would pile up terabytes a day (an upper bound: not every hour is the peak), so any history goes elsewhere, off the busy path. The 25 MB a second coming in is small next to the 1 GB a second one server's network carries.

6. Services: a gateway and three services

• Gateway: holds every app's WebSocket and passes messages in and out.
• Location service: saves each driver's newest position and forwards the ones a rider is watching.
• Matching service: takes each ride request, finds the drivers nearest the pickup and offers the ride, closest first.
• Trip service: owns the trip once a driver accepts: pickup, drop-off, the route, the receipt.

Each grows with its own load, and a rush of updates can't slow down matching.

7. Scale: positions in memory

Say one database server takes about 5,000 writes a second: the updates arrive 50× faster, each only replacing the last. Disk writes with copies for a value replaced 4 seconds later make no sense, and a row per update grows by terabytes a day.

So the latest positions go into an in-memory location store, one entry per driver, overwritten on every update. If it restarts, every driver's next update refills it within 4 seconds. Say one in-memory server takes about 100,000 writes a second: 250,000 need at least 3, so the store is split by area of the map (sharding). The trips database keeps trips and drivers' status, a few writes per ride.

8. Deep dive: finding nearby drivers

Checking every online driver means 1 million reads per request: even in memory, at about 100 ns a read, 0.1 s of work per request, and 500 million reads a second at 500 requests a second, nearly all of them drivers in other cities. Sorting by distance still needs every distance, and an index on latitude returns a band of drivers circling the globe.

Instead, split the map into cells of about 1 km, keep a list of the drivers in each, and let every update file its driver under the right cell. A search reads the rider's cell and its 8 neighbors, a 3×3 block, because a driver can be just across the border. In the lesson's map, Ana's own cell is empty while Ben waits about 200 m away in the next one:

driver   cell     distance from Ana   read by the search?
Ben      (2, 3)   0.2 km              yes, the cell to her right
Dee      (3, 2)   1.2 km              yes, the cell below
Cy       (1, 1)   1.4 km              yes, a corner neighbor
Eli      (2, 4)   1.9 km              no, two cells away
Gus      (0, 2)   2.2 km              no, two cells away

Wherever the rider stands in her cell, the block holds every driver within 1 km: 9 short lists instead of 1 million positions. Where it's empty, as in the countryside, the search widens ring by ring.

A common way to name the cells is a geohash: a short code for each square of the map, where each extra character splits the square into 32. Six characters make a cell of about 1.2 km × 0.6 km at the equator. Nearby points usually share a prefix: two points about 200 m apart in downtown San Francisco are both in 9q8yyk, and a point about 500 m north is in 9q8yym. But two points only about 70 m apart on either side of a border get different codes: one more reason to read the neighbors.

Cell size is a trade-off: 10 m cells put 10,000 cells in a square kilometer, and a car at 30 km/h changes cell about every second; 50 km cells hold a whole region's drivers.

9. Deep dive: matching without double booking

The matching service offers the ride to one driver at a time, closest first, and marks that driver reserved while the offer is out, with a timeout of, say, 15 seconds:

time   what happens
0 s    Ben (0.2 km) is reserved and gets the offer
15 s   no answer: Ben is released; Dee (1.2 km) is reserved and gets it
21 s   Dee accepts, and the trip gets its driver

A decline moves the offer on at once; silence waits the full timeout. If Ben declined at 5 s and Dee never answered, Cy would get the offer at 20 s. The closest driver gets the first chance, and nobody taps Accept on a ride that's gone. The price is waiting, so some designs offer to two or three drivers at once and take the first accept, with the same guard as below.

The race: Ana and Kim ask from the same corner at the same moment, and Ben is closest for both. Two matching servers each read "available", write "reserved" and send an offer: two rides for one car. Reading again just before writing only narrows the gap; locking the whole drivers table makes every ride in every city wait in one line. The fix is the conditional update from the Concurrency and Locks lesson:

UPDATE drivers SET status = 'reserved'
WHERE id = 'ben' AND status = 'available';
-- Ana's server: 1 row changed, so it sends the offer
-- Kim's server: 0 rows changed, so it tries Kim's next closest driver

The database runs the two one after the other, so exactly one wins; drivers already on a trip fail the same check.

Once Dee accepts, her position goes every 4 seconds from her gateway server to the location service, which saves it, sees that Ana is waiting for Dee, and sends it to the gateway server holding Ana's WebSocket. That server is found the way a chat message finds its reader: a channel per user, or a lookup of which server holds each connection. Ana's position travels the other way, during the trip too.

10. Deep dive: hot cells

Each server of the store holds the cells of one area. When a concert ends, thousands of fans ask for rides and, say, 600 drivers crowd into the stadium's cell, all on one server: the hot key from the Sharding lesson. Split the hot spot: a cell is the piece the store places on a server, so a cell too busy for one server becomes 4 smaller cells on 4 servers, and a crowded quarter splits again. A quadtree works this way, so downtown gets small cells and the countryside keeps big ones.

Caching the stadium's drivers for a minute serves positions that are stale after 4 seconds. Splitting the store by driver id scatters every neighborhood over every server, so each of the 500 requests a second asks all of them.

What breaks first

• A location store server crashes: its area is blind until the next updates, within 4 seconds; keep a replica if that matters.
• Stale positions: a phone that loses signal stops updating; skip positions older than, say, 30 seconds.
• A late accept: Ben taps Accept just after his 15 seconds. The trip takes only the driver it's offered to now, with the same kind of conditional update.

Summary: the order to follow

1. Scope: ask for a ride, match a driver nearby, watch each other live.
2. Data: positions (replaced every 4 s), trips, drivers and riders.
3. API: a WebSocket per app; POST /rides for a request.
4. Busy path: drivers' location updates, and the search that reads them.
5. Numbers: 250,000 updates a second, about 500 ride requests a second at the peak, 100 MB of latest positions.
6. Services: a gateway, then location, matching and trip services.
7. Scale: latest positions in an in-memory store, split by area.
8. Deep dives: map cells and their 8 neighbors; offers closest first, reserved by a conditional update, then live tracking; hot cells split smaller.

The same pieces carry over to food delivery and any app that tracks moving things: latest positions in memory, neighbors by cells, and one conditional update to decide who gets what.