Two million cars,
moving, every four seconds.

What the system has to do.

Five flows. Everything else in the product hangs off them, and everything hard about the design is already visible in the first three.

Out of scope here, on purpose: payments, driver onboarding, fraud, routing itself (assume a road-graph ETA service exists and answers in ~30 ms), maps and map matching. They are real systems, but they are not what makes dispatch hard.

The board on the right is a printed city plan with a hexagonal index laid over it, plus the dispatch bench off to the side. Drag things. Press I for a keyboard-reachable index of everything on it.

What “working” means, in numbers.

The 2-second budget is not generous once you spend it honestly:

Which leaves ~1.5 s of slack — and that slack is exactly what a batched matching window later spends, deliberately, to buy a better assignment.

How much of everything.

Start with the only number that matters — how often a car tells you where it is. Move the sliders below; every figure in green is computed live.

If you durably wrote every ping. Three replicas, plus an index entry, plus a write-ahead log — call it 3.2× the raw bytes on disk:

So you don’t. The current position lives in memory and is overwritten in place; the durable path gets a downsampled trace, and only for drivers who are actually on a trip (you need those for fare disputes and safety, nothing else):

The live index itself is small. That is the whole reason this design works:

Connections and matches. 25M trips/day averages 289/s; peak hour runs about 3× the daily mean.

Why a B-tree cannot do this.

The first design anyone writes is a table and a bounding box:

-- drivers(id, lat, lon, state, updated_at), INDEX (lat, lon)
SELECT id, lat, lon FROM drivers
WHERE lat BETWEEN 37.7610 AND 37.7790
  AND lon BETWEEN -122.4269 AND -122.4041
  AND state = 'idle'
ORDER BY st_distance(pt, :rider) LIMIT 12;

Run the scan on the board. The ochre band is what the index actually reads; the ring is what the rider actually wanted.

Three separate failures, in order of severity.

1. A B-tree is a one-dimensional total order. A composite index on (lat, lon) can only seek on the leading column. Because lat is a float, no two rows share a leading value, so lon never narrows the seek — it is a post-filter applied to every row the latitude range returns. You are running a 1-D range scan and throwing most of it away.
2. The band is not local. On a single global table, a ±1 km latitude range selects drivers at that parallel everywhere on Earth. San Francisco’s query reads San Jose, Seoul’s reads Pyongyang. Read amplification stops being 2–3× and becomes 20–50×.
3. It is the wrong table to index at all. Every one of the 500,000 pings per second changes an indexed column. That is not an in-place update; it is a delete plus an insert into a random B-tree leaf, plus a WAL record, plus later compaction or vacuum. Index maintenance, not the query, is what kills it.

The fix is not a faster B-tree. It is to choose a one-dimensional order that preserves two-dimensional locality, so that “near in space” becomes “near in the index”. That is a space-filling curve, and it is what every real answer here is built on.

Geohash, quadtree, S2, H3.

The inset on the board makes the neighbour argument concrete. Switch between the two patches in the dock and watch the ring.

The choice. H3 at resolution 9 for the live index, keyed by the 64-bit cell id, with resolution 8 and 7 parents stored alongside for cheap roll-ups (surge, supply heat, analytics). Real H3 figures, for calibration:

Each H3 resolution divides cell area by seven. The board’s four levels divide by about 2.7 so that all four fit legibly on one plan — the argument is identical, the ratio is drawn smaller.

Fine cells, or few cells.

A dispatch is a k-ring search: take the rider’s cell, take its neighbours, then theirs, until the rings cover the radius you are willing to send a car across. Ring k contains 3k² + 3k + 1 cells — 1, 7, 19, 37, 61, 91.

The radius is the product decision — how far you are willing to send a car — and k is only the bill for covering it. At 800 m that bill is one ring at res 7 and five at res 10, for exactly the same ground. Move both sliders and watch the two numbers trade places.

That is the whole trade, and it is not a trade between speed and accuracy — it is a trade between lookups and contention. Going one resolution finer multiplies the cells you touch by about three and divides the cars per bucket by about seven. So dispatch latency is U-shaped, and the minimum is not at either end:

Drop the rider pin into an empty corner of the plan to see exactly that: the rings expand to cover the radius, nothing inside it is free, the request fails and the cell heats up.

500,000 writes a second, and none of them matter for long.

The ingest path is deliberately split in two, and the split is the whole trick.

Why the hot path has no durability at all. The value of a position decays to zero in one ping interval. If a geo-index shard dies, every driver it owned re-pings within four seconds and the replacement is fully populated. Rebuild time is pingInterval, not a restore from backup. Paying for durability on 500K writes/s to protect four seconds of a self-healing cache is the single most expensive mistake available here.

Connections, not requests. Drivers hold a long-lived socket — a WebSocket or a QUIC stream — because the alternative is 500,000 TLS handshakes a second, and because the server needs to push offers. Sockets are the cost centre:

