System Design — Concept Notes

1. What Interviewers Actually Test

What they score you on

Level expectations

• Junior / new grad: a working high-level design, basic building blocks (load balancer, cache, database), sensible API. Depth is a bonus.
• Mid-level: all of the above, plus you drive the conversation, make estimates, and go deep on one area.
• Senior: you find the hard part yourself, discuss failure modes, consistency, cost and operations without being asked.

Written exam vs live interview

In a written exam (university paper, online assessment, take-home) nobody can answer your questions. So you state your assumptions instead of asking them. The marker is looking for the same signals, but on paper.

How to structure a written answer

1. Assumptions and requirements — functional (what it does) and non-functional (how well), as bullet points.
2. Estimates — 3–5 lines of numbers: users, requests per second, storage.
3. API — 3–5 endpoints.
4. Data model — tables or collections with key fields.
5. Architecture diagram — boxes and arrows, every box labelled, numbered arrows for the main flow.
6. Component explanation — one short paragraph per box, following the arrow numbers.
7. Scaling and deep dives — the hard part of this problem, explained properly.
8. Trade-offs and alternatives — a table: choice, why, cost.
9. Conclusion — two sentences summarising the design.

The full template is in the revision section: Written-exam template.

2. The Step-by-Step Framework

Step 1 — Clarify requirements (about 5 min)

Split them into two lists and write both on the board.

• Functional: "Who uses it? What are the 3–5 core actions?" Pick the core ones and say the rest are out of scope.
• Non-functional: scale, latency (speed), availability (uptime), consistency (does everyone see the same data at once?), durability (never lose data).

Good questions to ask:

• "How many daily active users (DAU) should I design for?"
• "Is it read-heavy or write-heavy? Roughly what ratio?"
• "Is it global, or one region?"
• "What matters more if we must choose: always available, or always correct?"
• "Do we need real-time updates, or is a few seconds of delay fine?"
• "Mobile, web, or both? Any existing systems I must integrate with?"
• "How long do we keep data? Is there anything we must never lose?"

Step 2 — Back-of-the-envelope estimates (about 3 min)

Rough maths for requests per second, storage and bandwidth (section 3). The point is not precision; the point is to decide things like "one database is fine" or "we must shard".

Step 3 — API (about 3 min)

List the main endpoints: method, path, inputs, output. This makes the functional requirements concrete.

POST /api/v1/urls          { longUrl }        -> { shortUrl }
GET  /{shortCode}                             -> 302 redirect

Step 4 — Data model (about 4 min)

Main entities (things you store) and their key fields. Say which database type you will use and why (section 10).

Step 5 — High-level design (about 10 min)

Draw the boxes: client, load balancer, services, cache, database, queue, storage. Walk through one request end to end. Start simple; do not add Kafka before you need it.

Step 6 — Deep dive (10–12 min)

Pick the hardest part of this problem, or let the interviewer pick. Examples: generating unique short codes, fan-out for a feed, matching riders to drivers. Go properly deep here.

Step 7 — Bottlenecks and scaling (about 5 min)

Ask "what breaks first at 10x the traffic?" Then fix it: caching, replicas, sharding, queues. Mention single points of failure (one box whose failure takes everything down).

Step 8 — Wrap-up (about 2 min)

Summarise the design in 3–4 sentences, list what you would add with more time (monitoring, security, analytics), and name one trade-off you consciously made.

3. Back-of-the-Envelope Estimation

Powers of two (data sizes)

Handy sizes: a character is 1 byte (ASCII), a number (int64) is 8 bytes, a UUID is 16 bytes, a timestamp is 8 bytes. A typical database row is 100 bytes to 1 KB.

Latency numbers every engineer should know

Latency is how long one operation takes. You do not need exact values, just the ladder.

(ns = nanosecond, a billionth of a second; µs = microsecond, a millionth; ms = millisecond, a thousandth.)

The three lessons: memory is much faster than disk; disk is much faster than a network hop across the world; avoid round trips, especially cross-region ones.

The formulas

Seconds in a day     ≈ 86,400  ≈ 100,000 (round up, easier maths)

Average QPS          = daily requests / 86,400
                     ≈ daily requests / 100,000
Peak QPS             ≈ 2x to 3x average (say "peak factor")

Write QPS            = DAU x writes per user per day / 86,400
Read QPS             = write QPS x read:write ratio

Storage per day      = writes per day x size per item
Storage total        = storage per day x 365 x years  (x replication factor, often 3)

Bandwidth (ingress)  = write QPS x size per item      (data coming in)
Bandwidth (egress)   = read QPS x size per item       (data going out)

Servers needed       ≈ peak QPS / QPS one server handles (assume ~1,000 for a simple API)
Cache memory         ≈ 20% of daily read data (80/20 rule: 20% of items get 80% of reads)

QPS means queries (or requests) per second. DAU means daily active users.

A fully worked example: a photo-sharing app

Assumptions, stated out loud: 100 million DAU. Each user uploads 1 photo every 10 days (0.1 per day) and views 50 photos per day. Average photo 500 KB. Keep photos for 10 years.

Writes per day   = 100M x 0.1          = 10M uploads/day
Write QPS        = 10M / 100k          = ~100 uploads/sec   (peak ~300)

Reads per day    = 100M x 50           = 5B views/day
Read QPS         = 5B / 100k           = ~50,000 views/sec  (peak ~150k)
Read:write ratio = 50,000 / 100        = 500 : 1  -> very read-heavy

Storage per day  = 10M x 500 KB        = 5 TB/day
Storage 10 years = 5 TB x 365 x 10     = ~18 PB  (before replication)

Egress bandwidth = 50,000 x 500 KB     = 25 GB/sec  -> must use a CDN

Metadata         = 10M rows/day x ~500 bytes = 5 GB/day -> ~18 TB in 10 years
                   -> too big for one comfortable DB node, plan to shard

What the numbers tell you, and what to say:

• 500:1 read-heavy → heavy caching and a CDN matter more than write speed.
• 18 PB of photos → object storage like S3 (section 18), not a database.
• 25 GB/s outgoing → no single server can do that; a CDN serves the photos (section 9).
• 18 TB of metadata → shard the metadata database or use a wide-column store.

4. Key Non-Functional Terms

Availability and the "nines"

Availability is written as a percentage. Each extra 9 cuts allowed downtime by ten.

Components in series multiply: if a request needs service A (99.9%) and B (99.9%), total availability is 99.9% x 99.9% ≈ 99.8%. More required hops means lower availability.

Components in parallel add up: two redundant copies each at 99% give 1 − (0.01 x 0.01) = 99.99%. Redundancy is how you buy nines.

Latency vs throughput

Latency is how long one car takes to drive down a road. Throughput is how many cars pass per hour. Widening the road (more lanes) raises throughput but does not make any single car faster. You can have high throughput and bad latency at the same time — for example, a batch system.

Measure latency with percentiles, not averages. p50 is the median (half of requests are faster). p99 means 99% of requests are faster than this; the slowest 1% are slower. Users notice the p99, and a page making 100 calls hits a p99 on almost every load.

Availability vs reliability vs durability

• A system that answers every request with wrong data is available but not reliable.
• A system that is down for an hour but loses nothing is not very available, but is durable.

5. How a Request Travels

The steps in order

