Design a Ride-Hailing Service: Matching Riders to Drivers

"Design a ride-hailing app" sounds like a search problem: find the nearest driver. The search is the easy part. The hard part is that every position you search is out of date within seconds, so the system spends almost all of its effort absorbing location updates, and a matching decision has to be made from a map that is always moving.

The problem it solves

Pin the requirements and the numbers first. The lesson's illustrative assumptions:

• 50,000 active drivers in one city, each sending its position every four seconds: 12,500 writes a second.
• Ride requests are far fewer than pings, and each must be matched within a few seconds.
• A driver is offered one ride at a time, and a ride goes to one driver.
• Positions are disposable; trips, fares and payments are not.

That asymmetry decides the architecture. The driver map is a write-heavy, short-lived dataset, so it belongs in memory and is overwritten in place. The durable database only sees an event when a trip is accepted, which is orders of magnitude rarer.

The intuition

Split the system into three parts.

1. Location ingest. Drivers keep a persistent connection (see WebSockets vs polling) and stream pings. Each ping overwrites one entry in an in-memory index keyed by grid cell. A driver who crosses a cell boundary must be removed from the old cell, or they show up twice.
2. Candidate search. A request maps the rider's position to a cell, reads that cell and its eight neighbours, and widens to the next ring only if too few drivers are free. The choice of cell scheme, geohash, quadtree or fixed squares, is covered in designing a proximity service; here a fixed grid is enough.
3. Ranking and offering. Candidates are ranked by road ETA, not straight-line distance. The ride is offered to the best one under a short hold, so no driver receives two offers at once; a decline or a timeout releases the hold and the offer moves on.

Partition the index by city or region: rides almost never cross regions, so shards rarely talk, and a busy city cannot slow a quiet one. A hot cell such as an airport costs CPU, not disk.

Sizing, still illustrative: at roughly 100 bytes per driver entry including overhead, 50,000 drivers is about 5 MB. Memory is not the constraint; write rate and freshness are.

Watch it run

The animation starts from the load: fifty thousand drivers pinging every four seconds is 12,500 writes a second. Each ping overwrites one entry in the grid cell it falls in, held in memory. A rider asks for a trip, and their position falls in cell gb7. Reading that one cell gives three candidates instead of scanning a city. But the closest driver is fifty metres away in gbe, the cell to the north, because a cell boundary is not a road. So the neighbours are read as well: four candidates, still only nine lookups. Ranking them by road ETA reorders the list, because the nearest driver is across a river, eleven minutes out, while the best ETA is four minutes. The offer goes to one driver and is held, so nobody else is offered the same ride. They decline, the hold is released, and the offer moves to the next candidate. Accepted: only now does a durable trip record need to exist at all, one write per trip. The last frame restates the rule: positions never touch disk, because a table taking 12,500 overwrites a second is what fails first.

The code

A toy model: a grid of square cells over a flat city measured in kilometres. A ping overwrites the driver's entry and moves it between cells when needed:

import math
from collections import defaultdict

class DriverIndex:
    """In-memory grid of square cells: cell -> {driver: (x, y)}, positions in km."""
    def __init__(self, cell_km=1.0):
        self.cell = cell_km
        self.cells = defaultdict(dict)
        self.where = {}                          # driver -> cell, so a move can leave it

    def key(self, x, y):
        return (math.floor(x / self.cell), math.floor(y / self.cell))

    def ping(self, driver, x, y):                # 12,500 of these a second: overwrite only
        new, old = self.key(x, y), self.where.get(driver)
        if old is not None and old != new:
            del self.cells[old][driver]
        self.cells[new][driver] = (x, y)
        self.where[driver] = new

    def nearby(self, x, y, rings=1):             # own cell plus the ring(s) around it
        cx, cy = self.key(x, y)
        found = {}
        for dx in range(-rings, rings + 1):
            for dy in range(-rings, rings + 1):
                found.update(self.cells.get((cx + dx, cy + dy), {}))
        return found

idx = DriverIndex()
for d, (x, y) in {"d1": (2.40, 5.30), "d2": (2.10, 5.80), "d3": (2.70, 5.10),
                  "d4": (3.02, 5.52), "d5": (7.0, 1.0)}.items():
    idx.ping(d, x, y)
rider = (2.97, 5.50)
print(sorted(idx.nearby(*rider, rings=0)))       # ['d1', 'd2', 'd3']
print(sorted(idx.nearby(*rider)))                # ['d1', 'd2', 'd3', 'd4']
idx.ping("d4", 3.05, 6.20)                       # d4 drives north into another cell
print(idx.where["d4"], sorted(idx.cells[(3, 5)]))  # (3, 6) []
idx.ping("d4", 3.02, 5.52)                       # and back to the river bank

The rider's own cell misses d4, 50 metres away across the boundary; the 3×3 read finds it. Now rank by a toy road network with a river along x = 3 and one bridge, and offer under a hold:

