Learnings

System design, part 9 of 12

HLD Case Studies: Advanced

Eight worked high-level designs of the harder kind asked at senior and staff level: payments, seat booking, ride hailing, video streaming, file sync, a web crawler, a job scheduler and a metrics pipeline. Every case follows the same five steps, so you can compare them and reuse the shape on a question you have not seen. All numbers are order-of-magnitude assumptions, stated so the arithmetic can be checked.

How to use these

Part 1 of 9 · the template and the pattern map

Each case is one part with five short chapters in a fixed order. Read one case end to end, then close the page and redraw its architecture diagram and its hardest deep dive from memory. The simpler cases are in HLD Case Studies: Core.

The five-step template

How to use these

StepYou produceTime in 45 minCommon mistake
1. Requirements and scale3 to 5 functional needs, non-functional targets with numbers, what is out of scope, one estimation tableabout 7 minEstimating everything. Compute only the numbers that change the design.
2. API and data model3 to 5 endpoints, the main entities, the store and whyabout 5 minPicking a database before knowing the access patterns.
3. High-level designOne diagram of 8 to 12 boxes, then the main write path and read path in wordsabout 10 minDrawing every component you know instead of the ones this problem needs.
4. Deep divesThe 2 to 4 hard parts, each with alternatives and a choiceabout 15 minGoing deep on the easy part. Name the hard part yourself before you are asked.
5. Trade-offs and follow-upsDecisions with what was paid, failure modes, what changes at 10xabout 5 minPresenting the design as free of cost.

Senior signal: in every case below one property is the reason the question exists (money is never duplicated, a seat is sold once, a host is never hammered). State that property in the first two minutes and let it drive every later choice.

Which patterns each case exercises

How to use these

The cases reuse a small set of ideas. Components are covered in Building Blocks, stores and stream processing in Data Systems, and coordination patterns in Distributed Systems Patterns.

CaseThe property that mattersPatterns it exercisesRevise in
Payment systemMoney moves exactly onceIdempotency keys, double-entry ledger, state machine, saga, outbox, reconciliationDistributed Systems Patterns, Data Systems
Seat bookingA seat is sold onceConditional writes, optimistic and pessimistic locking, TTL holds, admission queue, cache with stale readsData Systems, Building Blocks
Ride hailingFresh locations, one trip per driverGeospatial index, in-memory state with TTL, WebSockets, compare-and-set, partitioning by regionBuilding Blocks, Distributed Systems Patterns
Video streamingSmooth playback at low cost per byteObject storage, queue and worker DAG, CDN tiers, metadata and blob split, stream aggregationBuilding Blocks, Data Systems
File syncNo lost edit, few bytes movedContent-addressed blocks, change journal, long poll, versioning, write ordering across two storesData Systems, Distributed Systems Patterns
Web crawlerPolite, broad, no repeatsPriority and per-host queues, Bloom filter, fingerprints, hash partitioning, rate limitingBuilding Blocks, Data Systems
Job schedulerEvery due job runs, on timeLeases and visibility timeouts, fencing tokens, leader election, sharding, retries and dead lettersDistributed Systems Patterns
Metrics and click aggregationCorrect counts, cheap queriesDurable log, windows and watermarks, roll-ups, time-series storage, batch reconciliationData Systems, Building Blocks

Payment system and digital wallet

Part 2 of 9 · correctness when the outcome is unknown

Design a wallet: users top up from a card or bank through an external payment provider, pay merchants and send money to each other. This is the site's bank example at scale. It is asked because throughput is modest and correctness is everything: money must never be created, lost or moved twice, even when a call times out.

Requirements and scale

Payment system

KindRequirement
FunctionalTop up a wallet through an external provider. Transfer wallet to wallet and pay a merchant. Refund a payment. Show balance and statement.
Non-functionalNo double or lost money movement (consistency over availability on the write path). Durability with zero acknowledged writes lost (synchronous replication). 99.99% API availability. p99 under 500 ms for an internal transfer, under 2 s when the provider is involved. Every movement auditable for years.
Out of scopeOnboarding and identity checks, card issuing, currency conversion, chargeback workflow, lending.
QuantityArithmeticResult (approx.)
Daily active usersassumed, of 300M registered50M
Payments per day50M users x 2100M
Write QPS100M / 86,400 s; peak x51,160/s average, 5,800/s peak
Read QPS (balance, history)10 reads per write11,600/s average, 58,000/s peak
Ledger storage100M x 2 entries x 200 B = 40 GB/day; x 36514.6 TB/year
Payment rows100M x 500 B = 50 GB/day; x 36518 TB/year
Bandwidth1,160/s x 2 KB2.3 MB/s (about 19 Mbps), not a constraint

Interview tip: say out loud that a few thousand writes per second is small. The design is shaped by failure handling and auditability, not by load.

API and data model

Payment system

Entries are append-only and carry a signed amount. The balance on ACCOUNT is a cache of the sum of its entries, updated in the same transaction.
  • Store: a relational database with ACID transactions (PostgreSQL or MySQL, or a distributed SQL database), synchronously replicated, sharded by account id when one node is not enough. The reason is multi-row transactions and unique constraints, not query flexibility.
  • Money: integers in minor units (paise, cents) plus a currency code. Never floats.
  • Idempotency key: unique on (caller, key), stored with a hash of the request and the response, kept at least 24 hours.

High-level design

Payment system

The payment service owns the state machine, the ledger service owns the money. The provider is reached through one adapter and answers twice: in the response and by webhook.
  • Internal transfer (write): the payment service stores the idempotency key and a payment row, calls the risk service, then the ledger service posts two entries and updates both balances in one database transaction. An outbox row is written in that same transaction.
  • Top-up (write): the payment is saved as pending before the provider is called. The adapter sends the charge with our attempt id as the provider's idempotency key. The ledger is credited only after the provider confirms, by response or by webhook, whichever arrives first.
  • Read: balance comes from the account row on the primary for anything that decides a debit. Display reads and statements can use replicas, paginated by (account id, entry id).
  • Async: a relay publishes outbox rows to the event log. Notifications, analytics and reconciliation consume it and must be idempotent, because delivery is at least once.
  • Reconciliation: a scheduled job compares the provider's settlement report with our ledger and flags every difference.

Deep dives

Payment system

1. Double-entry ledger as the source of truth

Every movement is one transaction of two or more entries that sum to zero. Entries are never updated or deleted. A mistake is fixed by posting a reversing transaction.

TransactionAccountAmount (paise)Sum
T1: Rishikesh tops up 500.00provider_clearing-50,0000
wallet:rishikesh+50,000
T2: Rishikesh sends Sandhya 200.00wallet:rishikesh-20,0000
wallet:sandhya+20,000
T3: Sandhya pays a merchant 100.00, fee 2%wallet:sandhya-10,0000
merchant:store+9,800
revenue:fees+200
  • Sign convention here: positive means we owe the account holder more. The clearing account is money the provider owes us, so it runs negative until the settlement arrives. Real ledgers record debit and credit with account types; the invariant is the same.
  • Invariants to check continuously: each transaction sums to zero; all entries together sum to zero; every stored balance equals the sum of that account's entries.
  • Derived balance: the balance column is updated in the same transaction as the entries, and can be rebuilt by replaying entries. No overdraft: UPDATE account SET balance = balance - :amt WHERE id = :id AND balance >= :amt and abort if no row changed.
  • Deadlocks: a transfer touches two account rows. Always lock them in account id order.
  • Alternative rejected: a mutable balance column with no entries. It is fast, but it cannot explain how a balance came to be and cannot be repaired after a bug.

2. Idempotency end to end and the payment state machine

A timeout does not leave Pending. Only a definite answer from the provider moves a payment to a terminal state.
HopKey that makes a retry harmless
Client to APIIdempotency-Key header, unique constraint, stored response returned on replay
Payment service to ledgerUnique (payment id, entry type) on the ledger transaction, so a second post is rejected
Adapter to providerProvider idempotency key = our attempt id. A retry of the same attempt reuses it; a new key is used only after a definite failure
Provider webhook to usSignature check, then deduplicate on the provider's event id
Event log to consumersEvent id stored by each consumer (delivery is at least once)
  • Exactly-once effect is at-least-once delivery plus idempotent handling. No hop delivers exactly once on its own.
  • Each transition is a conditional update: UPDATE payment SET status = 'SUCCEEDED' WHERE id = :id AND status = 'PENDING', in the same transaction as the ledger post. If no row changed, another worker already did it and this one stops.

3. The external provider: sync call, webhook, reconciliation

