Lesson 8 of 8 · 60 min

Worked design — marketplace/dispatch + mock

Geo dispatch (H3/S2), atomic matching, ETA/surge, two-sided consistency, fraud altitude, 45-min mock rubric, and pointer to ml-system-design for AI-native rounds.

Lesson 8 · Capstone

Marketplace / dispatch + mock rubric

Two-sided systems under time pressure

Ride-sharing / food delivery / freelance marketplaces force geo indexing, matching/dispatch, ETA, surge, fraud signals, and two-sided consistency (rider thinks they’re matched; driver must agree). Uber’s H3 (reported 2018): hexagonal hierarchical index, 16 resolutions; uniform neighbor distance vs square/geohash diagonal ambiguity. Uber real-time push platform (reported ~2020): >70,000 QPS push class with gRPC streaming. DoorDash dispatch eng posts (reported) emphasize greedy + ML scoring and cost-aware assignment. This is the L5–L6 classic. We end with a self-scored mock rubric and a pointer to ml-system-design for AI-native pivots. Instrument marketplace health with: match rate, match time p99, cancel rate, ETA error, driver utilization, and payment auth success. Those metrics tell you whether geo, dispatch, or payments is sick — not a generic CPU graph alone.
Running example: ride hailing. Rider requests trip; system finds nearby drivers; one accepts; track trip; price with optional surge; pay. Same skeleton maps to DoorDash-style delivery with extra merchant constraints. Marketplace correctness is a state machine wearing a map costume — if accept is not atomic, no amount of H3 poetry saves double-dispatch.

Requirements & NFRs

  1. 01Cities / multi-region launch?
  2. 02p99 match time target (e.g. < 5–30s to offer)?
  3. 03Can drivers reject? stacked trips?
  4. 04Pricing: upfront fare vs meter + surge?
  5. 05Fraud: promo abuse, GPS spoofing altitude?
  6. 06Consistency: double-dispatch to two drivers forbidden.
  7. 07Payment auth hold vs capture timing?
  8. 08Cold start in a new city?

Capacity sketch (decision-linked)

python Marketplace fairness and second-order effects: always offering the geographically nearest driver can starve drivers one block away and create cancellation loops; acceptance probability and idle time belong in the score. Surge without smoothing creates UX whiplash and gaming. Payment auth holds expire — your state machine must handle expired holds before trip start. These product-systems overlaps are where L6 candidates sound different from L5: they see incentives and failure modes, not only geo indexes.
1# Heuristic example — label as interview assumptions2rides_per_day = 5_000_0003ride_qps = rides_per_day / 86_400          # ~60 QPS starts; peaks 5–10× in cities4# Location updates dominate if naive:5# 5M active drivers * 1 Hz = 5M writes/s → impossible as row-per-ping OLTP6# Budget after sampling/batching, e.g. target ~10k–100k geo-index updates/s class78# Uber-class reported anchors (label reported):9# - push platform >70k QPS10# - H3 res ~9 city-scale cells; neighbor rings for nearby query11# - dispatch is not the largest byte pipe; GPS ingest is1213# DECISIONS FORCED:14# 1) do NOT write raw 1Hz GPS to primary OLTP15# 2) in-memory geo index (H3/S2 cells) for active supply16# 3) Kafka (or equiv) for location stream → cold analytics17# 4) match engine separate from trip SoT state machine
Geo index (H3 / S2 / geohash). Map lat/long → cell IDs. Drivers live in cells; request queries center cell + ring neighbors (k-ring). Cell size trades precision vs fan-out. Update driver cell on significant move, not every GPS tick. Memory store (Redis geo / custom) for active supply; cold history elsewhere. H3 (Uber reported rationale): hexagons give more uniform neighbor distances than square geohash diagonals. S2 is Google’s spherical geometry library; fine if stack already uses it. PostGIS is great at low scale / complex polygons, hard as the sole index at millions of moving points.
python
1def find_candidates(lat, lng, k=2, limit=20):2	cell = geo.cell(lat, lng)3	cells = geo.kring(cell, k)4	drivers = []5	for c in cells:6		drivers.extend(supply.active_in(c))  # memory index7	drivers = filter_eligible(drivers)     # status, capacity, constraints8	return rank_by_eta(drivers, lat, lng)[:limit]910GEO INDEX TRADEOFF11Index       Pros                         Cons                      Pick when12----------  ---------------------------  ------------------------  ---------------------13PostGIS     SQL, rich geo queries        hard shard at 1M+ movers  low scale / polygons14H3          uniform hex neighbors        approx; library           ride/food dispatch15S2          strong geometry lib          neighbor dist varies      Google-centric stacks16Geohash     simple                       rectangles; density skew  prototypes

