Loading...
A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match. This is a hard question, and the signal concentrates in three places: noticing the write:read ratio before designing anything, the two-tier location store and the staleness it buys, and the race hiding inside "first driver to accept wins."
The trap is designing the search system and ignoring the firehose. 500K drivers reporting every 3 seconds is ~167K location writes/sec against ~12 ride requests/sec — roughly 14,000:1. This is not a search system with some writes; it is a write firehose with a trickle of searches on the side. Candidates who reach for PostGIS or Redis GEO without asking whether it absorbs that write rate, or who jump straight to the matching algorithm, are designing the 12-requests-per-second problem and ignoring the 167,000-writes-per-second one.
Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):
Build incrementally while you talk. Draw the driver write path and the rider read path as two separate entries — not one "client" box. Trace one ride request from rider tap to driver accept through your diagram. Argue the tradeoff, not "industry standard."
Read this before you go in. These are the decisions, and why they matter.
Compute the write rate before designing anything: 500K active drivers ÷ 3 s ≈ 167K writes/s; 1M rides/day ≈ 12 requests/s (~116 at 10× peak). Say the ratio out loud. Three traffic classes fall out of it — location writes (167K/s), rider map polls (tens of thousands/s at peak), dispatch (12–116/s) — with different latency budgets and failure consequences. Do not put them behind the same service.
The Yelp-style QuadTree is the right index for "who is near this point" — and it dies here, because its contents move. Every driver movement is a remove-plus-reinsert, and every insert can split a cell. At 167K updates/s the tree spends its life repartitioning; a stopped driver whose GPS jitters across a cell edge becomes an oscillator.
The fix is not a different tree. It is a second tier in front of it: DriverLocationHT, an in-memory hash table (driver_id → old + new position, available flag; 35 bytes/driver, 35 MB for 1M drivers) that absorbs every write as an O(1) overwrite. A worker refreshes the QuadTree from it in batches, guaranteeing the index reflects a driver within 15 seconds. Storing the old position next to the new is what makes the refresh cheap — the refresher knows which cell to remove from without searching.
Own the staleness with a number: at 30 mph (~13.4 m/s), 15 seconds is up to ~200 m of error. Fine for generating candidates — you re-read the true position from the hash before offering — and wrong for the moving dot on the rider's map, which is fed from the hash, never the tree. Cheap refinements worth volunteering: coalesce (five reports in a window → one tree op), skip updates that do not change cell (kills most tree mutations), and ±10% hysteresis on the split/merge limit so dense cells stop thrashing.
Two options for partitioning both tiers. By region (city, geohash prefix): reads hit one partition, but downtown at 6pm, the airport, and a stadium emptying all make one server hot. By hash of DriverID: uniform by construction — no shard gets hot because a stadium emptied — at the cost that every nearby-search must fan out to all partitions and merge. Ride demand is geographically concentrated, so uniform load is worth the scatter.
Say the surprising consequence: the whole driver QuadTree is only ~12 MB (500K × 24 B). You are not partitioning for capacity — you are partitioning because one machine cannot absorb 167K writes/s and serve queries at the same time. So keep the partition count modest, and mitigate the fan-out's tail (a query is as slow as its slowest partition) with a deadline plus partial results — a rider does not need every nearby driver.
A driver's new position has two audiences, and they want different mechanisms.
Push (subscribe riders to the drivers their query returned) breaks on one question: what happens when a new driver enters the area the rider is watching? Nobody resubscribes them without tracking every rider's viewport server-side — a moving-object join for every open app. Pull (the app polls every ~5 s with its current location) is stateless, picks up newcomers for free, and a backgrounded app just stops asking.
The answer that gets full credit is both, for different things: pull for browsing the map (5-second staleness on uncommitted dots is invisible), push for ride offers and in-trip tracking — an offer with a seconds-long TTL cannot wait for a poll, and once a ride is accepted the subscriber set is exactly two known parties, so the viewport problem does not exist.
Offer serially to the nearest driver and every decline costs a full TTL — three rounds at 15 s is 45 seconds of a rider staring at a spinner. So offer to the top ~3 in parallel and take the first acceptance. Now say what that sentence hides: two drivers accept 40 ms apart on different servers. The fix is a compare-and-set on the ride row — state='ACCEPTED', driver=X WHERE state='OFFERED' — so the database is the arbiter and the loser gets "too late." You need the mirror CAS on the driver's dispatch state too, or one driver can win two rides. Offers carry a TTL (Redis is a natural fit) and a late acceptance is rejected; the rider's request carries an idempotency key so a double-tap on a flaky network does not dispatch two cars. And reconcile before you offer: candidates came from a 15-second-stale index, so re-read availability from the hash first.
A position is overwritten every 3 seconds and the fleet re-reports itself after any crash — recovery is measured in seconds, not restores. A trip is money. Model it as an explicit state machine (REQUESTED → OFFERED → ACCEPTED → ARRIVING → IN_PROGRESS → COMPLETED, plus CANCELLED), every transition durable before it is acknowledged. A phone going dark mid-trip is normal, not exceptional: the trip stays IN_PROGRESS, the app buffers points and uploads on reconnect, the fare is computed from the reconstructed trail with gaps interpolated conservatively, and a sweeper force-closes trips that never resume.
One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.
Rough numbers are fine; the method is what gets graded. Use the ratio to justify the hash-in-front-of-index split, and the 12 MB to keep the partition count honest.
Two entry paths that never share a service: drivers write, riders read and request. The hash absorbs the firehose; the index answers proximity on a slower clock; the aggregator does scatter-gather and drives the dispatch handshake; trips are the only tier where correctness beats freshness.
Mobile Client (Driver App)
→ Load Balancer → Location Service (distributed)
↔ Redis (DriverLocationHT: old+new pos, available — 3 s truth)
→ Queue → Worker (batched refresh, ≤15 s) → Spatial Index Service (QuadTree partitions, distributed)
→ Cassandra (location trail, downsampled off-trip)
Mobile Client (Rider App)
→ API Gateway → Aggregator Service (distributed)
→ scatter-gather → all Spatial Index Service partitions
↔ Redis (reconcile true position; offers with TTL)
↔ Postgres (Trips — durable state machine, CAS accept)
→ Third-party API (Maps/ETA for ranking)
→ WebSocket Server → offers to drivers; in-trip updates to both
Index-Map Service (partition → {driver, pos} reverse index — the rebuild path)
Scheduler → Worker (trip sweeper: force-close abandoned IN_PROGRESS trips)
available flag — the flag, not position, is what removes a driver from the candidate pool. Feeds the rider's map and the pre-offer reconciliation. 35 MB.COMPLETED, never block dispatch.REQUESTED, deduplicating on the key.REQUESTED/OFFERED → ACCEPTED), plus the mirror CAS claiming the driver. Losers get a cancellation; a late acceptance after TTL is refused.available flips back to true.A location ping (the other path): app fires on its 3-second timer → Location Service checks the timestamp, overwrites old→new in the hash (O(1), no tree), appends to the trail, marks dirty. Every ~15 s the batched change-set hits the index. The ack carries a server-controlled next_report_interval — backpressure for stationary drivers or overload.
Two drivers accept 40 ms apart on different servers: without a serialisation point you assign one ride twice and the rider watches two cars converge. The CAS in the trip store — not a check-then-write in application code, not a distributed lock — is the answer.
A driver's phone loses signal for eight minutes mid-trip: the trip is not the connection. It stays IN_PROGRESS; the app buffers points and uploads on reconnect; billing reconstructs the trail, interpolates the gap conservatively, and flags implausible gaps for review. The sweeper force-closes trips that never resume so the driver is not pinned unavailable forever.
DriverLocationHT: driver_id → {old_lat, old_lng, new_lat, new_lng, available, updated_at} — Redis, 35 B/driver
Trips(ride_id, rider_id, driver_id, state, pickup, dropoff, requested_at, accepted_at, completed_at, fare) — Postgres, shard by ride_id
Offers(offer_id, ride_id, driver_id, sent_at, expires_at, outcome) — Redis, TTL a few seconds
Trail(ride_id | driver_id, lat, lng, ts) — Cassandra, append-only, downsampled off-trip, 90 days hot
IndexMap: partition_id → HashSet{driver_id, lat, lng} — Index-Map Service, replicated
available flips on acceptance, not trip start, or you offer a second ride to a driver already driving to a pickupFixed hierarchical cells — geohash, S2, or H3 — instead of a QuadTree: a move becomes a set-remove/set-add with no splits, no merges, no oscillation, and the two-tier design becomes optional; you trade adaptive cell sizing for a per-city resolution choice. Deriving the tree and then naming H3 as what production does is a strong finish; opening with "just use H3 / Redis GEO" skips the reasoning being tested. Kafka between ingest and refresh. Region-partitioned index with consistent hashing, if you answer the hot-region question. What matters is that you can argue the tradeoff.