Design cards

One page per design, for the last pass before a round. Each card fills in a design that lesson 8 gives in its sections "Eight spoken skeletons", "API and tables for the five card designs" and "The pushback bank". The payments ledger (Design 3) and notifications (Design 6) are in lesson 8 in full, so they have no card here. Every volume, price and count is invented; prices use the list in lesson 8's "The Operate-it block that closes every design", and node counts use its table "What one box handles".

Design 1: URL shortener

Prompt and never-list. Create a short code for a long URL, redirect it, take an optional alias and expiry, delete a link. Never reuse a code for another URL; never answer a wrong "not found" for a live link. Out, said aloud: click analytics, abuse scanning, login.

Numbers. 100 million links a month at 100 reads per write: 38.6 creates a second, 116 at peak; 3,858 redirects a second, 11,574 at peak. Five years is 6.0 billion rows, 3.0 TB at 500 bytes. So reads dominate a hundred to one, a cache pays for itself, and the data fits a few shards.

Boxes. Load balancer, stateless app tier, look-aside cache, a store sharded by code (11,574 / 2,000 a shard = 6 shards, three copies, 18 nodes), and an ID service handing each app server blocks of 1,000.

API and tables. The key is the code; uniqueness comes from the counter, and an alias is an insert that fails on the key.

POST   /v1/urls  {long_url, alias?, expires_at?}  Idempotency-Key
       -> 201 {code, short_url} | 409 alias taken | 400 bad URL
GET    /{code}           -> 302 Location: long_url | 404 | 410 expired
DELETE /v1/urls/{code}   -> 204 | 403 not the owner
urls(code PK, long_url, owner_id, created_at, expires_at)
    sharded by code; cache code -> long_url with an expiry
code: a number from a counter block per app server, in base 62
    (scramble it if codes must not be guessable)

Deep dive. The code. Base 62 at 7 characters gives 3.52 trillion codes. Sequential codes are enumerable, so issue a random code or a keyed permutation of the counter; at 6.0 billion live links one random guess hits with probability 0.17%, so rate-limit misses as well as creates. Redirect with 302 and a short max-age while clicks may matter; 301 saves load only if you stop counting.

Failures. A replica that has not seen a new code: check the primary before a 404 and cache a 404 for seconds at most. ID service down: creates fail, redirects carry on. A cache loss sends 11,574 reads a second to the store, so the shards are sized for peak, not average.

Staff adds. Scopes the round to the redirect contract and the delete race (a cached link after delete); plans expiry sweeps and legal takedown; names who owns the ID service.

Operate and cost. Canary at 1% for 15 minutes; page on redirect errors above 1% for 5 minutes; RPO 5 s, RTO 5 min (assumed). About Rs 8.96 lakh a month: 18 store nodes at Rs 40,000 (Rs 7.2 lakh), 8 app servers (Rs 96,000, assumed), 3 cache nodes (Rs 48,000), and redirect egress of 5.0 TB (3,858 a second x 2,592,000 seconds x 500 bytes) at Rs 6.4 per GB (Rs 32,000). The data, 0.5 TB a node, fits the disk the node price includes. The store nodes dominate.

Next stop: Design 2: news feed, 2 min

Design 2: news feed

Prompt and never-list. Post, follow, read a feed newest first; ranking out. Never lose a post; a user's own post shows in their own feed at once (read-your-writes). Delivery to followers within seconds is fine.

Numbers. 300 million daily users reading five times: 52,083 feed reads a second at peak. 50 million posts a day at 200 followers on average is 115,741 timeline writes a second on the mean if every post is pushed, 347,222 at peak. The mean hides skew: one account with 20 million followers turns one post into 20 million writes. So push for ordinary authors and pull for large ones.

Boxes. Post service and store, a follow graph indexed both ways, a fan-out queue and workers, a timeline cache, a read service that merges large authors in, a CDN for media.

API and tables. The key is the cursor, a position and not an offset, and the follower index that fan-out reads.

POST   /v1/posts  {text, media_key?}        -> 201 {post_id}
GET    /v1/feed?cursor=...&limit=20     -> 200 {items[], next_cursor}
       cursor: opaque (time + post_id), never an offset
PUT    /v1/follows/{user_id}  -> 204;  DELETE /v1/follows/{user_id}
posts(post_id PK, author_id, created_at, text, media_key)
    sharded by post_id
follows(follower_id, followee_id), second index on followee_id
timeline (Redis): tl:{user_id} -> up to 800 post_ids, newest first
authors above 10,000 followers (assumed): no fan-out, merged at read

Deep dive. The threshold, assumed at 10,000 followers: authors above it are pulled at read time. If the top 1% of authors, about 12,000 followers each, hold 60% of follow edges (assumed), pushes drop to the other 40%: 46,296 writes a second on the mean, 138,889 at peak. The mean still hides the skew, so measure the tail. Timelines keep 800 post ids each: 1.92 TB raw, 5.8 to 14.4 TB with overhead and copies, 90 to 225 memory nodes of 64 GB. Responses at 20 KB are 8.3 Gbit/s at peak, more than one network card.