Matching / dispatch

Flow: request → pin fare → candidate set → offer to top driver(s) with timeout → accept → lock trip. Strategies: offer one-by-one (simpler consistency) vs batch / parallel offers (marketplace efficiency; Uber-style deadline-driven dispatch discussions). Critical: single assignment — use atomic claim (compare-and-set trip state CREATED→OFFERED→ACCEPTED) so two drivers cannot own one trip. On cancel: re-dispatch with new candidates; preserve rider UX with realtime status events.
python
1def accept_trip(trip_id, driver_id):2	# atomic transition protects two-sided consistency3	ok = db.cas(4		trip_id,5		expect_status="OFFERED",6		expect_driver=driver_id,7		new_status="ACCEPTED",8	)9	if not ok:10		return 409  # already taken / expired offer11	notify_rider(trip_id)12	return 2001314# Trip state machine (sketch)15# REQUESTED → OFFERED → ACCEPTED → EN_ROUTE → IN_PROGRESS → COMPLETED16#                ↘ EXPIRED/CANCELED → re-dispatch or fail

ETA, surge, payments, fraud (altitude)

ETA: distance/speed heuristics → traffic model service → cache ETAs by cell pairs. Used in ranking candidates and pricing UX. Surge: demand/supply imbalance per geo cell → multiplier with caps and smoothing; recompute on an interval; show upfront to rider. Surge is a control loop, not a constant. Payments: auth hold on match, capture on complete; refunds on cancel rules; Stripe-style idempotency keys. Fraud: promo abuse, GPS spoofing, collusion — async scoring + policy hooks; do not invent a full ML fraud platform unless asked (ML companion track for model systems).

End-to-end ride narration

Rider app → API (rate limited) → pricing → trip row → geo supply query → offer via WS/push to driver → accept CAS → both parties track via realtime → complete → payment capture → async analytics. Failures: no drivers (expand ring / wait / surge), payment fail (cancel policy), GPS loss (last known + penalty), region/city outage (degrade that city), driver cancel (re-dispatch).

Senior signals vs mid-level

code
1TOPIC       MID-LEVEL                         SENIOR2----------  --------------------------------  -----------------------------------------3Geo         “Postgres + PostGIS”              H3/S2 cells; resolution; boundary effects4Dispatch    “find nearest driver”             parallel offers; timeouts; re-dispatch;5                                              fairness; atomic claim6Surge       “raise price when busy”           cell supply/demand; smoothing; caps; UX7Failure     “retry”                           GPS dropout, ETA degrade, payment fallback8Scale       “more servers”                    GPS sampling budget; index write path

Capstone mock — 45 minutes

code
1MOCK CLOCK20–8 min   Requirements + NFRs + non-goals (multi-city stretch)38–13 min  Capacity: rides/day, location update strategy, geo query QPS413–20 min API + data model (trip, driver, location cells, payments)520–30 min High-level diagram + dispatch deep dive (CAS offer/accept)630–40 min ETA/surge OR multi-city OR failure modes (pick one deep)740–45 min Cost, metrics that page, 10× story, open questions89Self-score (1–5): framing · capacity-with-why · data model ·10dispatch correctness · tradeoffs · failure/ops · communication1112SENIOR TELLS (use across the whole track)131 Names a number in first 60s142 States NFRs explicitly153 Identifies hot partition + mitigation164 Calls out read/write asymmetry175 Consistency vs availability for the use case186 Failure modes + recovery197 Cost unit ($/ride, $/1k req)208 What NOT to build at this scale219 Observability: what pages; SLO2210 Evolution at 10× / 100×

When the round turns AI-native

