Skip to content

02. Food Delivery 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 three that carry the design's weight — three-sided matching (reconciling customer, restaurant, and courier state), the batch dispatch optimizer, and live order tracking — and pins down the data, the algorithm the optimizer actually runs, and the concurrency corners where a courier gets double-booked or a meal falls through the cracks.

Data models

The order is the transactional spine. It carries the three parties' identities, the geography dispatch needs, and an explicit state so no transition can be skipped.

CREATE TABLE orders (
    order_id        BIGINT       PRIMARY KEY,
    city_id         INT          NOT NULL,          -- shard key
    customer_id     BIGINT       NOT NULL,
    restaurant_id   BIGINT       NOT NULL,
    courier_id      BIGINT       NULL,              -- set at ASSIGNED
    state           SMALLINT     NOT NULL,          -- see state machine below
    drop_lat        DOUBLE       NOT NULL,
    drop_lng        DOUBLE       NOT NULL,
    prep_ready_at   TIMESTAMP    NULL,              -- predicted food-ready time
    eta_at          TIMESTAMP    NULL,              -- current predicted delivery
    idempotency_key UUID         NOT NULL,
    version         INT          NOT NULL DEFAULT 0,-- optimistic-lock guard
    created_at      TIMESTAMP    NOT NULL,
    UNIQUE (customer_id, idempotency_key)           -- dedupe retried placements
);

CREATE INDEX idx_dispatch  ON orders (city_id, state, prep_ready_at);  -- dispatch pool
CREATE INDEX idx_courier   ON orders (courier_id, state);              -- courier's active legs

Three deliberate choices. city_id is the shard key because every dispatch, tracking, and supply query is local to one metro — there is no cross-city join, so sharding by city gives clean isolation and lets a hot city scale alone. The (customer_id, idempotency_key) unique constraint makes order placement idempotent at the store, so a client retry after a network timeout can never mint a second dinner. And version is the optimistic-lock column that lets the dispatch commit claim a courier without a distributed lock (below).

The courier's live state is not in this table — it lives in the in-memory index, because it changes every 4 seconds and durability is worthless:

# Geospatial index (Redis GEO + a state hash per courier)
GEOADD couriers:city:{cid}  {lng} {lat}  courier:{courier_id}     # position
HSET   courier:{courier_id}  state {AVAILABLE|EN_ROUTE|AT_STORE}  \
                             capacity_left {n}  batch_order_ids {...}  ts {epoch}

# Radius query dispatch runs per restaurant:
GEOSEARCH couriers:city:{cid} FROMLONLAT {r_lng} {r_lat} BYRADIUS 3 km ASC COUNT 40

capacity_left is what makes batching expressible in the index: a courier already carrying one order but with room for another still shows up as a candidate, tagged with how much slack it has. The travel-time matrix is a separate small cache keyed by cell pair:

# Refreshed once/minute from the routing engine, under live traffic
HSET  ttm:city:{cid}  "{cellA}:{cellB}"  seconds        # directed, A→B

Component internals

Component 1 — Three-sided matching: the order state machine

Responsibility: keep the customer, restaurant, and courier views of one order consistent, and expose exactly when an order is dispatchable. The subtlety of "three-sided" is that the three parties commit at different times — the customer at placement, the restaurant at acceptance, the courier at assignment — and the order must not advance until the relevant sides have committed.

STATES:  CREATED → CONFIRMED → ASSIGNED → PICKED_UP → DELIVERED
                 ↘ REJECTED           ↘ (courier declines → back to CONFIRMED pool)
         (any)   → CANCELLED

transition(order_id, from_state, to_state, mutation):
    # single guarded write; refuses out-of-order transitions
    UPDATE orders
       SET state = to_state, <mutation>, version = version + 1
     WHERE order_id = :order_id AND state = from_state
    # 0 rows updated  → someone else moved it; caller re-reads and reconciles

The guard WHERE state = from_state is the whole trick: transitions are conditional writes, so two actors racing to move the same order (a courier accepting while a timeout job cancels) cannot both win — one updates one row, the other updates zero and backs off. Dispatchability is a derived predicate, not a state: an order is dispatchable when state = CONFIRMED AND prep_ready_at - now() <= courier_travel_horizon. That is why an order does not enter the dispatch pool the instant the restaurant accepts — it enters when the food is close enough to ready that a courier dispatched now arrives as it comes up, which is what keeps couriers from idling at counters and food from cooling on the pass.

Component 2 — Batch dispatch optimizer

