SyntaxPilot
Courses/System Design/Lesson 32
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

System Design · Lesson 32 of 40

Design Uber/Ola ride matching

queued

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 cells dictionary (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_of turns a position into its cell: // divides and rounds down, so 10.3 // 1 = 10.0 and int makes 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 with tdr1".
  • 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 cos and sin), 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.
  • latest holds one entry per driver. in_cell is the cell index: each cell's set of drivers (a set holds each item once and removes one quickly with discard).
  • 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)
  1. Driver apps send a location ping every 4 seconds to the location service.
  2. 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).
  3. 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.
  4. The matcher asks the routing service for each candidate's ETA by road and sorts them, shortest first.
  5. 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.
  6. Once accepted, the trip is saved in a normal trips database (on disk, kept for good: fares, receipts, history).
  7. 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

  1. 200,000 checks per booking (1 billion a second) → grid cells (4,487 checks).
  2. Squares: 2 neighbour distances → hexagons, 1 distance (H3).
  3. 270 million rows an hour → latest only, in memory, indexed by cell.
  4. Closest car, 22.2 minutes away → match by ETA (6.3 minutes).
  5. DOUBLE BOOKED → atomic claim.
  6. 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

  1. Homework: in the GRID demo, try 0.5 km cells. How many checks now? Same driver?
  2. Homework: in the LOC demo, ping every 2 seconds instead of 4. How many pings a second and rows an hour?
  3. Homework: in the CAS demo, add a third rider. How many get D7?
  4. Homework (comment): what should happen when a driver's phone goes offline, say in a tunnel?
  5. In the GRID demo with only 50 drivers, the 9-cell search crashes. Make it widen ring by ring until it finds someone.
  6. Each location ping is about 100 bytes (our assumption). With 75,000 pings a second, how much data arrives per second? Per day?
  7. Why not save every ping as a row in the trips database and query "latest ping per driver" when someone books?
  8. A driver gets the offer but never taps Accept. What should the system do, and why does the claim need a timeout?
  9. 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.