02. Ride-Hailing Service — Low-Level Design¶
~22 min read · Part 3 of 4 (Overview → HLD → LLD → Q&A)
The HLD named the boxes. This file opens the four that carry the design's weight — the geospatial index, the matching/dispatch loop, ETA, and surge — and pins down the data, the algorithms, and the concurrency corners where a ride-hailing system actually breaks.
Data models¶
Two data planes, two shapes. The live location plane is an in-memory index keyed by geographic cell; the trip plane is a durable table keyed by trip id.
Geo Index (in-memory). The primary structure maps a cell id to the drivers currently in it. In Redis-with-geo terms, one sorted structure per shard; conceptually:
cell_id (H3 res-8 int) → {
driver_id → { lat, lng, heading, status, ts } # one entry per driver
}
driver_id → cell_id # reverse index for cheap cell-move
Two deliberate choices. First, the key is the cell, not the driver, because the hot query is "everyone in these cells" — keying by cell makes a candidate gather a handful of bucket reads instead of a scan. Second, we keep a reverse driver_id → cell_id map so that when a driver's update lands in a new cell we can remove them from the old one in O(1); without it, a moving driver would leave copies in every cell they ever visited. Each entry has a TTL of a few update intervals so a driver who goes silent ages out.
Trip Store (durable).
CREATE TABLE trip (
ride_id UUID PRIMARY KEY,
rider_id BIGINT NOT NULL,
driver_id BIGINT NULL, -- null until matched
status SMALLINT NOT NULL, -- requested/matched/enroute/started/completed/cancelled
pickup_lat DOUBLE NOT NULL,
pickup_lng DOUBLE NOT NULL,
dropoff_lat DOUBLE NOT NULL,
dropoff_lng DOUBLE NOT NULL,
surge_mult DECIMAL(3,2) NOT NULL DEFAULT 1.0,
fare_cents INT NULL, -- set at completion
requested_at TIMESTAMP NOT NULL,
matched_at TIMESTAMP NULL,
region_id INT NOT NULL -- shard key
);
CREATE INDEX idx_rider ON trip (rider_id, requested_at DESC); -- "my trips"
CREATE INDEX idx_driver ON trip (driver_id, requested_at DESC); -- "driver earnings"
Driver assignment (the strongly-consistent bit). The single-trip-per-driver guarantee needs its own authoritative record, separate from the sloppy location index:
CREATE TABLE driver_assignment (
driver_id BIGINT PRIMARY KEY,
ride_id UUID NULL, -- the trip they're on, or null if free
version BIGINT NOT NULL -- for compare-and-set
);
region_id is the trip shard key so a region's trips co-locate and a regional outage is contained. The driver_assignment row, not the location index, is the arbiter of "is this driver free" — location is allowed to be stale, assignment is not.
Component internals¶
Component 1 — Geospatial index (geohash vs quadtree vs H3)¶
Responsibility: turn a (lat, lng) into a shardable cell id, support upsert-driver and query-cells, and gather candidates near a pin with uniform, predictable coverage.
The choice of how to cell the world is the signature decision. Three families:
- Geohash interleaves latitude and longitude bits into a base-32 string; a prefix is a rectangular cell, and dropping characters zooms out. It is trivial to compute and store, and prefix-matching gives cheap range scans. Its flaw for matching is that neighbors are awkward: two points can be geographically adjacent but share no prefix (the boundary problem), and rectangular cells have non-uniform neighbor distances (a cell's east-west and north-south neighbors are different distances away), so "gather the 8 neighbors" over-covers in one direction and under-covers in another.
- Quadtree recursively splits space into four quadrants, subdividing only where density is high. It adapts to density — downtown cells are deep and small, rural cells shallow and large — which is exactly the uneven-density property of a city. Its cost is that it is a tree: it needs rebalancing as drivers move, and it is harder to shard cleanly than a flat cell id.
- H3 tiles the world in hexagons at fixed resolutions. Hexagons have the property square cells lack: all six neighbors are equidistant and share an edge, so a k-ring (the set of cells within k steps) is a clean, uniform disk of coverage. That uniformity is why the candidate gather is predictable —
kRing(cell, 2)covers a roughly circular ~2 km area with 19 hexes at resolution 8, with no directional bias.
We choose H3 at resolution 8 as the default (edge ~460 m, ~0.74 km² per hex), stepping to a finer resolution in dense downtowns so no single hex holds thousands of drivers, and coarser in sparse areas. The interface:
class GeoIndex:
def cell_of(lat, lng, res) -> CellId # H3 index
def upsert(driver_id, lat, lng, heading, status) # write to cell, move if changed
def query(center_cell, k) -> list[DriverState] # all drivers in kRing(center, k)
def k_ring(cell, k) -> list[CellId] # uniform disk of cells
query reads the k-ring's buckets from the owning shard(s) and concatenates them. Because cells map to shards deterministically, a query touching 19 hexes usually touches one or a few shards, not all of them.
Why not persist it? Every entry is overwritten within 4 seconds, so durability would mean writing 1.25M rows/second to disk to store data that is worthless before the write flushes. The index is in-memory precisely because its data has a 4-second half-life.
Component 2 — Matching / Dispatch¶
Responsibility: turn a pickup point into an accepted driver within seconds, doing bounded work and never assigning one driver twice.
class Matcher:
def match(ride_id, pickup, product) -> Assignment | NoDriver
def _gather(pickup) -> list[DriverState] # geo query + available filter
def _prune(cands, pickup) -> list[DriverState] # top ~20 by haversine
def _rank(cands, pickup) -> list[(driver, eta)] # ETA-sorted
def _dispatch(ride_id, ranked) -> Assignment | NoDriver # offer loop + claim
def _claim(driver_id, ride_id) -> bool # atomic single-trip guard
The split matters: _gather and _prune are cheap and touch only in-memory state; _rank is expensive (calls ETA) and runs on a pruned set; _dispatch is where latency actually goes, because it waits on humans. The claim is a single atomic operation, isolated from all the ranking work above it.
Component 3 — ETA / Routing¶
Responsibility: answer "road-network seconds from A to B under current traffic," fast enough to rank ~20 candidates inside the match budget.
Straight-line distance is not an ETA — a driver 400 m away across a river with no nearby bridge is 12 minutes out, while one 900 m away down a clear avenue is 3 minutes. So ETA runs a shortest-path query over a weighted road graph where edge weights are live travel times. Computing Dijkstra from scratch per query is too slow at scale, so production systems precompute acceleration structures (contraction hierarchies or equivalent) that answer a point-to-point query in well under a millisecond over an in-memory graph, then layer a learned correction for real-world pickup friction (finding the passenger, parking, one-way streets). Matching calls it in a batch for the pruned candidates:
Batching the ~20 candidate origins against the single pickup destination is what keeps ETA cost at ~20 queries/match instead of one round-trip per candidate.
Component 4 — Surge / Pricing¶
Responsibility: per cell, turn the recent demand/supply imbalance into a fare multiplier that both rations scarce cars and pulls more drivers in.
class Surge:
def observe_request(cell) # increment demand window
def multiplier(cell) -> float # from demand:supply ratio
For each cell it keeps a rolling window (say the last 2 minutes) of request count as demand, and reads available-driver count in the cell's k-ring from the Geo Index as supply. The multiplier is a bucketed function of the ratio — e.g. ratio < 1 → 1.0×, 1–2 → 1.5×, 2–4 → 2.0×, capped. It is recomputed every few seconds per active cell and published so Matching can read it in one lookup. It is intentionally cheap and lossy: a lost surge computation just recomputes on the next tick.
Core algorithm — matching the 6pm downtown request¶
Walk the threaded scenario through match() with its numbers. The rider drops a pin downtown at 6pm; there are ~500 online drivers within 2 km, each reporting every 4 seconds.
- Compute the pickup cell.
cell = cell_of(pickup.lat, pickup.lng, res=8)→ one H3 hexagon (~460 m edge). - Gather candidates.
query(cell, k=2)readskRing(cell, 2)= 19 hexagons covering a ~2 km disk. Downtown at rush hour these buckets hold ~500 driver states. Filter tostatus == available— say ~180 are idle and not on a trip; the other ~320 are carrying passengers. - Prune before spending on ETA. Sort the 180 available by cheap haversine distance to the pin and keep the closest 20. This is the latency-optimality tradeoff made concrete: computing a road-network ETA for all 180 would cost 180 routing queries; pruning first cuts that to 20, a 9× reduction, and the 21st-closest car is almost never the best pickup anyway.
- Rank by real ETA.
batch_time_to(20 origins, pickup)returns road-network seconds. The nearest-by-line car (across a one-way street) comes back at 6 minutes; the third-nearest, on the same avenue, comes back at 2 minutes and ranks first. Straight-line pruning got us the right set; road ETA picks the right car. - Price it.
Surge.multiplier(cell)— downtown at 6pm, demand (requests in the last 2 min) far exceeds idle supply, so the ratio lands around 2, returning 1.8×. Return202to the rider now with the 2-minute ETA and 1.8× estimate; the human is no longer waiting on a blank screen. - Dispatch loop. Offer to the #1-ranked driver; push the offer; wait ≤15 s. If they accept, run
_claim. On decline or timeout, fall through to #2, then #3. At 6pm acceptance is high (drivers want the surge fare), so this usually resolves on the first or second offer — time-to-match ~2–4 seconds including the human tap. - Atomic claim.
_claim(driver_id, ride_id)flips the driver's assignment and inserts the trip in one conditional step (below). If it wins, publishmatched; the rider's screen shows the car, and that car's ongoing 4-second location updates animate it moving toward the pin.
The whole path touched in-memory state for steps 1–3, ~20 routing queries in step 4, one surge lookup in step 5, and exactly one durable strongly-consistent write in step 7. Everything expensive was bounded before it ran.
Sequence diagram — a match under the atomic claim¶
Rider Matcher GeoIndex ETA Surge Assignment Driver
│ POST /rides │ │ │ │ │ │
├────────────▶│ query(cell,k=2) │ │ │ │
│ ├───────────▶│ 500 states │ │ │
│ │◀───────────┤ │ │ │ │
│ │ prune→20; batch_time_to │ │ │
│ ├──────────────────────▶│ ETAs │ │ │
│ │◀──────────────────────┤ │ │ │
│ ├─ multiplier(cell) ────┼─────────▶│ 1.8× │ │
│◀─ 202 matching, eta 2m, 1.8× ───────┤ │ │ │
│ │ offer #1 ─────────────┼──────────┼────────────┼─────────▶│
│ │◀──────── accept ──────┼──────────┼────────────┼──────────┤
│ ├─ claim(driver,ride) CAS ─────────┼───────────▶│ ok │
│ │ insert trip (durable) │ │ │
│◀─ push: matched, driver=D, car@… ───┤ │ │ │
│◀╌╌ car moves (D's 4s location updates flow through GeoIndex) ╌╌╌╌╌╌╌╌╌╌│
The expensive ranking happens before any human is involved; the one consistency-critical operation is the single CAS on the assignment row.
Concurrency and edge cases¶
- Double-dispatch (the assignment race). Two matchers, serving two riders, both rank driver D first and both offer. Both drivers-side accepts arrive. The guard is a compare-and-set on
driver_assignment:UPDATE driver_assignment SET ride_id=:r, version=version+1 WHERE driver_id=:d AND ride_id IS NULL. Exactly one update affects a row; the other sees zero rows changed, treats its accept as lost, apologizes to that driver, and the matcher falls through to its next candidate. The location index never arbitrates this — only the assignment row does. - Accept-after-timeout. A driver taps accept at second 16, after the matcher already gave up and offered #2 who accepted. The claim CAS fails (the row is no longer null / the ride is taken), and the late accept returns
409. The offer carries an expiry the client checks too, but the server-side CAS is the real guard — never trust the client's clock. - Idempotent ride request. A rider on a flaky connection retries
POST /rides. Requests carry a client-generated idempotency key; the matcher records it against theride_idso a retry returns the existing in-flight match rather than starting a second dispatch for the same rider (and a second surge charge). - Out-of-order location updates. GPS packets can arrive out of order over mobile networks. Each carries a
ts; the index upsert only overwrites if the incomingtsis newer than the stored one, so a delayed stale packet cannot rewind a driver's position. - Stale / ghost drivers. A driver whose app crashes stops reporting but might linger in a cell. The TTL on each entry (a few update intervals) evicts them, and the match-time
status == availablecheck plus a freshness check ontsskip any entry older than, say, 15 seconds — so a stale car is never offered a trip. - Cell-boundary flapping. A driver parked exactly on a cell edge can jitter between two cells on successive GPS readings, causing churn. The reverse
driver_id → cell_idmap means each update cleanly moves them (remove-from-old, add-to-new) rather than duplicating, and the k-ring query spans neighbors anyway, so a driver on a boundary is still found from either side. - Location vs assignment consistency. These are deliberately different: a driver flipped to
on_tripindriver_assignmentmay still showavailablein the location index for a second or two until their next update. The matcher therefore re-checks the authoritative assignment row at claim time; the locationstatusis only a cheap pre-filter, never the final word.