After a timeout the payment may or may not have happened. The service never guesses: it waits for the webhook, asks the provider by key, and the conditional update makes whichever arrives second a no-op.
ChannelGives youWeakness
Synchronous responseFast answer for the user in the common caseLost on timeout or crash
WebhookAsynchronous results (bank transfers, 3-D Secure, delayed captures)Can be late, duplicated, out of order or never sent
Status poll by keyResolves pending payments older than a few secondsCosts provider quota; needs backoff
Reconciliation jobFinal safety net: settlement file vs ledger, daily or hourlySlow; differences go to a suspense account and a review queue

Failure mode: treating a timeout as a failure and retrying with a new key charges the customer twice. Treating it as success credits money that may never arrive. Unknown is a real state and needs its own handling.

4. One transaction or a saga

CaseUseWhy
Both accounts in one database or shardOne ACID transaction: entries, balances, payment status, outbox rowSimplest correct answer. Keep wallet balance and ledger in the same database so this stays possible.
Accounts on different shardsTwo local transactions through a transit account, driven by the outbox (or a distributed SQL database that does the two-phase commit for you)The credit leg cannot fail for a business reason, so it is retried until it succeeds; no compensation needed.
A step outside our systems (provider, bank payout)Saga with a hold: move funds to a holding account, call out, then settle the hold or release itAn external party cannot join our transaction. The hold keeps the money unspendable while the outcome is unknown.

5. Risk, card data and audit

  • Risk check placement: synchronously after validation and before any money moves, with a tight budget (about 100 ms) and a defined behaviour on timeout (decline or step-up above a threshold, allow below it). Heavier models run asynchronously on the event log and can freeze an account afterwards.
  • PCI scope: the card number is entered into the provider's hosted field and goes straight to the provider, which returns a token. Our systems store and pass only the token, so most of the platform stays outside PCI DSS scope.
  • Auditability: immutable entries, a row per state transition with actor and time, the raw provider messages kept, and write access to the ledger limited to the ledger service.

Trade-offs and follow-ups

Payment system

DecisionAlternativeWhy
Append-only ledger, balance derivedMutable balance onlyAudit and repair. Pays extra storage and one more write.
Relational, synchronous replicationEventually consistent key-value storeMulti-row atomic writes and no lost commits. Pays write latency and failover complexity.
Save PENDING before calling the providerCall first, write afterA crash after the call would leave a charge we know nothing about.
Saga with holds for external stepsTwo-phase commitProviders do not take part in 2PC. Pays for explicit pending states.
Outbox and event log for side effectsPublish directly after commitA crash between commit and publish loses the event.
Failure modeMitigation
Crash after provider success, before the ledger postRecovery worker scans PENDING payments older than N seconds and queries the provider; the webhook covers the same gap
Duplicate or out-of-order webhooksDeduplicate by event id; apply only legal state transitions
Two concurrent debits on one walletConditional balance update or row lock inside the transaction
Hot merchant account (thousands of credits per second on one row)Append entries without locking the merchant balance and fold them in periodically, or split into sub-accounts
Provider outageCircuit breaker, second provider behind the adapter, payments queue as pending rather than fail silently
  • How do you prove no money was lost? Sum of all entries is zero, balances match entries, ledger matches the provider settlement report. Run all three on a schedule and alert on any difference.
  • How does a refund work? A new transaction with reversing entries linked to the original payment, with its own idempotency key and its own provider call.
  • Multiple currencies? One account per currency. A conversion is two transfers through an exchange account at a recorded rate.
  • Can balance be read from a replica? For display only. Any decision to debit reads and writes the primary in one transaction.
  • What changes at 10x? Shard by account id, move statements to a read store fed by the event log, archive old entries to cold storage with periodic balance snapshots.

Senior signal: separating "delivered at least once" from "applied once", naming unknown as a state, and volunteering reconciliation as the last line of defence before the interviewer asks.

Ticket and seat booking

Part 3 of 9 · contention on scarce inventory

Design booking for concerts and cinemas: a user picks specific seats, holds them for a few minutes, pays and gets a ticket. It is asked because thousands of people race for the same seat and exactly one may win, and because a flash sale sends a hundred times the normal traffic at one event.

Requirements and scale

Seat booking

KindRequirement
FunctionalBrowse an event and its seat map with availability. Hold chosen seats for a few minutes. Pay and confirm. Release seats on cancel or expiry. Queue users fairly when demand exceeds capacity.
Non-functionalA seat is never sold twice (strong consistency on seat state). The seat map may be a few seconds stale. Hold p99 under 200 ms. Survive a 100x spike without the database falling over. Admission order roughly first come, first served.
Out of scopePricing rules, seat-map authoring, payment internals (see the payment case), resale, recommendations.
QuantityArithmeticResult (approx.)
Daily active usersassumed20M
Read QPS (browse, seat map)20M x 10 views = 200M/day; / 86,400; peak x52,300/s average, 11,600/s peak
Bookings1M/day / 86,40012/s average
Flash sale arrival2M users for 50,000 seats, arriving within 60 s33,000 new sessions/s at the edge
Flash sale booking loadadmit 500 users/s x 4 calls each2,000 requests/s on the booking path, by design
Storage1M bookings x 1 KB = 1 GB/day; seats: 10,000 live events x 5,000 seats x 100 B365 GB/year of bookings; 5 GB of live seats
Bandwidthavailability for 5,000 seats is about 1 KB; x 11,600/s12 MB/s peak; the 50 KB static layout comes from the CDN

Interview tip: the data is tiny. The whole problem is a short burst of contention on a few thousand rows, so the design goal is to control how much traffic reaches those rows.

API and data model

Seat booking

One row per seat per event. The seat row itself carries the hold and its expiry, so one conditional write decides who wins.
  • Store: a relational database sharded by event id. All seats of an event live on one shard, so holding three seats together is one local transaction.
  • Cache: availability per event in an in-memory store, refreshed from change data capture. It serves reads only and never decides a sale.

High-level design

Seat booking

Reads go to the CDN and the cache. Only admitted users reach the booking service, and only the booking service writes seat state.
  • Read: static layout from the CDN, availability from the cache. A seat that looks free but is not simply fails at hold time with 409 and the client refreshes.
  • Hold (write): one transaction flips every requested seat from free to held with an expiry. All seats or none.
  • Checkout: the payment is created with the hold id as its idempotency key. On success the seats move from held to booked, conditional on the hold still owning them.
  • Expiry: a delayed message releases the hold at its deadline. The hold query also treats an expired hold as free, so correctness never depends on the worker being on time.
  • Flash sale: the waiting room sits in front and releases users at a fixed rate with a signed, short-lived token that the gateway checks.

Deep dives

Seat booking

1. Preventing double booking

ApproachHowGood whenCost
Pessimistic lockSELECT ... FOR UPDATE on the seat rows, check, then updateContention is high and the transaction is shortWaiters queue on the lock; a slow transaction blocks others; never hold it across the payment
Optimistic lockRead the row with its version; UPDATE ... WHERE version = :vConflicts are rareUnder a flash sale most attempts fail and retry, wasting work
Atomic conditional update (chosen)One statement that sets held only if the seat is free; count the rows changedThe check fits in the WHERE clauseNone extra: one round trip, the row lock lasts for one statement
Distributed lock in a cacheSET seat:key NX PX ttl before touching the databaseShedding load before the databaseNot a correctness guarantee on its own (expiry, failover); the database condition must stay

2. Reservation state machine and the payment timeout

Held is the only state with a clock. Every transition is a conditional update on the current state and the owning hold id.
  • Make the hold outlive the payment: for example an 8 minute hold with a 6 minute payment session, so a payment that succeeds can still be confirmed.
  • Payment succeeds after the hold expired: try to take the same seats again atomically. If they are gone, refund automatically and tell the user. Never confirm seats the hold no longer owns.
  • Payment outcome unknown: keep the seats held (extend once) until the payment resolves, as in the payment deep dive.
  • Abuse: cap seats per hold and active holds per user, or bots hold the house without paying.

3. Flash sale: virtual waiting room and fairness

The queue absorbs the spike at the edge. The booking path sees a steady, chosen rate, and admission slows or stops as inventory runs out.
  • Queue page is static and served by the CDN. It polls a cheap status endpoint with backoff, so 2M waiting users cost little.
  • Fairness: first come, first served by enqueue time once the sale is open. Users who arrived before opening are shuffled into a random order, which removes the reward for hammering refresh at the exact second.
  • Token: signed, bound to the user and event, valid for about 10 minutes, one active token per user. The gateway rejects booking calls without one.
  • Alternative: plain rate limiting returns errors and rewards whoever retries fastest. A queue keeps order and gives an honest wait time.

4. Inventory in cache or database

Inventory lives inUse forRisk
Database only, cache for display (chosen for seats)Assigned seating, where each seat is a rowDatabase write rate is the ceiling, which the waiting room controls
Cache counter as the gate, database as the recordGeneral admission: an atomic decrement of "remaining" in the cache, then an order rowCache loss or failover can oversell or strand stock; needs a rebuild from the database and a reconciliation job
Database counterSmall sales: SET remaining = remaining - :n WHERE remaining >= :nOne hot row; split stock into buckets if it becomes the bottleneck

