Contents

Course · 16

How do the classic interview designs actually work?

Eleven classic questions, each worked with the framework from page 15: requirements, numbers, API, data model, a picture, deep dives, trade-offs and the follow-ups interviewers ask. Real-company numbers are dated and linked; estimates are marked as assumptions.

TL;DR

Almost every classic design is the same skeleton plus one hard part; the interview is about finding and solving that one part.

URL shortener: unique short IDs. Feed: fan-out and celebrities. Chat: ordering and delivery. Payments: never charge twice.
Read-heavy systems precompute and cache. Twitter (2012) served about 300k timeline reads per second against about 6k writes.
"Exactly once" over a network is a myth; real systems do at-least-once plus idempotency.
Each design ends with 3-4 follow-ups; a rapid-fire set of 16 more closes the page.

designs, each end to end

3.5T

7-character base62 codes (62^7 = 3,521,614,606,208)

41bits

of milliseconds in a Snowflake ID

3,2,2

common N,R,W in Amazon's Dynamo paper

—Words you need

Each word once, in plain English glossary

Base62

Writing numbers with 0-9, a-z, A-Z: 62 symbols.

Snowflake ID

A 64-bit ID made from time, machine and a counter.

Token bucket

A bucket refills with tokens; each request spends one.

WebSocket

A connection that stays open so the server can push.

Fan-out

Copying one item to many places, like every follower's feed.

Idempotent

Doing it twice has the same effect as once.

Quorum

Enough replicas agreeing, like 2 of 3, to call it done.

Bloom filter

Tiny memory set: says "maybe seen" or "surely not".

Trie

A tree of letters; each path spells a prefix.

Transcoding

Re-encoding a video into other sizes and formats.

ABR

Adaptive bitrate: the player switches quality as the network changes.

Geohash / H3

Ways to cut the map into cells with short IDs.

Ledger

An append-only money log; every move has two sides.

Reconciliation

Comparing your records with the bank's to catch gaps.

PSP

Payment service provider, like Stripe or Adyen.

CDN

Servers near users that keep copies of files.

—How each design is laid out

Same eight steps every time framework

Step	What you will see
Requirements	3-4 functional lines, the non-functional numbers that matter
Estimation	A worked `pre` block. Inputs are assumptions (the Alex Xu style numbers); results are computed
API and data model	The calls and the main tables or keys
Architecture	One picture, at most 6 boxes; coral marks the part the deep dive is about
Deep dives	The hard part, with options compared
Actually	What a real company or spec does, with the link
Bottlenecks and trade-offs	What breaks first and what each choice costs
Follow-ups	3-4 interviewer questions with model answers

Framework: page 15. Building blocks: pages 01-14.

Core web

01URL shortener (like bit.ly)

Hard part: unique short codes at scale interview favourite

Turn a long URL into a short code, and redirect anyone who opens the code. It sounds tiny. The interview is about generating unique codes without a bottleneck, and serving reads fast.

Requirements

Create: long URL in, short URL out. Optional expiry.
Redirect: open short URL, land on the long URL.
Scale (assumption): 100M new URLs a day, reads 10x writes, keep for 10 years.
Redirect must be fast and highly available. A code must never point to the wrong URL.

Estimation

writes  = 100M / 86,400                ≈ 1,160 /s      (peak ×2 ≈ 2.3k)
reads   = 10 × writes                  ≈ 11,600 /s     (peak ≈ 23k)
records = 100M × 365 × 10              = 365 billion
storage = 365B × 500 bytes (assumed)   ≈ 182 TB
code length: 62^6 = 56.8 billion  < 365B   // too few
             62^7 = 3.52 trillion  > 365B   // 7 characters is enough

API and data model

POST /v1/urls  { longUrl, expiresAt? }  → 201 { shortUrl }
GET  /{code}                            → 302 Location: longUrl   (404 if missing)

Url { code (PK), longUrl, userId, createdAt, expiresAt }   // read by code only: key-value access

Writes take an ID and store one row. Reads are one cache lookup and a 302.

Deep dive: how to make the code

Option	How	Good	Cost
Hash + cut	MD5 or SHA of the URL, keep 7 base62 chars	Same URL gives same code; no coordination	Collisions: must check the DB and retry with a salt
Global counter → base62	One counter (DB sequence or Redis `INCR`), encode in base62	No collisions, short codes	Counter is a single point; codes are guessable
Counter ranges	Each server grabs a block of 1,000 IDs at a time	Counter is hit 1,000x less	Gaps when a server dies (fine)
Snowflake	64-bit ID from time + machine + sequence, then base62 (11 chars)	No central service at all	Longer code; needs unique machine IDs and sane clocks

Time sits in the high bits, so bigger ID means later, roughly.

In everyday words

A coat check. You hand over a coat and get a small ticket number. Two coats must never get the same number, and finding a coat by ticket must be instant.

Actually

Twitter's Snowflake README: "41 bits (millisecond precision w/ a custom epoch gives us 69 years)", "10 bits - gives us up to 1024 machines", "12 bits - rolls over every 4096 per machine". The code (IdWorker.scala) splits the 10 bits into datacenterIdBits = 5 and workerIdBits = 5, with twepoch = 1288834974657 (computed: 2010-11-04 01:42:54 UTC). 2^41 ms ≈ 69.7 years. For the redirect, RFC 9110 says a 301 may be cached heuristically by browsers, so later clicks never reach you; a 302 "resides temporarily", so every click comes back (good for analytics). github.com/twitter-archive/snowflake

Bottlenecks and trade-offs

Concern	Choice	Trade-off
Read load (23k/s peak)	Redis cache, code → URL, LRU	A deleted link may live until TTL
301 vs 302	302 if you count clicks; 301 if you want less traffic	301 loses analytics; 302 costs a hit per click
Storage 182 TB	Key-value store sharded by code	No joins (none needed)
Guessable codes	Shuffle IDs or add random bits	Slightly longer codes

Follow-up questions

Same long URL submitted twice: same code? easy

Show answer

It is a product choice. With a counter, each submit gets a new code, which is simpler and lets each user track their own clicks. To reuse, add an index on the long URL (or its hash) and look it up first; that costs an extra read on every write. Bit.ly-style services usually give per-user codes. I would ask the interviewer, then pick.

How do you handle expired links? medium

Show answer

Store expiresAt. On read, if it is past, return 404 (or 410 Gone) and delete lazily. Set the cache TTL to no later than the expiry, so the cache never serves a dead link. A background job sweeps old rows in batches to free storage. If codes are reused after expiry, the cache TTL rule matters even more, or someone gets the wrong page.

The counter service dies. What happens? medium

Show answer

With ranges, each app server holds a block of, say, 1,000 unused IDs, so writes keep going until blocks run out. The counter itself sits in a replicated store (a DB sequence with failover, or ZooKeeper). Lost blocks just leave gaps, which are harmless. With Snowflake there is no central counter at all; the risk moves to clock skew, which Twitter's code handles by refusing IDs if the clock goes backwards.

How would you add click analytics without slowing redirects? hard

Show answer

The redirect path only reads the cache and returns 302. It also drops a small click event (code, time, country, referrer) onto a queue like Kafka, fire-and-forget. Consumers count in batches into a time-series or column store. The redirect latency stays a single cache read. Cost: counts are a few seconds behind, and a crash can lose a few events unless the producer waits for acks.

The whole design is one key-value lookup plus one ID generator. Spend the deep dive on the ID choice and say its cost.

Source: Snowflake README · IdWorker.scala · RFC 9110 §15.4 · Hello Interview, Bitly · Pages 04, 07

02Rate limiter

Hard part: one shared count across many servers core

Stop any one client from sending too many requests. The algorithms (token bucket, sliding window) are covered in page 03. Here the focus is the distributed design: where it sits and how many gateway nodes share one count.