Responsibility: on each tick, assign the pool of dispatchable orders to couriers — allowing batches — so as to minimize total food-in-transit time and courier miles, subject to the food-hot budget and courier capacity.

class DispatchTick:
    def run(cell_id) -> list[Assignment]:
        orders   = pool.dispatchable(cell_id)               # e.g. ~30 orders
        couriers = geo.candidates(cell_id, radius_km=3)      # e.g. ~40 couriers
        trips    = self.enumerate_trips(orders, couriers)    # singles + feasible batches
        cost     = self.score(trips)                         # via ETA service
        return self.solve_assignment(cost)                   # min-cost matching

    def enumerate_trips(orders, couriers):
        # single-order trips: every (courier, order) within reach
        # batch trips: (courier, [o1, o2]) only if batch_feasible(o1, o2, courier)
        ...

    def batch_feasible(o1, o2, courier) -> bool:
        # o2 added to o1's trip must keep BOTH within the food-hot budget
        extra = incremental_delay(courier, o1, o2)   # detour + second-drop wait
        return extra <= FOOD_HOT_BUDGET_MIN and detour_km(o1, o2) <= MAX_DETOUR

The optimizer does not consider every possible batch — that is combinatorially hopeless. It prunes to feasible batches first (batch_feasible throws out any pairing that would blow the +8-minute food-hot budget or wander too far), then scores the survivors, then solves. Pruning before scoring is what keeps the cost matrix small enough to solve in milliseconds per cell.

Component 3 — Live tracking and ETA

Responsibility: push each customer their courier's position and a refreshed ETA every ~5 s, cheaply enough to do it for 33,000 orders at once.

def refresh_eta(order) -> minutes:
    courier_cell = cell_of(geo.position(order.courier_id))
    drop_cell    = cell_of(order.drop_lat, order.drop_lng)
    # two matrix lookups + remaining prep, NOT a fresh routing call
    if order.state < PICKED_UP:
        return ttm[courier_cell][store_cell] + wait_at_store + ttm[store_cell][drop_cell]
    return ttm[courier_cell][drop_cell]           # already carrying the food

The ETA is a couple of hash lookups against the travel-time matrix plus the kitchen estimate — no per-request routing call. That is the design's answer to 6,600 ETA recomputes/second: precompute the expensive part (cell-to-cell times, once per minute for the whole city) and make the per-order path a memory read. To stop the number from flapping second to second, the pushed ETA is smoothed (an exponential moving average) so it drifts rather than jumps.

Core algorithm — one dispatch tick during the 7pm rush

Put the threaded scenario on the optimizer. At 7pm the city is taking 14 orders/second. The dispatch tick runs every 15 seconds, so each tick a given cell sees roughly its share of 14 × 15 ≈ 210 newly-dispatchable orders citywide; partitioned across, say, seven busy H3 cells, one cell's tick handles ~30 dispatchable orders against ~40 candidate couriers. Here is the tick.

  1. Collect the pool. Query idx_dispatch for CONFIRMED orders in this cell whose prep_ready_at is within the travel horizon: 30 orders. Query the geospatial index for couriers within 3 km, including partly-loaded ones with capacity_left ≥ 1: 40 couriers, of which 6 are already carrying one order and could take a second.

  2. Enumerate trips. For each order, the reachable couriers give ~30 × (a handful each) single-order candidate trips. Then form batch trips: for the 6 partly-loaded couriers and for pairs of orders from the same or adjacent restaurants, test batch_feasible. Say 25 order-pairs pass the +8-minute food-hot budget and detour cap; the rest are pruned. The candidate set is now a few hundred trips, not the astronomically many theoretical ones.

  3. Score each trip. Ask the ETA service for each trip's cost. A single trip's cost is pickup_travel + wait_for_ready + drop_travel. A batch trip's cost is the total food-in-transit time across both orders plus a penalty for the delay imposed on the first order's food. Using the travel-time matrix, all few-hundred scores are lookups — no routing calls in the hot loop.

  4. Solve the assignment. Build the cost matrix (couriers × trips, with the constraint that each courier takes at most one trip and each order appears in exactly one chosen trip) and solve the min-cost assignment. At 30 orders × 40 couriers the matrix is tiny; a Hungarian or min-cost-flow solve is well under a millisecond. The solver naturally prefers a batch when its combined cost beats two singles — which during the rush it usually does, because couriers are the scarce resource.

  5. Commit atomically. For each chosen assignment {courier → [o1, o2]}, claim the courier and transition the orders in one guarded step (below). Of the 30 orders, suppose 12 batch into 6 two-order trips and 18 go single — 24 couriers used instead of 30. Across the whole rush that ratio is the 1.4 orders/trip from the overview, and it is why 14,000 couriers cover work that would otherwise need 20,000.

  6. Leftovers roll forward. Any order that found no feasible courier this tick (fleet momentarily short in this cell) stays in the pool and ages; if its unassigned-order age crosses a threshold, it escalates — widen the radius, relax the batch budget, or trigger the supply mitigations. It is never dropped.