AI-native companies still run classic SD, but prompts may embed retrieval, inference, agent orchestration, or evaluation. Do not invent a half-baked RAG pipeline in this track’s style. Use the same framework (scope, capacity, dataflow, failure, cost), then switch depth to the existing companion course ML & LLM System Design (ml-system-design) for GPU memory, KV cache, embedding/index, eval harnesses, and model serving. Classic primitives here still apply to the non-ML edges (gateway, rate limit, multi-tenant, multi-region).
Capstone win condition: you drive the clock, keep dispatch correct under concurrency, and narrate what breaks at 10× — without cargo-culting a dozen databases.

Interview answers — marketplace capstone

  1. 01Match in <5s? → H3 candidates + cached ETA + parallel offers + timeout ladder.
  2. 021M GPS pings/s? → sample/batch; Kafka; memory geo index; cold store async.
  3. 03Why H3? → hex neighbor uniformity (Uber reported rationale); still approx.
  4. 04Surge fairly? → cell supply/demand, smooth, cap, explain to rider.
  5. 05Driver gaming? → fraud signals, acceptance quality, cooldown.
  6. 06Payment fail mid-trip? → policy state machine; retry capture; support path.
  7. 07GPS drift? → last known + radius penalty; map-match when available.
  8. 08Traffic routing? → ETA service / map provider; cache segments.
  9. 091000 cities? → city-sharded control planes; local supply indexes.
  10. 10A/B dispatch? → shadow assignment + marketplace metrics (cancel, ETA error).
  11. 11Cold start city? → incentives/surge caps; seed supply; smaller rings.
  12. 12ETA accuracy? → road graph + traffic features; measure error, not vibes.
articleUber — H3: Hexagonal Hierarchical Spatial IndexUber EngineeringarticleUber — Real-Time Push PlatformUber EngineeringarticleDoorDash — ML and optimization for dispatchDoorDash EngineeringarticleHelloInterview — Uber problem breakdownHello Interviewarticleinterviewing.io senior system design guideinterviewing.io

Data model and APIs

code
1POST /trips/estimate → {eta, price, surge}2POST /trips → {trip_id, status=REQUESTED}3POST /trips/{id}/accept4POST /trips/{id}/start|end5POST /drivers/{id}/location  {lat,lng,ts,speed?}6GET  /drivers/nearby?lat&lng&radius78drivers(id, cell_id, lat, lng, status, last_ping_at, vehicle_type)9trips(id, rider_id, driver_id, status, pickup, dropoff, prices, timestamps)10trip_events(trip_id, type, ts, payload)  -- audit1112# Active supply in memory keyed by H3 cell; durable driver profile in OLTP

Dispatch deep dive — parallel offers

Parallel offers: send offer to top N drivers with a deadline; first valid accept CAS wins; others get revoke. Improves match time vs sequential ringing, increases cancel/noise if N is too large. Score drivers by ETA, acceptance probability, fairness (who has been idle), vehicle constraints. Timeout ladder: expand ring or raise surge if no accept. Always keep the trip state machine as source of truth for who owns the trip.
code
1DISPATCH SEQUENCE21. Create trip REQUESTED + fare quote id32. Query H3 ring → candidates43. Rank → top N54. Mark OFFERED (version++) + notify drivers65. Accept: CAS OFFERED→ACCEPTED for that driver only76. Revoke outstanding offers87. Track EN_ROUTE → IN_PROGRESS → COMPLETED98. Payment capture; async analytics1011If step 5 is not atomic, you will double-dispatch under load.
Multi-city: shard control plane by city/region; supply indexes are local; pricing configs local; payments global with idempotency. Data residency may pin trip PII. Failures isolate per city so one region’s outage does not take global API down — cell-level degrade.

Cross-cutting synthesis for the whole track

code
1FIVE INSIGHTS TO CARRY OUT OF TRACK 221. Hot partitions are the recurring villain (celeb, viral code, busy channel, surge cell).32. Read/write asymmetry shapes architecture before brand names do.43. Caches are state with a staleness budget, not free performance.54. Quantify before you architect; label numbers reported vs heuristic.65. Production systems evolve (Cassandra→Scylla, pure push→hybrid, squares→H3).78FANOUT CHEAT9one-to-many normal → push10celeb/power-law → hybrid11DM → small fanout either way12chat rooms → stream + per-channel order13marketplace → geo pull + parallel offer
Final practice: run the 45-minute mock twice — once for ride-hail, once for food delivery (extra merchant prep time constraint). Score yourself on the senior tells checklist. Anything below 4 on dispatch correctness or capacity-with-why is a re-drill before real interviews.