Requirements

Limit by user, IP or API key, for example 100 requests a minute.
Reject with HTTP 429 Too Many Requests and a Retry-After header.
Adds very little latency (one memory round trip). Works across all gateway nodes.
If the limiter breaks, the API should keep working (fail open), as a rule of thumb.

Estimation

clients        = 10M active keys (assumption)
state per key  ≈ 100 bytes (tokens + last refill time + key)
memory         = 10M × 100 B = 1 GB     // fits in one Redis node; shard for QPS, not size
checks         = every request: same QPS as the API (say 50k/s) → Redis cluster

API and data model

allow(key, rule) → { allowed: bool, remaining, retryAfterMs }
Redis: rl:{userId}  → hash { tokens, ts }   TTL = window
Rules: { route: "/v1/orders", per: "user", limit: 100, window: 60s }

One shared counter store, so every gateway node sees the same count.

Deep dive: making the count correct

The race: two gateway nodes both read "99 used", both allow, count goes to 101. Fix it by making read-check-write one atomic step inside Redis. A Lua script runs atomically, so no other command runs in the middle.

-- token bucket in one atomic Redis script (sketch)
local t = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = math.min(cap, (t[1] or cap) + (now - (t[2] or now)) * rate)
if tokens < 1 then return 0 end
redis.call('HSET', KEYS[1], 'tokens', tokens - 1, 'ts', now)
redis.call('PEXPIRE', KEYS[1], ttl)
return 1

In everyday words

A club with a bouncer at each of five doors. If each bouncer counts alone, the club overfills. They need one shared clicker, and only one hand may press it at a time.

Actually

Redis docs: "Redis guarantees the script's atomic execution. While executing the script, all server activities are blocked during its entire runtime." So the read-and-update cannot interleave. The status 429 is defined in RFC 6585 ("the user has sent too many requests in a given amount of time") and may include Retry-After. Details on bucket vs window algorithms, with sources, are on page 03. redis.io: scripting with Lua

Bottlenecks and trade-offs

Concern	Choice	Trade-off
Redis round trip on every call	Local in-memory pre-check, sync to Redis in small batches	Slightly over the limit for a moment
Redis down	Fail open (allow) with a local fallback limit	Short window of no protection
Hot key (one huge customer)	Shard by key; give big customers their own limit	More rules to manage
Fixed window burst at the edge	Sliding window or token bucket	A bit more state per key

Follow-up questions

Where should the limiter live? easy

Show answer

At the API gateway or a sidecar, before the request costs anything. Client-side limits are useless because clients can be changed. A per-service limiter inside the app is fine for protecting a specific database call, but the general limit belongs at the edge. Managed gateways (AWS API Gateway, Envoy) already do this. Cost: the gateway must reach the shared counter store fast.

Limit across two regions? hard

Show answer

A global exact count needs a cross-region round trip (~100 ms) per request, which is too slow. Instead, give each region a share of the limit (say 50/50, rebalanced by recent traffic) and count locally, or sync counts asynchronously every second and accept slight overshoot. Most products accept "about 100 a minute" over "exactly 100". I would say that trade-off out loud.

Token bucket or sliding window? medium

Show answer

Token bucket allows short bursts up to the bucket size, then a steady rate. It needs only two numbers per key. Sliding window log is exact but stores a timestamp per request, which costs memory. Sliding window counter approximates with two counters and is a good middle. For a public API I pick token bucket: bursty clients are normal, and it is cheap.

The algorithm is easy. The design question is the shared, atomic counter and what happens when it is down.

Source: Redis Lua scripting · RFC 6585 §4 (429) · Page 03, 05

Social and messaging

03Chat system (like WhatsApp)

Hard part: delivery, order and offline users interview favourite

One-to-one and small group chat, with online status and ticks. The hard parts: keeping millions of open connections, finding which server holds the recipient, keeping order, and not losing messages for offline users.

Requirements

Send and receive 1:1 and group messages (groups up to a few hundred).
Delivery ticks (sent, delivered, read) and online / last-seen status.
Offline users get messages when they come back, plus a push notification.
Scale (assumption): 50M DAU, 40 messages each a day. Low latency. Never lose a message.

Estimation

messages   = 50M × 40 = 2B a day  → 2B / 86,400 ≈ 23k /s   (peak ×3 ≈ 70k)
storage    = 2B × 100 bytes        ≈ 200 GB a day ≈ 73 TB a year
sockets    = say 10M online at peak
servers    = 10M / 100k sockets each (planning figure, assumption) = 100 chat servers

API and data model

WebSocket frames:  send{ clientMsgId, chatId, body } → ack{ clientMsgId, msgId, ts }
                   deliver{ msgId, chatId, from, body }  ← client replies delivered{ msgId }
Message  ((chatId, bucket), msgId) → { from, body, ts }       // msgId is time-sortable
Session  userId → chatServerId     (Redis, TTL heartbeat)
Inbox    userId → pending msgIds    (for offline delivery)

Save first, then deliver. The store is the source of truth, sockets are just pipes.

Deep dive: delivery, order, presence

Problem	Solution	Why
Find recipient's server	Session registry: userId → server, in Redis; or route by consistent hash	Chat servers are stateful (they hold sockets)
Message order	Order per chat by a server-given, time-sortable msgId (Snowflake style); client sorts by it	Clocks on phones lie; one sequence per chat is enough
Duplicates on retry	`clientMsgId` from the phone; server dedups	Phone resends after a timeout; no double message
Offline user	Message is already saved; add to inbox; send push; deliver on reconnect	Store first, deliver second
Presence	Heartbeat every N seconds; offline after a few missed beats; fan out only to open chats	Telling all contacts on every change is too costly

Each tick is an acknowledgement travelling back to the sender.

In everyday words

A post office. Your letter is first stamped "received" at the counter (one tick). The postman gets a signature at the door (two ticks). The friend opens it (blue ticks). If nobody is home, the letter waits at the depot.

Actually

WhatsApp wrote in January 2012 that one server held over 2 million TCP connections, on FreeBSD and Erlang. Discord's 2017 post shows a real message schema: primary key ((channel_id, bucket), message_id), buckets of about 10 days so partitions stay under ~100 MB, and Snowflake message IDs so they sort by time. In 2023 Discord moved from 177 Cassandra nodes to 72 ScyllaDB nodes, with p99 history reads going from 40-125 ms to 15 ms. discord.com/blog (2017)

Bottlenecks and trade-offs

Concern	Choice	Trade-off
Millions of sockets	Many chat servers, L4 load balancing, sticky connections	Server restarts drop many sockets: clients must reconnect with backoff
Big groups	Fan-out on write to each member's inbox up to a size; beyond, members pull	Write amplification vs read cost
Message store	Wide-column store partitioned by chat	Hot partition for a very busy channel
End-to-end encryption	Server stores only ciphertext	No server-side search

Follow-up questions

Why WebSockets and not HTTP polling? easy

Show answer

Chat needs the server to push the moment a message arrives. Short polling wastes requests and adds delay; long polling holds a request open but re-creates it after each message. A WebSocket is one long-lived two-way connection with small frames, so pushes are instant and cheap. Cost: servers become stateful (they hold sockets), so I need a session registry and reconnect logic.

How do you guarantee no message is lost? medium

Show answer

The sender's app keeps the message until the server acks it, retrying with the same clientMsgId. The server acks only after writing to the replicated store. Delivery to the recipient is at-least-once: the server keeps it in the inbox until the device sends "delivered". Duplicates are dropped by msgId on the device. So: persist before ack, retry until ack, dedup on both sides.

How do you keep order in a group chat? hard

Show answer

