Eight worked high-level designs, the ones asked most often: URL shortener, rate limiter, key-value store, unique ID generator, notification system, news feed, chat and search autocomplete. Every case follows the same five steps, so you learn the rhythm as well as the answers. All numbers are order-of-magnitude assumptions chosen to make the arithmetic easy; in an interview, state yours and move on.
How to use these
Part 1 of 9 · the template and the map
Do not memorise the designs. Memorise the five steps and the two or three deep dives that make each problem different, then rebuild the rest from Building Blocks.
Each case below has these five chapters, in this order. Timings assume a 45 minute interview.
Step
What you produce
Time
Common mistake
1. Requirements and scale
3 to 5 functional, non-functional with numbers, out of scope, a small estimate
5 to 7 min
Estimating everything; only compute numbers that change a decision
2. API and data model
3 to 5 endpoints, main entities, the store and why
5 min
Picking a database before knowing the access pattern
3. High-level design
One diagram, read path and write path walked end to end
10 min
Drawing 25 boxes and explaining none
4. Deep dives
2 to 4 hard parts, each with alternatives
15 min
Waiting to be asked; propose the deep dives yourself
5. Trade-offs and follow-ups
Decisions with reasons, failure modes, what changes at 10x
5 min
Presenting the design as having no costs
Interview tip: the estimate exists to answer three questions: does it fit on one machine, is it read-heavy or write-heavy, and what is the hot path. Say the answer out loud after the arithmetic.
Trie and prefix index, batch and stream processing, multi-layer caching, sharding
URL shortener
Part 2 of 9 · read-heavy key lookup
Map a long URL to a short key and redirect on lookup. It is asked because it is small enough to finish, yet forces a real decision on key generation, caching and the redirect status code.
Functional: create a short URL for a long one; redirect short to long; optional custom alias; optional expiry; click counts per link.
Non-functional: redirect adds under about 50 ms at p99; redirects available 99.99%; a created link is never lost; keys are not trivially enumerable.
Out of scope: accounts and billing, malware and spam scanning, a dashboard UI.
Quantity
Arithmetic
Result (approx.)
New URLs
Assumption
100 M per month
Write QPS
100 M / (30 x 86,400 s = 2.6 M s)
40 per second average, 200 peak (5x)
Read QPS
100 reads per write: 10 B per month / 2.6 M s
4,000 per second average, 12,000 peak (3x)
Daily users
10 B / 30 = 333 M redirects per day, about 10 per user
30 M DAU
Storage
100 M x 12 x 5 years = 6 B rows x 500 bytes
3 TB
Bandwidth
4,000 per second x 500 bytes
2 MB per second out
Key space
62^7
3.5 x 10^12 keys, about 600x the 6 B needed
Cache
20 M hot links x 500 bytes
10 GB, one Redis node plus replica
What the numbers say: 100:1 read-heavy, 3 TB total, a 10 GB hot set. The whole problem is a cached key lookup; writes are almost irrelevant to capacity.
Two tables. The hot path reads one row by primary key; click counts live elsewhere and are filled asynchronously.
Store: a key-value or wide-column store (DynamoDB, Cassandra) or sharded MySQL. Every query is a single-key get or a conditional put, with no joins, so pick for operational simplicity and replication.
Analytics: a columnar or time-series store fed from the event log, never the URL table.
Collisions need a check and retry with a salt; same-URL dedup is rarely wanted per user
Base62 of a counter
Each server leases a range of ids, encodes the next one
Unique by construction, no read before write
Sequential keys are enumerable; needs a range allocator
Pre-generated keys
A key service creates random unused keys offline and hands out batches
Unguessable, no collision at write time
One more stateful service; unused batches are lost on a crash (acceptable)
Counter ranges remove the per-write coordination. A keyed bijective permutation of the id before encoding hides the sequence.
Collision odds for random keys: with 6 B keys used out of 3.5 x 10^12, a random key is taken about 0.17% of the time (6 x 10^9 / 3.5 x 10^12). Always insert with "put if absent" and retry.
Pick: counter ranges plus a permutation, or the key service. Both avoid a read before every write.
Read path: cache and 301 versus 302
Cache-aside on the redirect. Cache unknown keys too (short TTL) so scans of random keys do not hammer the store.
Status
Browser behaviour
Use when
301 Moved Permanently
Caches the mapping; later clicks may never reach you
Lowest load matters more than analytics, and targets never change
302 Found (or 307)
Asks you every time
You need click analytics, expiry, deletion or editable targets. The usual choice.
Custom aliases and expiry
Aliases share the key namespace: conditional insert, return 409 if taken. Reserve words (api, admin), restrict the alphabet, and keep generated keys at a fixed length that aliases may not use, so the two can never collide.
Expiry: check expires_at on read and answer 410; delete lazily with the store's TTL feature or a background sweep. Set the cache TTL to no more than the time left.
Do not recycle expired keys quickly: old links in the wild would point to a stranger's target.
Analytics as an async pipeline
The redirect never writes a counter synchronously. It appends an event (key, time, country, referrer) to a log such as Kafka and returns.
A stream job aggregates per key and minute or day with idempotent upserts, because delivery is at least once.
Trade-off: counts lag by seconds to minutes, and under overload you shed events, not redirects.
Scaling the store
Shard by hash of short_key; 3 TB over 5 years is a handful of shards, each replicated 3 times.
Most reads never reach it: with a 90% cache hit rate the store sees about 1,200 of the 12,000 peak reads per second.
Multi-region: replicate the store asynchronously and serve redirects from the nearest region; route creates to a home region or use region-prefixed key ranges to avoid conflicts.
Redirect latency and availability do not depend on analytics
Failure mode: cache down. Redirects fall through to the store at 10x the usual load; keep replicas sized for it or shed with a small local in-process cache.
Failure mode: one viral link. It is a hot key, but a read-only one: a local cache in each redirect instance absorbs it.
Failure mode: range allocator down. Servers keep working from their leased range; lease early.
Follow-up
One-line answer
Same long URL submitted twice?
Return a new key by default; dedup per owner needs an index on (owner, hash of URL).
How do you stop abuse?
Rate limit creates per account and IP, check targets against a blocklist asynchronously, allow takedown by key.
How short can keys be?
62^6 is 57 B, enough for the 6 B estimate; 7 leaves headroom and keeps random-key collisions rare.
Can users edit the target?
Yes with 302: update the row and delete the cache entry.
Senior signal: you say early that this is a cached point lookup with a 10 GB hot set, spend the time on key generation and the 301 or 302 choice, and keep analytics off the redirect path without being asked.
Rate limiter
Part 3 of 9 · a check on every request
Decide, for each incoming request, whether a client is within its allowance. It is asked because the algorithm is easy and the distributed version is not: atomic counting, where the limiter sits, and what happens when its store fails.
Functional: limit requests per key (user, API key, IP) and per rule (endpoint, plan); several rules per request; reject with 429 and tell the client when to retry; change rules without a deploy.
Non-functional: adds about 1 ms at p99; limiter failure must not take the API down; accuracy within a few percent is acceptable; works across many gateway instances.
Out of scope: network-level DDoS protection, monthly billing quotas, bot detection.
Quantity
Arithmetic
Result (approx.)
Active clients
Assumption
50 M per day
Requests
50 M x 170 per day = 8.5 B / 86,400 s
100,000 per second average, 300,000 peak (3x)
Limiter checks
2 rules per request x 300,000, sent as one script call
300,000 Redis calls per second at peak
Storage
50 M keys x 2 rules x 100 bytes
10 GB of RAM
Bandwidth
300,000 per second x 200 bytes per round trip
60 MB per second inside the data centre
What the numbers say: memory is trivial; throughput is not. One Redis shard handles on the order of 100,000 simple operations per second, so plan several shards keyed by client, or avoid the network hop for most requests.
The limiter runs inside the gateway. Rules arrive out of band; only the counters need a shared store.
Request path: the middleware matches the request to its rules, builds the keys, and runs one atomic script in Redis that updates the counters and returns the decision.
Allowed: forward to the backend and add the rate limit headers. Rejected: answer 429 with Retry-After; the backend never sees the request.
Rule path: operators change rules in the rules service; limiters receive them by push or poll and keep them in memory, so the hot path reads no database.
Sharding: Redis Cluster shards by key; put the client id in a hash tag so all counters for one client land on one shard and one script can touch them.
The mechanics are in Building Blocks; this is the comparison to have ready.
Algorithm
State per key
Bursts
Weakness
Use when
Token bucket
Tokens, last refill time
Allowed up to bucket size
Two parameters to tune
Default for public APIs
Leaky bucket
Queue or level, last leak time
Smoothed away
Bursts wait or drop
Protecting a backend that needs a steady rate
Fixed window
One counter
Up to 2x the limit across a boundary
Boundary spike
Coarse quotas (per day)
Sliding log
A timestamp per request
Exact
Memory grows with the limit
Low limits that must be exact
Sliding window counter
Two counters
Approximately exact
Assumes even spread in the previous window
High limits, cheap and accurate enough
Distributed counting with Redis
Read, decide, write from two gateways is a lost update. The check and the update must be one atomic step on the server.
INCR then EXPIRE from the client is a second race: if the client dies between the two commands the key never expires and the client stays blocked for good. A Lua script (or SET key 0 EX 60 NX followed by INCR) closes it, because Redis runs a script as one unit.
Token bucket in Redis is the same idea: one script reads {tokens, last_refill}, refills by elapsed time, subtracts the cost and writes back.
Use Redis server time inside the script, or pass a time from one source; gateway clocks disagree.
Local versus global limits
Hybrid: each instance leases a batch of tokens from the global counter and spends it locally, so most requests need no Redis call.
Mode
Gain
Cost
Local only (limit / instances each)
No network hop, no dependency
Wrong when load is uneven or instance count changes
Global (Redis on every request)
Accurate
A hop per request, Redis on the critical path
Hybrid (leased batches)
Redis load drops by the batch size
Overshoot up to batch size x instances; more code
Placement
Where
Gain
Cost
Use for
API gateway or edge
One place, rejects before any backend work
Knows little about business cost of a call
Per-client and per-IP limits on public APIs
Sidecar proxy
Language independent, per-service rules
Needs a mesh; an extra local hop
Service-to-service limits
Library in the service
Can limit by business meaning (per tenant, per expensive query)
One implementation per language, upgrades are slow
Fine-grained internal limits
When the limiter store is down
Policy
Behaviour
Choose for
Fail open
Allow traffic, alert, fall back to a coarse local limit
Most APIs: a limiter outage should not become a product outage
Fail closed
Reject until the store is back
Limits that are a security or cost control: login attempts, OTP sends, paid third-party calls
Give the Redis call a tight timeout (a few milliseconds) and a circuit breaker; a slow limiter is worse than a missing one.
Multi-region
Per-region limits: split the quota by region. Simple, no cross-region latency; a client that roams can get up to the sum.
Shared global limit: each region counts locally and replicates counts asynchronously. Approximate by the replication lag, which is usually acceptable.
Never make a synchronous cross-region call on the request path: it costs tens of milliseconds and couples regions.
Failure mode: hot key. One huge tenant puts all its counting on one shard; lease batches locally or split the tenant's key into sub-keys.
Failure mode: Redis failover loses recent counters (asynchronous replication). Clients get a brief extra allowance; accept it.
Failure mode: rejected clients retry at once and add load. Send Retry-After and make 429 responses cheap.
Follow-up
One-line answer
Different cost per endpoint?
Pass a cost to the bucket: an expensive call takes several tokens.
Limit by IP behind NAT?
IP is a weak identity; prefer API key or user, keep IP limits loose.
Hard versus soft limits?
Soft limits log or throttle (queue, slow down); hard limits reject.
How are rules updated safely?
Versioned config, staged rollout, and a shadow mode that counts without rejecting.
Senior signal: you name the race before the interviewer does, state the fail-open or fail-closed choice per rule and not globally, and offer shadow mode for rolling out a new limit.
Key-value store
Part 4 of 9 · Dynamo-style, always writable
Design a distributed store for get and put that survives node and network failures. It is asked because it tests the core of distributed data: partitioning, replication, consistency and repair. The design below follows the published Dynamo paper, which Cassandra and Riak also build on.
Functional:put(key, value), get(key), delete(key); opaque values up to about 1 MB; consistency tunable per request.
Non-functional: writes accepted even during node failure or partition (AP); p99 under about 10 ms; add nodes with no downtime; no single point of failure; each key on 3 replicas.
Out of scope: range scans, secondary indexes, multi-key transactions.
Quantity
Arithmetic
Result (approx.)
Callers
Infrastructure: clients are services, not end users
DAU not applicable
QPS
Assumption: 200,000 reads + 50,000 writes per second
250,000 per second average, 500,000 peak (2x)
Logical data
10 B keys x 1 KB
10 TB
Physical data
10 TB x 3 replicas
30 TB
Nodes
30 TB / 2 TB per node = 15, kept about 60% full
About 25 nodes
Bandwidth
Client: 250,000 x 1 KB; replication: 50,000 x 1 KB x 3
250 MB per second client, 150 MB per second between nodes
What the numbers say: a few dozen nodes, each serving about 20,000 operations per second at peak. Small enough that every node can know the whole ring, which is what makes one-hop routing and gossip practical.
Decide which copy is newer, or detect that two are concurrent
Tombstone flag and time
A delete is a write, so it replicates and is not undone by a stale replica; purged after a grace period
Each node persists its share in a local LSM-tree engine (see the deep dive). There is no schema and no central metadata store; ring membership is the only shared state.
Any node can coordinate. It forwards to the N replicas for the key and answers after W (or R) of them reply. Dashed edges are the hinted handoff path, used when replica C is unreachable.
Routing: the client (or a load balancer) reaches any node; that node hashes the key, finds the N replicas on the ring and acts as coordinator.
Write: coordinator sends the put to all N, returns success after W acks; the rest finish in the background.
Read: coordinator asks all N, returns after R replies, reconciles versions and repairs stale replicas.
Failure: if a replica is down, another node takes the write with a hint and hands it back later.
Symmetry: every node has the same role. No leader, so no failover; the price is conflict handling.
Consistent hashing with virtual nodes: each physical node owns many small ranges of the hash ring, so adding or losing a node moves about 1/n of the keys and spreads the load over many peers.
Preference list: the first N distinct physical nodes clockwise from the key, ideally in different racks or zones.
The request goes to all N replicas; W only sets how many acks the coordinator waits for. Latency is that of the W-th fastest replica.
N, W, R
Property
Use when
3, 2, 2
R + W > N: every read quorum overlaps the last write quorum; tolerates one node down for both
Default
3, 1, 1
Fastest; reads can be stale
Caches, metrics
3, 3, 1
Fast consistent reads; a write fails if any replica is down
Read-heavy, rarely written
3, 1, 3
Fast writes; a read fails if any replica is down
Write-heavy ingestion
Trade-off: R + W > N is not linearizability. Sloppy quorums, concurrent writers and partial write failures can still return stale or conflicting versions.
Versioning and conflict resolution
Vector clocks, as in the Dynamo paper. D3 and D4 are concurrent (neither clock dominates), so a read returns both and the next write, via A, merges them.
Strategy
Gain
Cost
Vector clocks, siblings returned to the client
No silent data loss
Client must merge; clocks grow and need pruning
Last write wins by timestamp
Simple, no siblings (the Cassandra default)
Clock skew silently drops a write
CRDT values (counters, sets)
Merge is automatic and correct
Only for data types with a defined merge
Failure handling and repair
Problem
Mechanism
How it works
Replica briefly down
Sloppy quorum and hinted handoff
The next healthy node accepts the write with a hint naming the owner and replays it when the owner returns
Replica missed a write
Read repair
On a read the coordinator sees an old version and pushes the newest to that replica
Cold data diverged, or a node was replaced
Anti-entropy with Merkle trees
Replicas compare hash trees per key range and transfer only the ranges that differ
Who is in the cluster, who is dead
Gossip
Each node exchanges membership and heartbeat state with a few random peers every second; state spreads in O(log n) rounds
Merkle comparison between two replicas: descend only where hashes differ. Two replicas in sync exchange one hash.
Storage engine
LSM tree: a write is one sequential append plus a memory update. Reads check the memtable, then only the SSTables whose Bloom filter says "maybe".
LSM tree (RocksDB, Cassandra): sequential writes, good compression; pays with compaction I/O and reads that may touch several files. The usual choice here.
B-tree (InnoDB): predictable reads, in-place updates; random write I/O. Choose for read-heavy workloads with many range scans.
Even load, cheap rebalancing; gives up range scans
Conflicts
Vector clocks
Last write wins
No silent loss; more work for clients
Engine
LSM tree
B-tree
Write throughput
Failure mode: a deleted key comes back. A replica that was down longer than the tombstone grace period still has the old value and repair copies it back. Repair every node within the grace period.
Failure mode: hints pile up during a long outage. Cap hint storage and rely on Merkle repair afterwards.
Failure mode: hot key. Hashing spreads keys, not load per key; cache in front or split the key in the application.
Follow-up
One-line answer
How does a new node join?
It announces itself by gossip, takes over vnode ranges, and streams those ranges from the current owners before serving.
How do you detect a dead node?
Missed gossip heartbeats, judged by a suspicion level and not one fixed timeout (the phi accrual detector in Cassandra).
Multi-datacentre?
Place replicas per datacentre and use a local quorum for latency; replicate across asynchronously.
Read-your-writes?
R + W > N with strict quorums gets close; for a hard guarantee use a consensus-based store.
Senior signal: you separate the four repair mechanisms by the failure each one covers, say plainly that quorum overlap is not linearizability, and can state when you would not build this and would use a consensus-based store instead.
Unique ID generator
Part 5 of 9 · coordination-free uniqueness
Produce unique, roughly time-ordered 64-bit ids at high rate from many machines. It is asked because the answer fits on a whiteboard and still probes clocks, coordination and failure handling.
Functional: ids are unique across all machines and datacentres; fit in a signed 64-bit integer; sort roughly by creation time; can be generated in batches.
Non-functional: 100,000 ids per second at peak; under 1 ms per id; no network call per id; keeps working when the coordination service is down.
Out of scope: gapless sequences (invoice numbers), unguessable ids (use random tokens for secrets).
Quantity
Arithmetic
Result (approx.)
Callers
Infrastructure: called by other services
DAU not applicable
QPS
Assumption
10,000 per second average, 100,000 peak
Ids per day
10,000 x 86,400
864 M
Storage
The generator keeps no ids
None (8 bytes per id wherever it is used)
Bandwidth
100,000 x 8 bytes
0.8 MB per second, negligible
Capacity per worker
2^12 = 4,096 per ms x 1,000
4 M per second
Lifetime
2^41 ms / (3.15 x 10^10 ms per year)
69 years from the chosen epoch
What the numbers say: one worker covers the peak 40 times over. Workers are added for availability and locality, not throughput.
Too wide for the requirement; random inserts fragment B-tree indexes
UUID v7 (time + random)
128 bits
Yes
None
Still 128 bits; a good default when 64 bits is not required
DB auto-increment, stepped (server k of n issues k, k+n, ...)
64 bits
Per server only
A database write per id
Hard to add servers; the database is the bottleneck
Ticket server with ranges
64 bits
Roughly
One call per range of, say, 1,000 ids
Central service to keep available; ids reveal volume
Snowflake-style
64 bits
By time, k-sorted
Only at startup
Depends on clocks; worker ids must be managed
Clock skew and going backwards
The generator never issues an id with a timestamp below the last one it used. A small backwards step is waited out; a large one takes the worker out of service.
Why it goes backwards: NTP step corrections, VM migration, leap second handling. Configure NTP to slew, not step.
Restart hazard: a restarted worker forgets its last timestamp. Persist it periodically (and start from the persisted value plus a margin), or take a fresh worker id on every start.
Alternative: treat the timestamp field as a logical clock that only moves forward and may run slightly ahead of wall time under bursts.
Worker id assignment
Method
Gain
Cost
Static configuration
No dependency
Manual, breaks with autoscaling; a copy-paste error gives duplicate ids
Lease from etcd or ZooKeeper
Safe with autoscaling; ids are reused after a lease expires
Needed at startup; must stop generating if the lease is lost
Derive from IP or host name
No coordination
Collisions unless the address space maps cleanly into 10 bits
Multiple datacentres
Reserve the top bits of the worker id for the datacentre; each datacentre then assigns machine bits on its own, with no cross-site calls.
Uniqueness holds globally. Ordering across sites is only as good as clock sync (typically milliseconds with NTP), so never use id order as proof of causality.
Tune to fleet size; 4,096 per ms per worker is rarely needed
Worker ids
Leased
Static
Safe under autoscaling
Clock moving back
Wait or refuse
Keep generating
Duplicates are worse than a brief outage of one worker
Failure mode: two workers with the same worker id produce duplicates silently. Fence with leases, and keep a unique constraint where the ids are stored.
Failure mode: coordination service down. Running workers continue; only new workers cannot start.
Failure mode: ids leak information (creation time, rough volume). Do not expose them where that matters.
Follow-up
One-line answer
Need strictly increasing ids globally?
That needs a single sequencer or consensus; expect a throughput and availability cost.
JavaScript clients?
Numbers above 2^53 lose precision; send ids as strings in JSON.
What after 69 years?
Pick a recent custom epoch; widening the timestamp later means a new id format.
Why do sorted ids help the database?
Inserts append to the right edge of the index, and the id doubles as a creation-time sort key.
Senior signal: you raise clock regression and duplicate worker ids yourself, and you size the bit fields from the numbers instead of reciting 41 / 10 / 12.
Notification system
Part 6 of 9 · reliable delivery through third parties
Send push, SMS and email on behalf of many internal services. It is asked because the delivery itself is outsourced, so the design is all about queues, retries, duplicates, limits and provider failure.
Functional: send by push (APNs for iOS, FCM for Android), SMS and email; templates with parameters; per-user channel preferences and opt-out; delivery status per notification; scheduled and bulk sends.
Non-functional: transactional messages (OTP, payment alerts) leave within about 2 seconds; promotional within minutes; at-least-once with no user-visible duplicates; a slow provider must not block other channels.
Out of scope: building an SMTP or SMS gateway, an in-app inbox, the campaign authoring tool.
Quantity
Arithmetic
Result (approx.)
Users
Assumption
100 M DAU
Notifications
100 M x 10 per day
1 B per day: 800 M push, 150 M email, 50 M SMS
QPS
1 B / 86,400 s
11,600 per second average, 58,000 peak (5x, campaigns)
Storage
1 B x 500 bytes of delivery log per day x 30 days kept
500 GB per day, 15 TB retained
Bandwidth
11,600 x 1 KB payload
12 MB per second average, 58 MB per second peak
What the numbers say: the 5x bursts come from campaigns, and providers throttle you. Queues absorb the burst; the design question is how to stop a campaign from delaying an OTP.
One queue and one worker pool per channel: a slow SMS provider backs up only the SMS queue.
Accept: the API authenticates the caller, deduplicates on the idempotency key, loads preferences, drops opted-out channels, and enqueues one message per remaining channel. It answers 202 once the messages are durably queued.
Send: a channel worker renders the template, applies per-user and per-provider rate limits, calls the provider and records the result in the delivery log.
Track: providers report delivered, bounced or failed through webhooks; a small consumer updates the delivery row.
Bulk: a campaign is expanded into per-user messages by a separate job that feeds the promotional queues at a controlled rate.
Idempotency key: SET key NX with a 24 hour TTL, or a unique index; return the first notification id
Queue redelivers after a worker crash (at-least-once)
Worker checks and conditionally updates the delivery row for (notification id, channel) before sending
Worker sent, then crashed before recording it
Cannot be fully closed; pass a stable message id or collapse key to the provider where it supports one (apns-collapse-id, FCM collapse_key)
Two services send the same event
Derive the idempotency key from the business event, not from the request
Trade-off: exactly-once delivery to a phone does not exist. Aim for at-least-once with deduplication, and decide per message type whether a rare duplicate or a rare loss is worse.
Retries, backoff and dead-letter queues
Only transient errors are retried. Permanent errors fail at once and clean up (an invalid push token deletes the device row).
Backoff: exponential with jitter, for example 1 s, 2 s, 4 s, 8 s, 16 s, then dead-letter. Honour the provider's Retry-After.
TTL per message type: an OTP that is 2 minutes late is noise; drop it instead of retrying.
Dead-letter queue: holds what could not be sent, with the reason, for alerting and replay after a fix. Alert on its growth rate.
Implement the delay with a delayed queue or a retry topic per backoff tier, not by sleeping in the worker.
Priority and per-user rate limits
Separate queues and reserved workers by priority, so a 50 M user campaign cannot sit in front of an OTP.
Per user: a cap on promotional messages (say 3 per day per channel) and quiet hours in the user's time zone; transactional messages bypass both.
Per provider: a token bucket at the provider's agreed rate, with transactional traffic taking tokens first.
Provider failover and delivery tracking
A circuit breaker per provider moves traffic to the secondary when error rate or latency crosses a threshold, and probes the primary before moving back.
SMS and email have interchangeable vendors, so keep two integrated and send a little traffic to the secondary all the time. Push has no substitute: APNs and FCM are the only route to their devices, so queue and retry.
Failover risk: a message accepted by A just before the breaker opened may be re-sent through B. This is the duplicate case above.
Tracking: "sent" means the provider accepted it; "delivered" needs a receipt, which push gives only partially. Opens and clicks come from the client or tracked links.
Senior signal: you separate transactional from promotional traffic in the first diagram, classify errors as transient or permanent before talking about retries, and admit where a duplicate can still slip through.
News feed and timeline
Part 7 of 9 · fan-out and precomputed reads
Show each user recent posts from the accounts they follow. It is asked because of one decision with no free answer: do the work when a post is written, or when a feed is read, and what to do about accounts with millions of followers.
Functional: publish a post (text plus media); follow and unfollow; load the home feed, newest or ranked, with paging; like a post and see like counts.
Non-functional: feed load under 200 ms at p99; a new post appears for followers within a few seconds (eventual consistency is fine); feed reads stay available when the write side is degraded.
Out of scope: ads, search, direct messages, recommending accounts the user does not follow.
Quantity
Arithmetic
Result (approx.)
Users
Assumption
200 M DAU
Feed reads
200 M x 5 per day = 1 B / 86,400 s
11,600 per second average, 35,000 peak (3x)
Posts
200 M x 0.5 per day = 100 M / 86,400 s
1,160 per second
Fan-out writes
100 M posts x 200 followers average = 20 B per day
230,000 timeline inserts per second
Post storage
100 M x 1 KB per day x 365
100 GB per day, 36 TB per year
Media storage
20% of posts x 500 KB = 20 M x 0.5 MB
10 TB per day, in object storage
Timeline cache
200 M users x 500 entries x 16 bytes
1.6 TB of RAM
Bandwidth
11,600 x 20 posts x 1 KB
230 MB per second of JSON; media goes through the CDN
What the numbers say: reads outnumber posts 10 to 1, but fan-out multiplies each post by 200, so the write side does 20 times more work than the read side. That ratio is the whole problem.
The write path (top) precomputes timelines asynchronously; the read path (Feed service) is two lookups: ids from the cache, then post bodies.
Post: the post service stores the post and emits an event; it answers the author without waiting for fan-out.
Fan-out: workers read the author's followers in pages and push the post id into each follower's timeline.
Read: the feed service takes a page of ids from the timeline cache, fetches the posts and authors (a multi-get, mostly from cache), drops deleted or blocked items, and returns them with a cursor.
Media: clients upload directly to the object store with a presigned URL and download through the CDN; the API tier never carries the bytes.
An account has millions of followers; work is wasted on inactive users
Fan-out on read (pull)
One insert
Query every followee and merge
A user follows thousands; read latency grows
Hybrid
Push for normal accounts, nothing for celebrities
Cache read plus a merge of a few celebrity lists
More code paths; needs a threshold (say 100,000 followers)
Fan-out on write. The author gets an answer before any timeline is touched; followers see the post when the worker reaches them.Hybrid read: the precomputed timeline is merged with the recent posts of the few celebrities this user follows.
The arithmetic that justifies hybrid: one post from an account with 100 M followers is 100 M cache writes. At 100,000 writes per second that is about 17 minutes of fan-out for a single post, delaying everything behind it.
Feed storage, ranking and cursors
Storage: one Redis sorted set per user, member and score both the time-sortable post id; trimmed to the newest 500 or so. Store ids only, never post bodies.
Inactive users: skip them in fan-out and rebuild the timeline by pull on their next visit. This removes a large share of the 230,000 inserts per second.
Ranking: a common design takes a few hundred candidates from the timeline and scores them with a model using features such as recency, affinity to the author and predicted engagement. Chronological order is the fallback when the ranker is slow or down.
Cursor, not offset: the cursor is the last post id seen (opaque to the client); the next page is "ids below the cursor". Offsets skip or repeat items because new posts shift every position.
Media through a CDN
Upload: presigned URL straight to the object store; an asynchronous job makes thumbnails and renditions; the post references media by id.
Download: immutable, versioned URLs with long cache lifetimes, so the CDN serves nearly all of the 10 TB per day.
Like counters
Truth is the POST_LIKE row (post, user): it makes a like idempotent and answers "did I like this".
The count is a denormalised counter updated asynchronously from like events, cached, and allowed to lag by seconds.
Hot posts: buffer increments in memory and flush in batches, so one viral post does not cause thousands of writes per second to one row.
Consistency expectations
Who
Expectation
How
Author
Sees own post at once
Insert into the author's own timeline synchronously, or merge it on the client
Followers
See it within seconds
Asynchronous fan-out; monitor fan-out lag
Everyone
Deleted posts disappear
Filter at hydrate time; lazily remove ids from timelines
Fast reads for most users without celebrity write storms
Timeline content
Post ids only
Full posts
Small, and edits or deletes need no rewrite
Paging
Cursor on post id
Offset
Stable under inserts
Counters
Asynchronous, approximate
Transactional count
Write throughput on hot posts
Failure mode: timeline cache node lost. Timelines are derived data: rebuild by pull on demand, and replicate the cache to keep rebuild load small.
Failure mode: fan-out backlog. Feeds go stale but stay readable; scale workers, and prioritise active followers.
Failure mode: hydrate fan-in. One feed page needs 20 posts and authors; use multi-gets and a per-request deadline, and return a partial page over an error.
Follow-up
One-line answer
A user follows a new account?
Merge that account's recent posts into the timeline asynchronously.
Where is the celebrity threshold?
Where the fan-out time for one post exceeds the freshness target; tune from fan-out lag.
How do you shard the timeline cache?
By user id; every operation touches one user's key.
New posts while the user is scrolling?
Keep the cursor stable and show a "new posts" marker that reloads from the top.
Senior signal: you compute the fan-out multiplier before choosing a strategy, treat the timeline as a rebuildable cache and not a source of truth, and skip inactive users without being asked.
Chat and messaging
Part 8 of 9 · stateful connections, ordered delivery
Deliver messages between users in real time, in order, without loss, whether or not the recipient is online. It is asked because it is the standard stateful system: long-lived connections, routing to the right server, ordering and offline sync.
Functional: 1:1 and group chat (up to about 1,000 members); sent, delivered and read receipts; presence and last seen; delivery to offline users with a push notification; history synced across a user's devices.
Non-functional: under 500 ms end to end at p99 when both sides are online; no acknowledged message is lost; messages in one conversation appear in the same order for everyone; 100 M concurrent connections.
Out of scope: voice and video calls, the media pipeline (same as the feed: object store plus CDN), spam detection.
Quantity
Arithmetic
Result (approx.)
Users
Assumption
500 M DAU
Messages
500 M x 40 per day = 20 B / 86,400 s
230,000 per second average, 700,000 peak (3x)
Connections
20% of DAU online at peak
100 M concurrent
Gateway servers
100 M / 100,000 connections per server
1,000 servers
Storage
20 B x 200 bytes per day x 365
4 TB per day, 1.5 PB per year before replication
Bandwidth
230,000 x 200 bytes
46 MB per second average, 140 MB per second peak (text only)
What the numbers say: write-heavy, with reads mostly of recent messages. Connection count, not QPS, sizes the gateway tier; message volume sizes the store.
Messages are partitioned by conversation and clustered by seq, so "the next 50 after seq 1200" is one sequential range read. Receipts are two integers per member, not a row per message.
Store: a wide-column store (Cassandra, ScyllaDB, HBase): append-heavy writes, range reads within a partition, linear scale-out. Bucket very large conversations by month so no partition grows without bound.
Also needed: the same MEMBER data keyed by user (the inbox), so "my conversations, most recent first" is one query.
Gateways only hold connections. The chat service persists first, then looks up which gateway holds the recipient and delivers through it.
Connect: the client opens a WebSocket to a gateway through a load balancer; the gateway authenticates it and writes user, device and gateway into the session registry.
Send: gateway forwards to the chat service, which assigns the next seq for the conversation, persists the message, and acks the sender.
Deliver: for each recipient device the chat service finds the gateway in the registry and pushes the message down that connection.
Offline: no session means a push notification; the message waits in the store until the device reconnects and pulls everything after its last seq.
Presence: gateways report heartbeats to a separate service, so presence load cannot slow messaging.
A request per message, higher latency; keep as fallback
Server-sent events
Simple server push
One direction only; sends need separate requests
Registry: Redis, session:{user_id} to a map of device id to gateway id, with a TTL refreshed by heartbeats (about every 30 s).
Routing: the chat service calls the gateway directly (RPC) or publishes to a per-gateway channel; never broadcast to all gateways.
Gateway dies: its connections drop, clients reconnect with backoff and jitter to another gateway, registry entries are overwritten or expire. In-flight messages are safe because they were persisted before delivery.
Deploys: drain gateways gradually; 100,000 clients reconnecting at once is a self-made thundering herd.
1:1 message flow, receipts and ordering
Persist before ack, ack before deliver. The three ticks are three events: stored by the server, received by the device, seen by the user.
Ordering: the server assigns a per-conversation, strictly increasing seq. Client timestamps are untrusted and are used only for display.
Assigning seq: route all writes for a conversation to one owner (partition by conversation id) and increment there, or use an atomic counter or conditional write per conversation. A global sequence is unnecessary and would be a bottleneck.
No loss, no duplicates: the client retries a send with the same client_msg_id until acked; the server deduplicates on it. A device that sees seq 44 after 42 knows it must fetch 43.
Group message flow
A group message is stored once in the conversation partition. Only the delivery fans out, and only to members who are online.
Small groups: fan out on send as shown.
Very large groups or channels: stop pushing every message; send a lightweight "new activity" signal and let clients pull by after_seq. Read receipts become counts or are switched off.
Batch the registry lookups and group deliveries per gateway, so a 1,000 member group costs tens of calls, not a thousand.
Offline delivery, multi-device sync and presence
Topic
Design
Watch for
Offline delivery
Message stays in the store; a push notification wakes the app; on reconnect the device pulls each changed conversation after its last seq
Push is best effort and may be dropped; correctness comes from the pull
Multi-device
Each device is its own session and keeps its own sync position; the sender's other devices receive the message too
Read state is per user, delivery state per device
Presence
Heartbeat sets a key with a short TTL; no heartbeat means offline; last seen is written on disconnect
Flapping on bad networks: delay the offline transition by a few seconds
Presence fan-out
Push changes only to users currently viewing that contact or chat; otherwise fetch on open
Pushing every change to every contact is quadratic
End-to-end encryption
With end-to-end encryption (the Signal protocol is the widely documented design), clients publish public keys through the server and encrypt each message for every recipient device, so the server stores and routes only ciphertext it cannot read. The architecture above is unchanged, but server-side search and content moderation are no longer possible, and adding a device, restoring history and group membership changes all become key management problems.
Storage and write cost; the per-recipient copy is simpler only for tiny groups
Failure mode: stale registry entry points to a dead gateway. Delivery fails fast, the entry is removed, and the offline path (push plus pull) takes over.
Failure mode: reconnect storm after a network blip. Jittered backoff on clients, admission control on gateways.
Failure mode: hot conversation partition (a huge active group). Time-bucket the partition and switch the group to pull.
Follow-up
One-line answer
Typing indicators?
Ephemeral events through the same connection, never persisted, dropped under load.
Message search?
A separate index fed asynchronously; on the device only if end-to-end encrypted.
Multi-region?
Users connect to the nearest region; a conversation has a home region for seq assignment, or accept per-region order with a merge rule.
Why not Kafka as the message store?
It suits transport between services, not per-conversation random reads over years of history.
Senior signal: you state the invariant "persist, then ack, then deliver", make the pull by seq the source of correctness with push as an optimisation, and separate the stateful gateway tier from the stateless logic.
Search autocomplete
Part 9 of 9 · precomputed answers, tight latency
Return the top few completions for each prefix a user types. It is asked because the read path must be nearly free, which pushes all the work into an offline index build and layers of caching.
Functional: up to 8 suggestions for a prefix; ranked by popularity; trending queries appear within minutes; unsafe or blocked suggestions never shown.
Non-functional: under 100 ms end to end at p99, under 10 ms inside the service; highly available (degrade to no suggestions, never block search); results may be minutes stale.
Out of scope: the search results themselves, spelling correction, deep personalisation.
Quantity
Arithmetic
Result (approx.)
Users
Assumption
100 M DAU
Searches
100 M x 10 per day
1 B per day
Suggest requests
1 B x 6 per search (after debounce) = 6 B / 86,400 s
70,000 per second average, 210,000 peak (3x)
Index size
50 M prefixes x (20 byte key + 10 x 30 bytes)
16 GB, fits in RAM on one machine
Query log
1 B x 100 bytes
100 GB per day
Bandwidth
70,000 x 500 bytes
35 MB per second average, 105 MB per second peak
What the numbers say: the index is small and the request rate is large. You replicate for throughput long before you need to shard for size, and every request you answer from a cache is one the service never sees.
Two loops: a fast serving path (top) that only reads memory, and a slow build path (bottom) that turns query logs into a new index version.
Read: the browser asks the CDN; on a miss the suggest service normalises the prefix, looks it up in memory, merges any trending entries, filters, and returns with a cache lifetime.
Log: completed searches (not keystrokes) go to the query log asynchronously.
Batch build: every hour or day, aggregate counts with time decay, drop rare and blocked queries, compute the top k for every prefix, publish a snapshot.
Swap: servers load the new snapshot beside the old one and switch atomically; a bad build is rolled back by pointing at the previous version.
Streaming: a stream job counts queries over a sliding window and feeds a small trending delta, so breaking topics do not wait for the next batch.
A trie with the top-k list stored at every node. A lookup walks one node per typed character and reads the list; it never explores the subtree.
Structure
Lookup
Memory
Updates
Use when
Plain trie, counts at leaves
Walk the prefix, then search the subtree: slow for short prefixes
Smallest
Cheap
Never for serving
Trie with top-k at each node
O(prefix length)
Medium; prefixes share structure
A count change touches every ancestor
In-process index on one machine
Hash map: prefix to top-k
O(1)
Largest; each prefix stored in full
Rebuild offline
Simple sharding and KV or CDN friendly; the usual choice
Both serving structures are the same idea: the answer for every prefix is computed before anyone asks. Limit prefix length (about 20) and keep only prefixes of queries above a count threshold.
Building the index: batch plus streaming
Batch build
Streaming update
Input
Days or weeks of query logs
The live event stream, sliding window of minutes to hours
Output
A complete, versioned snapshot
A small delta of trending queries
Freshness
Hours
Minutes
Strength
Simple, reproducible, easy to roll back
Catches breaking topics
Weakness
Stale between builds
Approximate counts, easier to game; needs stricter filtering
Score with a decayed count (recent days weigh more) so last year's event does not outrank today's.
Sampling the log (1 in 10) is fine for popular queries and cuts build cost.
Serving path, caching and the latency budget
Short prefixes are few and extremely popular, so the CDN answers them. Long prefixes are rare, miss the cache and hit the service.
Layer
What it does
Budget (approx.)
Browser
Debounce, cancel superseded requests, cache results per prefix for the session
0 ms on a hit
Network to the edge
One round trip on a kept-alive connection
20 to 50 ms
CDN
Caches by full URL for minutes
1 to 5 ms
Edge to origin (miss only)
Round trip to the nearest region
10 to 30 ms
Suggest service
Normalise, look up, merge, filter
1 to 5 ms
Sharding the index
First question: does it need sharding at all? At 16 GB, no: run many identical replicas per region. Shard when languages, markets or longer prefixes push it past one machine's memory.
Hash of the prefix: even load, and works because a lookup is an exact key match. The natural choice for the prefix map.
Range by leading characters: needed for a real trie; ranges must be sized from the measured distribution (s is far busier than x) and kept in a shard map.
Ranking, personalisation and filtering
Ranking: decayed frequency, optionally adjusted by click-through on the suggestion and by language or region (a separate index per market keeps responses cacheable).
Personalisation: per-user responses cannot be shared in a CDN. Keep the global list cacheable and blend the user's own recent searches on the client.
Filtering at build time: blocklist, classifiers for offensive or dangerous content, and a minimum number of distinct users per query so one person's private query can never be suggested.
Filtering at serve time: a small blocklist checked on every response, so a takedown works in minutes without a rebuild; purge the CDN for the affected prefixes.
Failure mode: a bad index build ships empty or offensive results. Validate the snapshot (size, sample queries), roll out to a few servers first, keep the previous version loaded.
Failure mode: manipulation. Coordinated queries push a phrase into suggestions; count distinct users, cap per-user contribution, review fast risers.
Failure mode: suggest service down. The search box still works; the client hides the dropdown after a short timeout.
Follow-up
One-line answer
Typos and fuzzy matching?
Out of the basic design; add an edit-distance pass or a separate spelling service for prefixes with no results.
Matching in the middle of a phrase?
Index word-level prefixes as extra keys; costs index size.
Many languages?
An index per language with language-specific normalisation; the request carries the language.
How fresh is fresh enough?
Hourly batch covers almost all traffic; the trending delta covers news events.
Senior signal: you notice from the estimate that the index fits in memory and say "replicate, do not shard", put most of the latency budget on the network and caches, and treat filtering as a first-class requirement.
Cheat sheet
One line per case. If you can rebuild the design from its row, you know it.
Precompute top-k for every prefix offline, serve from memory and caches
Immutable in-memory prefix index
Freshness of the index without giving up cacheability
Patterns that repeat: keep the hot path to one lookup; move work to write time or offline when reads dominate; put a queue wherever a slow or external dependency sits; treat caches and derived views as rebuildable.
Questions that repeat: what is the hot key, what happens when the cache or queue is down, where can a duplicate appear, what changes at 10x.