Matching at scale: geo-sharded dispatch
- Shard the matcher and geo index by city cells so dispatch scales horizontally and fails locally.
- Make in-flight matching state recoverable: lease-based shard ownership and rebuild-from-stream.
From 1.6: the offer protocol and the accept-time invariant. From 2.2's check: in-flight offers are hidden state in a "stateless" service. From 2.3: city sharding. This lesson applies the same partitioning to the matcher's memory.
Dispatch quality needs a coherent view of a local market — every driver and open request in one area, in memory, updated by the second. So we shard the matcher the same way we sharded the data: each dispatch shard owns a set of hex cells (roughly, cities or districts of megacities), holds its supply/demand picture in memory, subscribes to its cells' location stream, and runs the offer protocol locally. A shard-ownership map (backed by a coordination service granting leases) routes requests; leases expire, so a dead shard's cells are claimed by a survivor within seconds.
The crucial four-nines question: what happens to in-flight offers when a shard dies? Answer: the in-memory picture is a cache, rebuilt from streams — supply from the next 4-second pings (1.4), open requests re-read from the trip store (Requested state, 1.7). Offers in flight at the moment of death are simply lost, and that is a designed loss: the new shard re-dispatches those requests, the accept-time conditional assignment (1.6) makes double-assignment impossible, and the rider experiences a few extra seconds of "finding your driver". We protect the invariant absolutely and the latency statistically — knowing which property gets which guarantee is the lesson.
flowchart TB
REQ["Ride requests"] --> RT["Dispatch router — cell to shard lease map"]
RT --> DS1["Dispatch shard 1 — city A cells, in-memory market"]
RT --> DS2["Dispatch shard 2 — city B north"]
RT --> DS3["Dispatch shard 3 — city B south"]
PINGS[["Location stream — partitioned by cell"]] --> DS1
PINGS --> DS2
PINGS --> DS3
COORD[("Coordination service — leases, 10 s TTL")] --- RT
COORD --- DS1
COORD --- DS2
COORD --- DS3
DS1 --> TS[("Trip store — conditional assign, source of truth")]
DS2 --> TS
DS3 --> TS
Worked example: a dispatch shard dies at peak
sequenceDiagram
autonumber
participant DS2 as Shard 2 (dying)
participant CO as Coordination service
participant DS3 as Shard 3 (survivor)
participant K as Location stream
participant TS as Trip store
participant R as Affected riders
DS2--xCO: lease heartbeats stop
CO->>CO: lease expires after 10 s
CO->>DS3: cells of shard 2 claimable — DS3 acquires
DS3->>K: subscribe to acquired cells
Note over DS3,K: supply picture rebuilds in ≤ 4 s (next pings)
DS3->>TS: query open requests in acquired cells
TS-->>DS3: 214 requests in Requested state
DS3->>DS3: re-run offer protocol for all 214
DS3->>R: offers resume — riders saw ~15 s extra wait
Note over TS: any late accept from a shard-2 offer hits conditional assign — no double assignment possible
Cells at shard boundaries: a pickup on the border needs candidates from the neighbor shard. Solve with overlap reads (a shard may read — never offer from — a one-ring halo of neighbor cells via the shared geo index) or align boundaries with natural barriers (rivers, highways) where markets barely mix. Never let two shards offer the same driver concurrently without the conditional assign backstop.