I do not use phone clocks. The server stamps each message with a time-sortable ID from one sequence per chat (or a Snowflake ID, which is roughly ordered). All members sort by that ID, so everyone sees the same order. Two messages sent in the same millisecond get some order, but the same order for all, which is what users need. Strict global order across chats is not needed.

How does a user with 3 devices get every message? hard

Show answer

Track sessions per device: userId → list of (deviceId, server). Fan the message to every online device. Each device keeps its own "last synced msgId"; on reconnect it asks for everything after that. So the inbox becomes a per-device cursor, not a single queue. With end-to-end encryption, the sender encrypts once per device key, which is why device count is usually capped.

Save first, then deliver, and let IDs carry the order. Sockets are pipes; the store is the truth.

Source: WhatsApp blog, Jan 2012 · Discord 2017 · Discord 2023 · Pages 02, 09

04News feed / timeline

Hard part: fan-out and the celebrity problem interview favourite

Show each user the recent posts of people they follow. Reads far outnumber writes, so the main question is: do the work when someone posts (fan-out on write), or when someone reads (fan-out on read)?

Requirements

Post text or media. Follow users. See a home feed, newest or ranked.
Feed loads fast (say under 200 ms). A few seconds of delay for new posts is fine.
Scale (assumption): 300M DAU, 10 feed opens and 1 post per user a day, average 200 followers.

Estimation

feed reads = 300M × 10 / 86,400   ≈ 34.7k /s   (peak ≈ 100k)
posts      = 300M × 1  / 86,400   ≈ 3.5k /s
fan-out    = 3.5k posts × 200 followers ≈ 700k feed inserts /s   // the real write load
feed cache = 300M users × 800 IDs × 8 bytes ≈ 1.9 TB of RAM (spread over a cluster)

API and data model

POST /v1/posts { text, mediaIds }        GET /v1/feed?cursor=…&limit=20
Post   { postId (Snowflake), authorId, text, mediaKeys, createdAt }
Follow { followerId, followeeId }          // both directions indexed
Feed   feed:{userId} → Redis list of postIds, capped length

Push for normal users, pull for celebrities, merge at read time.

Deep dive: push, pull or both

Model	How	Good	Bad
Fan-out on write (push)	On post, insert postId into every follower's feed list	Reads are one list fetch: fast	A user with 30M followers means 30M inserts per post
Fan-out on read (pull)	On read, fetch recent posts of everyone you follow and merge	Writes are cheap	Slow reads; heavy for users who follow thousands
Hybrid	Push for normal authors; pull for celebrities, merged at read time	Bounded write cost and fast reads	Two code paths; merge logic

In everyday words

A newspaper. For a small club, you post a copy into each member's letterbox. For a national paper read by millions, you do not; people pick it up at the shop. The hybrid feed does both.

Actually

Twitter's 2012 talk (written up in 2013) gives the real numbers: about 300k QPS of timeline reads, about 6,000 writes per second (peaks over 12k/s), home timelines kept as 800 entries in a Redis cluster, each copy replicated 3 times. Fan-out aimed to finish "under 5 seconds", but a user with 31 million followers (Lady Gaga) made it slow enough that replies could arrive before the original tweet. highscalability.com (2013)

Bottlenecks and trade-offs

Concern	Choice	Trade-off
Celebrity posts	Threshold (say 1M followers): no push, pull at read	Merge cost on every read
Inactive users	Do not push to users idle for 30 days; rebuild their feed on login	First load after a break is slow
Feed cache memory	Store only IDs, cap length (Twitter used 800)	Old posts need a DB query
Ranking	Fetch ~500 candidates, rank with a model, return top 20	More CPU per read

Follow-up questions

A user unfollows someone. What happens to the feed? medium

Show answer

The cheap answer: filter at read time. The feed service checks the current follow list and drops posts from people no longer followed. A background job can also remove those IDs from the cached list. Exact, instant removal from millions of lists is not worth it. Cost: a small read-time check. Same idea for deleted posts: hydrate the IDs and skip missing ones.

Why store only post IDs in the feed cache? easy

Show answer

Memory and edits. An 8-byte ID times 800 entries is ~6 KB per user; full posts would be 100x more. And if a post is edited or deleted, it is changed in one place (the post cache), not in millions of feed lists. Reading the feed becomes: fetch 20 IDs, then a multi-get of 20 posts from the post cache. Two fast memory calls instead of one big one.

How do you paginate a feed that changes while I scroll? medium

Show answer

Cursor pagination, not page numbers. The cursor is the last postId I saw. "Give me 20 older than this ID." Because Snowflake IDs sort by time, new posts arriving at the top do not shift what I see lower down, so no duplicates or skips. Page offsets would break as soon as new posts arrive. New posts show as a "20 new posts" banner instead.

Where does the 700k inserts per second go? hard

Show answer

Into a sharded Redis cluster, through a queue. The post service writes the post, then emits one event to Kafka. Fan-out workers read the follower list in pages and pipeline inserts (Twitter pipelined about 4k destinations at a time). Shard feeds by userId so inserts spread evenly. If workers fall behind, posts appear late but nothing is lost: the queue holds them. Celebrity pull keeps the worst case bounded.

Pick push or pull from the read/write ratio, then fix the celebrity case with a hybrid. That is the whole interview.

Source: High Scalability on Twitter's "Timelines at Scale" · InfoQ talk page · Pages 05, 09

05Notification system

Hard part: many channels, retries without duplicates core

Many services want to tell users things: order shipped, new message, password changed. One notification service sends push, SMS and email, respects user settings, retries failures, and never spams the same alert twice.

Requirements

Channels: iOS push (APNs), Android push (FCM), SMS, email.
User preferences and quiet hours; templates; rate limits per user.
Soft real time (seconds are fine). At-least-once delivery, but no visible duplicates.
Scale (assumption): 10M notifications a day, bursts of 100x during campaigns.

Estimation

average = 10M / 86,400       ≈ 116 /s
burst   = campaign to 5M users in 10 min ≈ 8.3k /s   // design for the burst
log     = 10M × 1 KB          ≈ 10 GB a day of send records

API and data model

POST /v1/notify { eventId, userId, type, data }     // eventId = dedup key
Prefs   { userId, channel, enabled, quietHours }
Device  { userId, deviceToken, platform, updatedAt }
SendLog { eventId, channel, status, attempts, providerId }

The queue in the middle is what makes retries and spikes safe.

Deep dive: retries and dedup

Problem	Solution
Same event sent twice by the caller	`SET dedup:{eventId}:{channel} 1 NX EX 86400` in Redis; if the key exists, drop it
Provider timeout	Retry with exponential backoff and jitter; after N tries, move to a dead-letter queue
One slow channel blocks others	Separate queue and worker pool per channel
Dead device tokens	Provider says token is invalid → delete it
Campaign floods	Lower-priority queue; per-provider rate limit

In everyday words

A mail room. Letters are sorted into trays by type: post, courier, fax. If the courier does not answer, you try again later. A stamp on each letter's ID stops the same letter going out twice.

Actually

Providers limit what you can send and keep. Apple's guide says the request body "must not be compressed and its maximum size is 4KB (4096 bytes)". Firebase says if you do not set a lifespan, FCM keeps an undelivered message for the default of four weeks; the maximum time_to_live is 2,419,200 seconds (28 days). So "offline storage" for push is partly done by the provider, which is why your own inbox (in-app list) is still needed. firebase.google.com: message lifespan

Bottlenecks and trade-offs

Concern	Choice	Trade-off
Delivery guarantee	At-least-once + dedup key	Tiny chance of a duplicate if the dedup store loses a key
Ordering	Not guaranteed across channels	"Delivered" may arrive before "Shipped"; add timestamps
Preferences check	Cache prefs in Redis	A just-changed setting may be ignored for a minute
Provider outage	Second provider for SMS/email; queue holds push	Cost and two integrations

