These are the notes for System Design episode 32, our sixth full design problem. Asha gets off the train at 9 pm, opens the app and taps Book. Around her, thousands of cars are online and every one of them is moving. Within seconds one nearby driver must get the offer, and that driver must never be given to two riders at once. Today you design ride matching: you'll write the requirements, find that checking every driver costs 1 billion distance checks a second and cut the city into grid cells instead (200,000 → 4,487 checks for the same answer), see why square cells are uneven and hexagons have just one distance to every neighbour (Uber's H3), handle 75,000 location pings a second by keeping only the latest position, in memory, discover that the closest car on the map can take 22.2 minutes while another takes 6.3 and match by ETA, and watch two riders get the same driver (DOUBLE BOOKED!) before fixing it with an atomic claim. Every demo is plain Python and runs as-is; outputs are real (Python 3.13). The city size, driver counts, bookings per second, speeds and road distances are our own assumptions for the exercise; the real-world facts come from the sources at the end.
Ride matching means pairing a rider who wants a trip with one suitable free driver, quickly. Example: you tap Book in Uber or Ola and a driver 3 minutes away gets the offer.
The problems
| Problem | What it teaches |
|---|---|
| Asha at the station, 9 pm | Requirements: a driver in seconds, fresh locations, huge scale, one driver per ride |
| Checking every driver | Linear scan vs a grid of cells (a spatial index) |
| Squares are uneven | Hexagon cells; Uber's H3 and its resolutions |
| 75,000 pings a second | A live location store: latest only, in memory, indexed by cell, split across servers |
| Closest isn't fastest | Straight-line distance vs road distance; matching by ETA |
| Two riders, one driver | Race conditions; an atomic claim (check and set in one step) |
| Put it all together | Driver apps → location service → matcher → offer → trips database, plus the live map |
Problem 0: Asha at the station (requirements)
Requirements are the list of what the system must do and how well, written before any design. Example: "a rider gets a driver within a few seconds".
Functional requirements (what it does):
- The rider taps Book → a nearby free driver gets the offer.
- The driver accepts → both see each other live on the map.
Non-functional requirements (how well it works):
- Fast: a match in a few seconds.
- Fresh: driver locations change every few seconds, because cars keep moving.
- Huge: hundreds of thousands of drivers online (our assumption for the demos: 200,000 to 300,000 in one big city).
- Correct: one driver, one ride, never double booked.
A few words first:
- A driver is online when his app is open and he is ready to take rides. A free driver is online and not on a trip or holding an offer.
- An offer is the ride request sent to one driver's phone; he can accept or let it time out.
- Double booking means one driver is given to two riders at the same time. Example: D7 is sent to both Asha and Ravi.
Problem 1: checking every driver (grid cells)
The obvious way first: look at every driver and keep the closest. A linear scan means checking every item in a list, one by one. Example: reading all 200,000 drivers to find one.
import math, random
random.seed(32)
CITY = 20 # a 20 km x 20 km city
drivers = [(random.uniform(0, CITY), random.uniform(0, CITY))
for _ in range(200_000)] # 200,000 drivers online
rider = (10.3, 7.8) # Asha, waiting at the station
def nearest_scan(r):
checked, best = 0, None
for d in drivers: # look at EVERY driver
checked += 1
if best is None or math.dist(r, d) < math.dist(r, best):
best = d
return best, checked
best, checked = nearest_scan(rider)
print(f"nearest: {math.dist(rider, best):.3f} km away, checked {checked:,}")
requests_per_sec = 5_000 # bookings across the city
print(f"distance checks per second: {checked * requests_per_sec:,}")
Output:
nearest: 0.023 km away, checked 200,000
distance checks per second: 1,000,000,000
math.dist(a, b)is the straight-line distance between two points (as the crow flies, ignoring roads). Example: from (0, 0) to (3, 4) is 5.- It finds a driver 23 metres away, but it checked all 200,000. If 5,000 people book every second (our assumption), that's 200,000 × 5,000 = 1,000,000,000 distance checks a second, for one city.
- A driver 15 km away can never be the answer, yet we checked him anyway. We need to look only near Asha.
Real life: finding a friend in a stadium
| A cricket stadium | Ride matching |
|---|---|
| Check all 50,000 seats, one by one | Scan every driver: 200,000 checks. Far too slow |
| "Block C, near gate 4": go straight to block C | Grid cells: the city cut into 1 km squares. Look only nearby |
| Each block's seat list: who sits where | Cell index: cell → drivers inside it. A small list to check |
- A grid is the map cut into equal squares, like graph paper. A cell is one of those squares. Example: with 1 km cells, the point (10.3, 7.8) km is in cell (10, 7).
- An index is an extra structure that takes you straight to the data you want without scanning everything. Example: a book's index takes you from "HLS" to page 54.
- A spatial index (or geo index) is an index by location: from an area, straight to the things inside it. Our
cellsdictionary (cell → list of drivers) is one; this kind is often called a geo grid. - Neighbouring cells are the cells touching yours. With squares there are 8 (left, right, up, down and the 4 corners), so with yours you search a 3 × 3 block of 9 cells.
import math, random
random.seed(32)
CITY, CELL = 20, 1 # 1 km x 1 km cells
drivers = [(random.uniform(0, CITY), random.uniform(0, CITY))
for _ in range(200_000)]
rider = (10.3, 7.8)
def cell_of(p):
return (int(p[0] // CELL), int(p[1] // CELL))
cells = {} # cell -> drivers inside it
for d in drivers:
cells.setdefault(cell_of(d), []).append(d)
def nearest_grid(r):
cx, cy = cell_of(r)
nearby = [d for dx in (-1, 0, 1) for dy in (-1, 0, 1)
for d in cells.get((cx + dx, cy + dy), [])]
return min(nearby, key=lambda d: math.dist(r, d)), len(nearby)
best, checked = nearest_grid(rider)
print(f"nearest: {math.dist(rider, best):.3f} km away, checked {checked:,}")
print("cells in the city:", len(cells))
Output:
nearest: 0.023 km away, checked 4,487
cells in the city: 400
cell_ofturns a position into its cell://divides and rounds down, so 10.3 // 1 = 10.0 andintmakes it 10.cells.setdefault(key, []).append(d)puts each driver into his cell's list once, creating the list the first time.cells.get(key, [])returns the cell's list, or an empty list if that cell has no entry (an empty cell, or outside the city). Square brackets would crash there (see Common mistakes).- The same driver, 23 metres away, but 4,487 checks instead of 200,000: about 45 times less work for the same answer. A 20 × 20 km city has 400 cells of 1 km.
- If the 9 cells are empty, search one ring further out: a ring is the next layer of cells around the block you already searched (the 5 × 5 block, then 7 × 7, and so on). See Practice 5.
You just invented a geo grid, a spatial index. Two other well-known spatial indexes (general textbook knowledge, not used in the demos):
- A geohash turns a latitude and longitude into a short string, where nearby places usually share the same starting letters. Example: two points in the same neighbourhood might both start with
tdr1, so "everyone in this area" becomes "every key starting withtdr1". - A quadtree splits the map into 4 squares, then splits any square with too many points into 4 smaller ones, and so on. Example: a busy city centre ends up with many tiny squares, an empty field with one big one.
Problem 2: squares are uneven (hexagons and H3)
Real life: tiles on a floor
| Floor tiles | Map cells |
|---|---|
| Square tiles: side neighbours close, corner ones far | Square cells: 8 neighbours, 2 distances. Uneven |
| A honeycomb: every neighbour shares a side | Hexagon cells: 6 neighbours, 1 distance. Even all round |
| Big tiles made of small ones: zoom in or out | Resolutions: each finer level about 1/7 the area. Uber's H3 has 16 |
- A hexagon is a six-sided shape, like a honeycomb cell. Hexagons fit together with no gaps.
- The centre-to-centre distance is how far your cell's middle is from a neighbour's middle. It tells you how far "one cell away" really is.
import math
# square cells: the 8 cells around you, centre to centre
square = [(dx, dy) for dx in (-1, 0, 1) for dy in (-1, 0, 1)
if (dx, dy) != (0, 0)]
print("square neighbours:", len(square))
print(" distances:", sorted({round(math.hypot(x, y), 2) for x, y in square}))
# hexagon cells: the 6 cells around you, centre to centre
hexes = [(math.cos(math.radians(a)), math.sin(math.radians(a)))
for a in range(30, 360, 60)]
print("hexagon neighbours:", len(hexes))
print(" distances:", sorted({round(math.hypot(x, y), 2) for x, y in hexes}))
Output:
square neighbours: 8
distances: [1.0, 1.41]
hexagon neighbours: 6
distances: [1.0]
math.hypot(x, y)is the length of the line from (0, 0) to (x, y). The{...}set keeps each distance once.- Squares: 8 neighbours at 2 distances (1 for the side cells, 1.41 for the corner ones). Hexagons: 6 neighbours, all at exactly 1.
- For hexagons, the centres of the 6 neighbours lie on a circle around yours (at 30°, 90°, 150°, ... using
cosandsin), so "one cell away" means the same distance in every direction.
Why it matters: when you say "search the cells around Asha", squares reach further towards the corners than towards the sides; hexagons reach evenly. Uber's engineering blog on H3 says: "hexagons have only one distance between a hexagon centerpoint and its neighbors', compared to two distances for squares or three distances for triangles", and that this matters because "people in a city are often in motion".
- H3 is Uber's hexagonal hierarchical spatial index: a grid of hexagon cells covering the whole Earth, made open source. Uber: "We use a grid system to bucket events into hexagonal areas, in other words, cells."
- A resolution is one cell size in a grid that comes in several sizes. Hierarchical means the sizes are levels: each finer level splits cells into smaller ones. "H3 supports sixteen resolutions", and each finer resolution has cells with one seventh the area. Example: a coarse resolution to count a whole neighbourhood, a fine one to place a car on a street.
- Surge pricing means raising the price where many riders want cars and few cars are free. Supply is free drivers; demand is riders asking for trips. Uber: "we calculate surge pricing by measuring supply and demand in hexagons."
You just invented hexagonal cells!
Problem 3: 75,000 pings a second (a live location store)
Real life: the map is always moving
| Step | What happens |
|---|---|
| Every driver's phone sends its location every 4 seconds | Uber's real design (InfoQ: "the driver's phones post location updates to the server every four seconds") |
| Save every ping as a new row in a normal database | 270 million rows an hour, and we need only the last one |
| Overwrite one entry per driver, in memory | Small and fast: latest only |
- A location ping (location update) is one small message from the driver's phone: "I'm driver D7 and I'm at (x, y) right now".
- A row is one record in a database table. Example: (D7, 3.9, 4.2, 9:00:04 pm).
- In memory means the data is kept in the server's RAM (fast to read and write, but lost if the server restarts), not on disk. Example: a Python dictionary, or an in-memory store like Redis.
- Overwrite means replacing the old value with the new one instead of adding another. Example:
latest["D7"] = new_position.
ONLINE, EVERY = 300_000, 4 # drivers online, seconds per ping
print(f"location pings per second: {ONLINE // EVERY:,}")
print(f"rows per hour if we keep them all: {ONLINE // EVERY * 3600:,}")
latest = {} # driver -> (cell, x, y)
in_cell = {} # cell -> set of drivers
def ping(driver, x, y):
cell = (int(x), int(y))
old = latest.get(driver)
if old and old[0] != cell: # crossed into a new cell
in_cell[old[0]].discard(driver)
in_cell.setdefault(cell, set()).add(driver)
latest[driver] = (cell, x, y) # overwrite: keep only the newest
ping("D7", 3.9, 4.2)
ping("D7", 3.95, 4.3) # 4 seconds later, same cell
ping("D7", 4.02, 4.4) # crossed the line
print("D7 stored once:", latest["D7"])
print("cell (3, 4):", in_cell[(3, 4)], " cell (4, 4):", in_cell[(4, 4)])
Output:
location pings per second: 75,000
rows per hour if we keep them all: 270,000,000
D7 stored once: ((4, 4), 4.02, 4.4)
cell (3, 4): set() cell (4, 4): {'D7'}
- 300,000 drivers (our assumption) ÷ 4 seconds = 75,000 pings a second. Keeping every ping: 75,000 × 3,600 = 270,000,000 rows an hour.
latestholds one entry per driver.in_cellis the cell index: each cell's set of drivers (a set holds each item once and removes one quickly withdiscard).- D7 pings three times. The third ping crosses from cell (3, 4) into cell (4, 4), so he is moved from the old cell's set to the new one:
set()(empty) and{'D7'}. And he is stored once, with his newest position.
Splitting it across servers. One server can't hold a whole country's drivers and pings, so the cells are split across many servers. Sharding means splitting data across several servers, each holding one part (episode 13). Example: cells in the north of the city on server 1, the south on server 2.
- A consistent hash ring (episode 13) places servers and keys on a circle, and each key goes to the next server clockwise, so adding a server moves only a small share of the keys.
- InfoQ's report of Uber's talk: Ringpop (Uber's library) "uses a consistent hash ring ... to distribute state across nodes", and Google S2 cells were used to shard the data. S2 is Google's open-source library that divides the Earth into cells (square-like cells on a sphere), much like our grid.
You just invented a live location store!
Problem 4: closest isn't fastest (match by ETA)
Real life: the car across the river
| Driver | On the map | By road |
|---|---|---|
| Ravi | 780 metres away: the closest, looks perfect | There's a river and the bridge is far: 7.4 km, 22 minutes |
| Meera | 1.7 km away: further on the map | Same side, a straight road: 2.1 km, 6 minutes |
- Road distance is how far a car must actually drive along the roads. It can be much longer than the straight line (rivers, one-way streets, flyovers).
- ETA (estimated time of arrival) is how long the driver will take to reach the rider. Example: 2.1 km at 20 km/h → 6.3 minutes.
import math
rider = (0.0, 0.0)
drivers = { # name: (position km, road km to the rider)
"Ravi": ((0.6, 0.5), 7.4), # across the river: bridge detour
"Meera": ((1.4, 0.9), 2.1), # same side, direct road
}
SPEED = 20 # km/h in city traffic
for name, (pos, road) in drivers.items():
line = math.dist(rider, pos)
eta = road / SPEED * 60 # minutes
print(f"{name:<6} line {line:.2f} km road {road} km ETA {eta:.1f} min")
by_line = min(drivers, key=lambda n: math.dist(rider, drivers[n][0]))
by_eta = min(drivers, key=lambda n: drivers[n][1] / SPEED)
print("closest on the map:", by_line, "| fastest to arrive:", by_eta)
Output:
Ravi line 0.78 km road 7.4 km ETA 22.2 min
Meera line 1.66 km road 2.1 km ETA 6.3 min
closest on the map: Ravi | fastest to arrive: Meera
eta = road / SPEED * 60: 7.4 km ÷ 20 km/h = 0.37 hours = 22.2 minutes; 2.1 ÷ 20 × 60 = 6.3 minutes. (20 km/h is our assumed city speed.)min(drivers, key=...)picks the name with the smallest value: by straight line Ravi, by ETA Meera.
So the grid only gives candidates: the free drivers in the nearby cells who might be a good match. Then a routing service (a service that finds the best route on the road map and estimates its time, using the road network and traffic) works out each candidate's real ETA, and the matcher picks the shortest. InfoQ's report of Uber's talk says the same: Uber "chooses the shortest ETA". You just invented ETA-based matching!
Problem 5: two riders, one driver (an atomic claim)
Real life: the last movie seat
| A cinema counter | Ride matching |
|---|---|
| Two counters, one last seat: both see it free and both sell it | Two bookings at once: both see D7 free. Both get him! |
| Grab the seat card first: only one hand can hold it | Atomic claim: check and set in one step. Only one wins |
| "Sorry, next show?": the loser gets another option | Try the next driver: offer the next best ETA. Nobody is stuck |
- A thread is one line of work running at the same time as others inside the same program. Example: two threads, one booking for Asha and one for a second rider, Ravi.
The obvious way: check if D7 is free, then mark him busy.
import threading, time
driver_status = {"D7": "free"}
booked = []
def book(rider): # the obvious way: check, then set
if driver_status["D7"] == "free":
time.sleep(0.05) # network + database time
driver_status["D7"] = "on trip with " + rider
booked.append(rider)
riders = [threading.Thread(target=book, args=(name,))
for name in ("Asha", "Ravi")]
for t in riders: t.start()
for t in riders: t.join()
verdict = "DOUBLE BOOKED!" if len(booked) > 1 else "ok"
print("D7 given to:", sorted(booked), "->", verdict)
Output:
D7 given to: ['Asha', 'Ravi'] -> DOUBLE BOOKED!
time.sleep(0.05)stands in for the network and database time between reading and writing (50 milliseconds).t.start()starts each thread;t.join()waits for it to finish.- Both threads checked while D7 was still free, and both set him. The check and the set were two separate steps, and the other request slipped in between.
- A race condition is a bug where the result depends on which of two things running at the same time happens first. Example: two bookings both read "free" before either writes "busy".
The fix: do the check and the set in one step.
- Atomic means "all at once, as one indivisible step": nobody else can see or change things halfway through. Example: grabbing the cinema's seat card.
- A lock lets only one thread at a time run a piece of code; others wait their turn. In Python,
with lock:takes the lock and releases it at the end of the block. - Check-and-set (also called compare-and-set, CAS) means "set this to the new value only if it still has the old value", as one atomic step. Example: "set D7 to offered, only if D7 is still free".
import threading, time
driver_status = {"D7": "free"}
lock = threading.Lock()
result = {}
def claim(driver, rider): # check AND set in one step
with lock:
if driver_status[driver] != "free":
return False
driver_status[driver] = "offered to " + rider
return True
def book(rider):
time.sleep(0.05) # same network time as before
if claim("D7", rider):
result[rider] = "got D7"
else:
result[rider] = "D7 taken, try the next driver"
riders = [threading.Thread(target=book, args=(name,))
for name in ("Asha", "Ravi")]
for t in riders: t.start()
for t in riders: t.join()
for r in sorted(result): print(r, "->", result[r])
print("D7:", driver_status["D7"])
Output (from our run):
Asha -> D7 taken, try the next driver
Ravi -> got D7
D7: offered to Ravi
- Which rider wins can change from run to run (in this run Ravi did), because both threads reach the lock at nearly the same moment. What never changes: exactly one rider gets D7, the other is told "D7 taken, try the next driver", and D7 is offered to exactly one person.
- In a real system the lock lives in the shared store, as a conditional update: a database or store write that only happens if a condition still holds. Example:
UPDATE drivers SET status = 'offered' WHERE id = 'D7' AND status = 'free', then check whether one row changed. It's the same idea as the idempotent, safe steps from episode 24 (idempotent: doing it twice has the same effect as doing it once). - An offer timeout: if the driver doesn't accept within a few seconds, the claim is released (D7 goes back to free) and the next driver gets the offer.
You just invented the atomic driver claim!
The full design
driver apps ──(ping every 4 s)──▶ location service ──▶ in-memory store: latest position,
indexed by cell, cells split across servers
▲
rider app ──(taps Book)──▶ matcher ── nearby cells ───────────────┘
│ candidates (free drivers only)
├──▶ routing service: ETA for each candidate
├──▶ atomic claim on the shortest-ETA driver ──▶ offer to his phone
│ (timeout → release → next driver)
└──▶ trips database: the accepted ride, saved for good
after accept: live positions pushed to both apps (the live map)
- Driver apps send a location ping every 4 seconds to the location service.
- The location service keeps only the latest position of each driver, in memory, indexed by cell (hexagons, like H3), with the cells split across servers (sharding, a consistent hash ring).
- The rider taps Book. The matcher looks in the rider's cell and the cells around it (widening the ring if needed) for free candidates.
- The matcher asks the routing service for each candidate's ETA by road and sorts them, shortest first.
- It claims the best driver atomically (set "offered" only if still "free") and sends the offer. If he doesn't accept in a few seconds, the claim is released and the next driver gets it. If the claim fails, it moves straight to the next candidate.
- Once accepted, the trip is saved in a normal trips database (on disk, kept for good: fares, receipts, history).
- Both apps get live positions pushed to them, so Asha watches her car arrive. Push means the server sends updates as they happen, instead of the app asking again and again.
Why two different stores? Locations change every 4 seconds and only the newest matters, so they live in fast, temporary memory. Trips must never be lost, so they go to a durable database. Using one store for both would make it either too slow for pings or too risky for trips.
The whole chain
- 200,000 checks per booking (1 billion a second) → grid cells (4,487 checks).
- Squares: 2 neighbour distances → hexagons, 1 distance (H3).
- 270 million rows an hour → latest only, in memory, indexed by cell.
- Closest car, 22.2 minutes away → match by ETA (6.3 minutes).
- DOUBLE BOOKED → atomic claim.
- Location service, matcher, offers with timeouts, trips database, live map.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| Loop over every driver | distance checks per second: 1,000,000,000 |
Far drivers can never win, but you check them all | Grid cells: search nearby only |
cells[(cx + dx, cy + dy)] at the city edge |
KeyError: (10, -1) |
Cells outside the city (or empty cells) have no list | cells.get(cell, []) |
| Search only the 9 cells on a quiet night | ValueError: min() iterable argument is empty |
No driver in the nearby cells | Widen the ring until you find candidates |
| Check if free, then set busy in a second step | D7 given to: ['Asha', 'Ravi'] -> DOUBLE BOOKED! |
Another request runs between check and set | Atomic claim: check and set in one step |
| Pick the closest on the map | closest on the map: Ravi (ETA 22.2 min) |
Rivers and one-way roads make the straight line lie | Grid for candidates, ETA to choose |
| Save every ping as a new row | rows per hour if we keep them all: 270,000,000 |
Matching needs only where the driver is now | Overwrite the latest, in memory; log history separately if needed |
| Forget to remove a driver from his old cell | The driver appears in two cells and gets matched from where he no longer is | The index goes stale | On a cell change, discard from the old cell's set |
The KeyError comes from the GRID demo with cells.get((cx + dx, cy + dy), []) changed to cells[(cx + dx, cy + dy)] and the rider moved to the southern edge, rider = (11.5, 0.3) (cell (11, 0)). The very first neighbour it looks at is (10, -1), which is outside the city (file path shortened):
Traceback (most recent call last):
File "edge.py", line 21, in <module>
best, checked = nearest_grid(rider)
~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^
File "edge.py", line 18, in nearest_grid
for d in cells[(cx + dx, cy + dy)]]
~~~~~^^^^^^^^^^^^^^^^^^^^
KeyError: (10, -1)
The ValueError comes from the original GRID demo with only range(50) drivers: Asha's 9 cells are empty, so min gets an empty list.
Mini project: a tiny ride-matching service
A location store indexed by 1 km cells, 300 drivers (100 of whom move and ping again), ETA-based choice with a made-up detour factor standing in for real roads, and an atomic claim, with Asha and Ravi booking from the same spot at the same moment and Meera booking elsewhere, in 70 lines:
# Mini project: a tiny ride-matching service: a location store indexed by
# 1 km grid cells, ETA-based choice among nearby candidates, and an atomic
# claim so two riders can never get the same driver. One process, no maps:
# road distance is straight-line distance times a made-up detour factor.
import math, random, threading, time
random.seed(12)
CELL, SPEED = 1, 20 # 1 km cells, 20 km/h in traffic
class LocationStore:
def __init__(self):
self.latest, self.in_cell = {}, {}
self.status, self.lock, self.pings = {}, threading.Lock(), 0
def ping(self, driver, x, y): # keep only the newest position
self.pings += 1
cell = (int(x // CELL), int(y // CELL))
old = self.latest.get(driver)
if old and old[0] != cell:
self.in_cell[old[0]].discard(driver)
self.in_cell.setdefault(cell, set()).add(driver)
self.latest[driver] = (cell, x, y)
self.status.setdefault(driver, "free")
def nearby(self, x, y): # drivers in the 9 cells around (x, y)
cx, cy = int(x // CELL), int(y // CELL)
return [d for dx in (-1, 0, 1) for dy in (-1, 0, 1)
for d in self.in_cell.get((cx + dx, cy + dy), set())]
def claim(self, driver, rider): # check AND set in one step
with self.lock:
if self.status[driver] != "free":
return False
self.status[driver] = "offered to " + rider
return True
store = LocationStore()
detour = {} # driver -> road km / straight km
for i in range(300): # 300 drivers in a 10 x 10 km city
d = f"D{i}"
detour[d] = random.choice([1.2, 1.3, 1.5, 4.0]) # 4.0 = across the river
store.ping(d, random.uniform(0, 10), random.uniform(0, 10))
for d in list(store.latest)[:100]: # 4 seconds later, 100 have moved
_, x, y = store.latest[d]
store.ping(d, min(9.99, x + 0.3), y)
def eta(driver, x, y): # minutes, from road distance
_, dx, dy = store.latest[driver]
return math.dist((x, y), (dx, dy)) * detour[driver] / SPEED * 60
matches = {}
def book(rider, x, y):
cands = [d for d in store.nearby(x, y) if store.status[d] == "free"]
time.sleep(0.05) # routing + network time
for tries, d in enumerate(sorted(cands, key=lambda d: eta(d, x, y)), 1):
if store.claim(d, rider): # shortest ETA first; if taken, next
matches[rider] = (d, round(eta(d, x, y), 1), len(cands), tries)
return
riders = [("Asha", 5.3, 4.8), ("Ravi", 5.3, 4.8), ("Meera", 2.0, 8.5)]
threads = [threading.Thread(target=book, args=r) for r in riders]
for t in threads: t.start()
for t in threads: t.join()
print("drivers stored:", len(store.latest), " pings handled:", store.pings)
for name, *_ in riders:
d, minutes, n, tries = matches[name]
print(f"{name:<6} -> {d:<5} ETA {minutes} min candidates {n} try {tries}")
near = min(store.nearby(5.3, 4.8),
key=lambda d: math.dist((5.3, 4.8), store.latest[d][1:]))
print(f"closest on the map to Asha: {near}, ETA {eta(near, 5.3, 4.8):.1f} min")
given = [m[0] for m in matches.values()]
print("riders matched:", len(given), " distinct drivers:", len(set(given)))
Output (from our run; Asha and Ravi may swap drivers between runs):
drivers stored: 300 pings handled: 400
Asha -> D279 ETA 2.2 min candidates 27 try 1
Ravi -> D180 ETA 2.5 min candidates 27 try 2
Meera -> D267 ETA 0.9 min candidates 23 try 1
closest on the map to Asha: D70, ETA 5.5 min
riders matched: 3 distinct drivers: 3
- 400 pings, 300 drivers stored: the 100 drivers who pinged twice are still stored once, with their newest position.
- Asha and Ravi stood at the same spot and both wanted D279 first. Only one claim succeeded; the other rider's first try failed and he got the next-best driver on try 2. 3 riders, 3 distinct drivers: no double booking.
- The closest car on the map to Asha, D70, would take 5.5 minutes (it's across the "river", detour 4.0); matching by ETA gave her a car in 2.2. Only 27 candidates were checked, out of 300 drivers.
Try extending it: add an offer timeout (if a driver doesn't accept, set him back to "free" and try the next), and make the 9-cell search widen to a bigger ring when there are no free candidates.
Practice
- Homework: in the GRID demo, try 0.5 km cells. How many checks now? Same driver?
- Homework: in the LOC demo, ping every 2 seconds instead of 4. How many pings a second and rows an hour?
- Homework: in the CAS demo, add a third rider. How many get D7?
- Homework (comment): what should happen when a driver's phone goes offline, say in a tunnel?
- In the GRID demo with only 50 drivers, the 9-cell search crashes. Make it widen ring by ring until it finds someone.
- Each location ping is about 100 bytes (our assumption). With 75,000 pings a second, how much data arrives per second? Per day?
- Why not save every ping as a row in the trips database and query "latest ping per driver" when someone books?
- A driver gets the offer but never taps Accept. What should the system do, and why does the claim need a timeout?
- Two riders are 50 metres apart and both book. Why is a lock inside one Python process not enough in the real system?
Solutions and hints
1. Change CELL = 20, 1 to CELL = 20, 0.5. Output:
nearest: 0.023 km away, checked 1,149
cells in the city: 1600
The same driver, 23 metres away, with 1,149 checks instead of 4,487: each cell is a quarter of the area, so the 9 cells hold about a quarter of the drivers. There are now 1,600 cells. The catch: 9 cells of 0.5 km cover only 1.5 × 1.5 km, so on a quiet night you'll need to widen the ring more often. Smaller cells mean fewer checks per cell but more cells to look in and more cell changes as cars move.
2. Change EVERY to 2. Output:
location pings per second: 150,000
rows per hour if we keep them all: 540,000,000
D7 stored once: ((4, 4), 4.02, 4.4)
cell (3, 4): set() cell (4, 4): {'D7'}
Pings double: 150,000 a second, 540 million rows an hour if you kept them. The latest-only store still holds one entry per driver; only the write rate doubles. Fresher positions cost twice the traffic.
3. Change ("Asha", "Ravi") to ("Asha", "Ravi", "Kiran"). Output (from our run; the winner can differ):
Asha -> D7 taken, try the next driver
Kiran -> D7 taken, try the next driver
Ravi -> got D7
D7: offered to Ravi
Still exactly one rider gets D7; the other two move to the next driver. (For comparison, the RACE demo with three riders gave D7 given to: ['Asha', 'Kiran', 'Ravi'] -> DOUBLE BOOKED!.)
4. If no ping arrives for a while (say 3 or 4 missed pings, our assumption), mark the driver stale: stop offering him new rides, but keep his last known position. If he's already on a trip, keep the trip going and show the rider "last seen here"; when the phone reconnects, its next ping updates the position. Don't cancel the trip just because the phone was silent in a tunnel.
5. Replace nearest_grid with a loop over rings (and use range(50) drivers):
def nearest_grid(r):
cx, cy = cell_of(r)
for ring in range(1, CITY + 1): # widen until someone is found
nearby = [d for dx in range(-ring, ring + 1)
for dy in range(-ring, ring + 1)
for d in cells.get((cx + dx, cy + dy), [])]
if nearby:
break
print("rings searched:", ring)
return min(nearby, key=lambda d: math.dist(r, d)), len(nearby)
Output:
rings searched: 3
nearest: 2.382 km away, checked 2
cells in the city: 46
Rings 1 and 2 were empty; ring 3 (a 7 × 7 block) found 2 drivers, and the nearest is 2.382 km away (a full scan of all 50 agrees). Only 46 of the 400 cells have anyone in them. One subtle point: a driver in a corner of ring 3 can be further away than one just inside ring 4, so a careful matcher searches one more ring after the first hit (and in any case ranks by ETA, not straight line).
6. 75,000 × 100 bytes = 7.5 MB a second; × 86,400 seconds = about 648 GB a day. Easy for a cluster to receive, but far too much to keep as "the current state". Keep the latest in memory; if you need history (trip routes, analytics), write it to a separate log or store built for that.
7. The table would grow by 270 million rows an hour (our numbers), and "latest per driver, in these cells" becomes a heavy query run thousands of times a second. Matching needs only the newest position, so overwrite one entry per driver in memory, indexed by cell.
8. Hold the claim for a few seconds. If he doesn't accept, the claim expires: set him back to "free" (perhaps skip him for this rider) and offer the next-best ETA. Without a timeout, a driver who left his phone in his pocket would stay "offered" forever and Asha would wait for nobody.
9. In the real system the two bookings may run on different servers, each with its own memory and its own lock. The claim must be atomic in the shared store that owns D7: a conditional update ("set offered only if free") in the database or in-memory store, so whichever request arrives second sees "not free".
Quick quiz
A: 0.5 km on the map, ETA 15 min
B: 1.2 km on the map, ETA 4 min
C: 0.9 km on the map, already on a trip
Which driver gets Asha's ride?
- A. A, closest on the map
- B. B, shortest ETA
- C. C, it's between them
- D. Whoever answers first
Answer
B. Free drivers only, and among them the shortest ETA: C is already on a trip, so he isn't free, and between A and B, B arrives in 4 minutes. Closest on the map (A) can be the slowest to arrive (our demo: Ravi, 0.78 km but 22.2 minutes).
Interview questions: "Design Uber ride matching"
1. Clarify requirements. Which cities, how many drivers and riders? Ride types (car, auto, bike)? How fast must a match be? Pool rides? Then state: a match in a few seconds, fresh locations, hundreds of thousands of drivers online, one driver per ride, live map after accept.
2. Estimate (our own assumptions, say them out loud). "300,000 drivers online pinging every 4 seconds = 75,000 writes a second, about 7.5 MB/s at 100 bytes each. Keeping every ping = 270 million rows an hour, so keep only the latest, in memory. 5,000 bookings a second × 200,000 drivers = 1 billion checks a second if we scan, so we need a spatial index."
3. Location service. Ingest pings; store driver → latest (cell, position, status) in memory; cell → set of drivers; cells sharded across servers (consistent hashing). Hexagon cells (H3) or another grid (geohash, S2, quadtree).
4. Matching. Rider's cell + neighbouring rings → free candidates → routing service ETAs → sort by ETA → atomic claim → offer with timeout → next driver on decline or timeout.
5. Trips and the live map. Accepted trips in a durable database; positions pushed to rider and driver apps (WebSockets or similar) while the trip lasts.
6. Correctness and failures. Conditional updates for claims; idempotent booking requests (a retry must not book twice, episode 24); stale drivers (no recent pings) excluded; a location server failing loses only temporary state, rebuilt from the next round of pings within seconds.
Common follow-ups:
- Geohash vs quadtree vs hexagons? (Geohash: simple string prefixes, square-ish cells of uneven neighbour distance. Quadtree: adapts to density, more work to update as cars move. Hexagons: one neighbour distance, used by Uber's H3; S2: Google's cells on a sphere.)
- How do you handle a busy city centre vs an empty suburb? (Smaller cells or more servers where it's dense; widen the ring where it's sparse.)
- How would you compute surge pricing? (Count supply and demand per cell, per hexagon, as Uber describes, and raise prices where demand is far above supply.)
- What if the routing service is slow? (Cache ETAs between cells for a short time, fall back to straight-line estimates with a detour factor, cap the number of candidates you route.)
- How do you avoid one driver getting all the offers, or riders getting the same driver? (Atomic claims; fairness rules such as skipping drivers who just declined.)
- What breaks if a location shard goes down? (Those cells look empty until pings land on a replacement; the consistent hash ring moves only that shard's cells.)
Glossary
| Term | Meaning |
|---|---|
| Ride matching | Pairing a rider with one suitable free driver, quickly |
| Requirements (functional / non-functional) | What the system must do / how well it must do it |
| Online / free driver | App open and ready / online and not on a trip or holding an offer |
| Offer | A ride request sent to one driver, who can accept or let it time out |
| Double booking | One driver given to two riders at the same time |
| Linear scan | Checking every item one by one |
| Straight-line distance | Distance as the crow flies, math.dist, ignoring roads |
| Grid / cell | The map cut into equal shapes / one of those shapes |
| Index | An extra structure that takes you straight to the data you want |
| Spatial index / geo index / geo grid | An index by location: from an area to the things inside it |
| Neighbouring cells | The cells touching yours: 8 for squares, 6 for hexagons |
| Ring | The next layer of cells around the block already searched |
| Geohash | A string code for a location; nearby places share starting letters |
| Quadtree | A map split into 4 squares, busy squares split again into 4, and so on |
| Hexagon | A six-sided cell; all 6 neighbours at the same centre distance |
| H3 | Uber's open-source hexagonal hierarchical spatial index, 16 resolutions |
| Resolution | One cell size in a multi-size grid; each finer H3 level ≈ 1/7 the area |
| Hierarchical | Arranged in levels, big cells made of smaller ones |
| Surge pricing | Higher prices where demand is far above supply |
| Supply / demand | Free drivers / riders asking for trips |
| Location ping | A small message from the driver's phone with his current position |
| Row | One record in a database table |
| In memory | Kept in RAM: fast, but temporary |
| Overwrite | Replace the old value instead of adding another |
| Location store / location service | Holds each driver's latest position, indexed by cell |
| Sharding | Splitting data across servers, each holding one part (episode 13) |
| Consistent hash ring | Servers and keys on a circle; adding a server moves few keys (episode 13) |
| Ringpop | Uber's library that uses a consistent hash ring to spread state across nodes |
| S2 cells | Google's open-source cells covering the Earth, used by Uber to shard data |
| Road distance | How far a car must actually drive along roads |
| ETA | Estimated time of arrival: how long the driver takes to reach the rider |
| Candidates | Free drivers in nearby cells who might be matched |
| Routing service | Finds the best road route and estimates its time |
| Matcher | The service that picks candidates, ranks by ETA and claims a driver |
| Thread | One line of work running at the same time as others in a program |
| Race condition | A bug where the result depends on which concurrent step happens first |
| Atomic | Done as one indivisible step |
| Lock | Lets only one thread at a time run a piece of code |
| Check-and-set / compare-and-set (CAS) | Set a new value only if the old value is still there, atomically |
| Conditional update | A database write that only happens if a condition still holds |
| Atomic claim | Marking a driver "offered" only if still free, in one step |
| Offer timeout | The claim is released if the driver doesn't accept in time |
| Idempotent | Doing it twice has the same effect as doing it once (episode 24) |
| Stale driver | One whose pings stopped; not offered new rides |
| Trips database | Durable store for accepted rides, fares and history |
| Push | The server sends updates as they happen, instead of the app asking |
KeyError |
Python's error for reading a dictionary key that isn't there |
dict.get(key, default) |
Read a key, or get the default if it's missing |
Summary
- Ride matching must be fast, use fresh locations, handle huge numbers of drivers, and be correct: one driver, one ride.
- Scanning every driver is 200,000 checks per booking (1 billion a second at 5,000 bookings a second); a grid of cells (a spatial index) finds the same driver with 4,487 checks.
- Square cells have neighbours at 2 distances (1 and 1.41); hexagons have one. Uber's open-source H3 uses hexagon cells with 16 resolutions, each finer one about 1/7 the area, and measures supply and demand per hexagon for surge pricing.
- Drivers' phones ping every 4 seconds (Uber, per InfoQ): 75,000 pings a second for 300,000 drivers. Keep only the latest position, in memory, indexed by cell, and shard the cells (Uber: Ringpop's consistent hash ring, S2 cells).
- The closest car on the map can take 22.2 minutes while another takes 6.3: the grid gives candidates, the shortest ETA chooses (as Uber does).
- Check-then-set lets two riders get the same driver (DOUBLE BOOKED!); an atomic claim (check and set in one step, a conditional update in the shared store) lets exactly one win, with an offer timeout and the next driver as backup.
Next episode: you order biryani, and a rider reaches the restaurant just as it's packed. How? Design Swiggy and Zomato food delivery.
Sources: Uber Engineering blog, "H3: Uber's Hexagonal Hierarchical Spatial Index": "We use a grid system to bucket events into hexagonal areas, in other words, cells"; "hexagons have only one distance between a hexagon centerpoint and its neighbors', compared to two distances for squares or three distances for triangles"; "people in a city are often in motion"; "we calculate surge pricing by measuring supply and demand in hexagons"; "H3 supports sixteen resolutions"; each finer resolution has cells with one seventh the area; H3 is open source. InfoQ (March 2015), report of Uber's real-time market platform talk: "the driver's phones post location updates to the server every four seconds"; Uber "chooses the shortest ETA"; Ringpop "uses a consistent hash ring ... to distribute state across nodes"; Google S2 cells were used to shard data. City size, driver counts, bookings per second, speeds, road distances and ping sizes are our own stated assumptions; geohash, quadtree and the other definitions are general textbook knowledge.