Gateways are stateless fan-in: terminate TLS, authenticate, decode, and forward to the geo-index shard that owns the driver’s cell. They keep no per-driver state beyond the socket, so a gateway can be drained and replaced without touching dispatch.

Backpressure. A ping is the most droppable message in the system: if a shard is saturated, drop the older queued ping for that driver and keep the newest. Coalescing by driver id turns a queue into a state and makes overload harmless.

Nearest-first is a local optimum.

Greedy dispatch answers each request the instant it arrives with the nearest idle car. It is correct, it is fast, and it is measurably worse than waiting.

The failure, minimally. Rider A appears; the only car nearby is 200 m away and greedy gives it to A. One second later Rider B appears 80 m from that same car; B now gets a car from 900 m out. Total pickup distance 1,100 m. Had you waited one second and solved both together: 80 + 400 = 480 m.

Batched window matching. Collect requests for a fixed window — 2 to 5 seconds — then solve a bipartite minimum-cost assignment over the whole batch. Cost is road ETA, not straight-line distance, plus terms for driver acceptance probability and for how long the rider has already waited.

Press Run a 20-minute A/B in the dock. Both arms replay the same seeded demand against the same starting board, so the difference is the algorithm and nothing else.

The second figure is empty running: the share of a busy driver’s time spent driving to a pickup rather than carrying someone. It is the number that decides whether a shift pays, and shortening pickups is the only way to move it.

What it costs. Up to one window of added latency on every request — which is exactly the 1.5 s of slack the SLO budget left over. And a harder algorithm: Hungarian is O(n³), so at 400 requests × 900 candidate drivers you use an auction or min-cost-flow solver with a candidate cap, which lands in single-digit milliseconds.

The board is a control loop.

Per cell, over a rolling window, count open requests and idle drivers. The ratio is the only input:

The loop. Price rises → some riders defer (demand elasticity) and drivers move toward the ochre cells (supply elasticity) → the ratio falls → the price falls. Turn the surge toggle on and watch the tokens migrate: unmatched requests drop and average ETA follows, without a single extra driver existing.

Consistency of a price. A quote is generated once, stamped with a quote id, and honoured for its TTL. It must not be recomputed at accept time, or a re-tap after a network blip charges a different fare. So the quote is a small, durable, idempotent record — while the surge surface that produced it is soft state that can be thrown away and recomputed from the last few minutes of events.

Degrading. If the pricing service is unavailable, serve 1.0× and keep matching. A city that dispatches at the wrong price is a bad day. A city that will not dispatch is an outage.

Chip height is open demand in that cell. Chip ink density is the surge multiplier. Both are damped, so you can see the loop settle rather than snap.

One trip, one driver, exactly once.

Everything so far has been soft state. The trip is not. It is the one strongly consistent object in the system, and it is small enough that this is affordable: a single-partition record keyed by trip id, with linearisable writes.

Never double-dispatch a driver. The offer is not a message, it is a compare-and-set on the driver record:

// atomic; fails if anyone else got there first
CAS(driver.state, 'idle' → 'offered', expect version = v)
  ok    → send the offer, arm a 15 s TTL
  fail  → drop this candidate, take the next from the k-ring

Both the matcher and the TTL reaper race on that same record, and only one wins. The board’s Offer to a second driver button attempts exactly this race — it is refused, and the refusal is logged.

Exactly-once acceptance. Mobile networks retry. The driver’s accept carries an idempotency key of (tripId, driverId, offerId); the server records the outcome against that key. A retry returns the stored result rather than re-executing. “Exactly once” here is at-least-once delivery plus idempotent application — there is no other kind.

Shard by geography, then deal with the consequences.

Dispatch queries are local, so the partition key must be spatial. Sharding by driver id would force every k-ring search to fan out to every shard — the one thing the index exists to prevent.

The hot-city problem. Shards are equal in area and wildly unequal in load. The largest metro can carry 60,000 concurrent drivers and thousands of requests a minute while a small one carries two hundred. Fixes, in the order you should reach for them:

1. Sub-shard the hot city by res-6 parent cell, with a routing table the gateways cache. A k-ring near a sub-shard boundary fans out to at most two or three sub-shards — bounded, because the ring is bounded.
2. Split reads from writes inside the shard: ingest lands on a per-cell striped write path, dispatch reads a lock-free snapshot. They stop competing for the same locks.
3. Only then add machines. The index is 288 MB globally — you are sharding for throughput and blast radius, never for capacity, and remembering that keeps the design honest.

Failover. Kill a district in the dock and watch it grey out. What actually happens:

In-flight trips are untouched. A trip that is already accepted lives in the trip store, and its live tracking is a socket fan-out through the gateway — neither depends on the geo index. What stops is new dispatch inside the failed district. Requests raised during the window are queued client-side and retried with the same idempotency key, so the recovery produces no duplicate trips.

Every decision, what it bought, what it cost.

Press H to strip every overlay for a clean shot of the board, M to cycle motion modes, I for the keyboard index.