Failures. Fan-out lag: measure it as the SLO. A duplicate push dedupes by post id. A lost cache node: rebuild those timelines by pulling. Ranking down: a 50 ms timeout and newest-first.

Staff adds. Fan-out cost under skew and read-your-writes across regions as the two hard parts; moving a user between push and pull without loss; the fan-out queue on a cost line with an owner.

Operate and cost. Merge changes behind a cohort flag; page on queue lag above 30 seconds; RPO seconds for posts, RTO 15 minutes (assumed). About Rs 51.2 lakh to Rs 94.4 lakh a month: 90 to 225 memory nodes at Rs 32,000 (Rs 28.8 lakh to Rs 72 lakh), 100 app and fan-out servers (Rs 12 lakh, assumed), 20 store nodes (Rs 8 lakh, assumed) and 6 queue brokers at Rs 40,000 (Rs 2.4 lakh). The timeline cache dominates; media egress is the CDN bill, quoted apart.

Next stop: Design 4: chat, 2 min

Design 4: chat

Prompt and never-list. One-to-one and groups up to 256, with sent, delivered and read; offline users catch up. Never lose an acknowledged message; everyone sees one conversation in one order. Out: media, end-to-end encryption, search, voice.

Numbers. 500 million daily users sending 40 messages: 694,444 messages a second at peak and, at 2.6 deliveries each, 1.8 million deliveries a second. 100 million sockets at peak, at 100,000 a gateway and 10 KB each, kept two thirds full: 1,500 gateways. So the connection tier is the size of the system.

Boxes. Gateways holding sockets, a registry of user to gateway with an expiry, a chat service, a message log partitioned by conversation (70 shards, three copies, 210 nodes; 360 TB for 30 days: 20 billion messages a day at 200 bytes, three copies), push for offline devices.

API and tables. The key is (conversation, seq): one ordered log per conversation, and the client's message id makes a resend safe.

WebSocket, client to server
  send(conversation_id, client_msg_id, body)  -> {seq} once stored
  ack(conversation_id, kind, up_to_seq)        kind: delivered | read
  sync(conversation_id, last_seq)        -> messages after last_seq
WebSocket, server to client
  message(conversation_id, seq, sender, body, sent_at)
HTTP: login; GET /v1/conversations/{id}/messages?before_seq=...
messages(conversation_id, seq, sender, client_msg_id, body, sent_at)
    partitioned by conversation_id, sorted by seq
    UNIQUE (conversation_id, sender, client_msg_id)
members(conversation_id, user_id)
cursors(conversation_id, user_id, delivered_seq, read_seq)
registry: user_id -> gateway_id, with an expiry

Deep dive. Order. One writer per conversation assigns seq; the client's message id makes a resend return the same seq. A device that sees a gap in seq calls sync. Delivered and read are cursors per member, not flags per message. The writer's ownership is fenced, so a paused old owner cannot assign a number twice.

Failures. A gateway dies: about 67,000 clients reconnect with jitter, about 2,200 a second over 30 seconds, and sync loses nothing because the append happens before delivery. The registry points at a dead gateway: the push times out and the message waits in the log.

Staff adds. End-to-end encryption (the server still sequences and stores encrypted bodies but cannot search them); a home region per conversation so one writer stays one writer.

Operate and cost. Drain gateways a few at a time; page on send-to-delivered p99 above 2 seconds; RPO 0 for acknowledged sends, RTO 5 minutes (assumed). About Rs 2.93 crore a month: 1,500 gateways (Rs 1.8 crore); 210 log nodes at Rs 40,000 (Rs 84 lakh), since 694,444 appends a second over 15,000 batched a node, two thirds busy, is 70 shards, with three copies; 360 TB is 1.71 TB a node, over the 1 TB a node includes, so it sits on block storage at Rs 8 per GB (Rs 28.8 lakh). The gateways dominate.

Next stop: Design 5: ride matching, 3 min

Design 5: ride matching

Prompt and never-list. Drivers report position every 4 seconds; a rider requests; one nearby driver gets a 10-second offer. Never put a driver on two rides or match a ride twice. Out: pricing, routing and ETA, payments.

Numbers. 1 million drivers online: 250,000 updates a second, but the latest positions are only 100 MB. Rides are 694 a second at peak. So the write rate is the problem, the match rate is not: keep positions in memory and store a sampled trail, 432 GB a day keeping every fifth point instead of 2.16 TB.

Boxes. 38 location gateways, an in-memory latest-position store, a cell index (geohash), a matcher, a ride store, push to drivers.

API and tables. The key is the driver: the claim is a compare-and-set on the driver's state with a lease, and the accept carries the ride id as its fencing token.

driver: PUT  /v1/drivers/{driver_id}/location {lat, lon, at}  every 4 s
rider:  POST /v1/rides {pickup, drop}  Idempotency-Key
        -> 202 {ride_id, status: MATCHING}
offer:  pushed to one driver {ride_id, expires_in: 10 s}
driver: POST /v1/rides/{ride_id}/accept  -> 200 | 409 offer gone
drivers(driver_id PK, status AVAILABLE | OFFERED | ON_RIDE,
        offer_ride_id, offer_expires_at)
