Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Worked design: matching riders to drivers

A location firehose, proximity matching, and an offer state machine — the three hard problems of dispatch.

Why not keep driver positions with the trips?

Riders request a trip; the system finds nearby available drivers, offers the job, and tracks the trip to completion. The first instinct is one database: a drivers table with a position column, next to trips. The estimate says no. Say 1 million active drivers pinging location every 4 seconds — 250,000 location writes/second against maybe a few hundred trip requests/second. For dispatch those 250,000 writes are disposable, since each ping is superseded by the next one four seconds later, while the few hundred trip writes must never be lost. In one store, the disposable flood competes for the same write capacity as the writes that matter, and can bury them. So the estimate splits the system in two: a write-heavy location side that must be cheap and can tolerate losing a ping, and a low-volume dispatch side that must be correct. Split them by durability requirement, into separate stores.

The location side: wrong by a few seconds, on purpose

Driver pings are the textbook firehose (see High-write ingestion): buffer through a log behind a thin ingest service (it authenticates the device; apps never write to the log directly), keep only the latest position per driver in a TTL'd geospatial index (cell → drivers, see Geospatial indexing & proximity search), and let history flow to analytics in batches. A driver whose pings stop simply expires from the index, so presence heals itself; whether that driver is free to take a trip is the dispatch side's state, below. That heartbeat-plus-TTL signature is the one Presence & ephemeral state describes for online indicators.

Location path: absorb, index, expire

The TTL decides how wrong this side is allowed to be, which makes it a correctness bound, not a cleanup nicety. Ranking candidates by a position from two minutes ago dispatches a driver who left; with a 30-second TTL and a ping every 4 seconds, a driver who goes silent stops being a candidate within 30 seconds. That bound needs the time the ingest service received the ping, carried in the event, not the moment the index consumer got to it: a ping that sat in a lagging log must not renew a silent driver, so the index skips a ping older than the one it holds and the query drops entries older than 30 seconds.

The dispatch side: right every time

Matching is a query (drivers in my cell + neighbors, ranked by distance and rating) — but assignment is the hard part: two riders must never book the same driver. The natural code reads first and writes second, and under concurrency it double-books:

  1. Dispatcher 1, serving rider A, runs SELECT … WHERE driver_id = 7 AND state = 'available' and finds driver 7.
  2. Dispatcher 2, serving rider B, runs the same query a few milliseconds later and also finds driver 7.
  3. Dispatcher 1 sets driver 7 to offered with a plain UPDATE and sends driver 7 the offer for rider A's trip.
  4. Dispatcher 2 does the same for rider B. Driver 7 now holds two offers.

Model the driver's side of the offer as a state machine — available → offered → assigned, and back to available when the offer is declined or expires — with every transition a conditional update that only succeeds from the expected prior state (Transactions & isolation levels explains why a condition inside the write closes the race): SET state='offered', offer_id=? WHERE driver_id=? AND state='available'. The accept and the expiry use the same pattern and also name the offer (WHERE driver_id=? AND state='offered' AND offer_id=?), so a late tap on an expired offer cannot accept the next one, and a slow sweeper cannot release a driver who already holds a newer offer. With that condition, dispatcher 2's update finds driver 7 already offered, changes no row, and moves to the next candidate. The winner is decided by whose conditional update succeeded, never by who read "available" first. Modelling the states themselves, with their events and guards, is what State machines: states, events and guards covers.

Offer the job to one driver with a 15-second expiry; a decline or timeout moves to the next candidate. The offer goes out through a queue (Message queues & async workers) rather than an inline call to the push provider: a third party's slow second must not become the rider's, and a lost push only lets the expiry fire.

Dispatch path: query, offer, conditionally assign

Each failure lands on one side

  • Geo index lost. It rebuilds itself from the ping stream within one TTL window. Ephemeral state with a live source needs recovery time, not backups.
  • Dispatch service crashes mid-offer. The offer carries an expires_at, enforced by the accept condition (AND expires_at > now()) and by a sweeper that releases the driver only while that same offer still holds them; the state machine makes abandoned offers self-cleaning instead of leaking locked drivers.
  • No terminal states. Offers that can't expire and trips that can't be cancelled leak drivers into a permanently-busy limbo — every state machine needs its exits drawn.
  • Sequential offers. Offering to one driver at a time is slower to match than broadcasting to five drivers — but with broadcast the first conditional accept wins, the other offers must be withdrawn at once, and drivers who tapped accept a moment too late are told the job is gone, which is a product decision as much as an engineering one.

Two paths, one meeting point

Ride-Sharing Dispatch is this design with more around it. The skill it tests here is restraint: the location firehose and the offer state machine stay two separate paths that meet only at the geo-index query, and the offer edge carries its states and its 15-second expiry. The challenge also asks for live trip updates and payment, which this article does not draw. Food Delivery Platform keeps the same dispatch core and adds a third side, the restaurant, whose accept or reject is a second state machine.

Practice this