Trade-offs and follow-ups

Seat booking

DecisionAlternativeWhy
Conditional update in the databaseLock in a cacheThe database constraint is the only thing that survives every failure.
Hold with TTL before paymentLock the seat only at paymentUsers do not pay for seats that vanish. Pays with seats idle during abandoned holds.
Stale availability on readsRead seat state from the primaryProtects the database. Pays with occasional "seat just taken" errors.
Waiting roomAutoscale everythingInventory is fixed, so more servers only let more people fail faster.
Shard by eventShard by userMulti-seat holds stay in one transaction. Pays with one hot shard per hot event.
Failure modeMitigation
Expiry worker down, seats stuck as heldExpired holds count as free in the hold query; the worker only tidies up
User double-clicks or the client retries the holdIdempotency key returns the same hold
Cache shows sold-out seats as freeHold returns 409 with the taken seats; cache entries have a short TTL as a backstop
Hot event overloads its shardWaiting room rate set from measured shard capacity; move the event to a dedicated shard before the sale
Payment confirmed but booking write failsRetry the confirm from the payment event; refund if the hold is lost
  • How long should the hold be? Long enough to pay (5 to 10 minutes), short enough that abandoned seats return while buyers are still queued.
  • "Best available" instead of picking seats? The server picks adjacent free seats and applies the same conditional update; on conflict it picks again.
  • Hotel or flight inventory? Inventory is a count per room type per night, so a stay is a conditional decrement across several date rows in one transaction.
  • How do you show live availability? Push seat changes for the open event over a WebSocket or server-sent events from the change stream.

Senior signal: pointing out that scaling out cannot help when the inventory is fixed, so the answer is admission control plus one cheap atomic write, and that the hold must be correct even if every background worker is down.

Ride hailing

Part 4 of 9 · moving objects and real-time matching

Design a service that matches a rider to a nearby driver and tracks the trip live for both. It is asked for three things at once: a location stream with a very high write rate, a geospatial index over objects that keep moving, and a stateful dispatch flow where a driver must never be given two trips.

Requirements and scale

Ride hailing

KindRequirement
FunctionalDrivers stream their location. A rider gets a fare estimate and ETA, then requests a ride. The system offers the trip to a suitable nearby driver who accepts or declines. Both sides see live position and status. The trip runs through its lifecycle to a final fare.
Non-functionalMatch within about 10 s at p95. Driver positions at most about 5 s old. 99.99% availability for request and dispatch. A driver has at most one active trip. Losing an individual location point is acceptable.
Out of scopePayments, the routing engine itself, shared rides, driver onboarding, ratings.
QuantityArithmeticResult (approx.)
Daily active usersassumed20M riders, 5M drivers; 2M drivers online at peak, 1M on average
Trips20M/day / 86,400; peak x4230/s average, 900/s peak
Location writes2M drivers / 4 s interval500,000/s peak, 250,000/s average
Nearby-driver queries20M trips x 20 lookups = 400M/day; / 86,400; peak x44,600/s average, 18,500/s peak
Live index size2M drivers x 100 B200 MB, fits in memory
Location history250,000/s x 86,400 = 21.6B points/day x 50 B1.1 TB/day raw, before sampling and compression
Bandwidth in500,000/s x 100 B50 MB/s (400 Mbps) at peak

Interview tip: location writes outnumber trip writes by about 1,000 to 1 and have opposite needs. Say early that they get different stores: memory for the latest position, a database for trips.

API and data model

Ride hailing

DataShapeStoreWhy
Latest driver positioncell id -> set of drivers; driver -> {position, ts}, TTL 30 sIn-memory geo index, sharded by cityOverwritten every 4 s; durability is worthless, speed is everything
Driver statedriver -> AVAILABLE, OFFERED or ON_TRIP, with a versionKey-value store with compare-and-setThe single guard against double dispatch
Tripride id, rider, driver, status, fare, timestampsRelational or distributed SQL, partitioned by cityDurable, transactional status changes, used for billing
Location history(trip id, ts) -> pointEvent log into a wide-column or object storeAppend-only, large, read rarely (fare, disputes, analytics)

High-level design

Ride hailing

Two separate paths: the location stream on top (memory and a log), the trip flow below (a database). Dispatch is the only component that reads both.
  • Location (write): the driver app sends a point every 4 s over its WebSocket. The location service overwrites the driver's entry in the geo index and appends the point to the log. Nothing on this path touches a database.
  • Request (write): the ride service creates the trip row as matching and hands it to dispatch.
  • Match: dispatch reads nearby available drivers from the geo index, ranks the best few by ETA, reserves one with a compare-and-set and pushes an offer down that driver's socket.
  • Accept: the trip row gets the driver and the driver state becomes on-trip. On decline or a 10 to 15 s timeout the driver is released and the next candidate is offered.
  • Read: the rider's socket receives the assigned driver's position, which the location service fans out to subscribers of that trip.

Deep dives

Ride hailing

1. Geospatial index for nearest-driver search

IndexIdeaStrengthWeakness
GeohashInterleave latitude and longitude bits into a string; a shared prefix means a shared rectangle. 6 characters is about 1.2 km x 0.6 km.Just a string key: works in any key-value store or sorted indexTwo nearby points can sit in different cells, so always query the cell plus its 8 neighbours; cell shape varies with latitude
QuadtreeSplit a square into four whenever it holds too many pointsAdapts to density: small cells downtown, large in the suburbsAn in-memory tree that must be rebalanced as drivers move; harder to shard
Hexagonal cells (H3 style)A fixed hierarchy of hexagons; resolution 8 is about 0.7 square km per cellAll six neighbours are the same distance away, so "rings around a cell" is a clean radius search; also a good unit for surgeA library dependency; a hexagon's children do not fit exactly inside it
Cells give a cheap candidate set. The expensive routing ETA is computed only for the top few.
  • Choice: fixed cells (geohash or hexagons) as keys in an in-memory store, because moving a driver is two cheap set operations and the key shards naturally. A quadtree fits static points of interest better than moving drivers.

2. Location ingestion at 500,000 writes per second

DecisionChoiceAlternative and why not
TransportOne persistent WebSocket per driver, small binary messagesHTTP per update pays connection and header overhead 500,000 times a second
Latest positionOverwrite in memory with a TTL; a driver who stops sending disappearsA database row per update turns a cache problem into a write-scaling problem
HistoryAppend to a log, consume in batches into cold storageSynchronous history writes would couple dispatch latency to storage
ShardingBy city, then by cell range inside large citiesBy driver id spreads one city's drivers over every shard, so a nearby query fans out everywhere
ClientSend less often when stationary; batch points when offline and replay to history onlyFixed interval wastes battery and bandwidth

3. Dispatch and the trip state machine

Offered loops back to Matching until a driver accepts. Every transition is a conditional update, so a late accept on an expired offer is rejected.
  • No double dispatch: reserve the driver with a compare-and-set from AVAILABLE to OFFERED before sending the offer. Two dispatchers that pick the same driver cannot both succeed.
  • Greedy vs batched matching: greedy offers the nearest driver immediately (simple, low wait). Batched collects requests and drivers in an area for a few seconds and solves an assignment that minimises total pickup time (better overall, slightly slower first answer).
  • Dispatcher crash: the offer carries an expiry stored with the driver state, so a reserved driver frees itself; the trip stays in matching and another dispatcher picks it up.

4. Live updates, ETA, surge and partitioning

TopicApproach
Updates to both partiesDriver app holds a WebSocket (it sends constantly anyway). Rider app holds one during an active trip; a mobile push notification covers the app being in the background. A connection registry maps user to gateway node so any service can reach a user.
ETAShortest path on a road graph whose edge weights are travel times from live and historical traffic, made fast by precomputed shortcuts. Straight-line distance is used only to shortlist candidates.
Surge pricingA stream job computes demand (open requests) over supply (available drivers) per cell over a sliding window of a few minutes, then smooths and caps the multiplier. The quoted price is locked for a short time so it does not change under the rider.
PartitioningA trip starts and ends in one metro area, so city or region is the shard key for the geo index, dispatch and trips. It is also the failure boundary: one region's outage does not take down others.

Trade-offs and follow-ups

Ride hailing