riders(rider_id PK, name, phone)
rides(ride_id PK, rider_id, driver_id, status, pickup, drop,
      requested_at, version)
claim:  UPDATE drivers SET status = 'OFFERED', offer_ride_id = ?
        WHERE driver_id = ? AND status = 'AVAILABLE'
accept: succeeds only if offer_ride_id = ride_id and not expired
memory: driver_id -> latest position; cell -> set of driver_ids

Deep dive. The claim. Read the rider's cell and its eight neighbours, widen to 25 cells when fewer than 5 drivers are found. About 5% of updates cross a cell (a driver at 30 km/h moves 33 m in 4 seconds; on a geohash-6 cell of about 1.2 by 0.6 km that crosses an edge 5.2% of the time), so the index moves a driver only then. The claim is a compare-and-set from available to offered with a 10-second lease; the accept carries the ride id as a fencing token, so a late accept for an expired offer fails.

Failures. A driver goes silent: 12 seconds without an update drops them from the index. A matcher crash mid-offer: the lease expires and the driver is free again. A hot city on one shard: longer geohash prefixes spread over nodes.

Staff adds. Greedy against batch matching and its waiting cost; a degradation plan (wider radius, longer offers, a rider queue); location history as personal data with an owner.

Operate and cost. Ship to one city first against a control city; page on match-found rate below its band and location lag above 10 seconds; RTO 5 minutes, locations refill in 4 seconds (assumed). About Rs 10.45 lakh a month: 38 gateways at 10,000 updates each, two thirds busy (Rs 4.56 lakh); 250,000 position writes over 50,000 a cache node, two thirds busy, is 8 shards with a replica each, 16 nodes (Rs 2.56 lakh); 6 index nodes at Rs 32,000 (Rs 1.92 lakh, assumed); 10 matchers (Rs 1.2 lakh, assumed); the sampled trail kept 30 days (assumed), 13 TB of object storage at Rs 1.6 per GB (Rs 20,800). The update stream dominates. In a schema-only round, say that positions and claims live in memory and only rides are a durable table.

Next stop: Design 7: checkout and a flash sale, 2 min

Design 7: checkout and a flash sale

Prompt and never-list. Reserve one unit for 10 minutes, take payment, confirm or release; one unit per buyer. Never oversell; a payment that lands after release is refunded, never fulfilled. Out: search, coupons, delivery, the provider's internals.

Numbers. 1,000 units, 2 million people, 200,000 attempts a second at noon, so 199,000 of every 200,000 answers are "no" and the design is mostly about saying no cheaply. One stock row at 2 ms a transaction serves about 500 holds a second. So split stock into 20 rows of 50 and admit only 2,000 buyers at a time through a token gate.

Boxes. CDN for the page, an edge gate handing out admission tokens, a sold-out flag in a cache, checkout servers, a database with stock rows, holds, orders and an outbox, a payment saga, a sweeper for expired holds.

API and tables. The key is the conditional decrement on a stock bucket, with the hold, the order, the one-per-buyer row and the outbox row in the same transaction.

POST /v1/sales/{sale_id}/buy  Idempotency-Key  {sku}
     -> 201 {hold_id, order_id, expires_at = now + 10 minutes}
     | 409 sold out | 409 already bought in this sale
POST /v1/orders/{order_id}/confirm   (called by the payment saga)
     -> 200 PAID | 410 hold expired: refund automatically
stock(sku, bucket, avail)  CHECK (avail >= 0); 20 buckets a SKU
holds(hold_id PK, order_id, sku, bucket, expires_at, state)
orders(order_id PK, buyer_id, sku, status PENDING | PAID | RELEASED)
sale_buyers(sale_id, buyer_id) PK: one unit per buyer
outbox(event_id PK, order_id, kind, payload, sent_at NULL)
guard: UPDATE stock SET avail = avail - 1
       WHERE sku = ? AND bucket = ? AND avail >= 1

Deep dive. The guard is a conditional decrement in the database, in one transaction with the hold, the order, the one-per-buyer row and the outbox row. Redis may say no early (gate tokens, the sold-out flag) but never yes: an asynchronous failover can lose an acknowledged decrement, which is a unit sold twice.

Failures. A server dies after commit: the retry with the same key gets the same hold. The provider times out: ask it for the status by key before deciding. The sweeper stops: page on the oldest expired hold above 1 minute.

Staff adds. Fixing the words, not the promise: the cart says a unit is not reserved until checkout; uneven draining of the 20 rows; config levers during the sale instead of deploys.

Operate and cost. Never first-deploy on a sale day; page on units sold above stock; the gate is the wall. About Rs 5.84 lakh a month: 30 app servers for the whole shop (Rs 3.6 lakh, assumed), 3 database nodes on local SSD (Rs 1.92 lakh) and 2 cache nodes for the gate and the flag (Rs 32,000). Each sale adds 200,000 requests a second for 10 minutes, 120 million, about Rs 9,600 at Rs 80 per million CDN requests.