The step that makes this survive the rush is #2's pruning and #4's per-cell partitioning: without them the solve is citywide and combinatorial and misses its 15-second window; with them each cell solves a 30×40 problem in parallel in milliseconds, and the tick comfortably fits.

Sequence diagram — dispatch commit with an atomic courier claim

DispatchTick   OrderService     Orders DB        Geo Index     Courier App
     │              │               │                │              │
     │ solve() → assign C→[o1,o2]   │                │              │
     ├──── claim(courier=C) ───────────────────────▶│              │
     │              │               │   HSET state EN_ROUTE if AVAILABLE (CAS)
     │◀─── ok / already-taken ──────────────────────┤              │
     │  (if already-taken: drop this assignment, C is reused elsewhere)
     ├─ transition(o1 CONFIRMED→ASSIGNED, courier=C, ver-guard) ─▶│
     │              ├──── UPDATE … WHERE state=CONFIRMED AND version=v ─▶│
     │              │◀──── 1 row (won)  /  0 rows (lost, reconcile) ─────┤
     ├─ transition(o2 CONFIRMED→ASSIGNED, courier=C) ─────────────▶│
     │              │                                              │
     │              ├──────────── push offer (o1+o2) ─────────────▶│
     │              │◀──────────── accept ─────────────────────────┤
     │              ├─ emit ASSIGNED events → bus                   │
     │              │                                              │
     │  (courier declines) ──▶ release claim, orders → back to pool │

The claim on the geospatial index (compare-and-set AVAILABLE → EN_ROUTE) is the fast first guard; the versioned order transitions are the durable second guard. Both must succeed for the assignment to stand, and either failing rolls the courier and orders back into the next tick's pool.

Concurrency and edge cases

  • Double-assignment of one courier. Two cells' ticks (or two orders in one tick) can target the same edge-of-boundary courier. The compare-and-set claim on the courier's index state (AVAILABLE → EN_ROUTE) is the arbiter: exactly one CAS wins, the loser drops that assignment and the courier is matched elsewhere or next tick. Without it, one courier gets two conflicting pickups and one order strands — the single consistency corner the overview flagged as non-negotiable.
  • Order moved out from under a commit. Between building the solve and committing, a CONFIRMED order might get cancelled by the customer. The versioned transition (WHERE state = CONFIRMED AND version = v) updates zero rows, the dispatch commit sees the order slipped away, and it releases the claimed courier for the next tick.
  • Idempotent placement. A retried POST /orders carries the same idempotency_key; the UNIQUE (customer_id, idempotency_key) constraint collapses it to the first order rather than creating a duplicate dinner and a duplicate charge.
  • Courier declines or goes offline after assignment. The offer has a short accept deadline. On decline or timeout, the orders transition ASSIGNED → CONFIRMED (back to the pool) and the courier's claim is released; the next tick re-matches them, aged, so they are prioritized.
  • Stale courier position. If a courier's last ping is older than a few seconds (ts in the index), dispatch treats them as lower-confidence — it may still consider them but widens the ETA margin, and tracking shows the last known dot rather than a gap. A courier silent for too long is dropped from the candidate set entirely.
  • Batch commitment after pickup. Once a courier has picked up a batch, it cannot be unbundled — the food is in the bag. So batch_feasible is checked at assignment time against predicted conditions; if traffic then worsens, the second order's ETA drifts but the batch holds. This is the accepted risk of batching, and it is why the food-hot budget is set conservatively (+8 min, not +15).
  • Prep-time error feeding dispatch. If a restaurant's prep_ready_at is optimistic, a courier arrives to wait; if pessimistic, food cools on the pass. Per-restaurant learned prep models bound this, and dispatch uses the predicted ready time plus a small buffer rather than the restaurant's raw self-report.
  • Tracking vs dispatch view skew. Both read the same geospatial index, so a customer's dot and the dispatcher's view of that courier are always the same snapshot — there is no separate tracking position that could disagree with the one dispatch matched on.