DecisionAlternativeWhy
Positions in memory, not durablePersist every point before acknowledgingA lost point is replaced in 4 s. Pays with a cold index after a node restart (refilled within seconds).
Fixed cellsQuadtreeCheap updates and easy sharding. Pays with uneven cell load between dense and sparse areas.
WebSocketPollingPush in both directions with low overhead. Pays with stateful gateways and reconnect handling.
Shard by cityShard by user idQueries stay local. Pays with uneven shard sizes and special handling at region borders.
Compare-and-set on driver stateDistributed lock around dispatchOne atomic write, no lock service on the hot path.
Failure modeMitigation
Geo index node lostReplica per shard; otherwise the index refills from the next round of updates
Stale driver (app killed, tunnel)TTL on the position; dispatch filters on timestamp age
WebSocket gateway restartClients reconnect with jittered backoff and resume from the trip state in the database
Driver accepts after the offer expiredConditional update fails; the driver app is told the trip is gone
Demand spike (rain, an event ending)Surge raises supply and lowers demand; batched matching; widen the search ring gradually
  • Pickup near a city border? Cells belong to one region; the neighbour ring query is allowed to read the adjacent region's index.
  • How is the fare computed? From the stored trip trace (distance and time) and the price locked at request time, by a job that reads the location history.
  • How do you test dispatch changes? Replay recorded location and request logs through the new matcher and compare wait times.
  • What changes at 10x? More shards per large city, finer cells in dense areas, and location updates sampled before they reach the history log.

Senior signal: treating latest position as disposable state and trips as durable state, and choosing the shard key (city) from the query that must stay local rather than from the entity id.

Video streaming platform

Part 5 of 9 · big blobs, long pipelines, expensive bytes

Design a platform where creators upload videos and viewers watch them on any device and network. It is asked because it separates a slow, heavy write pipeline (upload and transcode) from a huge, latency-sensitive read path (CDN delivery), and because the dominant constraint is the cost of storage and egress.

Requirements and scale

Video streaming

KindRequirement
FunctionalUpload large files reliably. Transcode into several resolutions and bitrates. Play with adaptive quality. Store and serve metadata (title, channel, status). Count views.
Non-functionalPlayback starts in under 2 s at p95 with rebuffering under 1% of watch time. 99.99% availability for playback; processing may take minutes. Uploaded sources are never lost. View counts may lag by seconds to minutes.
Out of scopeRecommendations, search, comments, live streaming, ads, DRM details.
QuantityArithmeticResult (approx.)
Daily active usersassumed, each watching 30 min/day100M
Playback starts100M x 6 videos = 600M/day; / 86,400; peak x36,900/s average, 21,000/s peak
Uploads500,000/day / 86,4006/s
Source storage500,000 x 200 MB (about 5 min at 5 Mbps)100 TB/day
Total storagesource 100 TB + renditions about 100 TB = 200 TB/day; x 36573 PB/year before replication
Concurrent viewers100M x 30 min / 1,440 min2.1M average
Egress2.1M x 2.5 Mbps; per day 100M x 1,800 s x 2.5 Mbps / 85.2 Tbps average, about 10 Tbps peak; 56 PB/day
Playback events2.1M viewers / 10 s heartbeat210,000 events/s

Interview tip: the request rates are ordinary. The numbers that shape the design are petabytes stored and terabits per second served, so the answer is object storage plus a CDN, and the application servers never touch video bytes.

API and data model

Video streaming

The database holds only pointers (object keys) and state. Video bytes live in object storage and are never read through the database.
  • Metadata: a relational or distributed SQL store keyed by video id, with a cache in front, because rows are small and read on every playback start.
  • Blobs: object storage for sources and segments: cheap per byte, very high durability, served directly to the CDN.
  • Counters: a separate key-value or analytical store fed by the event stream, so view traffic never loads the metadata database.

High-level design

Video streaming

Write path on top: bytes go straight to storage and a queue drives transcoding. Read path at the bottom: the API returns a manifest URL and every segment comes from the CDN.
  • Upload (write): the API creates the video row and returns pre-signed part URLs. The client uploads parts in parallel directly to the source bucket, then calls complete.
  • Process: the completion event enqueues a job. Workers transcode, write segments and manifests to the segment bucket and mark the video ready in the metadata database.
  • Play (read): the playback API checks status and access, and returns a signed manifest URL. The player fetches the manifest and then segments from the nearest CDN edge.
  • Adapt: after each segment the player measures throughput and buffer level and picks the next segment's rendition.
  • Count: the player posts batched playback events to an event stream that feeds view counts (see the last deep dive).

Deep dives

Video streaming

1. Resumable, chunked upload

The API handles a few small calls. The gigabytes flow from client to storage, and a failure costs one part, not the whole file.
  • Part size of 8 to 16 MB balances retry cost against request count. Unfinished uploads are aborted by a lifecycle rule after a few days.
  • Alternative: streaming through the application servers ties up a connection per upload for minutes and doubles the bandwidth bill. An offset-based resumable protocol is equivalent when storage does not offer multipart.

2. Transcoding as a DAG of jobs

Splitting at keyframes turns one long encode into many short, independent tasks that fan out across workers and fan back in at packaging.
  • Orchestration: each node is a task row plus a queue message. A coordinator enqueues a task when its parents are done. Tasks are idempotent: output key is derived from (video, rendition, chunk), so a retry overwrites the same object.
  • Failure handling: visibility timeout and retry with backoff per task; after N attempts the task goes to a dead letter queue and the video is marked failed. Only the failed chunk is redone.
  • Scheduling: publish the low renditions first so the video is watchable early. Separate queues by priority and size so one 4-hour upload does not starve short ones. Workers are stateless, so cheap interruptible instances fit.
  • Alternative: one monolithic encode per video is simpler but cannot be parallelised and restarts from zero on failure.

3. Adaptive bitrate and the CDN

PieceWhat it is
Rendition ladderThe same video at several qualities, for example 240p at about 0.4 Mbps, 480p at 1 Mbps, 720p at 2.5 Mbps, 1080p at 5 Mbps (illustrative values)
SegmentsEach rendition cut into 2 to 6 s files that all start on a keyframe at the same timestamps, so the player can switch rendition at any segment boundary
ManifestA master playlist listing the renditions and one playlist per rendition listing segment URLs (HLS .m3u8, DASH .mpd). One set of fragmented MP4 segments can serve both formats
Player logicStart low for a fast first frame, then step up or down from measured throughput and buffer level
A cache hierarchy: the edge holds what is popular nearby, a regional tier shields the origin, and the long tail is fetched on demand.
  • Cache keys: segments are immutable, so they get a long TTL and a versioned path. Re-encoding publishes under a new path instead of invalidating.
  • Skew: a small share of videos gets most of the views. Pre-warm expected hits; let the long tail miss to the regional tier, or serve it from fewer locations to save cache space.
  • Access control: signed URLs or tokens checked at the edge, so private videos stay cacheable.
  • Alternative: progressive download of one MP4 is simple but cannot adapt to the network and wastes bytes the viewer never watches.

4. View counts as a stream, and where the money goes

A view is an event, not a database increment. The stream gives a fast approximate count and a batch job over the archive gives the audited one.
  • Why not UPDATE video SET views = views + 1: a popular video becomes one hot row taking thousands of writes per second. Aggregating per video per window turns that into one write per window.
  • What counts as a view: deduplicate by session id and require a minimum watch time; filtering of bots happens in the batch pass. The same pipeline shape is the metrics case.
Cost driverLever
Egress (largest)More efficient codecs for popular titles (spend CPU once, save bytes on every view), cap bitrate by device, own or negotiated CDN capacity
StorageMove sources and rarely watched renditions to cold tiers; keep fewer renditions for the long tail and transcode the rest on demand
ComputeInterruptible instances for transcoding; encode the expensive codecs only after a video proves popular

Trade-offs and follow-ups

Video streaming

DecisionAlternativeWhy
Direct-to-storage uploadUpload through the APIApp tier stays small and stateless. Pays with signed-URL handling in the client.
Chunked parallel transcodeOne job per videoFaster and retries are cheap. Pays with a coordinator and many small tasks.
Segmented HTTP streamingA stateful streaming protocolPlain cacheable files work with any CDN. Pays a few seconds of latency, which is fine for on-demand video.
Metadata and blobs in different storesEverything in one storeEach store does what it is good at. Pays with a consistency gap between them (below).
Approximate real-time countsExact synchronous countersNo hot rows. Pays with counts that lag and are corrected later.
Failure modeMitigation
Transcode worker dies mid-taskMessage becomes visible again after the timeout; idempotent output keys
Video row says ready but segments are missingMark ready only after the packager has verified every object exists; write blobs first, metadata last
A corrupt or hostile source fileProbe step validates and enforces limits; encoders run sandboxed with time and memory caps
CDN or region outageMore than one CDN, selected per session through the manifest URL; the player retries on another host
A video goes viral before caches are warmRegional tier collapses concurrent misses into one origin fetch
  • How do you delete a video? Flip the status first (playback stops at once), purge the CDN, then delete objects asynchronously.
  • How does live streaming differ? Segments are produced continuously, manifests change every few seconds and need short TTLs, and latency becomes the main target.
  • Duplicate uploads? The source hash detects exact re-uploads so the transcode can be reused.
  • What changes at 10x? Mostly the bill: more aggressive tiering, per-title encoding ladders and CDN capacity placed inside access networks.