1. DNS lookup — the browser asks "what is the IP for api.example.com?" The answer is cached at several levels (browser, OS, internet provider) for a set time called the TTL (time to live).
2. TCP connection — TCP is the protocol that guarantees bytes arrive in order and complete. Opening one costs a round trip (the "three-way handshake").
3. TLS handshake — TLS is the encryption behind the padlock and https://. It proves the server is who it claims (with a certificate) and agrees a secret key. Costs 1–2 more round trips.
4. HTTP request — method (GET, POST…), path, headers, maybe a body.
5. Server side — load balancer → app server → cache / database → build the response.
6. HTTP response — a status code (200 OK, 404 Not Found, 500 Server Error), headers and body.

HTTP in one table

Idempotent means doing it twice has the same effect as doing it once. This matters for retries (section 16).

Versions: HTTP/1.1 uses one request at a time per connection. HTTP/2 sends many requests over one connection at once (multiplexing). HTTP/3 runs over QUIC (on UDP) to avoid delays when a packet is lost — good on mobile networks.

6. Vertical vs Horizontal Scaling

Making a server stateless

• Sessions → a shared store (Redis) or a signed token the client holds (JWT, section 24).
• Uploaded files → object storage (S3), never the server's local disk.
• In-memory caches → fine for data everyone shares (config), but user-specific data belongs in a shared cache.
• Scheduled jobs → a single scheduler or a queue, so ten servers don't run the same job ten times.

Once servers are stateless you can use auto-scaling: the cloud adds servers when CPU or queue length goes up, and removes them when traffic drops.

7. Load Balancers

Layer 4 vs Layer 7

The "layers" come from the OSI network model. Layer 4 is the transport layer (TCP/UDP: IP addresses and ports). Layer 7 is the application layer (HTTP: URLs, headers, cookies).

Algorithms

Health checks

The LB calls an endpoint like /health every few seconds. After a few failures in a row, the server is removed; after a few passes, it comes back. Active checks are these regular pings; passive checks watch real traffic for errors.

Sticky sessions

Sticky sessions (session affinity) send the same user to the same server every time, usually via a cookie. They make a stateful app work behind an LB, but they cause uneven load and lose the user's state when that server dies. Prefer stateless servers; use stickiness only when you must (for example, a WebSocket connection is naturally sticky).

Is the load balancer a single point of failure?

It can be. Fixes: run two LBs in active-passive (one takes over via a shared floating IP) or active-active mode, or use a managed cloud LB that is already redundant. At the global level, DNS load balancing or GeoDNS sends users to the nearest region.

8. Caching

Where caches live (layers)

Cache patterns (how reads and writes flow)

Eviction — what to throw out when the cache is full

• LRU (Least Recently Used) — drop what hasn't been read for the longest time. The default choice.
• LFU (Least Frequently Used) — drop what is read least often. Better when some items are always popular.
• FIFO (First In, First Out) — drop the oldest entry. Simple, rarely the best.
• TTL (Time To Live) — each entry expires after a set time. Not really eviction, but always set one: it limits how stale data can get.

Invalidation — keeping the cache correct

"There are only two hard things in computer science: cache invalidation and naming things." When the database changes, the cached copy is stale (out of date). Options:

• Delete on write — after updating the DB, delete the key. The next read refills it. Prefer delete over update: updating can race with another writer and leave the wrong value.
• Short TTL — accept up to N seconds of staleness. Simple and robust.
• Event-driven — the DB's change stream (CDC, change data capture) publishes events that delete keys.
• Versioned keys — user:42:v7; bump the version on change so old keys are simply never read again.

Problems you should name

Redis vs Memcached

Redis: rich data types (lists, sets, sorted sets, hashes), persistence, replication, pub/sub, Lua scripts. Memcached: plain key-value strings, multi-threaded, very simple. Default to Redis unless you only need a dumb, huge cache.

9. CDN (Content Delivery Network)

Push vs pull CDN

What to know

• Cache control: the origin sets Cache-Control: max-age=… to tell the CDN how long to keep a file.
• Cache busting: put a version or hash in the filename (app.3f9a2c.js). A new deploy means a new name, so users never get an old file. Much easier than asking the CDN to purge.
• Dynamic content: modern CDNs also speed up API calls by keeping warm connections to the origin, and can run small bits of code at the edge.
• Bonus: CDNs absorb DDoS attacks (section 24) and reduce your bandwidth bill.
• Cost: you pay per GB delivered; stale content is possible until TTL expires.

10. Choosing a Database

ACID vs BASE

• ACID (typical of SQL): Atomic (all or nothing), Consistent (rules like "balance can't go negative" always hold), Isolated (concurrent transactions don't see each other's half-done work), Durable (committed means saved).
• BASE (typical of many NoSQL): Basically Available, Soft state, Eventually consistent — replicas agree eventually, not instantly.

The database types and when to use each

How to choose (the questions to ask yourself)

1. Do I need transactions across several records? (money, stock levels) → SQL.
2. What is the access pattern? Always by one key → key-value. Whole object at once → document. Append-heavy, time-ordered per user → wide-column.
3. How much write volume? Tens of thousands of writes per second across regions → Cassandra/DynamoDB style.
4. Is the schema stable? Stable → SQL. Changing often or varied → document.
5. Are relationships the point? → graph.

Polyglot persistence means using several databases in one system, each for what it does best — for example Postgres for users and orders, Redis for sessions, Cassandra for messages, S3 for photos, Elasticsearch for search.

11. Replication

Three replication styles

Synchronous vs asynchronous

• Synchronous: the leader waits for the follower to confirm before telling the client "saved". Safe (no data loss on failover) but slower, and a slow follower blocks writes.
• Asynchronous: the leader confirms immediately and ships changes in the background. Fast, but if the leader dies the last few writes may be lost.
• Semi-synchronous: one follower is synchronous, the rest async. Common compromise.

Replication lag and its symptoms

Replication lag is the delay before a follower has the latest data. Usually milliseconds, sometimes seconds under load. It causes visible bugs:

• Read-your-own-write fails — you post a comment, the page reloads from a lagging follower, your comment is missing. Fix: read from the leader for a few seconds after the user writes, or read the user's own data from the leader.
• Time going backwards — two reads hit different followers; the second is further behind. Fix: monotonic reads — pin a user to one follower.

Failover