RIVER_X, BRIDGE = 3.0, (3.0, 4.4)

def eta_min(a, b, kmh=12):
    """Toy roads: a street grid, a river along x = 3 and one bridge across it."""
    street = lambda p, q: abs(p[0] - q[0]) + abs(p[1] - q[1])
    same_bank = (a[0] < RIVER_X) == (b[0] < RIVER_X)
    km = street(a, b) if same_bank else street(a, BRIDGE) + street(BRIDGE, b)
    return round(km / kmh * 60, 1)

cands = idx.nearby(*rider)
print(min(cands, key=lambda d: math.dist(rider, cands[d])))       # d4
ranked = sorted(cands, key=lambda d: eta_min(rider, cands[d]))
print([(d, eta_min(rider, cands[d])) for d in ranked])
# [('d3', 3.4), ('d1', 3.9), ('d2', 5.8), ('d4', 11.3)]

class Offers:
    """At most one open offer per driver; a hold lapses if nobody answers."""
    def __init__(self):
        self.held = {}                           # driver -> (ride, expires_at)

    def try_hold(self, driver, ride, now, ttl=15):
        current = self.held.get(driver)
        if current and current[1] > now:
            return False                         # someone else's offer is still open
        self.held[driver] = (ride, now + ttl)
        return True

    def release(self, driver):
        self.held.pop(driver, None)

def dispatch(ride, ranked, offers, answers, now):
    for d in ranked:
        if not offers.try_hold(d, ride, now):
            continue
        if answers.get(d) == "accept":
            return d                             # only now is a durable trip written
        offers.release(d)                        # declined: free them, try the next
    return None

offers = Offers()
print(dispatch("r1", ranked, offers, {"d3": "decline", "d1": "accept"}, now=0))  # d1
print(dispatch("r2", ranked, offers, {"d1": "accept", "d2": "accept"}, now=1))   # d2

The straight-line winner is the worst ETA. The second rider skips d1, whose hold is still open. In production, try_hold must be one atomic conditional write with an expiry in the shared store, because two matchers can race for the same driver.

Last, the index is checked against brute force on 300 seeded cities with three cell sizes: every driver sits in exactly one cell, and every driver within one cell width of a random rider, found by scanning everyone, is in the 3×3 read:

import random

rng = random.Random(35)
ok, own_cell_misses = True, 0
for _ in range(300):
    grid, truth = DriverIndex(cell_km=rng.choice([0.5, 1.0, 2.0])), {}
    for _ in range(300):                         # pings, many of them moves across cells
        d, p = "d%d" % rng.randrange(60), (rng.uniform(0, 10), rng.uniform(0, 10))
        grid.ping(d, *p)
        truth[d] = p
    stored = [(d, p) for cell in grid.cells.values() for d, p in cell.items()]
    ok &= len(stored) == len(truth) and dict(stored) == truth   # one cell per driver
    r = (rng.uniform(0, 10), rng.uniform(0, 10))
    near = {d for d, p in truth.items() if math.dist(r, p) <= grid.cell}   # scan everyone
    ok &= near <= set(grid.nearby(*r))
    own_cell_misses += len(near - set(grid.nearby(*r, rings=0)))
print(ok, own_cell_misses)                       # True 518

Reading only the rider's own cell would have missed 518 nearby drivers across those 300 requests.

The complexity

• Ping: O(1), two hash-map writes at most.
• Search: nine cell reads plus the drivers in them, independent of city size; ranking k candidates by ETA costs k routing estimates, usually the expensive step.
• Durable writes: one per trip, not one per ping.

Where it goes wrong

• Positions in a disk-backed table. 12,500 updates a second of data that is stale in four seconds is the first thing to fail.
• Own cell only. Riders near a boundary get a distant driver.
• Straight-line ranking. Rivers, one-way streets and motorways make the nearest driver the slowest.
• Offers without holds. Two matchers offer the same driver two rides; one rider waits for nothing.

Some dispatch systems also collect requests for a moment and solve them together as an assignment problem instead of greedily, one by one; as of October 2026 that is a known refinement rather than a requirement (from memory). Cell schemes vary too: square grids, geohash and hexagonal grids are all in use.

When it shows up in interviews

As "design a ride-hailing service", "design a food delivery dispatcher" or "match nearby drivers". Interviewers push on the write rate, boundary misses, how to stop double dispatch, what happens when a matcher crashes holding an offer (the hold expires), and how to shard by region.

How to say it in an interview

"Fifty thousand drivers pinging every four seconds is 12,500 writes a second of data that is stale in four, so positions live in memory, overwritten in place in a grid-cell index, sharded by city. A request reads the rider's cell and its eight neighbours, widening if needed, and ranks candidates by road ETA, not distance. The ride is offered to one driver at a time under an atomic hold with a timeout, so nobody gets two offers. Only an accepted trip is written durably."