TOUGH TONGUE AI
  • Home
    LogoTOUGH TONGUE AI

    RESOURCES

    Loading...

    HomeLibrarySD Mock · Design Uber Backend

    SD Mock · Design Uber Backend

    Overview

    Design Uber's dispatch backend on a live architecture board — drag components, wire them up, and defend your design to an expert interviewer who watches every move.

    Your Instructions

    Design Uber backend

    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):

    • Notepad. Shared notes. Requirements, capacity math, schema, and end-of-session feedback live here. You can type in it too.
    • Architecture board. Your design canvas. Drag typed components, wire them, label edges, mark scaled tiers as distributed. If it is not on the board, it is not in your design.

    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."

    Design choices interviewers probe

    Read this before you go in. These are the decisions, and why they matter.

    The ratio that defines the problem

    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.

    A hash table in front of the tree

    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.

    Shard by driver, search by scatter-gather

    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.

    Getting positions onto screens: push vs pull

    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.

    Dispatch: one ride, three drivers, first accept wins

    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.

    Trips are durable; positions are disposable

    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.

    Reference solution

    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.

    Requirements (lock these or take the defaults)

    • Drivers report location + availability every 3 s; riders see nearby drivers live on a map
    • Rider requests a ride; nearby drivers are notified in real time; first to accept is assigned exclusively
    • During a trip both parties see each other's position; driver marks complete and returns to the pool
    • Scale: 300M customers, 1M drivers; 1M daily active customers, 500K daily active drivers; 1M rides/day; global but every query is local
    • Non-functional: absorb the write rate; bounded staleness (propose ~15 s for search, 3–5 s in-trip — the material leaves it unpinned, and asking is a strong signal); exactly-once driver assignment; availability via replicas + fast rebuild
    • Out of scope unless asked: surge, payments, pooling, road routing, fraud

    Capacity

    • 500K drivers ÷ 3 s ≈ 167K location writes/s vs 1M rides/day ≈ 12 requests/s (~116 at 10× peak) — ~14,000:1. The whole design follows from this ratio
    • DriverLocationHT: 1M drivers × 35 B ≈ 35 MB (old lat/lng + new lat/lng + 3-byte ID). Inbound bandwidth 500K × 19 B per 3 s ≈ 3.2 MB/s — nothing; the cost is the 167K ops/s, not the bytes
    • Driver QuadTree ≈ 12 MB (500K × 24 B; ~1,000 leaf cells at 500/cell) — you partition for throughput and availability, not size
    • Location trail: ~9,600 points per driver-day → ~91 GB/day raw, ~33 TB/yr; downsample off-trip (~5× saving), full resolution during trips

    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.

    Components to put on the board

    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)
    
    • Location Service. Ingests the 3-second pings, discards out-of-order updates by timestamp, overwrites the hash O(1), appends to the trail asynchronously, marks the driver dirty for the next refresh. Sharded by hash(driver_id) so no shard goes hot geographically.
    • Redis (DriverLocationHT). The 3-second truth: old + new position and the 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.
    • Spatial Index Service. In-memory QuadTree partitions, each holding a random slice of drivers, each answering "near this point" for its slice only. Up to 15 s stale by design. Trees split in different places per partition; that is fine.
    • Worker (refresh). Ships coalesced change-sets to the partitions every ~15 s; applies removes/inserts in batch, splitting cells once per batch, skipping same-cell moves.
    • Aggregator Service. Fans a search to every partition, merges top-k lists, reconciles against the hash, ranks by ETA, creates offers, performs the CAS accept. Deadline + partial results to cap tail latency.
    • WebSocket Server. The push channel: ride offers to drivers, in-trip position streams to the fixed pair. Browsing riders poll instead — no viewport subscriptions.
    • Postgres (Trips). The state machine, sharded by ride_id. The serialisation point for "first accept wins." Payment and receipts hang off COMPLETED, never block dispatch.
    • Index-Map Service. Reverse index: partition → set of {driver_id, lat, lng}. Exists for one reason — rebuilding a dead partition without scanning the whole driver table while riders silently see fewer cars.

    Walk one ride request: rider taps Request

    1. The app sends the request with pickup, dropoff and an idempotency key; the Aggregator writes a Trips row in REQUESTED, deduplicating on the key.
    2. It scatters a nearby-drivers query to every Spatial Index partition — drivers are sharded by ID, not geography — and each returns its own top-k near the pickup.
    3. It merges the partial lists, then reconciles each candidate against DriverLocationHT for current position and availability, because the index is up to 15 s stale.
    4. It ranks by ETA from the Maps service — the index generates candidates, the router ranks them; straight-line distance ignores rivers and one-way streets.
    5. It creates offers for the top 3 with a few-second TTL in Redis and hands them to the WebSocket Server for delivery.
    6. First driver to accept wins by CAS on the ride row (REQUESTED/OFFERED → ACCEPTED), plus the mirror CAS claiming the driver. Losers get a cancellation; a late acceptance after TTL is refused.
    7. Nobody accepts → offer to the next 3; after a few rounds, widen the radius.
    8. Both parties subscribe to each other's live position over the socket; on completion the fare is computed from the trail and 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.

    Schema

    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
    
    • Location and index shard key: hash(driver_id) — random distribution, no geographic hot shards
    • The old position is stored so the refresher knows which cell to remove from without searching the tree
    • Trip transitions are durable before acknowledged; available flips on acceptance, not trip start, or you offer a second ride to a driver already driving to a pickup

    Scaling and wrap-up

    • Both location tiers scale by adding shards; the aggregator scales stateless. Keep index partitions few — 12 MB of state needs throughput, not room
    • Failure: replicas everywhere + SSD snapshots; a failover loses a few seconds of positions and the fleet re-reports itself within one 3-second cycle. Both replicas of an index partition die → rebuild from the Index-Map reverse index, then re-apply the last 15 s from the hash; meanwhile degrade to fewer candidates, never an error
    • First metrics: p99 nearby-search (the scatter's tail), index refresh lag vs the 15 s budget, offer-acceptance rate and time-to-match, double-dispatch count (must be zero)
    • If time: surge (supply/demand per cell on the same index, slower cadence), pooling (matching becomes routing under detour constraints), GPS spoofing (server-side plausibility on speed and route), multi-region (shard the stack by region; identities are global)

    Equally defensible variants

    Fixed 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.

    More in System Design Interview Prep: AI Coach Edition

    • SD Mock · Design Dropbox
    • SD Coach · Transactional Systems
    • SD Mock · Design Ticketmaster
    • SD Coach · Batch and Stream Pipelines
    • SD Coach · Real-Time Chat and Collaboration
    • SD Mock · Design Facebook Messenger
    • SD Mock · Design Yelp / Nearby Friends
    • SD Coach · Media Streaming
    • SD Mock · Design YouTube / Netflix
    • SD Mock · Design Instagram
    • SD Coach · Agentic AI
    • SD Coach · Agentic AI Architectures (Slides)
    View the full course (43 sessions) →