Failover is switching to a replica when the leader dies: detect the failure (heartbeats time out), pick the most up-to-date follower, point writes at it. Danger: split brain — the old leader comes back and both think they are leader. Fixed with fencing (the old leader's writes are rejected) and consensus (section 22).

12. Sharding (Partitioning)

Sharding strategies

Consistent hashing

With plain hash(key) % N, going from 4 to 5 servers changes the answer for about 80% of keys — a huge, painful data move. Consistent hashing fixes this.

Virtual nodes: with only three points on the ring, one node may get a huge arc and most of the keys. So each physical server is placed at many points (for example 100–200 "virtual nodes"). This evens out load, and a stronger server can simply get more virtual nodes. Used by Cassandra, DynamoDB, and many caches.

Resharding

Resharding is changing how data is split — usually adding shards as data grows. It is expensive: data must be copied while the system keeps serving. Ways to make it easier:

• Consistent hashing so only a fraction moves.
• Start with many logical shards (say 1024) mapped onto a few physical machines. Growing means moving whole logical shards to new machines, never re-splitting data.
• Double-write during migration: write to old and new location, backfill, then switch reads.

Hotspots and the celebrity problem

A hotspot is one shard getting far more traffic than the others — for example a celebrity with 100 million followers when sharding by user_id. Fixes: add a random suffix to hot keys to spread them (celebrity_id#0..9), cache hot items, or give hot tenants their own shard.

What sharding costs you

• Cross-shard queries — a query not on the shard key must ask every shard (scatter-gather) — slow.
• Cross-shard joins and transactions — mostly gone; you design around them (denormalise, sagas).
• Operational complexity — backups, schema changes, monitoring times N.

13. Indexing, Denormalisation, Read Replicas

Indexes

• B-tree index — the default. A balanced tree, good for equality (=) and ranges (>, BETWEEN, ORDER BY). Lookup cost grows slowly (log n).
• Hash index — only equality lookups, very fast.
• Composite index — on several columns, e.g. (user_id, created_at). Follows the leftmost prefix rule: it helps queries on user_id, or user_id + created_at, but not on created_at alone.
• Covering index — the index includes every column the query needs, so the table itself is never read.
• LSM tree (log-structured merge tree) — used by Cassandra, RocksDB. Writes go to memory then are flushed to sorted files; very fast writes, reads may check several files.

The cost: every index slows down writes (it must be updated too) and uses storage. Index the columns you filter, join and sort on — not everything.

Normalisation vs denormalisation

Related: a materialised view is a precomputed query result stored like a table, refreshed periodically. CQRS (Command Query Responsibility Segregation) means using separate models (even separate databases) for writes and for reads, synced via events.

Read replicas

Followers from section 11 used to serve read traffic. A read-heavy app (most are) can add replicas to multiply read capacity. Remember replication lag: route "read after my own write" to the leader.

The scaling ladder for a database

1. Add the right indexes; fix slow queries.
2. Add a cache in front (section 8).
3. Scale the machine up (vertical).
4. Add read replicas.
5. Denormalise hot read paths / use materialised views.
6. Split by feature (users DB, orders DB) — vertical partitioning.
7. Shard (section 12).

14. CAP Theorem, PACELC and Consistency

PACELC — the fuller picture

CAP only talks about failures. PACELC adds normal times: "if Partition, choose A or C; Else (normal operation), choose Latency or Consistency." Even with a healthy network, waiting for replicas to agree costs time.

• PA/EL — Cassandra, DynamoDB: available and fast, eventually consistent.
• PC/EC — Spanner, HBase: consistent always, pays in latency.

Consistency models (strongest to weakest)

Quorums (tunable consistency)

In leaderless systems with N replicas, a write waits for W confirmations and a read asks R replicas. A quorum is a majority.

If  W + R > N   -> every read overlaps at least one replica with the latest write
                   -> strong-ish consistency

Typical: N = 3, W = 2, R = 2   (2 + 2 > 3)       balanced
         N = 3, W = 1, R = 1   fast, eventual
         N = 3, W = 3, R = 1   fast reads, slow and fragile writes

Conflicts in eventually consistent stores are resolved with last-write-wins (timestamps; simple but can lose data), version vectors (detect concurrent writes and let the app merge), or CRDTs (data types that merge automatically, like counters).

15. Message Queues & Event Streaming

Why use a queue

• Absorb spikes — 10x traffic for a minute just makes the queue longer; the database isn't crushed.
• Do slow work later — send emails, resize images, generate reports without making the user wait.
• Survive failures — the consumer is down? Messages wait until it's back.
• Decouple teams and services — the producer doesn't know or care who consumes.

Queue vs publish/subscribe

Kafka in plain words

Apache Kafka is an event streaming platform: a durable, append-only log of events that many consumers can read, and re-read, at their own pace.

• Topic — a named stream of events, like orders.
• Partition — a topic is split into partitions for parallelism. Order is guaranteed within a partition only. Messages with the same key (say order_id) always go to the same partition, so they stay in order.
• Offset — a message's position in the partition. Each consumer remembers its offset, so it can pause, resume or replay.
• Consumer group — consumers sharing the work; each partition is read by one consumer in the group. More partitions = more parallel consumers.
• Retention — messages are kept for a set time (days) even after being read, unlike a classic queue that deletes on ack.
• Replication — each partition is copied to several brokers (Kafka servers).

Delivery guarantees

In practice: use at-least-once delivery with idempotent consumers. Idempotent means processing a message twice has the same effect as once — for example, store processed message IDs and skip repeats, or use "set status = paid" rather than "add 10 to balance".

Dead-letter queue and backpressure

• Dead-letter queue (DLQ) — after N failed attempts, a "poison" message is moved aside so it doesn't block the queue forever. Alert on it; inspect and replay later.
• Backpressure — signalling upstream to slow down when consumers can't keep up. Options: bounded queue that rejects when full, rate-limit producers, auto-scale consumers on queue length, or shed low-priority work.
• Visibility timeout (SQS) — a taken message is hidden for N seconds; if not acked in time, it reappears for another worker.

16. API Design & Communication

REST vs GraphQL vs gRPC

Over-fetching = getting fields you don't need. Under-fetching = needing several calls to get everything.

Good REST habits

GET    /api/v1/users/42/posts?limit=20&cursor=abc   list a user's posts
POST   /api/v1/posts                                create (201 Created)
GET    /api/v1/posts/987                            read one
PATCH  /api/v1/posts/987                            partial update
DELETE /api/v1/posts/987                            delete (204 No Content)

• Nouns in URLs, verbs are HTTP methods. Plural collections.
• Version the API (/v1) so you can change it without breaking old clients.
• Correct status codes: 200, 201, 204, 400 (bad input), 401 (who are you?), 403 (not allowed), 404, 409 (conflict), 429 (too many requests), 500, 503.

Polling vs long polling vs WebSockets vs SSE

Pagination

Idempotency keys

Networks fail. A client sends "pay $50", the response is lost, the client retries — did we charge twice? An idempotency key is a unique ID the client generates and sends with the request (header Idempotency-Key: 7f3a…). The server stores the key with the result; a repeat with the same key returns the stored result instead of acting again.

POST /payments   Idempotency-Key: 7f3a9c   { amount: 50 }
server: key seen before?  yes -> return saved response
                          no  -> process, save (key -> response) with a TTL, return

17. Rate Limiting

The algorithms

Token bucket (per user), run on each request:
  tokens = min(capacity, tokens + (now - last_refill) x rate)
  last_refill = now
  if tokens >= 1: tokens -= 1; allow
  else: reject with 429 and Retry-After header

Sliding window counter example (limit 100/min):
  previous minute: 80 requests, current minute: 30, we are 25% into it
  estimate = 80 x 0.75 + 30 = 90   -> allow (90 < 100)

Where to put it

• Client side — nice for UX, never trusted (easily bypassed).
• API gateway / load balancer / edge — the usual place; rejects bad traffic before it costs you anything.
• In each service — protects specific expensive endpoints.
• Distributed — with many gateway servers, counters live in a shared Redis so all servers see the same count. Use atomic operations (INCR + EXPIRE, or a Lua script) to avoid race conditions.

What to limit by

User ID or API key (best), IP address (for anonymous traffic — but many users can share one IP), endpoint (login stricter than reads), and plan tier (free vs paid). Return headers such as X-RateLimit-Limit, X-RateLimit-Remaining and Retry-After.

18. Blob / Object Storage & File Uploads

Presigned URLs — upload straight to storage

Sending a 2 GB video through your app servers wastes their bandwidth and memory. Instead:

1. Client asks your API: "I want to upload video.mp4, 2 GB".
2. API checks permissions, creates a metadata row (status: pending), and asks S3 for a presigned URL — a temporary URL with a signature that allows exactly one upload to one key for, say, 15 minutes.
3. Client uploads directly to S3 using that URL.
4. S3 sends an event (or the client calls "upload complete"); the API marks the row uploaded and queues processing (thumbnails, virus scan, transcoding).

Downloads work the same way: presigned GET URLs for private files, or a CDN in front of public ones.

Chunked (multipart) uploads

Big files are split into chunks (say 5–10 MB each) uploaded separately, even in parallel. If the network drops, only the failed chunk is retried — the upload is resumable. The server (S3 multipart upload) stitches them together at the end. Each chunk can carry a checksum (a short fingerprint of its contents) to detect corruption.

Storage classes

Hot (frequently read, standard price), infrequent access (cheaper storage, pay per read), and archive (Glacier: very cheap, hours to retrieve). Lifecycle rules move old files to cheaper classes automatically.

19. Search

How an inverted index is built

Doc 1: "Red running shoes"      Doc 2: "Blue shoes for running"   Doc 3: "Red dress"

Tokenise, lowercase, stem ("running" -> "run"), drop stop words ("for"):
  red   -> [1, 3]
  run   -> [1, 2]
  shoe  -> [1, 2]
  blue  -> [2]
  dress -> [3]

Query "red shoes" -> red [1,3]  AND  shoe [1,2]  -> doc 1 (then rank)

Ranking uses scores like TF-IDF / BM25: a word counts more if it appears often in this document (term frequency) but rarely across all documents (inverse document frequency) — "the" is worthless, "Bluetooth" is meaningful.

Elasticsearch / OpenSearch

• A distributed search engine built on the Lucene library. Data is split into shards with replicas, across nodes.
• Supports full-text search, filters, fuzzy matching (typos), aggregations (facets like "brand: 12 results").
• Not the source of truth. The main database is. Sync changes to the search index via a queue or CDC (change data capture) stream. The index is near real-time — searchable after about a second.

Typeahead with a trie

A trie (prefix tree) stores words letter by letter; every path from the root spells a prefix. To suggest completions for "ca", walk c → a and collect words below. Store the top-k most popular completions at each node so lookup is instant. Full design in section 34.

20. Monolith vs Microservices

A modular monolith — one deployable, but with strict internal boundaries between modules — is often the best of both, and makes a later split easy.

The supporting pieces

• API gateway — the single front door for clients. It routes requests to the right service and handles cross-cutting jobs: authentication, rate limiting, TLS, request logging, response aggregation. Examples: Kong, AWS API Gateway, Nginx, Envoy. A BFF (Backend for Frontend) is a gateway tailored to one client type (mobile vs web).
• Service discovery — services start and stop constantly, with changing IPs. A service registry (Consul, etcd, Eureka, or Kubernetes DNS) keeps the live list; callers look up "where is the payment service right now?"
• Service mesh — a small proxy (a sidecar, e.g. Envoy) runs next to every service and handles networking: retries, timeouts, mutual TLS encryption, metrics, traffic splitting. The app code stays simple. Examples: Istio, Linkerd.
• Communication — synchronous (REST/gRPC: caller waits) for queries that need an answer now; asynchronous (events via Kafka) for "something happened" notifications. Prefer async between services to reduce coupling.

21. Reliability Patterns

The patterns

Exponential backoff with jitter:
  delay = min(cap, base x 2^attempt)
  sleep(random(0, delay))        # "full jitter"

  attempt 0: up to 100 ms, 1: up to 200 ms, 2: up to 400 ms, 3: up to 800 ms ... cap at 10 s

Circuit breaker states

22. Distributed Systems Essentials

Unique ID generation

Distributed transactions: 2PC vs saga

Placing an order might need to charge payment (payment service), reserve stock (inventory service) and create the order (order service) — three databases. How do they succeed or fail together?

The outbox pattern solves "update my DB and publish an event" atomically: write the event into an outbox table in the same local transaction, and a separate process publishes outbox rows to the queue.

Leader election and consensus (Raft in plain words)

Consensus means several machines agreeing on one value (who is leader, what the next log entry is) even if some crash. Raft is the most common algorithm:

1. Every node starts as a follower. The leader sends regular heartbeats.
2. If a follower hears nothing for a random timeout, it becomes a candidate, increases the term (election number) and asks others for votes.
3. A candidate that gets votes from a majority becomes leader for that term. Majority means only one leader per term is possible.
4. The leader receives writes, appends them to its log, and copies them to followers. An entry is committed once a majority has it.
5. That's why clusters have an odd number of nodes: 3 nodes survive 1 failure, 5 survive 2.

You rarely implement Raft; you use a system built on it: etcd, Consul, or ZooKeeper (which uses a similar protocol, ZAB). Paxos is the older, harder-to-explain relative.

Distributed locks

A distributed lock makes sure only one process across many machines does something at a time (e.g. only one worker processes a given payment).

• Redis: SET lock:order42 <owner> NX PX 30000 — set only if not exists, auto-expire in 30 s. Release only if you're still the owner. Simple, but not perfectly safe during failovers.
• ZooKeeper / etcd: consensus-backed, safer, slower.
• Fencing tokens: the lock service hands out an increasing number with each lock; the storage rejects writes with an old number. Protects against a paused process that wakes up thinking it still holds the lock.
• Often better: avoid locks with optimistic concurrency — a version column, UPDATE … WHERE version = 7; if 0 rows change, someone else won, retry.

Clocks

Machine clocks drift and can jump (NTP corrections), so "compare timestamps from two machines" is unreliable for ordering events.

• Lamport clocks — a counter each node increments and attaches to messages; gives a consistent order of cause and effect.
• Vector clocks — one counter per node; can tell whether two events are ordered or truly concurrent (a conflict).
• TrueTime (Google Spanner) — GPS and atomic clocks with a known error bound; waits out the uncertainty to give global ordering.

23. Observability

What to measure: the RED method for services — Rate, Errors, Duration. The four golden signals (Google SRE): latency, traffic, errors, saturation (how full a resource is).

SLI, SLO, SLA

SLA is looser than SLO so you get warned before you owe money. The gap between 100% and the SLO is the error budget: if you have budget left, ship features fast; if it's used up, focus on reliability.

Alerting

• Alert on symptoms users feel (error rate, latency SLO burn), not every CPU spike.
• Every alert must be actionable, with a runbook (step-by-step fix guide). Noisy alerts get ignored.
• Pages (wake someone up) for urgent user impact; tickets for everything else.

24. Security in Design

Authentication and authorisation

• Sessions — server stores a session in Redis; the browser holds a random session ID in a cookie. Easy to revoke.
• JWT (JSON Web Token) — a signed token containing the user ID and claims. Any service can verify it without a database lookup (stateless). Hard to revoke before it expires, so keep access tokens short-lived (15 min) with a refresh token to get new ones.
• OAuth 2.0 — a standard for letting one app access another on a user's behalf ("Sign in with Google", "allow this app to read your calendar") without sharing the password. OpenID Connect adds login (identity) on top.
• Authorisation models — RBAC (role-based: admin, editor, viewer) and ABAC (attribute-based: "owner of the document, in the same org"). Always check ownership on the server: "can user 7 read order 42?"
• In microservices, authenticate once at the API gateway, pass a verified identity (token) inward; services still authorise.

Protecting data

• In transit — HTTPS/TLS everywhere. TLS encrypts traffic and proves the server's identity via a certificate. Inside the network, mutual TLS (mTLS: both sides show certificates) between services, often via a service mesh.
• At rest — disks, databases and backups encrypted (AES-256), with keys in a KMS (Key Management Service).
• Passwords — never stored; hash with bcrypt/argon2.
• Secrets (API keys, DB passwords) — in a secrets manager (Vault, AWS Secrets Manager), never in code or logs; rotate them.
• Least privilege — every service and person gets only the access it needs.
• PII (personally identifiable information) — minimise, mask in logs, respect laws like GDPR (data residency, right to deletion).

Attacks to name

A WAF (Web Application Firewall) filters known-bad request patterns at the edge.

25. URL Shortener (TinyURL / bit.ly)

1. Requirements

• Functional: create a short URL from a long URL; redirect short → long; optional custom alias; optional expiry.
• Non-functional: redirects must be very fast (< 50 ms) and highly available; short codes must be unique and hard to guess in order; reads far outnumber writes (about 100 : 1).

2. Estimates

New URLs:     100M per month  → ~40 writes/sec  (peak ~200)
Redirects:    100 × writes    → ~4,000 reads/sec (peak ~20,000)
Storage:      100M × 12 months × 5 years = 6B rows
              6B × ~500 bytes ≈ 3 TB   (fits a small sharded DB)
Code length:  base62 (a–z, A–Z, 0–9) → 62^7 ≈ 3.5 trillion codes
              7 characters is plenty

3. API

POST /api/urls        { longUrl, customAlias?, expiresAt? }  → 201 { shortUrl }
GET  /{code}          → 301/302 redirect to longUrl, or 404
DELETE /api/urls/{code}                                        → 204

4. Data model

urls
  code        VARCHAR(10)  PRIMARY KEY   -- "aZ3k9x1"
  long_url    TEXT
  user_id     BIGINT
  created_at  TIMESTAMP
  expires_at  TIMESTAMP NULL

A key-value lookup by code is the only hot query, so either a SQL table or a key-value store (DynamoDB, Cassandra) works.

5. High-level design

6. Deep dives

• Generating the code. Three options:
  • Hash the long URL (MD5, take 7 chars) — simple, but collisions need a check-and-retry, and the same URL always gives the same code.
  • Counter + base62 — a unique number (e.g. 125) becomes a short string. No collisions. Give each app server a range of numbers (1–1M, 1M–2M…) from a coordinator like ZooKeeper so they never clash and never wait.
  • Random 7 chars — check the DB for a clash; fine because clashes are rare in 3.5 trillion.
  Counter ranges are the usual best answer. Mention that sequential codes are guessable; shuffle the bits if that matters.
• 301 vs 302. 301 (permanent) lets browsers cache the redirect — less load, but you lose click analytics. 302 (temporary) sends every click through you — more load, but you can count clicks.
• Caching. A small fraction of links get most clicks. Cache-aside in Redis with LRU eviction handles most reads.
• Analytics. Don't slow the redirect down. Push a click event onto a queue (Kafka) and count it asynchronously.
• Expiry. Check expires_at on read, and clean up with a background job.

7. Bottlenecks & trade-offs

26. Rate Limiter as a Service

1. Requirements

• Functional: limit by user, IP or API key; different rules per endpoint; return 429 with a Retry-After header.
• Non-functional: adds < 5 ms per request; works across many servers; if the limiter fails, the API must still work (fail open).

2. Estimates

API traffic:  50,000 req/sec  → 50,000 counter checks/sec
Keys:         10M active users × ~50 bytes ≈ 500 MB   (fits in Redis memory)

3. API / interface

// internal call from the gateway, or a middleware in each service
isAllowed(key = "user:42:/api/search", rule = { limit: 100, window: 60s })
  → { allowed: true, remaining: 57, resetAt: 1727340060 }

HTTP response headers:
  X-RateLimit-Limit: 100
  X-RateLimit-Remaining: 57
  Retry-After: 12          (only on 429)

4. Data model

Redis key:   rl:{userId}:{endpoint}:{windowStart}   → count   (TTL = window)
Rules:       stored in a config DB / file, cached in each gateway

5. High-level design

6. Deep dives

• Algorithm choice. Token bucket allows short bursts and is the most common answer. Sliding-window counter is accurate and cheap. Fixed window is simplest but lets through 2× at window edges.
• Race conditions. Two servers read "99", both allow, the count ends at 101. Fix: do read-and-increment atomically — Redis INCR, or a Lua script that runs as one step.
• Latency. One Redis round trip is ~1 ms. For extreme scale, keep a small local counter and sync to Redis every few hundred ms — slightly inaccurate, much faster.
• Failure. If Redis is down, fail open (allow requests) for normal APIs; fail closed for things like login attempts or payments.
• Where to put it. At the API gateway for global rules; inside a service for business rules ("3 password resets per hour").

7. Bottlenecks & trade-offs

27. Chat App (WhatsApp / Messenger)

1. Requirements

• Functional: 1:1 and group chat (up to ~500 members); sent / delivered / read ticks; online status and last seen; message history on any device; media (images, video).
• Non-functional: low latency (< 200 ms delivery when online); messages never lost; messages in order within a chat; very high availability.

2. Estimates

Users:       500M daily active
Messages:    40 per user per day → 20B/day → ~230,000 msg/sec (peak ~1M)
Storage:     20B × 100 bytes ≈ 2 TB of text per day
Connections: ~100M concurrent WebSockets; ~50K per server → ~2,000 chat servers

3. API

WebSocket (persistent):
  → send     { chatId, clientMsgId, text }
  ← ack      { clientMsgId, msgId, timestamp }
  ← message  { chatId, msgId, from, text, timestamp }
  → receipt  { msgId, status: "delivered" | "read" }

REST:
  GET  /chats/{chatId}/messages?before={msgId}&limit=50   (history, paginated)
  POST /media  → presigned upload URL

4. Data model

messages  (Cassandra — partition key = chat_id, clustering key = msg_id)
  chat_id, msg_id (time-ordered, e.g. Snowflake), sender_id, body, created_at

chats            chat_id, type (direct | group), members
user_inbox       user_id → undelivered msg_ids   (for offline users)
presence (Redis) user_id → { chatServerId, lastSeen }

Cassandra (wide-column) fits because the main query is "latest messages of chat X", writes are huge, and it scales horizontally.

5. High-level design

6. Deep dives

• Send flow. (1) Sender's app sends over WebSocket with a clientMsgId. (2) Server A stores the message in Cassandra, then acks the sender (one grey tick). (3) Server A looks up the receiver in presence. (4) If online, it routes the message via the queue to server B, which pushes it; the receiver's app sends a "delivered" receipt (two ticks). (5) If offline, the message stays in the receiver's inbox and a push notification is sent.
• Why WebSockets. The server needs to push to the client. Polling wastes battery and bandwidth; a WebSocket is one long-lived two-way connection.
• Ordering. Use a per-chat, time-ordered ID (Snowflake) and sort by it. Kafka partitioned by chat_id keeps one chat's messages in order.
• Duplicates. Networks retry. The clientMsgId is an idempotency key — if the server has already stored it, just ack again.
• Groups. For small groups, fan out: write the message once, deliver to each online member's server. For huge groups/channels, members pull instead.
• Presence. The app sends a heartbeat every ~30 s; if heartbeats stop, the user is marked offline after a timeout. Only broadcast presence to contacts who have the chat open, or it floods the system.
• Media. Upload directly to object storage with a presigned URL; the message only carries the file link.
• End-to-end encryption (Signal protocol): the server only stores and forwards ciphertext it cannot read. Mention it; don't design the crypto.

7. Bottlenecks & trade-offs

28. News Feed (Twitter / Instagram)

1. Requirements

• Functional: create a post (text, images); follow/unfollow; see the home feed; like and comment.
• Non-functional: feed loads fast (< 200 ms); a new post can take a few seconds to appear (eventual consistency is fine); very read-heavy.

2. Estimates

Users:        300M daily active, each opens feed ~10×/day → 3B feed reads/day → ~35,000/sec
Posts:        each user posts ~0.5/day → 150M/day → ~1,700/sec
Avg follows:  200   →  fan-out on write = 1,700 × 200 ≈ 340,000 feed inserts/sec
Feed cache:   keep 500 post IDs × 8 bytes per user ≈ 4 KB × 300M ≈ 1.2 TB (Redis cluster)

3. API

POST /posts                         { text, mediaIds[] }
GET  /feed?cursor={lastPostId}&limit=20
POST /users/{id}/follow
DELETE /users/{id}/follow

4. Data model

posts       post_id (Snowflake), author_id, text, media_urls, created_at
follows     follower_id, followee_id           (both directions indexed)
feed cache  Redis list  feed:{userId} → [post_id, post_id, ...]  (latest ~500)

5. High-level design

6. Deep dives — the fan-out decision

The standard answer is hybrid. Push posts from normal users into followers' feeds. For celebrities (say > 100K followers), don't fan out; instead, when a user opens their feed, pull recent posts from the few celebrities they follow and merge them in.

• Store IDs, not posts, in the feed cache. Hydrate from a post cache. Editing a post then updates one place.
• Only active users get pre-built feeds. For someone returning after months, build the feed on demand.
• Ranking. Chronological is simplest. For "relevant" feeds, fetch ~500 candidates, score them (likes, relationship, recency) with a ranking service, return the top 20.
• Pagination. Cursor-based (?cursor=lastPostId), not offset — new posts arriving would shift offsets.
• Media via object storage + CDN.

7. Bottlenecks & trade-offs

• Celebrity posts → hybrid model.
• Fan-out lag → acceptable; the feed is eventually consistent. The author sees their own post immediately (read-your-writes by inserting it client-side or into their own feed first).
• Redis memory → cap each feed at ~500 IDs; older pages fall back to the DB.

29. Notification System

1. Requirements

• Functional: send via push (iOS/Android), SMS, email, in-app; templates; user preferences and opt-outs; scheduled and bulk sends; delivery status.
• Non-functional: at-least-once delivery (no silent loss), no duplicates the user notices, soft real-time (seconds), handle spikes (a marketing blast to 10M users).

2. Estimates

Daily:   10M push + 1M SMS + 5M email  ≈ 16M/day ≈ 200/sec avg, spikes of 50,000/sec

The spike number matters more than the average — it's why queues are essential here.

3. API

POST /notifications
{ userId, type: "order_shipped", data: { orderId: 4471 },
  channels?: ["push", "email"], idempotencyKey: "order-4471-shipped" }
→ 202 Accepted { notificationId }

202, not 200: the request is accepted and will be processed asynchronously.

4. Data model

user_preferences  user_id, channel, opted_in, quiet_hours
devices           user_id, device_token, platform
templates         type, channel, subject, body_with_{placeholders}
notification_log  notification_id, user_id, channel, status (queued|sent|failed|opened), attempts

5. High-level design

6. Deep dives

• Why queues. They absorb spikes, let each channel scale separately, and survive provider outages — messages wait instead of being lost.
• Reliability. Workers ack the queue only after the provider accepts the message. Failures retry with exponential backoff; after N attempts they go to a dead-letter queue for inspection.
• No duplicates. Retries mean at-least-once, so deduplicate: store the idempotencyKey (or notificationId) in Redis with a TTL and skip if already sent.
• Preferences & quiet hours are checked before queueing. Legal requirement for marketing email: honour unsubscribes.
• Rate limiting per user — nobody wants 40 pushes an hour. Group or digest low-priority ones.
• Priority. Separate high-priority queues (OTP codes, security alerts) from bulk marketing.
• Tracking. Providers call back webhooks for delivered/bounced/opened; update the log.

30. File Storage & Sync (Dropbox / Google Drive)

1. Requirements

• Functional: upload/download files; sync across devices; version history; share with others; offline edits that sync later.
• Non-functional: never lose data (very high durability); large files (up to 50 GB); save bandwidth; sync within seconds.

2. Estimates

Users:     50M, avg 10 GB each → 500 PB total (object storage, not a DB)
Uploads:   ~2M file changes/day → ~25/sec avg, but each can be large
Chunk:     4 MB → a 1 GB file = 256 chunks

3. API

POST /files/upload-session  { path, size, chunkHashes[] }
     → { missingChunks[], presignedUrls[] }      // only upload what the server lacks
PUT  {presignedUrl}          (client → object storage directly)
POST /files/commit          { path, chunkHashes[], baseVersion }
GET  /files/changes?cursor=  → list of changes since cursor   (sync)
GET  /files/{id}/download    → chunk URLs

4. Data model

files          file_id, owner_id, path, latest_version, is_deleted
file_versions  file_id, version, chunk_hashes[], size, modified_by, created_at
chunks         chunk_hash (SHA-256) → object storage key, ref_count
changes        user_id, cursor (increasing), file_id, version    // sync journal

5. High-level design

6. Deep dives

• Chunking + dedup. Each chunk is named by its content hash. If the server already has that hash (from any user, or an earlier version), it isn't uploaded again. Editing one paragraph of a 1 GB file re-uploads one 4 MB chunk.
• Resumable uploads. A dropped connection only loses the chunk in flight.
• Presigned URLs. Clients upload directly to S3, so app servers never carry the heavy bytes.
• Metadata consistency. Use a SQL database with transactions: committing a new version must be all-or-nothing.
• Conflicts. Two devices edit offline. The commit includes baseVersion; if it's not the latest, the server rejects it and the client saves a "conflicted copy" rather than silently overwriting.
• Sync. Each device keeps a cursor into the changes journal and asks "what changed since cursor X?". A long-poll or WebSocket just says "something changed, go ask".
• Durability. Object storage replicates across zones (S3 promises 11 nines). Old versions are kept; chunks are deleted only when no version references them (ref_count = 0).

31. Video Streaming (YouTube / Netflix)

1. Requirements

• Functional: upload video; watch on any device; multiple resolutions; search; view counts, likes.
• Non-functional: smooth playback with fast start (< 2 s) worldwide; uploads can take minutes to process; huge storage and bandwidth; very read-heavy.

2. Estimates

Uploads:    500 hours of video per minute
Storage:    1 hour ≈ 1 GB raw → ~3 GB across all renditions
            500 × 60 × 24 × 3 GB ≈ 2 PB per day
Viewing:    1B hours watched/day; bandwidth is the #1 cost → CDN is mandatory

3. API

POST /videos                 { title, description } → { videoId, uploadUrl (presigned, resumable) }
GET  /videos/{id}            → metadata + manifest URL
GET  {cdn}/videos/{id}/master.m3u8   → list of qualities
GET  {cdn}/videos/{id}/720p/seg_0042.ts   → 4-second segment

4. Data model

videos      video_id, owner_id, title, status (uploading|processing|ready), duration, created_at
renditions  video_id, resolution, bitrate, manifest_path
views       counted in a stream processor, stored as aggregates (not one row per view)

5. High-level design

6. Deep dives

• Transcoding (converting to different formats/sizes) is slow and CPU-heavy, so it's a queue of jobs. Split the video into pieces and transcode them in parallel on many workers; stitch the results. Status goes processing → ready.
• Adaptive bitrate streaming (HLS or DASH). Each quality is cut into ~4-second segments. The manifest file lists them. The player measures download speed and picks the best quality it can sustain — switching mid-video without stopping.
• CDN. Popular videos are cached at edges worldwide. Netflix even places servers inside ISPs. The long tail of rarely watched videos is served from origin or regional caches.
• Resumable uploads for large files — upload in parts, retry just the failed part.
• View counts — don't write one DB row per view. Stream events through Kafka, count in batches, and accept that counts lag slightly.
• Cost. Bandwidth and storage dominate. Keep fewer renditions for unpopular videos; use cheaper cold storage for old ones.

32. Ride Sharing (Uber / Lyft)

1. Requirements

• Functional: rider requests a ride; see nearby drivers; match a driver; live tracking; fare estimate; payment; ratings.
• Non-functional: matching in seconds; location updates in near real time; a driver must never be matched to two riders; high availability.

2. Estimates

Active drivers:     5M, location update every 4 s → 1.25M writes/sec
Ride requests:      20M/day → ~250/sec (peak ~2,000)
Location data:      mostly in memory; only the latest position per driver matters for matching

The location write rate is the headline number. It rules out writing every update into a normal SQL database.

3. API

PUT  /drivers/me/location     { lat, lng }         (every 4 s, often over WebSocket)
POST /rides                    { pickup, dropoff }  → { rideId, fareEstimate }
GET  /rides/{id}                → status, driver, driver location
POST /rides/{id}/accept         (driver)
WebSocket: live location + status updates for an active trip

4. Data model

driver_locations (Redis GEO / in-memory)  driver_id → lat, lng, geohash, status, updated_at
rides (SQL)      ride_id, rider_id, driver_id, status, pickup, dropoff, fare, timestamps
trip_path        ride_id, points[]   (written in batches, for receipts and disputes)

5. High-level design

6. Deep dives

• Geohash. Encodes a lat/lng into a short string like tdr1w. Nearby points share a prefix. Longer string = smaller cell. To find drivers near a rider: take the rider's cell plus its 8 neighbours, list drivers in those cells, then sort by real distance or ETA. Redis has this built in (GEOADD, GEOSEARCH).
• Quadtree. A tree that splits the map into four squares, and keeps splitting busy squares until each holds a manageable number of drivers. Adapts to density (Manhattan gets tiny cells, the countryside huge ones). Geohash is simpler to shard; quadtree adapts better.
• Handling 1.25M updates/sec. Keep only the latest position in memory; shard the geo index by region/city. Write the full path to durable storage in batches, not per update.
• No double booking. When offering a ride to a driver, atomically set their status from available to offered (a Redis SET NX lock or a conditional DB update). If they don't accept in ~10 s, release and try the next driver.
• Trip state machine: requested → matched → driver arriving → in progress → completed / cancelled. Every transition is validated and stored.
• Surge pricing — compare demand (requests) vs supply (free drivers) per geohash cell every minute.
• Payments go through an external provider with idempotency keys so a retried charge never bills twice.

33. Web Crawler

1. Requirements

• Functional: crawl pages from seeds; store page content for indexing; re-crawl pages periodically.
• Non-functional: scale to billions of pages; polite (obey robots.txt, don't overload any site); robust to bad HTML, traps and slow servers; avoid duplicates.

2. Estimates

Target:    1B pages per month → ~400 pages/sec
Page size: ~500 KB → 500 TB per month of raw HTML (compress, store in object storage)

3. Components (the "API" here is the pipeline)

Seed URLs → URL Frontier (queue) → Fetcher → Parser → Link extractor
                 ^                                         |
                 |---- URL filter + "seen?" check ---------|
Fetched pages → content "seen?" check → object storage → indexer

4. Data

URL frontier     priority queues + per-host queues
seen URLs        Bloom filter / hash set of normalised URLs (billions)
seen content     hash (SimHash) of page content, to skip mirrors and duplicates
pages            object storage: url, fetched_at, content (compressed)
robots cache     host → robots.txt rules, crawl delay

5. Deep dives

• URL frontier is the heart. Two levels: priority queues (important/frequently changing pages first) feed per-host queues. Each worker takes one host at a time and waits between requests to that host — that's politeness.
• Dedup URLs. Normalise first (lowercase host, remove fragments and tracking params), then check a Bloom filter — a compact structure that answers "definitely new" or "probably seen". Billions of URLs in a few GB of memory.
• Dedup content. Many URLs serve the same page. Hash the content; skip if seen.
• DNS is a hidden bottleneck — cache DNS results.
• Traps. Infinite calendars or ?page=1,2,3… loops. Cap URL length and depth per site.
• Distribution. Partition by host (hash of hostname → worker), so one worker owns each site and politeness is easy.
• Re-crawling. Pages that change often get crawled more often; track change frequency per URL.

34. Search Autocomplete (Typeahead)

1. Requirements

• Functional: top-k (e.g. 5) suggestions per prefix, ranked by popularity; optionally personalised and trending.
• Non-functional: < 100 ms end to end; very high read rate; suggestions can be minutes to hours stale.

2. Estimates

Searches:   5B/day, ~6 keystrokes each → 30B lookups/day → ~350,000/sec
            (debouncing on the client cuts this a lot)

3. API

GET /suggest?q=new%20y&limit=5  → ["new york", "new year", "new york times", ...]

4. Data structure — the trie

(root)
 └ n
   └ e
     └ w          top5: [new york, new year, news, ...]
       └ " "
         └ y      top5: [new york, new year, new york times, ...]

A trie (prefix tree) has one node per character. The key optimisation is to store the top-k results in each node, so answering a prefix is a walk down a few nodes — no sorting at request time.

5. Design

• Two paths. The serve path reads a prebuilt trie from memory (or a key-value store of prefix → top5 in Redis). The build path runs offline: collect search logs → count query frequency (e.g. hourly/daily with Spark) → build a new trie → swap it in.
• Sharding. Split by prefix range (a–f, g–m…), balanced by traffic rather than alphabet, since some letters are far more common.
• Caching. Short prefixes ("a", "th") are requested constantly — cache them at the CDN and in the browser.
• Client tricks. Debounce (wait ~150 ms after typing stops), cancel stale requests, and reuse results: if you already have suggestions for "new", filter them locally for "new y".
• Trending. A streaming job (Kafka + Flink) boosts queries spiking in the last few minutes, merged with the daily results.
• Filtering. Remove offensive or dangerous suggestions before publishing the trie.

Cheat Sheet — If You Hear X, Reach for Y

Trade-offs to Mention

Numbers to Remember

Common Mistakes in Interviews

• Jumping into drawing before asking about requirements and scale. Spend the first 5 minutes asking.
• Staying silent. They grade your thinking. Talk through every choice.
• Buzzword soup — "Kafka, Kubernetes, microservices" with no reason. Every box needs a "because".
• Over-engineering a system for 1,000 users. Design for the stated scale, then explain how you'd grow.
• No numbers. Even rough estimates show you know what's big and what's small.
• Ignoring failure. Always say what happens when a server, DB or dependency dies.
• Only the happy path. Mention retries, duplicates, timeouts, and hot spots.
• Single points of failure left in the diagram — one DB, one LB. Show replicas.
• Not driving. Don't wait to be asked; propose the next step ("Shall I go deeper on the feed generation?").
• Defending a choice to the death. If the interviewer pushes back, weigh their point — adapting is a plus.

Interview Q&A — quick answers

Fundamentals

• Vertical vs horizontal scaling? Bigger machine vs more machines. Vertical is simple but has a ceiling and one point of failure; horizontal needs stateless servers and a load balancer but scales far.
• Why make servers stateless? So any server can handle any request. Then you can add, remove or replace servers freely. Keep session data in Redis or a token.
• Latency vs throughput? Latency is how long one request takes; throughput is how many requests per second you handle.
• What does 99.99% availability mean? About 52 minutes of downtime a year. Each extra nine costs much more.
• What is a single point of failure? A component whose failure takes down the whole system. Remove it with redundancy.
• L4 vs L7 load balancer? L4 routes by IP/port (fast, blind to content); L7 reads HTTP (can route by path, header, cookie).

Caching & data

• Cache-aside? App checks cache; on a miss it reads the DB and fills the cache. The most common pattern.
• Write-through vs write-back? Write-through writes cache and DB together (safe, slower). Write-back writes cache first and DB later (fast, can lose data).
• How do you invalidate a cache? TTLs plus deleting the key on update. Delete rather than update to avoid races.
• Cache stampede? A popular key expires and thousands of requests hit the DB at once. Fix with a lock so one request refills, or refresh early.
• SQL or NoSQL? SQL for relationships, transactions and correctness. NoSQL for huge scale, simple access patterns and flexible schemas.
• Replication vs sharding? Replication copies the same data (more reads, fault tolerance). Sharding splits different data across machines (more writes, more storage).
• What is consistent hashing? Servers and keys on a ring; a key goes to the next server clockwise. Adding or removing a server moves only ~1/n of keys.
• What is replication lag? Followers are behind the leader, so a read right after a write may return old data. Fix with read-your-writes (read from the leader for that user briefly).
• What is an index's cost? Faster reads, slower writes, more storage.

Distributed systems

• CAP theorem? During a network partition you must choose consistency or availability. Partitions will happen, so it's really C vs A when things break.
• PACELC? If Partition, choose A or C; Else, choose Latency or Consistency.
• Eventual consistency? All copies will match if writes stop — but reads may briefly be stale.
• Queue vs pub/sub? A queue gives each message to one consumer (work sharing); pub/sub gives each message to every subscriber (broadcast).
• At-least-once vs exactly-once? At-least-once may duplicate; make consumers idempotent. True exactly-once is expensive and rare.
• What is idempotency? Doing it twice has the same effect as once. Essential for retries — use idempotency keys.
• 2PC vs saga? 2PC locks all participants until everyone agrees (consistent, slow, fragile). A saga runs local transactions and undoes finished steps with compensating actions if a later one fails.
• How do you generate unique IDs at scale? Snowflake: timestamp + machine ID + sequence — unique, sortable, no central coordinator.
• What is a circuit breaker? After repeated failures it stops calling a dependency for a while and fails fast, so one bad service doesn't take everything down.
• Why add jitter to retries? So thousands of clients don't retry at the same instant and overload the recovering service again.

Communication & APIs

• REST vs GraphQL vs gRPC? REST: simple, cacheable, public APIs. GraphQL: client picks fields, good for varied frontends. gRPC: fast binary calls between internal services.
• Polling vs long polling vs WebSocket vs SSE? Polling asks repeatedly; long polling holds the request until data arrives; WebSocket is a two-way open connection; SSE is a one-way server-to-client stream.
• Offset vs cursor pagination? Offset is simple but slow on deep pages and skips/duplicates when data changes; cursor ("after id X") is stable and fast.
• What does an API gateway do? One entry point: routing, auth, rate limiting, logging, SSL termination.
• Why presigned URLs for uploads? The client uploads straight to object storage, so your servers don't carry large files.

Case-study one-liners

• URL shortener: counter ranges + base62, cache-aside redirects, 301 vs 302 for analytics.
• Chat: WebSockets, presence map to route to the right server, store then deliver, Snowflake ordering.
• News feed: hybrid fan-out — push for normal users, pull for celebrities.
• Notifications: per-channel queues, retries + dead-letter queue, dedupe with idempotency keys.
• Dropbox: content-hashed chunks, upload only missing chunks, metadata in SQL.
• YouTube: transcode to many qualities, HLS segments, CDN, adaptive bitrate.
• Uber: in-memory geohash index, lock the driver when matching.
• Crawler: URL frontier with per-host politeness, Bloom filter for seen URLs.
• Autocomplete: trie with top-k stored per node, rebuilt offline, cached at the edge.

Written-Exam Answer Template

Q: Design a ______.

1. Requirements
   Functional:      3–5 bullet points (what the user can do)
   Non-functional:  scale, latency, availability, consistency
   Assumptions:     "Assume 10M daily users, read:write = 100:1"

2. Estimates
   QPS (avg and peak), storage per year, bandwidth — show the working

3. API
   3–5 endpoints with method, path, request and response

4. Data model
   Main tables/collections with key fields; SQL or NoSQL and WHY

5. High-level design
   A labelled box-and-arrow diagram:
   client → LB → services → cache → DB / queue / object storage / CDN
   One sentence describing the main read path and write path

6. Deep dive (2–3 components)
   The hardest part of THIS problem (e.g. fan-out, matching, ID generation)

7. Scaling & reliability
   Sharding, replication, caching, queues; what happens when X fails

8. Trade-offs
   2–3 "I chose A over B because…, the cost is…"

9. Summary
   3 lines: the core idea of the design

Learning Path

1. Learn the framework (section 2) until you can run it without notes.
2. Practise estimates — do the maths for 3 systems out loud with round numbers.
3. Master the building blocks — for each, be able to say what it is, when to use it, and its cost.
4. Do the case studies — URL shortener first, then chat, news feed, and notifications. Draw each from memory.
5. Mock interviews — 45 minutes, timer on, talking out loud. Record yourself once; you'll spot silences and hand-waving.
6. Read real architectures — engineering blogs from Netflix, Uber, Discord, Slack and Instagram show these patterns in production.
7. Night before — read the cheat sheet, trade-offs, numbers and case-study one-liners on this page. Nothing new.