Senior signal: doing the egress arithmetic unprompted and letting cost drive choices (which codecs, which renditions, which tier), and keeping every video byte off the application servers.

File sync and storage

Part 6 of 9 · two stores that must agree

Design a service that keeps a folder identical across a user's devices and lets them share files. It is asked because the client is half the system (it chunks, hashes and syncs), because moving only changed bytes is the whole efficiency story, and because metadata and file content live in different stores that must stay consistent.

Requirements and scale

File sync

KindRequirement
FunctionalUpload and download files from any device. Sync changes automatically to the user's other devices. Share files and folders with people or by link, with roles. Keep version history and restore. Accept offline edits and resolve conflicts.
Non-functionalStored files are never lost or corrupted. A change reaches other online devices in under 10 s at p95. Metadata is strongly consistent within a folder tree. Only changed bytes are transferred. Files up to tens of GB, with resumable transfer.
Out of scopeReal-time co-editing inside a document, full-text search, previews, malware scanning.
QuantityArithmeticResult (approx.)
Daily active usersassumed, of 500M registered50M
File changes (metadata writes)50M x 10 = 500M/day; / 86,400; peak x35,800/s average, 17,000/s peak
Bytes uploaded500M changes x 500 KB250 TB/day
Bytes stored250 TB x 0.6 (assume 40% saved by deduplication and compression) = 150 TB/day; x 36555 PB/year
Metadata500M users x 200 files = 100B rows x 500 B50 TB, must be sharded
Bandwidth in250 TB / 86,400 s2.9 GB/s (23 Gbps) average
Open notification connectionsabout 2 online devices per active user100M mostly idle connections

API and data model

File sync

A namespace is a root folder or a shared folder. A file version is just an ordered list of block hashes, and the journal gives every change in a namespace a sequence number.
  • Metadata: a relational store sharded by namespace id. A commit updates the file, adds a version and appends to the journal in one transaction, which needs all three on the same shard.
  • Blocks: object storage keyed by content hash. Blocks are immutable, so they replicate and cache trivially.

High-level design

File sync

Bytes go to the block service, structure goes to the metadata service. The notification service only says "something changed"; the client then pulls the delta.
  • Client: a watcher sees a local change, the chunker splits the file and hashes each block, and a local database remembers the last synced state and the journal cursor.
  • Upload (write): the client asks which hashes are missing, uploads only those blocks, then commits the new blocklist with the version it was based on.
  • Commit: the metadata service checks permission and base version, verifies that every block exists, writes version and journal entry in one transaction, and publishes a change event.
  • Sync (read): other devices hold a long poll. When it returns they call delta with their cursor, download the blocks they do not have and rebuild the file.
  • Download: blocks are fetched with short-lived signed URLs, through a CDN for shared and public files.

Deep dives

File sync

1. Chunking and content-addressed deduplication

A block's name is the hash of its content. Editing one part of a large file uploads one block; an identical block is stored once.
ChoiceOptionsTrade-off
Block boundariesFixed size (about 4 MB) vs content-defined (a rolling hash picks the cut points)Fixed is simple, but inserting a byte at the start shifts every later block. Content-defined keeps boundaries stable after inserts at the cost of CPU and variable sizes.
Deduplication scopePer user or namespace vs globalGlobal saves the most, but "this block already exists" tells one user that someone else has the file. Scope the check to the account, or require proof that the client holds the content.
IntegrityServer recomputes the hash on uploadCosts CPU; without it a client could store bad content under a good name.
Resumable uploadFalls out of blocks: after a failure, check again and send only the missing onesNo separate upload-session protocol needed.

2. Sync protocol: journal, cursor, notification

The journal is the single ordered list of changes per namespace. A device is fully described by its cursor, so reconnecting after a week is the same call as after a second.
ChannelFit
Long poll (chosen)Changes are rare per device and one-directional; works through every proxy; servers hold cheap idle connections
WebSocketBetter when updates are frequent or bidirectional; more state to manage for little gain here
Mobile pushFor phones where a held connection costs battery; treat it as a hint, then pull the delta
Periodic pollingFallback only: wasteful at 100M devices and slow to notice changes

Trade-off: the notification carries no data on purpose. It can be lost or duplicated without harm, because the client always asks the journal for the truth.

3. Conflicts and versioning

StrategyBehaviourVerdict
Last writer winsThe later commit silently replaces the earlier oneLoses someone's work; acceptable only because the old version is still in history
Reject and keep both (chosen)A commit whose base version is stale gets 409; the client saves its copy as "name (conflicted copy)" and downloads the server versionNever loses data; the user merges by hand
Automatic mergeOperational transforms or CRDTs on document structureOnly for formats the service understands; that is the collaborative editor problem
  • Versioning is nearly free: a version is a blocklist, and unchanged blocks are shared between versions. Restore creates a new version that points at the old blocks.
  • Retention: keep versions for N days or N versions; deleted files go to a trash state first.

4. Keeping metadata and blocks consistent

RulePrevents
Upload blocks first, commit metadata secondMetadata pointing at a block that does not exist (a corrupt file)
Commit verifies every hash in the blocklist existsA client committing blocks it never finished uploading
Blocks with no reference are legal and are collected laterNeeding a transaction across two stores; a crash between the steps only leaves garbage
Garbage collection is delayed and mark-and-sweep: delete only blocks older than a grace period that no version referencesDeleting a block that an in-flight commit is about to reference

5. Sharing and permissions

  • Model: sharing a folder makes it its own namespace, mounted into each member's tree. Membership rows carry the role (viewer, editor, owner); files inherit from their namespace.
  • Enforcement: the metadata service checks membership on every commit and delta. Block downloads use signed URLs issued only after that check, so the block store needs no permission logic.
  • Links: a random token mapped to a file and role, with optional expiry and password. Revoking deletes the token.

Trade-offs and follow-ups

File sync

DecisionAlternativeWhy
Blocks addressed by hashWhole files as single objectsDelta sync, deduplication and resume from one mechanism. Pays with a blocklist per version and garbage collection.
Separate metadata and block storesOne storeTransactions where they matter, cheap bytes where they do not. Pays with ordering rules between the two.
Journal with cursorCompare full directory listingsSync cost is proportional to what changed. Pays with journal storage and compaction.
Shard metadata by namespaceShard by file idOne-transaction commits and ordered journals. Pays with large shared folders becoming hot shards.
Conflicted copiesLast writer winsNo silent data loss. Pays with clutter the user must clean up.
Failure modeMitigation
Client crashes mid-uploadRestart, re-check hashes, send the rest; nothing was committed
Notification service downClients fall back to calling delta on a timer; no data is lost, only freshness
Device offline for weeksIf its cursor is older than the retained journal, do a full listing and reconcile
Silent corruption of a blockHash verified on read; repair from another replica
Ransomware or mass accidental deleteVersion history and trash allow restoring a whole namespace to a point in time
  • Moving a folder with 100,000 files? Store parent pointers rather than full paths, so a move is one row change and one journal entry.
  • End-to-end encryption? Blocks encrypted with per-user keys no longer deduplicate across users; that is the price.
  • Small files? Many tiny blocks waste round trips; batch several into one request.
  • What changes at 10x? Cold storage tiers and erasure coding for old blocks, and splitting very large namespaces.

Senior signal: explaining the write order across the two stores and why orphan blocks are fine while dangling references are not, and making the notification a hint instead of a data channel.

Web crawler

Part 7 of 9 · a pipeline that generates its own load

Design a crawler that downloads billions of pages for a search index. It is asked because there are no users to bound the load: the system must decide what to fetch next, stay polite to every host, avoid fetching the same thing twice and survive a web that is partly hostile.

Requirements and scale

Web crawler

KindRequirement
FunctionalStart from seed URLs, download HTML pages, extract and follow links. Store page content for the indexer. Obey robots.txt and per-host rate limits. Skip URLs and content already seen. Revisit pages to keep them fresh.
Non-functional10 billion pages per month. Polite: about one request per second per host unless told otherwise. Robust to traps, slow servers and malformed pages. Important pages recrawled within hours, the rest within weeks. Scales by adding machines.
Out of scopeIndexing and ranking, running JavaScript, images and video, pages behind a login.
QuantityArithmeticResult (approx.)
Daily active usersnone: the crawler creates its own loadnot applicable
Fetch rate10B / (30 x 86,400 = 2.59M s); design for x23,900 pages/s average, 8,000/s peak
Storage10B x 100 KB = 1 PB/month raw; / 5 with compression200 TB/month
Bandwidth in3,900/s x 100 KB390 MB/s (3.1 Gbps)
URL-seen filter50B URLs x 10 bits = 500 Gbit62 GB Bloom filter at about 1% false positives
Hosts in flight3,900 pages/s at 1 request/s per hostat least 3,900 distinct hosts being crawled at every moment