Follow-up questions

Why a queue between the service and the workers? easy

Show answer

Three reasons. Bursts: a campaign of 5M sends lands in the queue and workers drain it at a safe rate. Failure isolation: if APNs is slow, only the push queue grows; email keeps flowing. Retries: a failed job goes back with a delay instead of blocking the caller. The caller gets "accepted" in milliseconds. Cost: notifications are a few seconds late under load, which this product allows.

How do you avoid waking users at 3 a.m.? medium

Show answer

Store each user's time zone and quiet hours in preferences. Before sending, the service checks: if inside quiet hours and the type is not urgent (security alerts are), schedule it for the end of quiet hours using a delay queue or a scheduled-jobs table. Also collapse: five "new like" alerts become one summary. Cost: more state and a scheduler, but far fewer users turning notifications off.

How do you track if a notification was opened? medium

Show answer

Each notification carries its eventId. When the app opens from it, the app calls a tracking endpoint with that ID; for email, a tracking pixel or redirect link does the same. Events go to a queue and into an analytics store. "Sent" comes from our log, "delivered" partly from the provider, "opened" from the app. They are separate facts; never assume sent means seen.

Queue per channel, retry with backoff, and an eventId dedup key. That trio is what makes it reliable.

Source: Apple: Communicating with APNs (archive guide) · Firebase: message lifespan · Pages 09, 05

Data infrastructure

06Distributed key-value store (like Dynamo)

Hard part: partitioning, replication, failures deep dive

Build get(key) and put(key, value) that scale to many machines and stay up when some die. This design is a tour of pages 07 and 08: consistent hashing, replication, quorums, and repair.

Requirements

Small values (under 1 MB). Simple get and put.
Always writable, even during failures. Tunable consistency.
Scale by adding nodes, with little data moving. Low p99 latency.

Estimation

data      = 10 TB (assumption) × 3 replicas = 30 TB on disk
per node  = 2 TB usable → 15 nodes, plus headroom → ~20 nodes
traffic   = 100k ops/s ÷ 20 nodes = 5k ops/s per node   // easy for SSD-backed nodes

API and data model

get(key)                 → [ (value, version) ... ]   // may return conflicting versions
put(key, value, context) → ok                         // context = version seen
storage per node: LSM tree (memtable + SSTables), commit log for durability

N=3 copies, W=2 acks. The slow replica catches up later.

Deep dive: the five techniques

Problem	Technique	What it buys
Spread keys over nodes	Consistent hashing with virtual nodes	Adding a node moves only a small share of keys
Keep writes available	Versioning (vector clocks), conflicts fixed on read	Writes never block; app or last-write-wins merges
Temporary node failure	Sloppy quorum + hinted handoff	Another node holds the write with a "hint" and hands it back later
Permanent failure / drift	Anti-entropy with Merkle trees	Replicas compare tree hashes, sync only what differs
Who is in the cluster	Gossip protocol	No central membership server

R + W > N  → every read overlaps the latest write (strong-ish reads)
N=3, W=2, R=2  → survives 1 slow/dead replica for both reads and writes
N=3, W=1, R=1  → fastest, but reads may be stale

In everyday words

Three friends each keep a copy of the club's address book. To add a number, you only need two of them to write it down. When the third comes back from holiday, the others fill in what they missed.

Actually

Amazon's Dynamo paper (SOSP 2007) lists exactly these: consistent hashing for partitioning, vector clocks with reconciliation during reads, sloppy quorum and hinted handoff for temporary failures, Merkle-tree anti-entropy for permanent ones, and gossip for membership. Its target was that "99.9% of the read and write requests execute within 300ms", and it reports (N,R,W) = (3,2,2) as the common setting (paraphrased; also in MIT's 6.824 notes as "standard 3,2,2"). allthingsdistributed.com: Dynamo paper

Bottlenecks and trade-offs

Concern	Choice	Trade-off
Consistency vs availability	AP with tunable R/W (Dynamo, Cassandra)	App must handle stale or conflicting reads
Conflict resolution	Last-write-wins by timestamp	Simple, but can silently drop a write
Hot keys	Cache in front; split the key	More moving parts
Write path	Commit log + memtable + SSTables (LSM)	Fast writes; reads may check several files (bloom filters help)

Follow-up questions

Why virtual nodes in consistent hashing? medium

Show answer

With one point per server on the ring, ranges are uneven and a failed node dumps its whole range on one neighbour. With many virtual points per server (say 100-256), each server owns many small ranges spread around the ring. Load evens out, and when a node fails, its ranges spread across many survivors. Bigger machines can take more virtual nodes. Cost: a bigger ring map to keep in memory.

What is a sloppy quorum? hard

Show answer

A strict quorum needs W acks from the key's own N replicas. If two of them are down, writes fail. A sloppy quorum takes the first N healthy nodes walking the ring, even if some are not the key's real owners. The stand-in stores the write with a hint naming the true owner and hands it over when the owner returns (hinted handoff). Result: writes stay available; cost: R+W>N no longer guarantees you read the latest value.

How does a read find two conflicting versions, and then what? hard

Show answer