Checkpoint

Two drivers hit accept on the same trip at once. What prevents double dispatch?

AWhoever’s HTTP request arrives at the LB first magically wins without storage checksBAtomic state transition / CAS on trip (only one OFFERED→ACCEPTED succeeds)CEmail both drivers a congratulations note
Sign up free to answer and see why

Checkpoint

Active drivers send GPS at 1 Hz. Naively writing every ping to a relational primary will…

ABe fine indefinitely at city scale without designBBlow write capacity — sample/batch updates and maintain a geo index of approximate positionsCOnly affect mobile battery, not the backend
Sign up free to answer and see why

Checkpoint

Rider requests a ride; 50 drivers within 2 km; need sub-5s match. Best approach?

ASynchronous scan of all drivers with full Dijkstra per candidate on the request thread with no geo indexBH3-based geo index → candidate cells + neighbors → score by ETA on cached segments → offer top N in parallel with timeoutCBroadcast offer to all 50 with no atomic claim
Sign up free to answer and see why

Checkpoint

Surge pricing design needs to…

ABe a single global constant foreverBTrack demand/supply per geo cell on an interval, smooth multipliers, show upfront where product requiresCAlways max out surge to 10× for revenue
Sign up free to answer and see why

Checkpoint

Interviewer pivots: “Now add an LLM that rewrites support tickets for trip disputes.” What should you do in this curriculum’s spirit?

ASpend the remaining time deriving CUDA kernelsBApply the same SD framework to the feature edges, then point deeper model/RAG/serving tradeoffs to ml-system-design companion depthCRefuse to discuss anything AI-related
Sign up free to answer and see why

Marketplace math + mock scorecard

code
1HEURISTIC CAPACITY2rides/day 5e6 → ~60 start QPS avg; city peaks 5–10x3drivers active * 1Hz GPS → millions/s if naive → MUST sample/batch4geo queries: H3 cell + k-ring → rank ETA → offer top N5match QPS is usually << GPS ingest QPS — size the location pipe first67REPORTED ANCHORS8Uber H3: hex hierarchy, uniform neighbors (2018 blog)9Uber push platform: >70k QPS class gRPC streaming (2020 blog)10DoorDash: optimization + ML scoring for dispatch (eng blog)1112CORRECTNESS CORE13trip state machine + CAS accept → single assignment14parallel offers with revoke losers15payment idempotency keys; auth hold → capture1617SURGE18per-cell supply/demand on interval; smooth; cap; show upfront1920MOCK 45m SELF-SCORE (1-5 each)21framing | capacity-with-why | data model | dispatch CAS22tradeoffs | failure/ops | communication23FAIL if double-dispatch possible even with pretty multi-region2425SENIOR TELLS (track-wide)26number in 60s; NFRs; hot key; R/W asymmetry; failure+cost;27what NOT to build; what pages; evolution at 10x2829AI PIVOT30same framework on edges; ml-system-design for model guts

Could you run the 45-min marketplace mock end-to-end and self-score without freezing on dispatch races?

New to itGetting thereConfident

Takeaways

  • Marketplace SD = geo supply index + atomic match + ETA/surge + payments idempotency.
  • Budget location updates; cell indexes beat scans.
  • Two-sided consistency is the correctness heart (CAS/claim).
  • Mock rubric rewards process and dispatch depth over logo density.
  • AI-native pivots → same framework, companion `ml-system-design` for ML/LLM guts.

Track complete: primitives → framework → senior layer → shortener → feed → chat → rate limit/search → marketplace. Rehearse mocks aloud; keep numbers decision-linked; label production figures reported vs heuristic.

Sources

Free to read · better with Enzo

Learn it with Enzo

Save your progress, answer the checkpoints, and let Enzo quiz you on what you just read.

Continue with EnzoSign up free