Interview tip: the last row is the insight. Politeness caps the rate per host, so throughput comes from breadth across hosts, and that shapes the frontier.

API and data model

Web crawler

There is no public API. These are the internal interfaces between stages.

DataKey and fieldsStoreWhy
URL recordreversed host + URL hash -> status, last crawl, ETag, fingerprint, next crawl timeWide-column storeTens of billions of small rows, point lookups, range scans per host
Page contentcontent hash -> compressed body, batched into large archive filesObject storageWrite once, read in bulk by the indexer; cheapest per byte
Frontier queuesper-host queues plus a schedule of when each host may be hit nextDisk-backed queues with an in-memory head, per shardToo large for memory, must survive restarts
URL-seen setBloom filter over normalised URLsMemory, per shard, checkpointedBillions of membership tests per day at memory speed
Robots and DNShost -> rules; host -> IP addresses, each with a TTLCacheRead before every fetch, change rarely

High-level design

Web crawler

A loop: the frontier feeds fetchers, parsed pages yield links, and unseen links return to the frontier. The two filters keep the loop from growing without bound.
  • Schedule: the frontier hands a fetcher a URL only when that URL's host is allowed another request.
  • Fetch: resolve the host from the DNS cache, check the cached robots rules, download with strict timeouts and a size cap.
  • Parse: validate, compute a content fingerprint, drop the page if the content was already seen, otherwise store it.
  • Extract: pull links, normalise them (lowercase host, remove fragments and tracking parameters, resolve relative paths), filter by rules, and add the unseen ones to the frontier with a priority.
  • Recrawl: a scheduler scans the URL records for pages that are due and feeds them back into the frontier.

Deep dives

Web crawler

1. The URL frontier: priority in front, politeness behind

Front queues decide what matters most. Back queues hold one host each, and a heap of "earliest next request" times guarantees a host is never hit faster than its limit.
  • Priority comes from page importance (link-based score, site quality) and how overdue a recrawl is. The selector favours high queues but never starves low ones.
  • Politeness: a fetcher pops the host with the earliest allowed time, fetches one URL from that host's queue, then pushes the host back with time = now + delay. The delay is the larger of the configured gap and a multiple of the last response time, so slow servers get more room.
  • Alternative: a single priority queue with a rate limiter in each fetcher. Popular hosts fill the head of the queue and fetchers sit idle waiting on them.

2. Distributing the frontier by host hash

Partition byPolitenessProblem
hash(host) (chosen)Each host is owned by exactly one node, so the limit is enforced locally with no coordinationA few giant hosts skew load; give them more back queues of their own and a higher allowed rate where the site permits
hash(URL)Many nodes fetch the same host, so a shared rate limiter is needed on every requestCoordination on the hot path
One central frontierTrivialA bottleneck and a single point of failure at thousands of URLs per second
  • Extracted links that belong to another node's hosts are forwarded in batches. Consistent hashing limits how many hosts move when a node is added or lost.
  • Each node keeps its own Bloom filter and DNS and robots caches for its hosts, so the same partitioning shards everything.

3. Duplicate detection: URLs and content

WhatTechniqueNotes
Same URL againNormalise, then test a Bloom filterNo false negatives. A false positive means a new URL is wrongly skipped; at about 1% that is acceptable, or confirm positives against the URL store.
Same content, different URLHash of the body (mirrors, session ids in URLs)Exact matches only: one changed character defeats it.
Near-duplicate contentSimHash: a 64-bit fingerprint where similar documents differ in few bits; treat a small Hamming distance (around 3) as duplicateCatches pages that differ only in ads, dates or counters. Needs an index that finds fingerprints within a few bits.
  • Alternative to Bloom: an exact set in the URL store costs a disk or network lookup per extracted link. A page has dozens of links, so the filter in memory removes most of those lookups.
  • A standard Bloom filter cannot delete. That is fine here: a URL once seen stays seen, and recrawls are scheduled from the URL store.

4. Robots, traps, freshness and DNS

TopicApproach
robots.txtFetch once per host and cache (commonly up to a day). Check every URL against it before fetching. If the file is unreachable with a server error, back off from the host rather than assume everything is allowed.
Spider trapsInfinite calendars, session ids, endlessly nested paths. Defences: cap URL length and path depth, cap pages per host scaled by host quality, detect repeating path patterns, and watch the duplicate-content ratio per host.
FreshnessRecrawl interval per page from its observed change rate and its importance: news front pages in minutes, archives in months. Conditional requests (If-None-Match, If-Modified-Since) make an unchanged page cost a 304 with no body. Sitemaps give hints.
DNSA lookup can take tens of milliseconds and many resolver libraries block. Run local caching resolvers, cache per host with the record's TTL, and resolve ahead of time for hosts about to be fetched.
Page storageCompress and append many pages into large archive files in object storage, indexed by content hash, so the indexer reads sequentially.

Trade-offs and follow-ups

Web crawler

DecisionAlternativeWhy
Breadth-first with prioritiesDepth-firstFinds important pages early and spreads load over hosts. Pays with a very large frontier.
Partition by hostPartition by URLPoliteness without coordination. Pays with skew from large hosts.
Bloom filter for seen URLsExact lookupMemory-speed checks. Pays with a small share of URLs never crawled.
Adaptive recrawlFixed interval for everythingSpends the budget where pages change. Pays with per-page bookkeeping.
Fetch and parse as separate stagesOne process does bothNetwork-bound and CPU-bound work scale separately. Pays with a queue between them.
Failure modeMitigation
Frontier node crashesQueues are on disk and replicated; leased URLs return after a timeout; the filter is rebuilt from a checkpoint
A host is slow or returns errorsExponential backoff per host; a slow host only blocks its own back queue
Huge or never-ending responsesSize cap, total time limit, abort on low transfer rate
The crawler overloads a small siteAdaptive delay from response time, obey crawl delay hints, identify the crawler in the user agent with a contact
Malicious contentParse in a sandbox; never execute fetched content
  • Pages that need JavaScript? A separate, much slower rendering tier with headless browsers, used only for pages that are detected to need it.
  • Why not depth-first? It dives into one site, which is both impolite and a trap risk.
  • How do you measure quality? Coverage of known important pages, average age of stored copies, duplicate rate, and fetches per useful new page.
  • What changes at 10x? More frontier shards and fetch locations closer to the hosts; the design stays the same.

Senior signal: deriving the architecture from politeness (one owner per host, breadth as the source of throughput) rather than starting from "a queue and some workers".

Distributed job scheduler

Part 8 of 9 · time, leases and at-least-once

Design a service that runs one-off jobs at a given time and recurring jobs on a cron schedule, for many teams. It is asked because "run this once at 09:00" hides hard problems: finding due jobs among millions cheaply, making sure a crashed worker's job still runs, and not running it twice when a worker was only slow.

Requirements and scale

Job scheduler

KindRequirement
FunctionalCreate a one-off job (run at time T) or a recurring job (cron expression with a time zone). Run it by calling a target (HTTP endpoint or queue). Retry failures with backoff. Pause, update, cancel. Show run history and status.
Non-functionalA due job is never silently skipped (at-least-once). It starts within a few seconds of its due time at p99. Schedules survive any single machine failure. No single point of failure. One tenant cannot starve another.
Out of scopeWorkflows with dependencies between jobs, placing jobs on machines by CPU and memory, sandboxing user code.
QuantityArithmeticResult (approx.)
Usersassumed: 100,000 teams (tenants), not end users50M job definitions
Runs100M/day / 86,4001,160/s average
Peak3M jobs due at exactly 00:00:00, drained within 60 s50,000 dispatches/s
Definitions storage50M x 1 KB50 GB
Run history100M x 500 B = 50 GB/day; x 30 days kept1.5 TB
Bandwidth1,160/s x 2 KB; peak 50,000/s x 2 KB2.3 MB/s average, 100 MB/s peak

Interview tip: cron load is not smooth. People schedule on the hour and at midnight, so the peak is about 40 times the average and the design must be sized for that second.

API and data model

Job scheduler

A run is identified by (job, scheduled time). That key is unique, so creating the same run twice is impossible, and it is the idempotency key passed to the target.
  • Store: a sharded relational or wide-column store with an index on (shard, next_run_at). It must support a range scan by due time and conditional updates; a plain key-value store cannot find due jobs.

High-level design

Job scheduler

Three roles: the scheduler decides when (and writes a run), the queue buffers, workers do. Each can fail and scale on its own.
  • Create (write): the API validates the schedule, computes next_run_at, assigns a shard from the job id and stores the job.
  • Schedule: each scheduler node owns some shards. It scans its shards for jobs that are due, and in one transaction inserts the run row and advances the job's next_run_at. Then it enqueues the run.
  • Execute: a worker leases a run, calls the target with the run id, heartbeats while it works, and reports the result.
  • Recover: a sweeper re-enqueues runs that were inserted but never enqueued, and runs whose lease expired.
  • Read: history and status come from the run table, moved to cheaper storage after the retention window.