Each value carries a vector clock: a counter per node that wrote it. If one clock is greater on every entry, it is newer and the old one is dropped. If neither dominates, the writes were concurrent, so the read returns both. The client merges (Dynamo's shopping cart takes the union) and writes back with both clocks as context. Simpler systems use last-write-wins instead, trading lost writes for simplicity.

Name the five techniques and the one problem each solves. Then R + W > N, with what you lose when you relax it.

Source: Dynamo paper (2007) · MIT 6.824 Dynamo notes · Pages 07, 08

07Web crawler

Hard part: the frontier, politeness and dedup core

Download a billion web pages a month for a search index. The hard parts: deciding which URL to fetch next, not hammering any one website, and not fetching the same URL or the same content twice.

Requirements

Start from seed URLs, follow links, store HTML.
Obey robots.txt and keep a polite delay per host.
Skip already-seen URLs and duplicate content. Recrawl pages that change.
Scale (assumption): 1B pages a month, average page 500 KB, keep 5 years.

Estimation

pages/s   = 1B / (30 × 86,400)       ≈ 386 /s    (peak ≈ 800)
storage   = 1B × 500 KB              = 500 TB a month → 30 PB over 5 years
URL set   = bloom filter for 1B URLs at 1% false positives:
            m = -n·ln(p) / (ln 2)^2  ≈ 9.6 billion bits ≈ 1.2 GB,  k ≈ 7 hash functions

API and data model

Frontier   priority queues (by importance) → per-host FIFO queues (one host per queue)
HostState  { host, robotsRules, robotsFetchedAt, nextAllowedFetchAt }
Page       { urlHash, url, contentHash, fetchedAt, s3Key }

A loop: every page you fetch feeds new URLs back into the frontier.

Deep dive: frontier, politeness, dedup

Part	How it works
Prioritiser (front queues)	Score URLs (page rank, freshness need) and put them in priority queues
Politeness (back queues)	Each back queue holds URLs of one host; a worker takes from a queue only after that host's delay has passed
URL dedup	Normalise the URL, then check a bloom filter; "surely not seen" → enqueue
Content dedup	Hash the page body (or a SimHash for near-copies); skip if seen
Traps	Max depth, max URL length, max pages per host

In everyday words

A librarian copying books from many shops. She keeps a to-do list, never sends two helpers to the same small shop at once, and ticks off titles she already has so she never copies one twice.

Actually

RFC 9309 (the robots.txt standard, 2022) says crawlers "SHOULD NOT use the cached version for more than 24 hours", the parsing limit "MUST be at least 500 kibibytes", a 4xx status means the crawler "MAY access any resources", and a 5xx means it "MUST assume complete disallow". A bloom filter never says "no" wrongly, only "maybe" wrongly, so a false positive just skips one new URL; the sizing formula above is the standard one. rfc-editor.org/rfc/rfc9309

Bottlenecks and trade-offs

Concern	Choice	Trade-off
DNS lookups	Local DNS cache per crawler	Stale IPs for moved sites
Bloom filter false positives	1% target	About 1 in 100 new URLs is skipped
Frontier too big for memory	Keep queue heads in memory, rest on disk	More disk I/O
Distributing work	Partition by host hash, so one host lives on one crawler	Big hosts make uneven load

Follow-up questions

Why partition the crawl by host and not by URL? medium

Show answer

Politeness is per host. If URLs of one host are spread across 100 crawlers, each one thinks it is being polite, but together they hammer the site. Hashing the host to one crawler keeps that host's delay in one place, along with its robots.txt cache and DNS entry. Cost: a huge host (like a big wiki) is stuck on one machine, so it gets a higher allowed rate or a split by path.

How do you decide when to recrawl a page? medium

Show answer

Track how often each page changed in past visits (compare content hashes). Pages that change often (news homepages) get a short revisit interval; stable pages get a long one. Important pages get a boost. HTTP ETag and Last-Modified let us do a cheap conditional GET that returns 304 when nothing changed. The revisit time becomes the URL's priority in the frontier.

Why a bloom filter and not a hash set of URLs? easy

Show answer

Memory. A billion URLs at ~100 bytes is ~100 GB as a set. A bloom filter with 1% false positives needs about 9.6 bits per URL: ~1.2 GB. It can say "maybe seen" wrongly (we skip a few new URLs), but never "not seen" wrongly, so we never refetch by mistake. If skipping is not OK, use the filter as a fast first check and confirm "maybe" answers in a disk-backed store.

The crawler is a loop. The frontier decides order and politeness; the bloom filter keeps the loop from eating itself.

Source: RFC 9309 robots.txt · Bloom filter sizing formula · Page 11

08Typeahead / search autocomplete

Hard part: answers in tens of milliseconds, per keystroke core

As you type "dis", show the top 5 searches starting with "dis". Every keystroke is a request, so reads are huge and must be very fast. The trick: do all the counting offline and serve from memory.

Requirements

Top 5 suggestions for a prefix, ranked by popularity.
Response well under 100 ms so it feels instant.
Popularity can lag by hours. Filter offensive terms.
Scale (assumption): 10M DAU, 10 searches each, 20 characters per search.

Estimation

requests = 10M × 10 × 20 / 86,400   ≈ 23k /s   (peak ≈ 50k)
           // debounce on the client cuts this a lot
trie     = say 100M distinct queries × ~30 bytes ≈ 3 GB + top-5 lists per node → fits in RAM per server

API and data model

GET /v1/suggest?q=dis&limit=5  → ["discord", "disney plus", ...]
Trie node: { children, top5: [(query, count)] }     // top-k cached at every node
Offline:   query_log → counts per query (daily / weekly window)

Online path is a memory lookup. All the counting happens offline.

Deep dive: why cache top-k at every trie node

A plain trie finds the prefix node fast, but then must walk every word below it to find the most popular ones. That can be millions of nodes for "a". Storing the top 5 at each node turns a read into: walk down the prefix (length L), return the stored list. The cost moves to build time and memory.

Approach	Read cost	Update cost
Trie, search subtree	Slow for short prefixes	Cheap
Trie with top-k per node	O(prefix length)	Rebuild or update every ancestor
Prefix → list in Redis / key-value	One lookup	Write every prefix of every query
Search engine completion suggester	Fast, in memory	Costly to build; managed for you

In everyday words

A shop assistant who has memorised "people who ask for 'dis' usually want these five things". She does not search the warehouse each time; she rehearses the lists every night after closing.

Actually

Elasticsearch's completion suggester is the off-the-shelf version. Its docs say it "uses data structures that enable fast lookups, but are costly to build and are stored in-memory", and that it is "a navigational feature" for search-as-you-type, "not meant for spell correction". That is the same trade-off as the trie: pay at build time and in memory to make reads cheap. elastic.co: search suggesters

Bottlenecks and trade-offs

Concern	Choice	Trade-off
Request volume	Debounce (wait ~100-200 ms after typing), browser cache of results	Slightly later first suggestion
Freshness	Rebuild hourly or daily; a small "trending" layer updated faster	Two sources to merge
Trie size	Shard by first letters (a-f, g-m …) or replicate whole trie	Uneven shards ("s" is huge)
Personalisation	Blend global top-k with the user's own history on the client	More logic, privacy care

Follow-up questions

How do you update counts without locking the live trie? medium

Show answer

Do not update it in place. Build a new trie offline from the latest aggregated counts, snapshot it, and load it on servers side by side; then switch traffic and drop the old one (blue-green). Reads never wait. For faster trends, keep a small separate structure fed by a stream (counts over the last hour) and merge its few results at read time.

How do you remove an offensive suggestion right now? easy

Show answer

A blocklist checked at serve time, in the suggest API, before returning results. It is small and pushed to all servers within seconds. The next offline build also drops the term so it does not come back. Waiting for a rebuild is too slow for a bad suggestion that is live now.

How would you shard the trie? hard

Show answer

If it fits in RAM (a few GB), I do not shard; I replicate the whole trie to every server and load-balance. That is simplest and avoids hot shards. If it does not fit, shard by prefix range, but split by measured traffic, not alphabet: "s" and "c" get their own shards, "x-z" share one. A small routing map tells the API which shard owns a prefix.

Count offline, serve from memory, cache the answer at each prefix. The read path should be a pointer walk.

Source: Elasticsearch suggesters · Pages 04, 11

Media, maps, money

09Video streaming (like YouTube)

Hard part: transcoding pipeline and adaptive playback interview favourite

Users upload videos; millions watch them on all kinds of networks. Two separate systems: an upload pipeline that turns one file into many versions, and a playback path where the CDN does almost all the work.

Requirements

Upload large files (resumable). Watch with smooth playback on phone or TV.
Quality adapts to the network. Start playing within a couple of seconds.
Scale (assumption): 5M DAU, 10% upload one video a day, average 300 MB.

Estimation

uploads   = 5M × 10% = 500k videos a day
storage   = 500k × 300 MB = 150 TB a day (originals; renditions add more)
egress    = the real cost: views × size. Serve from a CDN, not from origin.

API and data model

POST /v1/videos → { videoId, uploadUrl }     // presigned, multipart, resumable
GET  /v1/videos/{id}/master.m3u8            // from CDN
Video  { videoId, ownerId, title, status: uploading|processing|ready, durationS }
Rendition { videoId, height, bitrate, playlistKey }

Upload once, encode many times, serve from the edge.

Deep dive 1: the transcoding pipeline

Transcoding is the slow, costly step. Split the video into chunks (by GOP, a group of pictures that can be decoded alone), encode chunks in parallel on many workers, for each resolution and codec, then write segments plus playlists. Model it as a DAG (a graph of tasks with dependencies): split → encode ×N → package → thumbnail → mark ready.

The player, not the server, picks the quality for each next segment.

Deep dive 2: adaptive bitrate (HLS / DASH)

Piece	What it is
Segment	A few seconds of video, a normal HTTP file the CDN can cache
Media playlist	List of segments for one quality; `EXT-X-TARGETDURATION` is the max segment length
Master (multivariant) playlist	List of qualities, each with a `BANDWIDTH` in bits per second
Player logic	Measures download speed and buffer; picks the quality for the next segment

In everyday words

A tap that the viewer controls. On a fast pipe they open it fully (HD); when the pipe narrows, they turn it down so water never stops. The shop sells the same water in many pipe sizes.

Actually

HLS is RFC 8216. Its example master playlist lists three variants: BANDWIDTH=1280000, 2560000 and 7680000; BANDWIDTH is "the peak segment bit rate", and clients "should switch between different Variant Streams to adapt to network conditions". DASH is the ISO standard (ISO/IEC 23009-1) doing the same with an MPD file. Scale is real: YouTube said in 2019 that over 500 hours of video are uploaded every minute. Its MySQL sharding layer, Vitess, "was created in 2010 to solve the MySQL scalability challenges that the team at YouTube faced". rfc-editor.org/rfc/rfc8216 §8.4

Bottlenecks and trade-offs

Concern	Choice	Trade-off
Upload through app servers	Presigned URL: client uploads straight to object storage	Must validate after upload
Transcode cost	Encode popular videos in more renditions; rare ones fewer, or lazily	Rare videos may play in lower quality first
Egress bandwidth	CDN; for huge scale, own edge boxes inside ISPs	Cost and operations
Segment length	Short (2-6 s) for faster switching and startup	More files, more requests

Follow-up questions

How does a 2 GB upload survive a flaky phone network? medium

Show answer

Multipart, resumable upload. The file is split into parts (say 8 MB), each uploaded and acknowledged on its own, straight to object storage with presigned URLs (S3 multipart upload). If the network drops, the client asks which parts arrived and sends only the rest. When all parts are in, a complete call joins them and fires an event that starts transcoding. App servers never carry the bytes.

Why split the video into segments at all? easy

Show answer

Three reasons. Each segment is a plain HTTP file, so any CDN can cache it. The player can switch quality at every segment boundary. And seeking means jumping to segment N instead of downloading from the start. Cost: thousands of small files per video and a playlist to manage, which is cheap compared to the gains.

How do you count views at YouTube scale? hard

Show answer

Not with an UPDATE per view. Players send view events to a stream (Kafka). Stream jobs dedup (same user, same video, short window), filter bots, and add counts in time buckets; totals are flushed to the database every few seconds. The shown number is slightly behind and may be approximate for fresh videos. A sharded counter (many sub-counters summed on read) helps for one viral video.

Two systems: a heavy, async encode pipeline, and a playback path where the player picks quality and the CDN serves bytes.

Source: RFC 8216 HLS · Tubefilter on YouTube's 2019 figure · Vitess history · Pages 04, 11, 12

10Ride sharing (like Uber)

Hard part: "which drivers are near me?" at huge write rates interview favourite

Riders request a ride; the system finds nearby free drivers and offers the trip. Drivers send their location every few seconds, so location writes are enormous and short-lived. The key is a geospatial index: a way to ask "who is near this point" fast.

Requirements

Drivers share live location. Riders see nearby cars and request a ride.
Match within seconds; one driver must never get two trips at once.
Trip state is durable (requested → accepted → started → completed → paid).
Scale (assumption): 1M active drivers sending GPS every 4 s; 10M trips a day.

Estimation

location writes = 1M / 4 s          = 250k /s     // keep in memory, overwrite
trips           = 10M / 86,400       ≈ 116 /s     (peak ×5 ≈ 600)
location state  = 1M × ~100 bytes    ≈ 100 MB     // tiny; the rate is the problem, not the size

API and data model

WS  driver → { lat, lng, ts, status }                   (every 4 s)
POST /v1/rides { pickup, dropoff } → { rideId, status }
Geo index:  cellId → set of driverIds   (or Redis GEOADD drivers lng lat id)
Trip  { rideId, riderId, driverId, state, fare, timestamps }   // SQL, state machine

Location writes are huge and short-lived; keep them in memory, not in the trip database.

Deep dive: geospatial index options

Index	How	Good	Watch out
Geohash	Interleave lat/lng bits into a base32 string; same prefix ≈ near	Works in any key-value store or B-tree	Edge problem: neighbours across a cell line have different prefixes, so also search the 8 neighbour cells
Quadtree	Split a square into 4 until each cell holds ≤ K points	Adapts to density (dense city, empty desert)	In-memory tree; updates with moving drivers are costly
H3 (Uber)	Hexagon cells in 16 resolutions	All 6 neighbours at one distance; good for surge areas	Hexagons do not nest perfectly
Redis GEO	`GEOADD` / `GEOSEARCH`, a sorted set scored by a 52-bit geohash	Ready to use	One key per city to keep sets small

In everyday words

A city cut into numbered squares on a map. To find taxis near you, you look in your square and the eight squares around it, instead of phoning every taxi in the city.

Actually

Uber's H3 docs: resolutions 0 to 15; an average cell is 5.161 km² at resolution 7 and 0.105 km² at resolution 9. Uber's blog says hexagons have "only one distance between a hexagon centerpoint and its neighbors", which simplifies smoothing for surge pricing and dispatch. For geohash, Elasticsearch's table gives a 6-character cell of about 1.2 km × 609 m at the equator. Redis GEOSEARCH is O(N+log(M)) and returns "the raw 52-bit geohash-encoded score". h3geo.org resolution table

Deep dive: matching without double booking

Matching takes the nearest few free drivers (by road ETA, not straight line), offers the trip to one at a time with a short timeout, and on accept does an atomic state change: UPDATE drivers SET status='busy' WHERE id=? AND status='free'. If zero rows change, someone else got the driver; try the next one.

Bottlenecks and trade-offs

Concern	Choice	Trade-off
250k location writes/s	In-memory geo index, sharded by city/region; no DB write per ping	Location lost on crash (refilled within 4 s)
Cell size	Pick so a search covers a few hundred drivers	Too small: many cells; too big: too many candidates
Trip state	SQL with transactions	Fine at ~600 trips/s; shard by city later
Hot area (stadium)	Finer resolution where dense	More complex indexing

Follow-up questions

Why not store every GPS ping in the database? easy

Show answer

Because only the latest location matters for matching, and 250k writes per second would need a large cluster for data we overwrite in 4 seconds. Keep the current location in memory (Redis GEO or an in-process index), overwrite on each ping. If we need the route history (for fares or safety), send pings to a stream like Kafka and batch them into cheap storage later, off the hot path.

What is the geohash edge problem? medium

Show answer

Two points a few metres apart can sit on opposite sides of a cell border, so their geohashes share a short prefix or none. A search of only my cell misses the driver across the line. Fix: search my cell plus its 8 neighbours, then filter by real distance. H3 has the same need (search a ring of neighbours), but its hexagon neighbours are all the same distance away, which makes rings cleaner.

Driver's phone loses connection mid-trip. What happens? medium

Show answer

The trip state lives on the server, not the phone, so nothing is lost. The driver's location entry expires after a few missed pings, which removes them from matching. The rider sees "last known location". When the phone reconnects, the app fetches the current trip state and resumes. Pings buffered on the phone can be uploaded later for the fare. Durable state on the server, soft state in memory.

Hot, throwaway location data goes in memory with a geo index; trip state goes in a transactional database. Never mix them.

Source: H3 resolution table · Uber engineering: H3 · Elasticsearch geohash grid · Redis GEOSEARCH · Page 05

11Payment system

Hard part: never charge twice, never lose a cent deep dive

Take money from a customer through a payment provider (PSP), record it correctly, and prove later that your records match the bank's. Volume is small compared to other designs. Correctness is everything.

Requirements

Charge a card; refunds; payouts to sellers.
A retried request must never charge twice. Every cent is traceable.
Strong consistency for balances; full audit trail.
Scale (assumption): 1M payments a day.

Estimation

payments = 1M / 86,400 ≈ 12 /s   (peak ×10 ≈ 120 /s)   // one SQL primary is enough
ledger   = 2+ rows per payment → ~2M rows a day ≈ 730M a year

API and data model

POST /v1/payments   Idempotency-Key: 7f3c…   { orderId, amount, currency, method }
Payment   { id, orderId, amount, state: created|pending|succeeded|failed, pspRef }
Idem      { key PK, requestHash, responseCode, responseBody, createdAt }
LedgerEntry { txnId, account, debit, credit, ts }   // append-only; per txn: sum(debit) = sum(credit)

Three safety nets: idempotency key, ledger, reconciliation.

Deep dive: idempotency, ledger, reconciliation

Net	How	Catches
Idempotency key	Client sends a unique key; server saves the first result under it and returns the same result on retries	Double charge from retries and double clicks
Double-entry ledger	Every movement writes equal debits and credits, append-only, never updated	Money appearing or vanishing; gives a full audit trail
Reconciliation	Daily job compares the ledger with the PSP's settlement file	Lost webhooks, PSP errors, bugs
State machine	Payment moves only along allowed states; unknown results stay "pending" until checked	Timeouts where we do not know if the charge happened

// customer pays 100 for an order; we keep 10 as fee
txn 42:  debit  customer_funds    100
         credit seller_payable     90
         credit platform_revenue   10      // debits 100 = credits 100

In everyday words

A shop's paper receipt book. Every sale is written twice: cash in, goods out. You never rub out a line; you add a correcting line. At night you count the till and match it to the book.

Actually

Stripe's API docs: idempotency keys can be up to 255 characters; Stripe "saves the status code and body of the first request" for a key, and retries "return the saved response, including 500 errors"; keys can be removed "after they're at least 24 hours old"; and it "compares incoming parameters to those of the original request and errors if they're not the same". On "exactly once": Kafka gets it only inside Kafka (idempotent producer plus transactions); for outside systems its docs say the consumer should "store its offset in the same place as its output". Across a network to a bank, exactly-once delivery is a myth; you build at-least-once plus idempotency. docs.stripe.com/api/idempotent_requests

Bottlenecks and trade-offs

Concern	Choice	Trade-off
PSP call times out	Mark "pending"; query the PSP by our reference; never blindly retry with a new key	User waits for a final answer
Ledger store	SQL with transactions, append-only table	Harder to scale writes (fine at this volume)
Balance reads	Sum of entries, with periodic snapshots	Snapshot logic to maintain
Events to other services	Transactional outbox (page 10)	Extra table and relay process

Follow-up questions

The user double-clicks "Pay". Walk me through it. medium

Show answer

The client creates one idempotency key per checkout (not per click) and sends it on both requests. The first request inserts the key row (unique constraint) and proceeds. The second either finds the key with a saved result and returns it, or finds it "in progress" and gets a 409 to retry shortly. Either way only one PSP call happens. I also pass our payment ID as the PSP's own idempotency key, so even our retries to the PSP are safe.

Why double-entry instead of a balance column? medium

Show answer

A balance column is updated in place, so history is gone and a bug silently corrupts money. Double-entry writes immutable rows where debits equal credits for every transaction, so the books must always sum to zero. You can rebuild any balance at any time from entries, audit every cent, and catch bugs because an unbalanced transaction is rejected. Cost: more rows, and balances are computed (with snapshots for speed).

Is "exactly once" possible? hard

Show answer

Exactly-once delivery over a network is not: a sender cannot tell "lost request" from "lost reply", so it must retry, which may duplicate. What we build is exactly-once effect: at-least-once delivery plus idempotent processing (dedup by a key) or an atomic write of result and progress together. Kafka's exactly-once works inside Kafka via idempotent producers and transactions; once you touch a PSP or another database, you need idempotency keys again.

Reconciliation finds a mismatch. Then what? hard

Show answer

Classify it. PSP has a charge we marked failed or pending (often a lost webhook): fix our state and post the missing ledger entries. We have a success the PSP lacks: investigate, maybe refund or re-query. Amount mismatch (fees, currency): post an adjusting entry. Never edit old ledger rows; add correcting ones. Anything unclear goes to a human queue. Track mismatch counts as an alert metric.

Idempotency stops duplicates, the ledger makes money traceable, reconciliation catches whatever slips through. Say all three.

Source: Stripe: idempotent requests · Kafka design: delivery semantics · Modern Treasury: double-entry · Page 10

Practice

—When to use what

The one hard part of each design decision table

Situation	Pick	Why
Need unique IDs without a central bottleneck	Snowflake-style IDs or counter ranges	Each machine makes IDs alone; IDs sort by time
Short public codes	Counter + base62 (shuffled if guessing matters)	7 chars cover 3.5 trillion codes
One shared limit across many servers	Redis + atomic Lua script	No race between read and write
Server must push to clients	WebSockets + session registry	Instant delivery; find the right socket
Feed with normal users	Fan-out on write	Reads are one list fetch
Feed with celebrities	Pull for them, merge at read	Bounded write cost
Writes must stay available during failures	Leaderless replication, sloppy quorum	Accept writes with nodes down; fix later
Have I seen this item? (billions)	Bloom filter	~1.2 GB for 1B items at 1%
Prefix suggestions	Trie with top-k at nodes, built offline	Read is a short walk
Serve video worldwide	Segmented HLS/DASH on a CDN	Cacheable files, quality switching
Find things near a point	Geohash / H3 / Redis GEO	Search a few cells, not the world
Money	Idempotency keys + double-entry ledger + reconciliation	No double charge, full audit

—Common mistakes

Traps seen in these designs traps

Trap 1

Hashing URLs and ignoring collisions

Fix: check-and-retry with a salt, or use a counter.

Trap 2

Using phone clocks to order messages

Fix: server-given, time-sortable IDs per chat.

Trap 3

Pure fan-out on write for everyone

Fix: celebrity threshold and pull for them.

Trap 4

Writing every GPS ping to the database

Fix: overwrite in memory; stream history separately.

Trap 5

Claiming "exactly-once" payments

Fix: at-least-once + idempotency key + reconciliation.

Trap 6

Uploading video through app servers

Fix: presigned, multipart upload to object storage.

Trap 7

One crawler per URL, not per host

Fix: partition by host to keep politeness in one place.

Trap 8

Non-atomic rate limit check

Fix: one Lua script or atomic INCR with expiry.

—Rapid-fire design follow-ups

Across all eleven designs, with model answers 16 questions

Why does a URL shortener use 7 characters? easy

Show answer

Because of the count of codes needed. With base62 (0-9, a-z, A-Z), 6 characters give 62^6 ≈ 56.8 billion codes and 7 give ≈ 3.52 trillion. At 100M new URLs a day for 10 years we need 365 billion, which 6 characters cannot cover and 7 can, with room to spare. Shorter is nicer, so pick the smallest length that fits the 10-year total. Follow-up: what if we run out? Add one character; old codes still work.

Snowflake: what breaks if a server's clock jumps back? medium

Show answer

IDs could repeat or go out of order, because the timestamp is the top 41 bits. Twitter's original code refuses: if the current time is less than the last timestamp it logs "clock is moving backwards" and throws, rejecting requests until time catches up. Other fixes: wait out small jumps, or use a logical clock. Prevent it with NTP that slews (adjusts slowly) instead of stepping. Unique worker IDs (10 bits) matter just as much.

301 or 302 for a short link redirect? easy

Show answer

302 if you want analytics or the ability to change the target; 301 if you want to cut traffic. RFC 9110 says a 301 response may be cached heuristically, so browsers can go straight to the long URL next time without asking you; you lose the click and cannot change it. A 302 means "temporarily elsewhere", so every click comes back to you. Most shorteners that sell analytics use 302 (or 307).

How does the chat server know which server holds the recipient? medium

Show answer

A session registry: when a user connects, their chat server writes userId → serverId to Redis with a TTL, refreshed by heartbeats. To deliver, server A looks it up and forwards to server B over an internal channel (direct RPC or a pub/sub topic per server). If no entry exists, the user is offline: keep the message in the inbox and send a push. Alternative: consistent-hash users to servers, which avoids the lookup but complicates rebalancing.

What is the celebrity problem, in one minute? medium

Show answer

With fan-out on write, a post costs one insert per follower. For a user with 31 million followers (Twitter's 2012 example), one post means 31 million inserts; fan-out falls behind and others' tweets are delayed. Fix: above a follower threshold, do not push. Store their posts once, and at read time the feed service pulls recent posts from the celebrities you follow and merges them with your pushed feed.

Push notifications: how do you stop duplicates when a worker crashes mid-send? hard

Show answer

You cannot fully. If the worker sent to APNs but crashed before acking the queue, the job is redelivered and sent again. Reduce it: check a dedup key (eventId + channel) in Redis before sending and set it right after; give the notification a collapse key so the device shows one. The honest answer: at-least-once with dedup makes duplicates rare, not impossible. For push, a rare duplicate is acceptable; for payments it is not, so they use stronger idempotency.

In a Dynamo-style store, N=3, W=1, R=1. What can go wrong? medium

Show answer

R + W = 2, not more than N = 3, so a read may hit a replica that has not yet received the latest write: stale reads. And a write acked by one node is lost if that node dies before replicating. It is fast and very available, fine for caches or session data. For data that must be read back right after writing, use W=2, R=2 (R+W>N), accepting a bit more latency.

How do Merkle trees help replicas sync? hard

Show answer

Each replica builds a hash tree over a key range: leaves hash keys, parents hash their children. Two replicas compare root hashes; if equal, the whole range matches and nothing moves. If not, they compare children and walk down only the branches that differ, reaching the few keys that need copying. So syncing cost is proportional to the difference, not the data size. Dynamo used this for anti-entropy after long failures.

Crawler: how do you avoid crawler traps? medium

Show answer

Traps are sites that make endless URLs: calendars with "next month" forever, session IDs in URLs, infinite filter combinations. Defences: normalise URLs (drop session params, sort query strings), cap depth from the seed, cap URL length, cap pages per host per day, and detect near-duplicate content with hashes. Watch per-host metrics: a host producing many new URLs but few new contents is likely a trap.

Typeahead: what if the prefix is just one letter? easy

Show answer

That is exactly why each trie node stores its own top-k. The node for "a" already holds the 5 most popular queries starting with "a", so the answer is one lookup, as fast as for "amaz". Without the cache, "a" would need a scan of millions of descendants. Many products also wait for 2-3 characters or apply debounce, because one-letter results are rarely what the user wants and cost requests.

Video: why does the player, not the server, pick quality? medium

Show answer

Only the player sees its real download speed and buffer level, segment by segment. In HLS and DASH the server just publishes a master playlist of variants with their bandwidth (RFC 8216's example: 1.28, 2.56 and 7.68 Mbps); the player chooses each next segment. This keeps the server stateless and every segment a cacheable file, which is what lets CDNs serve almost all traffic. Cost: quality logic lives in many client apps.

Ride sharing: how do you prevent two riders getting the same driver? hard

Show answer

Make the assignment a compare-and-set. When a driver accepts, run an atomic update: set status busy where id = X and status = free. Exactly one request sees "1 row changed"; the other sees 0 and moves to its next candidate. A Redis lock with TTL on the driver ID also works. Also offer each trip to one driver at a time with a timeout, so drivers rarely get two offers at once.

Payments: the PSP call timed out. Charge or not? hard

Show answer

Unknown, so never assume. Keep the payment "pending". Query the PSP with our reference (or retry with the same idempotency key, which returns the original result rather than charging again). Listen for the webhook. Show the user "processing". Only mark failed when the PSP confirms. Retrying with a new key is the classic double-charge bug. Daily reconciliation catches anything still unclear.

Where does a CDN help across these designs? easy

Show answer

Anywhere the same bytes go to many users: video segments (most of the traffic), images and avatars in feeds and chat, static app files, and even hot short-link redirects or typeahead results with short cache headers. A CDN serves from an edge near the user, cutting latency and origin load. It does not help with personal, fast-changing data like a user's own feed or a payment status. Page 04 covers cache headers and invalidation.

Which of these designs need strong consistency? medium

Show answer

Payments and ledgers (money), driver assignment in ride sharing (no double booking), and short-code uniqueness (a code must map to one URL). Eventual consistency is fine for feeds, view and like counts, typeahead, presence, notifications and crawled pages. Saying this per feature, not per system, is a strong SDE-2 signal: you use strong consistency where errors cost money or trust, and cheaper eventual consistency everywhere else.

Design question: how would you add "seen by" to group chat? hard

Show answer

Do not store one row per message per member; that explodes. Store a read cursor per member per chat: the highest msgId they have read. "Seen by" for a message = members whose cursor is ≥ that msgId. The client updates its cursor when the chat is open (debounced), and the server fans the cursor change to online members. For a 200-member group, that is 200 small values per chat, not 200 rows per message.

—Cheat sheet

Numbers and facts to memorise numbers

Fact	Value	Source
Base62 codes, 6 / 7 chars	56.8 billion / 3.52 trillion	arithmetic
Snowflake layout	1 sign + 41 time (ms) + 5 DC + 5 worker + 12 sequence	Twitter README, IdWorker.scala
Snowflake limits	~69.7 years of time; 4,096 IDs per ms per worker	2^41 ms; 2^12
Twitter timelines (2012)	~300k read QPS, ~6k writes/s, 800 entries per timeline	High Scalability 2013
WhatsApp, one server (Jan 2012)	over 2M TCP connections	WhatsApp blog
Discord messages key	`((channel_id, bucket), message_id)`, ~10-day buckets	Discord blog 2017
Dynamo	(N,R,W) = (3,2,2); 99.9% of requests within 300 ms	Dynamo paper 2007
robots.txt cache / size	≤ 24 h; parse at least 500 KiB	RFC 9309
Bloom filter, 1B items, 1%	~1.2 GB, k ≈ 7	standard formula
HLS example variants	1.28 / 2.56 / 7.68 Mbps	RFC 8216 §8.4
H3	16 resolutions (0-15); res 9 ≈ 0.105 km²	h3geo.org
Geohash 6 chars	~1.2 km × 609 m	Elasticsearch docs
Stripe idempotency key	≤ 255 chars; prunable after ≥ 24 h	Stripe API docs
APNs payload / FCM max TTL	4 KB / 28 days	Apple guide / Firebase docs

Reference

—Sources

What	Where
Twitter Snowflake README and IdWorker.scala	github.com/twitter-archive/snowflake
HTTP redirects 301/302/307/308	RFC 9110 §15.4
429 Too Many Requests	RFC 6585 §4
Redis Lua atomicity; GEOSEARCH	redis.io scripting, redis.io GEOSEARCH
WhatsApp 2M connections (2012)	blog.whatsapp.com
Discord message storage (2017, 2023)	billions, trillions
Twitter timelines at scale	highscalability.com (2013)
APNs payload size; FCM lifespan	Apple archive guide, Firebase docs
Dynamo paper	allthingsdistributed.com, MIT 6.824 notes
robots.txt standard	RFC 9309
Elasticsearch completion suggester; geohash grid	suggesters, geohash grid
HLS	RFC 8216
YouTube 500 h/min (2019); Vitess history	tubefilter.com, vitess.io
H3	h3geo.org, uber.com/blog/h3
Stripe idempotency; Kafka semantics; double-entry	Stripe, Kafka design, Modern Treasury
Hello Interview Bitly breakdown	hellointerview.com
Estimation inputs (DAU, sizes)	Assumptions in Alex Xu's book style; results computed, not sourced

Course

—Where next

This is the last page course

Go back to page 15 and time yourself on one design a day, out loud. When a deep dive feels thin, revise its building block from the course home.