Deep dives

Job scheduler

1. Finding due jobs

ApproachHowFit
Indexed scanWHERE next_run_at <= now() on an index, every secondFine up to roughly a million jobs on one database; one scanner
Time buckets x shardsPartition key (shard, minute bucket); each scheduler reads only its shards' current bucketScales out; cost is proportional to due jobs, not total jobs
Timing wheel in memoryA ring of slots, one per second; jobs due soon are hashed into slots; a tick fires one slot. Insert and fire are O(1)Second-level precision at high volume, but memory only: must be reloaded from the store
Delay queueEnqueue with a delivery delay, or a sorted set scored by due timeGood for short delays; many managed queues cap the delay, and cron still needs a store
The usual combination: the durable store is the truth, and a small in-memory wheel holds only the next couple of minutes for precise firing.
  • A scheduler that restarts loses nothing: it reloads the window, and any bucket in the past that still has due jobs is processed first.
  • Add a random offset of a few seconds to jobs that allow it. It flattens the top-of-the-hour spike more cheaply than hardware.

2. Leases, visibility timeouts and "exactly one runner"

The lease makes sure a dead worker's job runs again. It cannot stop a slow worker from overlapping, so the attempt number fences stale reports and the target deduplicates by run id.
  • Lease: a conditional update sets owner, lease_until and attempt + 1 only if the run is ready or its lease has expired. A queue's visibility timeout is the same idea.
  • Exactly-once execution is not achievable in general: the scheduler cannot tell a dead worker from a slow one. The honest contract is at-least-once delivery plus idempotent jobs.
  • Lease length: short with heartbeats beats long without. Too short causes duplicates, too long delays recovery.
  • When a duplicate is unacceptable and the target cannot deduplicate, offer at-most-once: mark the run started before calling and never retry automatically. The price is runs lost on a crash.

3. Leader election and sharding

Scheduler topologyHowTrade-off
Single leaderOne active scheduler holds a lease in a coordination store (etcd or ZooKeeper style); standbys take over when it expiresSimple; throughput of one node; failover gap of one lease period
Sharded leaders (chosen)hash(job id) picks one of N virtual shards; each scheduler node holds leases on a set of shards; shards are reassigned when a node diesScales out and limits the blast radius; needs rebalancing
Leaderless claimEvery node runs SELECT ... FOR UPDATE SKIP LOCKED on due rowsNo coordination service; the database becomes the limit at a few thousand claims per second
  • Two leaders for one shard can happen briefly after a pause or partition. It is harmless because the run row has a unique key (job, scheduled time): the second insert fails.
  • Shard by job id, not by tenant, so one large tenant does not make a hot shard. Tenant fairness is enforced at dispatch with per-tenant concurrency limits.

4. Retries, dead letters, missed runs and observability

TopicApproach
RetriesExponential backoff with jitter, a maximum number of attempts, and a per-attempt timeout. Retry only failures that can succeed later (timeouts, 5xx), not validation errors.
Dead lettersAfter the last attempt the run goes to a dead letter queue with its error, is shown to the owner, and can be replayed by hand.
Missed runsAfter an outage, a job may have several past due times. The misfire policy per job says: run once now (coalesce), run every missed occurrence (backfill, rate-limited), or skip to the next. Default to run once.
Cron arithmeticCompute the next time from the scheduled time, not from when the run finished, or the schedule drifts. Store the time zone name and handle local times that occur twice or not at all when clocks change.
OverlapIf a run is still going when the next is due: allow, skip, or queue, chosen per job.
ObservabilityThe main indicator is schedule lag: dispatch time minus scheduled time. Also queue depth, lease expiries, retry and dead letter rates, all per tenant. Alert on a scheduler shard with no owner.

Trade-offs and follow-ups

Job scheduler

DecisionAlternativeWhy
At-least-once with idempotent jobsAt-most-onceA skipped payroll job is worse than a deduplicated repeat. Pays by pushing idempotency onto job authors.
Durable store plus in-memory wheelOnly a delay queueHandles cron, long horizons and edits. Pays with two components to keep in step.
Scheduler separate from workersSchedulers execute jobs themselvesA slow job cannot delay scheduling. Pays with a queue hop.
Sharded leadersOne leaderThroughput and smaller failures. Pays with a coordination store and rebalancing.
Run row written before enqueueEnqueue onlyThe run survives a lost message and gives history. Pays one extra write per run.
Failure modeMitigation
Scheduler node diesIts shard leases expire and move; the new owner processes overdue buckets first
Crash between writing the run and enqueueing itSweeper finds ready runs older than a threshold and enqueues them
Worker dies mid-runLease expires, the run is retried as the next attempt
Target is downBackoff, per-target circuit breaker, dead letters; other tenants unaffected because of per-tenant limits
Clock skew between nodesUse the database's time for due checks and lease expiry, not each node's clock
  • A job is edited while it is running? The run keeps the definition it started with; the change applies from the next run.
  • One tenant schedules a million jobs for the same second? Per-tenant dispatch limits and quotas at creation; their backlog waits, others do not.
  • Long-running jobs? Heartbeats extend the lease; a hard timeout bounds it.
  • Jobs with dependencies? That is a workflow engine: a DAG of tasks with state, built on this scheduler's primitives.

Senior signal: refusing to promise exactly-once execution, and showing the three layers that make duplicates harmless: a unique run key, a fenced attempt number and an idempotent target.

Metrics, monitoring and ad-click aggregation

Part 9 of 9 · counting a firehose correctly

Design a pipeline that ingests a very large stream of events (metric points, or ad clicks), aggregates them over time windows and serves dashboards and alerts. Monitoring and ad-click counting are the same shape; clicks add the demand that the numbers are right, because they are billed. It is asked for stream processing, time-series storage and the gap between fast answers and correct ones.

Requirements and scale

Metrics and click aggregation

KindRequirement
FunctionalIngest events from agents and SDKs. Aggregate by time window and dimensions (clicks per ad per minute, request rate per service). Query the last minutes to the last year for dashboards. Evaluate alert rules and notify. Produce exact totals for billing.
Non-functionalAn event is visible on a dashboard within about 30 s. Dashboard queries under 1 s at p95. Ingestion 99.99% available and never drops accepted events. Real-time numbers may be approximate; billing numbers are exact after reconciliation. Raw data kept for days, aggregates for a year or more.
Out of scopeLogs and traces, anomaly detection models, click-fraud rules, the agent itself.
QuantityArithmeticResult (approx.)
Daily active usersnot the driver; events are10B events/day
Ingest rate10B / 86,400; peak x5116,000/s average, 580,000/s peak
Raw storage10B x 200 B = 2 TB/day; x 30 days60 TB, about 12 TB compressed 5x
One-minute aggregates10M active series x 1,440 points = 14.4B points/day x 16 B230 GB/day raw, about 29 GB/day at 2 B per point compressed
Bandwidth in116,000/s x 200 B; peak x523 MB/s (185 Mbps) average, 116 MB/s peak
Query rate15,000 open dashboards x 10 panels / 30 s refresh5,000 queries/s

Interview tip: the aggregate storage row depends on the number of series, not the number of events. Doubling events costs little; doubling label combinations doubles the store. That is why cardinality gets its own deep dive.

API and data model

Metrics and click aggregation

DataShapeStoreWhy
Raw eventsappend-only, partitioned by a key such as ad idDurable log for days, then columnar files in object storageReplay and batch recompute need the originals
Aggregates(metric, dimension set, window start) -> sum, count, min, max, sketchTime-series or columnar analytical store, partitioned by timeSequential writes, time-range scans, strong compression of timestamps and values
Series indexlabel = value -> list of series idsInverted index beside the time-series storeFinds which series a query touches without scanning data
Alert rules and staterule, current state, since whenRelationalSmall, edited by people, needs transactions

High-level design

Metrics and click aggregation

The log decouples ingestion from everything else. The solid path is fast and approximate; the dashed path recomputes from raw data and corrects the stored aggregates.
  • Ingest (write): the gateway authenticates, validates, applies per-tenant limits and appends to the log. It acknowledges only after the log has the event, and does no aggregation itself.
  • Aggregate: the stream job reads the log, assigns each event to a window by its own timestamp, keeps running totals per key and writes finished windows to the time-series store.
  • Archive and correct: raw events are also written to cheap storage. A batch job recomputes each closed hour or day and overwrites the aggregates where they differ.
  • Query (read): the query service picks the coarsest resolution that satisfies the time range, fans out to the shards holding those series, merges and caches.
  • Alert: an evaluator runs each rule's query on a schedule and passes state changes to the notifier.

Deep dives

Metrics and click aggregation

1. Windows and late data

TermMeaning
Event time vs processing timeWhen it happened vs when the pipeline saw it. Aggregate by event time, or a slow network moves clicks into the wrong minute.
Tumbling windowFixed, non-overlapping (each minute). The default for counts.
Sliding windowOverlapping (last 5 minutes, updated every minute). For rates and alert conditions.
WatermarkThe job's estimate that all events up to time T have arrived, usually "largest timestamp seen minus a fixed delay". A window is emitted when the watermark passes its end.
Allowed latenessHow long after emission a window still accepts events and re-emits a corrected value.
Three fates for an event: on time, late but still accepted, or too late for the stream and left to the batch job.
  • Trade-off: a longer watermark delay catches more late events but makes every result later. Typical choice: emit early with a short delay, accept corrections for a few minutes, and let batch fix the rest.
  • Writes to the store must be upserts keyed by (series, window start), so a re-emitted window replaces the old value instead of adding to it.

2. Exactly-once counting and reconciliation with batch

Where counts go wrongEffectFix
Client retries a batch after a timeoutDuplicatesEvent id on every event; deduplicate in the stream job with keyed state kept for a bounded time
Stream job crashes and replays from the logDouble counting of in-flight eventsCheckpoint the job's state together with its log offsets, so a restart resumes both from the same point
Sink write is retriedDouble additionIdempotent upsert of the window total, or a transactional sink that commits with the checkpoint
Events later than allowed latenessUndercountBatch recompute from the raw archive
Ingest gateway acknowledges before the log write is durableLossAcknowledge after a replicated write; clients buffer and retry
  • What "exactly once" means here: each event affects the stored result once, even though it may be delivered and processed more than once. It is replay plus consistent checkpoints plus idempotent or transactional output.
  • Reconciliation: a batch job recomputes each closed period from the raw archive with full deduplication and compares with the stream's totals. Differences above a threshold raise an alert; the batch value is what billing uses.
  • Alternative: a single stream pipeline that reprocesses from the log when logic changes, with no separate batch code. It is simpler to maintain; it needs a long-retention log and enough capacity to replay.

3. Pre-aggregation, roll-ups and retention tiers

TierResolutionKept forUsed by
Raw eventsevery event7 to 30 daysReplay, batch, investigations
Fine10 s to 1 minabout 30 daysLive dashboards, alerts
Medium1 hourabout 1 yearWeekly and monthly views
Coarse1 dayyearsCapacity planning, billing history
  • Downsampling keeps sum, count, min and max per bucket so averages can be recomputed correctly. An average of averages is wrong when buckets have different counts.
  • Percentiles cannot be rolled up from percentiles. Store a mergeable sketch or histogram per bucket and merge those.
  • Pre-aggregation: compute totals for the dimension sets that dashboards actually group by (per campaign, per country). It trades storage and write work for fast reads; unplanned groupings fall back to a slower scan of finer data.
  • Storage engine: time-partitioned blocks, timestamps stored as deltas and values as differences from the previous value, which is why a point can cost about 1 to 2 bytes. Dropping an expired partition is a file delete.

4. Cardinality, the query path and alerting

  • Cardinality is the cost driver: the number of series is the product of the distinct values of every label. 100 services x 50 endpoints x 5 status codes = 25,000 series; add a user id label with 1M values and it becomes 25 billion. Memory for the index, storage and query time all follow series count.
  • Controls: per-tenant series limits, reject or drop unbounded labels (user id, request id, raw URL) at ingest, and keep such detail in logs or the raw archive instead.
  • Query path: choose the tier from the time range (a 30-day chart reads hourly points, not minutes), limit the series a query may touch, cache results aligned to step boundaries so refreshes reuse them.
The pending state is the "for 5 minutes" clause: it stops a single noisy point from paging someone.
  • Pipeline: evaluate rules on a schedule, then group related alerts, deduplicate, silence during maintenance, route by severity to chat, email or paging.
  • Missing data is a signal: alert when an expected series stops reporting. Monitor the monitoring system from outside it with a heartbeat alert that must keep arriving.

Trade-offs and follow-ups

Metrics and click aggregation

DecisionAlternativeWhy
Durable log before any processingAggregate in the gatewayAbsorbs spikes and allows replay. Pays with seconds of latency and log cost.
Stream for speed, batch for truthStream onlyBilling-grade totals. Pays with two code paths that must agree.
Pre-aggregated roll-upsAggregate raw data at query timeSub-second dashboards. Pays with fixed dimensions and extra writes.
Event-time windows with watermarksProcessing-time windowsCounts land in the right minute. Pays with late-data handling.
Hard limits on cardinalityAccept any labelsPredictable cost. Pays with less detail in metrics.
Failure modeMitigation
Stream job falls behindConsumer lag is the key metric; scale partitions and workers; shed low-priority streams first
Hot key (one ad gets most clicks)Pre-aggregate locally per worker, then combine; or add a random suffix to the key and merge in a second stage
A tenant sends a label explosionPer-tenant limits at the gateway; isolate tenants into separate partitions
Time-series store node lostReplicated shards; recent data can be rebuilt by replaying the log
Alerting outage goes unnoticedExternal heartbeat check; evaluator and notifier run in more than one zone
  • Pull or push collection? Pull (the server scrapes targets) gives the server control and shows a dead target at once. Push suits short-lived jobs and clients behind firewalls, and is the only option for clicks.
  • Top N ads in the last minute? Keep per-partition top lists in the stream job and merge them; exact top N needs the full counts.
  • Unique users instead of counts? Distinct counts do not add up across windows; store a mergeable cardinality sketch.
  • What changes at 10x? More log partitions, a tiered time-series store with object storage for old blocks, and stricter cardinality budgets.

Senior signal: defining exactly-once as an effect, not a delivery guarantee, keeping raw data so every number can be recomputed, and naming series cardinality as the thing that sets the bill.

Cheat sheet

CaseCore idea in one lineKey data storeHardest deep dive
Payment systemAppend-only double-entry ledger, idempotency keys on every hop, a state machine where unknown is a stateACID relational database, synchronously replicatedProvider timeout with unknown outcome, closed by webhook, status query and reconciliation
Seat bookingOne atomic conditional write per hold, a TTL on the hold, a waiting room in frontRelational database sharded by event; cache for display onlyFlash-sale admission and fairness without overselling
Ride hailingLatest positions in an in-memory cell index, trips in a database, compare-and-set to reserve a driverIn-memory geo index per city; SQL for tripsNearest-driver search over moving objects at 500,000 updates/s
Video streamingUpload straight to object storage, transcode as a parallel DAG, serve segments from a CDNObject storage plus CDN; small metadata databaseTranscoding pipeline and the cost of egress
File syncFiles are lists of content-addressed blocks; a per-namespace journal with cursors drives syncObject storage for blocks; relational metadata sharded by namespaceSync protocol and conflicts, with metadata and blocks kept consistent
Web crawlerFrontier with priority queues in front and per-host queues behind, partitioned by host hashDisk-backed frontier, Bloom filter, wide-column URL store, object storage for pagesFrontier design that is polite and still fast
Job schedulerDurable job store scanned by time bucket, runs leased to workers, duplicates made harmlessSharded store indexed by due time; coordination store for leasesLeases and fencing: at-least-once without harmful double runs
Metrics and click aggregationDurable log, event-time windows, roll-ups in a time-series store, batch as the source of truthEvent log plus time-series store; raw archive in object storageLate data and exactly-once counting, with cardinality as the cost

Recurring moves

  • Unknown outcome: persist intent first, call with an idempotency key, resolve later by query or callback (payments, bookings, scheduler).
  • Scarce resource: one atomic conditional write decides the winner; everything else is load shedding in front of it (seats, drivers, wallet balance).
  • Bytes and structure apart: blobs in object storage, pointers and state in a database, blobs written first (video, file sync, crawler).
  • Fast and exact apart: a stream gives the quick answer, a recompute from raw data gives the right one (view counts, clicks, reconciliation).
  • Shard by the query that must stay local: event, city, namespace, host, job id.

Practise next with the same template

QuestionThe deep dive that defines it
E-commerce checkoutInventory reservation and the order saga across stock, payment and shipping
Food deliveryThree-sided dispatch where the ETA includes restaurant preparation time
Collaborative editorConvergence of concurrent edits: operational transforms vs CRDTs
Distributed cacheConsistent hashing, replication and what happens to hot keys and node loss
Logging pipelineBackpressure when producers outrun the index, and the cost of indexing vs scanning
Stock exchange matching engineA single-threaded deterministic order book per symbol, fed by one sequenced log that is replicated for failover
Hotel reservationsInventory as counts per room type per night, and overbooking as a business rule

Next: Low-Level Design, where the focus moves from boxes and data flow to classes and their responsibilities.