System Design

Fundamentals: scalability, latency and availability

Every design discussion comes back to a few mental models: how the system grows (scalability), how fast it answers (latency) and how much work it can do (throughput), and how often it is up (availability).

Vertical vs horizontal scaling

Statelessness is the enabler: if app servers keep no session state (sessions live in Redis, a database or a signed token such as a JWT), any server can handle any request, so you can add, remove or replace servers freely and fail over instantly.

Latency vs throughput

• Latency is the time to complete one request. Throughput is requests (or bytes) per second. Batching increases throughput but can increase latency; you optimise the one the product needs.
• Report latency as percentiles, not averages: p50 (median), p95, p99, p99.9. The average hides the slow tail.
• Tail latency amplification: if one page load fans out to 100 backend calls and each has a 1 percent chance of being slow, about 63 percent of page loads hit at least one slow call (1 - 0.99^100). Mitigations: hedged or backup requests, timeouts, fewer fan-out hops, caching.
• Little's law: concurrent requests in flight = arrival rate x average latency. At 1,000 requests per second and 200 ms latency, about 200 requests are in flight, which sizes your thread pools and connection pools.

Availability and the nines

• Components in series multiply: a request that needs a 99.9% service and a 99.9% database is only about 99.8% available.
• Redundant components in parallel: two independent 99% replicas give 1 - 0.01^2 = 99.99%, provided failures are truly independent (different racks, zones or regions).
• Single point of failure (SPOF): any component whose failure takes the whole system down. Remove it with redundancy, health checks and automatic failover.
• SLI, SLO, SLA: an SLI is a measured indicator (for example, the fraction of requests under 300 ms); an SLO is the internal target (99.9% of requests under 300 ms); an SLA is the contractual promise to customers with penalties. The gap between 100% and the SLO is the error budget that teams can spend on risky launches.
• RTO and RPO: recovery time objective (how long you may be down) and recovery point objective (how much recent data you may lose) drive backup and multi-region choices.

Consistency, CAP and PACELC

As soon as data is copied to more than one machine, copies can disagree. Consistency models define what a reader is allowed to see; CAP and PACELC describe what you give up to get stronger guarantees.

CAP theorem

In a distributed system, when a network Partition happens you can keep only one of Consistency (every read sees the latest write, specifically linearizability) or Availability (every request to a non-failed node gets a non-error response). Because partitions cannot be ruled out in real networks, the practical choice is CP or AP during a partition.

• CP: reject or block requests on the minority side rather than diverge. Examples: bank ledgers, inventory reservation, leader election and configuration stores such as ZooKeeper or etcd.
• AP: keep serving and reconcile later (eventual consistency, conflict resolution). Examples: shopping carts, social feeds, like counts, DNS, Cassandra or DynamoDB in their default modes.
• "CA" only exists when there is no partition, which in practice means a single node or a single tightly coupled site.

PACELC

PACELC extends CAP: if there is a Partition, choose A or C; Else (normal operation), choose Latency or Consistency. Synchronous replication across regions is consistent but slow; asynchronous replication is fast but readers may see stale data. DynamoDB and Cassandra are typically PA/EL; Spanner and most relational setups with synchronous replicas are PC/EC.

Consistency models (strongest to weakest)

Quorums

With N replicas, a write waits for W acknowledgements and a read queries R replicas. If R + W > N, every read set overlaps every write set, so a read sees at least one copy of the latest write. N = 3, W = 2, R = 2 is a common balance; W = 1, R = 1 is fast but only eventually consistent; W = N makes writes fail if any replica is down. Conflicts in leaderless systems are resolved with version vectors, last-writer-wins timestamps (can lose updates) or CRDTs (data types that merge automatically).

ACID vs BASE

Isolation anomalies to know: dirty read, non-repeatable read, phantom read, lost update and write skew. Serializable isolation prevents all of them at a performance cost; many databases default to read committed or snapshot isolation.

Back-of-envelope estimation

Estimation turns requirements into numbers that justify your design: is it read-heavy or write-heavy, does the data fit on one machine, how many servers do you need? Precision does not matter; stating assumptions and rounding aggressively does.

Numbers to memorise

Latency numbers every engineer should know (order of magnitude)

Takeaway: memory is far faster than SSD, SSD far faster than disk, and anything crossing a region costs tens to hundreds of milliseconds. Keep hot data in memory and keep cross-region round trips off the request path.

Formulas

• QPS = daily active users x actions per user per day / 86,400. Peak QPS = QPS x peak factor.
• Storage = new items per day x bytes per item x retention days x replication factor.
• Bandwidth = QPS x average response size (separately for ingress and egress).
• Cache size (80/20 rule) = about 20 percent of the daily read working set.
• Servers = peak QPS / QPS per server, plus headroom (for example 30 percent) and N+1 or N+2 for failures.

Worked example: URL shortener

Assume: 100 M new short URLs per day, read:write = 10:1, keep 5 years, ~500 bytes per record

Writes: 100 M / 86,400            ~ 1,160 per second   (peak ~ 3,000)
Reads:  10 x 1,160                ~ 11,600 per second  (peak ~ 30,000)
Storage: 100 M x 500 B x 365 x 5  ~ 91 TB  (x3 replication ~ 275 TB)
Keys needed: 100 M x 365 x 5      ~ 183 billion
Base62 length 7: 62^7             ~ 3.5 trillion  -> 7 characters is plenty
Cache: hot-set proxy = 20% of daily *new* URLs x 500 B ~ 10 GB  -> fits in RAM
        (distinct URLs among 1 B daily reads is unknown; 20% of new keys is the usual interview stand-in)

Conclusions the numbers force: the system is read-heavy (so cache aggressively and use a CDN), storage outgrows one machine within a few years (so plan for a sharded key-value store), and 7-character keys are enough.

Load balancers, API gateways, DNS and CDNs

Before a request reaches your code it passes through DNS (which finds an address), often a CDN (which may answer from a nearby edge), and a load balancer or API gateway (which picks a healthy server and applies cross-cutting policy).

Client
  |  DNS lookup (GeoDNS / latency-based routing picks nearest region)
  v
CDN edge  --cache hit-->  response (images, JS, video segments)
  | miss / dynamic
  v
L4/L7 load balancer (TLS termination, health checks)
  v
API gateway (auth, rate limit, routing, request IDs)
  v
Stateless service instances (autoscaled)
  v
Cache  ->  Database  ->  Queue  ->  Workers

Load balancers

Algorithms: round robin (equal servers), weighted round robin (mixed capacity), least connections (long-lived or uneven requests), least response time, IP or consistent hashing (session affinity or cache locality), and "power of two random choices" (pick two at random, send to the less loaded, which is simple and close to optimal).

Health checks remove failing instances. The load balancer itself must not be a SPOF: run it as an active-passive or active-active pair with a floating IP, or use a managed, regionally redundant service. DNS round robin or anycast spreads traffic across load balancers or regions.

API gateway and reverse proxy

A reverse proxy sits in front of servers (Nginx). An API gateway is a reverse proxy with API-level concerns: authentication, rate limiting, request validation, routing to microservices, protocol translation (REST to gRPC), request aggregation, and adding correlation IDs for tracing. A service mesh (Envoy sidecars with Istio or Linkerd) moves similar concerns (mTLS, retries, timeouts, metrics) to service-to-service traffic.

DNS

DNS resolves names to IPs through a hierarchy (resolver, root, top-level domain, authoritative server) with caching at every level controlled by TTLs. GeoDNS or latency-based routing sends users to the nearest region; low TTLs allow faster failover but increase DNS traffic. Anycast announces the same IP from many locations so routing delivers users to the nearest one.

CDN

A content delivery network caches content on edge servers close to users, cutting latency and origin load. It is essential for images, video, JavaScript and CSS at global scale, and can also cache some API responses, terminate TLS and absorb DDoS traffic.

• Pull CDN: the edge fetches from the origin on the first miss and caches by TTL. Simple; first request is slow.
• Push CDN: you upload content to the CDN ahead of time. Good for large, predictable assets such as video releases.
• Invalidation: use versioned (content-hashed) file names such as app.3f9a2c.js so you never need to purge; purge APIs are slow and eventually consistent.
• Signed URLs protect private content on the CDN with expiring tokens.

Caching

A cache stores the results of expensive work (database queries, computed pages, remote calls) in fast storage, usually memory, so later requests are served quickly. Caching appears at every layer: browser, CDN, API gateway, application (in-process), distributed cache (Redis, Memcached), and inside the database (buffer pool).

Read and write strategies

# cache-aside read and invalidate-on-write
def get_user(user_id):
    key = f"user:{user_id}"
    user = cache.get(key)
    if user is None:
        user = db.query_user(user_id)
        cache.set(key, user, ttl=300 + random.randint(0, 60))   # jitter
    return user

def update_user(user_id, fields):
    db.update_user(user_id, fields)      # 1. write the source of truth
    cache.delete(f"user:{user_id}")      # 2. delete, don't set, the cached copy

Deleting rather than updating the cache avoids a race where two concurrent writers leave the older value in the cache. A small race still exists (a reader loads the old value just before the delete completes); short TTLs, delayed double-delete, or streaming invalidations from the database change log (change data capture) narrow it further.

Eviction policies

• LRU (least recently used): evict the item not used for the longest time. Good default for temporal locality; O(1) with a hash map plus doubly linked list.
• LFU (least frequently used): evict the least-used item. Better for stable popularity; needs frequency decay so old favourites do not stay forever.
• FIFO and random: simple, sometimes good enough.
• TTL: expire after a fixed time, which bounds staleness regardless of eviction.

Cache problems and fixes

Databases, indexes, replication and sharding

The database is usually the hardest part to scale because it holds state. Choose the storage model from the access patterns, then scale reads with replication and caching, and scale writes and storage with sharding.

SQL vs NoSQL

OLTP vs OLAP: OLTP systems handle many small, indexed reads and writes with low latency (the app database). OLAP systems handle few, huge scans and aggregations (the warehouse). Keep them separate, feeding the warehouse through ETL or change data capture.

Indexes and storage engines

• A B-tree / B+ tree index keeps keys sorted in wide, shallow pages, giving O(log n) lookups and efficient range scans. Index columns used in WHERE, JOIN and ORDER BY clauses.
• Costs: every insert or update must maintain each index (slower writes), plus extra storage. Do not index everything on write-heavy tables.
• Composite indexes follow the leftmost-prefix rule: an index on (country, city) helps queries on country or on country + city, not on city alone.
• A covering index includes every column a query needs, so the table itself is never read.
• LSM trees (Cassandra, RocksDB, LevelDB) buffer writes in memory (memtable) and flush sorted files (SSTables) that are merged in the background (compaction). Writes are sequential and very fast; reads may check several files, helped by Bloom filters.
• An inverted index maps each word to the documents containing it; it powers full-text search.

Replication

• Synchronous replication waits for the follower before acknowledging (durable, slower); asynchronous does not (fast, may lose data). Semi-synchronous waits for one follower.
• Read-your-writes on top of async replicas: route a user's reads to the leader for a short time after they write, or track the replication position they need.
• Failover must avoid split brain (two leaders): use a consensus-based coordinator (Raft, Paxos, ZooKeeper or etcd) and fencing tokens.

Sharding (partitioning)

Sharding splits data across nodes by a shard key so each node stores and serves a subset. It scales writes and storage beyond one machine.

Choosing a shard key: it should have high cardinality, spread load evenly, and match the dominant query so most requests touch one shard (for example user_id for a user's data, conversation_id for chat messages). Hard parts: hot shards (a celebrity), cross-shard joins and transactions (avoid them or use sagas), secondary indexes (local per shard or global), and resharding without downtime.

Consistent hashing

Map both nodes and keys onto a hash ring; each key belongs to the first node clockwise. Adding or removing a node moves only the keys between it and its neighbour, about 1/N of the data, instead of nearly all keys as with hash mod N. Virtual nodes (each physical node appears at many points on the ring) smooth out the load and let bigger machines take more points. Used by DynamoDB, Cassandra, distributed caches and load balancers.

Hash ring (positions 0 .. 2^32), walking clockwise:

  0 ---- k1 ---- [N1] ---- k2 ---- k3 ---- [N2] ---- k4 ---- [N3] ---- (wraps to 0)

  k1 -> N1     k2, k3 -> N2     k4 -> N3

Add node N4 between k2 and k3:
  0 ---- k1 ---- [N1] ---- k2 ---- [N4] ---- k3 ---- [N2] ---- k4 ---- [N3]
  only k2 moves (N2 -> N4); every other key stays where it was

Message queues, streams and idempotency

A message queue or log sits between producers and consumers so they no longer have to be up, fast, or scaled at the same moment. This is the backbone of asynchronous and event-driven architectures.

Why use one

• Decoupling: producers do not need to know who consumes or whether they are up.
• Load levelling: absorb spikes and let consumers work at a steady rate.
• Asynchrony: return to the user quickly and do slow work (emails, transcoding, fan-out) in the background.
• Fan-out: one event, many independent consumers (analytics, search indexing, notifications).
• Retries and durability: failed work is redelivered rather than lost.

Delivery semantics

End-to-end exactly-once delivery across arbitrary systems is not achievable in general; what you build is at-least-once delivery with idempotent consumers.

Idempotency

An operation is idempotent if doing it twice has the same effect as doing it once. SET balance = 100 is idempotent; balance += 10 is not. Retries, timeouts and at-least-once queues all cause duplicates, so every write path that can be retried must be idempotent.

# idempotency key pattern for a payment API
def charge(request):
    key = request.headers["Idempotency-Key"]           # client-generated UUID
    existing = store.get(key)
    if existing:
        return existing.response                        # replay, do not re-charge
    with db.transaction():
        if not store.insert_if_absent(key, status="in_progress"):
            return conflict_or_wait()                   # a concurrent duplicate
        result = payments.charge(request.amount)
        store.update(key, status="done", response=result)
    return result

Other techniques: unique constraints on a natural key (order ID), conditional writes with version numbers (optimistic concurrency), and consumer-side "already processed message IDs" tables.

Patterns around queues

• Dead-letter queue (DLQ): after N failed attempts, park the message for inspection instead of blocking the queue forever (a "poison message").
• Retry with exponential backoff and jitter: wait 1 s, 2 s, 4 s ... plus randomness so retries do not synchronise.
• Ordering: Kafka orders only within a partition, so partition by the entity whose order matters (for example user_id or order_id).
• Transactional outbox: write the business row and an "outbox" event row in the same database transaction; a relay publishes outbox rows to the queue. This avoids the dual-write problem where the DB commit succeeds but the publish fails, or vice versa.
• Saga: a long business transaction across services as a sequence of local transactions, each with a compensating action (refund, release inventory) if a later step fails. Choreographed through events or orchestrated by a coordinator.
• Backpressure: when consumers fall behind, slow producers (bounded queues, rate limits) or scale consumers; watch consumer lag as a key metric.
• Event sourcing and CQRS: store the log of events as the source of truth and build read-optimised views from it; separate the write model from read models.

API design and rate limiting

The API is the contract between clients and your system. Defining it early pins down what the system must do. Rate limiting protects that API from abuse, runaway clients and overload.

API styles

Good API design checklist

• Resource-oriented URLs and correct methods: GET /users/{id}, POST /orders, PATCH for partial updates. GET, PUT and DELETE should be idempotent; POST is not unless you add an idempotency key.
• Pagination: cursor-based (?after=opaque_cursor&limit=50) is stable under inserts and scales; offset pagination gets slow and skips or repeats rows when data changes.
• Versioning: /v1/ in the path or a header; only make additive, backwards-compatible changes within a version.
• Consistent errors with meaningful status codes: 400 bad input, 401 unauthenticated, 403 forbidden, 404 not found, 409 conflict, 429 too many requests, 5xx server errors.
• Authentication (OAuth 2.0 or tokens), authorisation checks on every resource, TLS everywhere.
• Idempotency keys on retries of non-idempotent operations; request IDs for tracing.
• Batch endpoints and field filtering to cut round trips for mobile clients.

POST /v1/urls                  { "long_url": "...", "custom_alias": null, "expires_at": null }
  -> 201 { "short_url": "https://sho.rt/aZ3kP9q" }
GET  /{short_key}              -> 301 or 302 Location: long_url
GET  /v1/users/{id}/feed?cursor=abc&limit=20
  -> 200 { "items": [...], "next_cursor": "def" }

Rate-limiting algorithms

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate, self.capacity = rate, capacity
        self.tokens, self.last = capacity, time.monotonic()
    def allow(self):
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False          # caller returns 429 with a Retry-After header

In a distributed deployment, keep the bucket state in a shared store such as Redis and update it atomically (a Lua script or an atomic increment with expiry) so concurrent gateway nodes do not race. For lower latency, keep local buckets on each node with a share of the global limit and sync periodically, trading some accuracy. Key limits by user, API key, IP or endpoint, and return 429 Too Many Requests with Retry-After and remaining-quota headers.

Reliability, resilience and observability

At scale, something is always failing: a disk, a node, a network link, a dependency, a deploy. Reliable systems assume failure and contain it so a local problem does not become a global outage.

Resilience patterns

Distributed-systems essentials

• Consensus (Raft, Paxos) lets a group of nodes agree on a value or a leader despite failures, as long as a majority is alive; with 5 nodes you tolerate 2 failures. Used for leader election, configuration and locks (etcd, ZooKeeper, Consul).
• Clocks are unreliable: wall clocks drift and jump, so do not order events across machines by timestamp alone. Use logical clocks (Lamport), version vectors, or bounded-uncertainty clocks (Spanner's TrueTime).
• Unique IDs at scale: UUIDs (random, 128-bit, not sortable), Snowflake-style IDs (timestamp + machine ID + sequence; 64-bit and roughly time-ordered), or database ticket servers that hand out ranges.
• Distributed locks need leases with expiry and fencing tokens (monotonic numbers checked by the storage layer) so a paused former holder cannot corrupt data.
• Two-phase commit gives atomic cross-node transactions but blocks if the coordinator fails; microservices usually prefer sagas.
• Gossip protocols spread membership and failure information peer to peer.

Monolith vs microservices

Observability

• Metrics: the RED method for services (Rate, Errors, Duration) and the USE method for resources (Utilisation, Saturation, Errors). The four golden signals: latency, traffic, errors, saturation.
• Logs: structured (JSON), with request IDs, sampled at high volume, scrubbed of personal data.
• Traces: distributed tracing (OpenTelemetry) follows one request across services to find where time goes.
• Alerts on SLO burn rate and user-facing symptoms, not on every internal cause.
• Safe rollout: feature flags, canary deployments (1 percent, then 10, then 50, then 100), automatic rollback on SLO regression, and a kill switch.

The step-by-step design framework

A system design interview is an open-ended conversation, usually 45 to 60 minutes. The biggest failure mode is not a wrong answer but a lack of structure: drawing boxes before understanding the problem, or spending 30 minutes on one detail. Use the same framework every time and say each step out loud.

1. Requirements (5-8 min) Functional: the three to five core features, and what is out of scope. Non-functional: users and scale, read/write ratio, latency target (p99), availability, consistency needs, durability, regions, privacy and compliance. Ask; do not assume.
2. Estimation (3-5 min) Daily active users, read and write QPS (average and peak), storage per year, bandwidth, cache size. Each number should drive a decision.
3. API design (3-5 min) A few core endpoints or RPCs with request and response shapes. This pins down the contract and the data you must store.
4. Data model (3-5 min) Entities, relationships, access patterns, SQL vs NoSQL with a reason, primary keys and partition keys.
5. High-level design (8-10 min) Draw clients, DNS/CDN, load balancer, services, cache, databases, queues and workers. Walk through the main read and write flows end to end.
6. Deep dive (10-15 min) Pick one or two of the hardest parts, or follow the interviewer's lead: sharding, the feed fan-out, consistency, the hot path, the ID generator.
7. Bottlenecks and trade-offs (5 min) Single points of failure, hot keys, scaling limits, what breaks at 10x. Name each trade-off: consistency vs availability, latency vs cost, complexity vs flexibility.
8. Operability and rollout (2-3 min) Metrics, alerts, dashboards, canary rollout, feature flags, kill switch, cost, and how the design evolves.

Generic high-level design
                      +-------+
 Clients --DNS-->     |  CDN  |  (static, media)
   |                  +-------+
   v
+---------------+     +--------------------+     +------------------+
| Load balancer | --> | Stateless services | --> | Cache (Redis)    |
+---------------+     |  (autoscaled)      |     +------------------+
                      +--------------------+ --> | DB primary       |--> read replicas
                              |                  +------------------+
                              v                         (sharded by key)
                      +----------------+     +---------+     +----------------+
                      | Queue / stream | --> | Workers | --> | Blob store,    |
                      +----------------+     +---------+     | search, OLAP   |
                                                             +----------------+

Universal levers to pull

Blueprints I: infrastructure designs

These blueprints are compact starting points. In an interview, run each through the full framework; here the focus is on the core idea, the crux, and what to deep-dive.

URL shortener (TinyURL, bit.ly)

• Requirements: create a short link, redirect quickly, optional custom alias and expiry, click analytics. Read-heavy (about 10:1 or more), p99 redirect under about 50 ms, highly available.
• API: POST /v1/urls returns the short URL; GET /{key} returns a 301 (permanent, cached by browsers, fewer hits but weaker analytics) or 302 (temporary, every click reaches you).
• Key generation options: base62-encode a unique 64-bit ID from a distributed ID generator (Snowflake-style) or from pre-allocated counter ranges per server (no collisions, but sequential keys are guessable, so optionally shuffle or encrypt the ID); or hash the long URL (MD5 or SHA-256) and take 7 characters, checking for collisions; or a key-generation service that pre-creates random unused keys.
• Storage: key-value store mapping key to (long URL, owner, created, expiry), sharded by key. About 91 TB over five years before replication in the worked estimate.
• Read path: CDN or edge cache, then Redis (cache-aside), then the KV store. Hot links are a tiny fraction of keys, so the hit ratio is high.
• Analytics: publish click events to a stream asynchronously (never on the redirect's critical path) and aggregate into a warehouse.
• Extras: rate limit creation, scan for malicious URLs, expire and garbage-collect old links.

POST /urls -> API -> ID generator -> base62(id) -> KV store (sharded by key)
GET /aZ3kP9q -> CDN -> LB -> redirect service -> Redis --miss--> KV store
                                         |
                                         +--> click event -> Kafka -> analytics

Rate limiter (distributed, at the API gateway)

• Requirements: limit requests per user, API key or IP per rule; low added latency (about a millisecond); accurate enough; highly available.
• Algorithm: token bucket for burst tolerance, or sliding window counter for accuracy with O(1) memory.
• State: Redis keyed by limiter:{client}:{rule}, updated atomically with a Lua script (read tokens, refill by elapsed time, decrement, set expiry) so concurrent gateway nodes do not race.
• Rules stored in configuration and cached locally on each gateway node.
• Response: HTTP 429 with Retry-After and X-RateLimit-Remaining headers.
• Failure policy: if Redis is unreachable, fail open (allow traffic, protect availability) for most APIs, or fail closed for expensive or abuse-prone ones; say which and why.
• Scale: shard Redis by client key; for extreme QPS, local in-memory buckets with periodic sync to a global count, accepting small overshoot. Multi-region: per-region limits or asynchronous global aggregation.

Distributed key-value store (Dynamo-style)

• Partitioning: consistent hashing with virtual nodes.
• Replication: each key stored on N = 3 successive nodes on the ring, across failure zones.
• Consistency knob: quorum reads and writes; R + W > N for read-after-write; lower values for speed.
• Conflict handling: version vectors to detect concurrent writes, resolved by the client or last-writer-wins.
• Failure handling: hinted handoff (a neighbour temporarily holds writes for a down node), read repair, and anti-entropy with Merkle trees to find and fix divergent ranges.
• Membership: gossip protocol with failure detection.
• Storage engine: LSM tree (write-ahead log, memtable, SSTables, compaction, Bloom filters), tombstones for deletes.

Distributed cache (Redis Cluster-like)

• Keys hashed into slots (Redis Cluster uses 16,384 hash slots) assigned to primary nodes, each with replicas for failover.
• Clients cache the slot map and are redirected when slots move during resharding.
• Eviction per node (LRU or LFU approximations), TTLs, memory limits.
• Hot keys: client-side local caching, key replication with suffixes, or read from replicas.
• Consistency is best effort: asynchronous replication can lose recent writes on failover, which is acceptable for a cache, not for a source of truth.

Notification system (push, SMS, email)

• Flow: producer services call a notification API (or publish events) with an idempotency key; the service validates, checks user preferences, quiet hours and opt-outs, renders templates, and enqueues per channel.
• Channel workers call provider adapters: APNs (iOS), FCM (Android), SMS gateways, email providers. Separate queues per channel and priority so a slow email provider does not delay urgent push messages.
• Device registry sharded by user or device ID, storing tokens; remove tokens the provider reports as invalid.
• Reliability: at-least-once with dedupe on the idempotency key, retries with backoff, dead-letter queue, provider failover.
• Protection: per-user and per-channel rate limits (avoid spamming), global throttles to respect provider quotas.
• Tracking: delivery, open and click events flow back into analytics; metrics on delivery rate per channel.

Services --> Notification API --> prefs/templates --> per-channel queues
                                                     |       |        |
                                                  push     SMS     email workers
                                                  (APNs/FCM) (gateway) (provider)
                                                     \_______|________/
                                                     retries, DLQ, delivery events

Distributed job scheduler / cron

• Jobs stored in a database with the next run time; an index on next_run_at.
• Scheduler nodes poll for due jobs in time buckets, claiming each atomically (conditional update or lease) so only one node dispatches it; leader election is an alternative.
• Dispatched jobs go on a queue to worker pools; workers heartbeat, and a job whose lease expires is retried.
• Jobs must be idempotent because at-least-once execution is the realistic guarantee.
• Support retries with backoff, timeouts, priorities, dependencies (a DAG, like a workflow engine), and history for auditing.
• Scale by sharding jobs across scheduler partitions; use a timing wheel or delay queue for high volumes of short delays.

Blueprints II: product designs

Product-style designs add large fan-out, real-time connections, media pipelines and geospatial data. The same levers apply, but each has one signature problem to solve.

Chat (WhatsApp, Messenger)

• Requirements: one-to-one and group messages, delivery and read receipts, online presence, offline delivery, message history, media, optional end-to-end encryption. Low latency (under a few hundred ms), messages never lost, ordered per conversation.
• Connections: clients keep a long-lived WebSocket (or MQTT) connection to a gateway fleet; a session registry maps user ID to gateway node.
• Send path: the gateway forwards to the chat service, which assigns a per-conversation sequence number, persists first, acknowledges the sender, then routes to the recipient's gateway, or to a push notification if offline.
• Storage: messages in a wide-column store partitioned by conversation_id and clustered by sequence number (fast "last 50 messages"). Clients sync by "give me everything after sequence N".
• Groups: fan out per member via a queue; for very large groups or channels, recipients pull instead.
• Receipts: sent (server persisted), delivered (recipient device acknowledged), read (recipient opened). Client-generated message IDs make resends idempotent.
• Presence: heartbeats with a TTL in a fast store; publish presence changes only to interested contacts, and throttle.
• End-to-end encryption: the Signal protocol; servers route ciphertext only, which limits server-side search and moderation.

Sender --WebSocket--> Gateway A --> Chat service --persist--> Message store (by conversation_id)
                                        |  ack sender
                                        +--lookup--> Session registry (user -> gateway)
                                        +--online--> Gateway B --WebSocket--> Recipient
                                        +--offline-> Push service (APNs / FCM)

News feed (Twitter/X, Instagram)

• Fan-out on write (push): when a user posts, write the post ID into each follower's precomputed timeline in a cache. Very fast reads; expensive writes for accounts with millions of followers.
• Fan-out on read (pull): build the timeline at read time by merging recent posts of everyone you follow. Cheap writes; slow reads.
• Hybrid (the standard answer): push for ordinary users, pull for celebrities, and merge at read time. Skip fan-out to inactive users.
• Storage: posts in a sharded store keyed by post ID; social graph in its own store; timelines as capped lists of post IDs in Redis; media on a CDN.
• Ranking: candidate generation, then a scoring model (recency, affinity, engagement), then filtering; cursor-based pagination.
• Asynchrony: fan-out workers consume "post created" events from a queue; feeds are eventually consistent, which is acceptable.

File storage and sync (Dropbox, Google Drive)

• Split files into chunks (about 4 MB); identify each by its content hash. Upload only chunks the server does not already have (deduplication and delta sync), resumable on flaky networks.
• Metadata service (relational DB, sharded by user or namespace): files, folders, versions, chunk lists, sharing permissions. Chunks live in object storage.
• Clients upload directly to object storage with pre-signed URLs, keeping large payloads off the app servers.
• Sync: each change bumps a version in a per-user change log; other devices long-poll or subscribe for notifications and pull changes since their cursor.
• Conflicts: if two devices edit the same version, keep both ("conflicted copy") or merge for structured documents.
• Durability through object-store replication or erasure coding; cold data moves to cheaper storage tiers.

Video streaming (YouTube, Netflix)

• Upload: resumable, chunked upload to object storage; a "video uploaded" event starts the pipeline.
• Transcoding pipeline: a DAG of jobs on a queue: split into segments, transcode each into multiple resolutions and bitrates in parallel, generate thumbnails, run content checks, then package as HLS or DASH manifests.
• Delivery: CDNs serve segments; adaptive bitrate players pick the quality segment by segment based on measured bandwidth. Popular content is pre-positioned at edges.
• Metadata (titles, views, comments) in databases and caches; view counts aggregated asynchronously.
• Cost dominates: storage of many renditions and CDN egress, so encode popular titles more aggressively and archive the long tail.

Ride-hailing (Uber) and proximity search

• Drivers send location every few seconds, a very high write rate. Keep current locations in memory in a geospatial index: geohash cells, a quadtree, or S2 or H3 cells, sharded by region.
• "Nearby drivers" queries the rider's cell and its neighbours, ranks candidates by estimated time of arrival, and offers the trip to one driver at a time with a timeout.
• The trip is an explicit state machine (requested, matched, arriving, in progress, completed, cancelled) stored durably; pricing includes surge based on supply and demand per cell.
• Location history streams to a log for analytics, ETA models and fraud detection. Eventual consistency is fine for positions; strong consistency is needed for assignment (a driver must not get two trips), using a conditional update or a lock.
• Proximity services such as Yelp or "find restaurants near me" use the same geospatial indexes, but the data is mostly static, so precomputed indexes and caching dominate.

Typeahead / autocomplete

• A trie of popular queries with the top-k completions cached at each prefix node, built offline from query logs (for example hourly) and served from memory.
• Shard by prefix range; replicate for read throughput; cache hot prefixes at the edge.
• Clients debounce keystrokes (about 100-200 ms) and cache recent results locally.
• Filter offensive or unsafe suggestions; personalise by blending global and user history.

Web crawler

• A URL frontier (prioritised queues) feeds fetcher workers; per-host queues enforce politeness (rate limits and robots.txt).
• Parse pages, extract links, normalise URLs, and dedupe with a Bloom filter or URL-hash store; detect near-duplicate content with content fingerprints (SimHash).
• Store raw pages in object storage; feed an indexing pipeline that builds an inverted index.
• Handle traps (infinite calendars), DNS caching, and recrawl scheduling by page change rate.

More prompts to practise

Mobile and embedded system design

A phone, watch or car head unit is itself a distributed system: apps, framework services, hardware abstraction layers (HALs), a modem and other co-processors talk over IPC, can crash independently, and share scarce resources. Fleets of such devices talk to cloud backends over unreliable networks. Device-side designs are judged on the usual criteria plus power, memory, intermittent connectivity, privacy and the fact that you cannot easily patch a broken device in the field.

On-device constraints that change the design

Distributed-systems patterns inside the phone's telephony stack

The Android telephony stack (apps, framework, RIL, radio HAL, vendor modem software) is a real-time, multi-actor, partially unreliable system inside one device. Its patterns map one-to-one onto general system-design vocabulary:

Blueprint: OTA (over-the-air) update system for 100 million devices

• Build and sign: the build system produces full and delta (binary diff) payloads per source-to-target build fingerprint; payloads and manifests are signed, and devices verify signatures and hashes before applying.
• Device-side safety: A/B (seamless) partitions: install to the inactive slot in the background while the user keeps working, switch slots on reboot, and automatically fall back to the old slot if the new one fails to boot (a boot-success marker). Anti-rollback counters stop downgrade attacks. Virtual A/B with snapshots saves storage.
• Rollout control: staged percentages (for example 1, 10, 50, 100 percent) targeted by model, region, carrier and build; automatic halt if crash rate, boot failures or install errors exceed the baseline; a kill switch via a signed manifest update.
• Distribution: devices check in periodically (with jitter to avoid thundering herds) with their fingerprint; the update server answers from a policy engine; payloads come from a CDN with resumable, range-based downloads, preferring Wi-Fi and charging, respecting user-chosen install windows.
• Telemetry: each device reports download, verify, install and first-boot outcomes, so the fleet dashboard shows success rate per build, model and carrier.
• Recovery: recovery mode and a factory-reset path as last resorts; staged rollouts limit the blast radius so they are rarely needed.

Build system --sign--> Payload store --> CDN
                          |
                    Update policy server  <-- check-in (fingerprint, region, carrier)
                          |  staged %, targeting, kill switch
                          v
Device: download (resumable, Wi-Fi) -> verify signature -> write inactive slot (B)
        -> reboot into B -> boot OK? mark successful : fall back to A
        -> report outcome --> telemetry --> rollout health gate (auto-halt)

Blueprint: fleet telemetry and metrics pipeline

• On device: record events (call drops, registration failures, crashes, battery drain) into a bounded ring buffer; aggregate and sample locally rather than shipping every event; scrub personal data and apply consent.
• Upload: batch uploads opportunistically (Wi-Fi and charging, or piggybacked on other network activity), compressed, with backoff on failure and a cap on data used.
• Ingest: regional collectors write to a stream; schema-versioned events; drop or quarantine malformed data.
• Processing: stream aggregation for near-real-time dashboards; batch jobs into a warehouse partitioned by build, region, carrier and model.
• Analysis: detect regressions by comparing a new build against a baseline cohort with statistical significance, so a handful of noisy devices is not mistaken for a fleet-wide bug; trigger alerts or halt rollouts automatically.

More device-flavoured prompts

Mobile client architecture

• Offline-first: the local database is the UI's source of truth; a sync engine reconciles with the server using change cursors and conflict rules.
• Network layer: one shared client with connection reuse (HTTP/2 or HTTP/3), request deduplication, retries with backoff, and caching headers.
• Background work: OS job schedulers (WorkManager on Android) with constraints such as unmetered network and charging.
• Push, not poll: a push message nudges the app to sync, saving battery and server load.
• Images and media: memory and disk caches, downsampling to display size, progressive loading.
• Server-driven configuration and feature flags to change behaviour without an app release.

Senior and principal expectations: trade-off talk

At senior, staff and principal levels, the question is less "can you produce a working design?" and more "can you lead a design discussion the way you would lead a real architecture review?" Interviewers look for judgement: knowing which problems matter, quantifying them, choosing deliberately, and planning for failure, operations and evolution.

What changes by level

How to talk about trade-offs

• Name the alternatives: "We could fan out on write or on read. Write gives fast reads but costs millions of writes per celebrity post; read is cheap to write but slow to render."
• Tie the choice to a requirement: "Since feed reads outnumber posts 100 to 1 and a 2-second delay is acceptable, I will push for normal users and pull for accounts over about 100,000 followers."
• State what you give up: "The cost is eventual consistency: a follower may see a post a few seconds late."
• Say when you would revisit: "If we need strict ordering across regions later, we would move this to a consensus-backed log."

Trade-offs you should be able to discuss fluently

Senior checklist beyond the happy path

• Failure modes: node, zone and region loss; dependency slowness; overload; bad deploys; data corruption. What is the blast radius, and how is it contained?
• Data lifecycle: retention, deletion (including privacy requests), backups and restore drills, schema migration without downtime (expand, migrate, contract).
• Security and privacy: authentication and authorisation, encryption in transit and at rest, secrets management, abuse and fraud, data residency.
• Operability: SLOs and error budgets, dashboards, alerting, on-call runbooks, capacity planning.
• Rollout and migration: feature flags, canaries, dual writes and backfills, shadow traffic, rollback plans.
• Cost: storage tiers, CDN egress, compute efficiency; call out the dominant cost driver.
• Evolution: what you would build for version 1 versus at 10x and 100x scale.

Consensus, clocks and probabilistic sketches

A few primitives show up in almost every senior design once you have more than one writer or need an approximate answer over huge streams. Know the story of each well enough to draw it, not just name it.

Raft in one picture

1. Leader election: a follower that times out of heartbeats becomes a candidate, increments its term, and asks for votes. A node votes for at most one candidate per term. Majority wins; the new leader sends heartbeats.
2. Log replication: clients write to the leader. The leader appends to its log and ships the entry to followers. The entry is committed once a majority has stored it; then the leader applies it and acknowledges the client.
3. Safety: a candidate can win only if its log is at least as up to date as the voters' logs, so a committed entry cannot be lost. With 2f+1 nodes you tolerate f failures.

Use Raft (etcd, ZooKeeper-style, Consul, TiKV regions) for leader election, configuration, and any small amount of data that must be linearizable. Do not put the request path of a high-QPS data plane through a single Raft group.

Ordering without a global clock

• Lamport clocks: a single counter that increments on every event and is piggy-backed on messages; they give a partial order (causality) but not concurrent-event identity.
• Version vectors: one counter per replica; comparing two vectors tells you happens-before or concurrent (conflict). Used in leaderless stores to detect concurrent writes.
• TrueTime (Spanner): GPS/atomic clocks with a bounded uncertainty interval; commit waits out the uncertainty so commits have a real-time order. Rare outside that design.

Bloom filters and sketches

• Bloom filter: bit array plus k hash functions. add sets k bits; maybe_contains is true if all k bits are set. False positives, never false negatives. ~10 bits/item for a 1 percent false-positive rate. Cannot delete (unless you use a counting Bloom filter). Classic uses: cache penetration ("this key is definitely not in the DB"), crawler URL-seen sets, LSM-tree SSTable indexes.
• Count-Min Sketch: approximate frequencies for heavy hitters in a stream, with bounded overestimate, tiny memory.
• HyperLogLog: approximate distinct count (cardinality) in about 1–2 KB.

Quick revision

• Start every design with functional and non-functional requirements, then estimate scale; never start with boxes.
• 1 million requests per day is about 12 per second; peak is about 2-3x average; a day is about 10^5 seconds.
• Memory is about 100 ns; 1 MB sequential from RAM is about 10-50 μs (not a few microseconds). SSD random is about 100 μs, same-DC round trip about 0.5 ms, cross-continent about 150 ms.
• Scale out with stateless services behind load balancers; keep session state in a shared store or token.
• Report latency as percentiles; fan-out amplifies tail latency.
• 99.9% availability is about 8.8 hours of downtime per year; 99.99% is about 53 minutes.
• Serial dependencies multiply availability down; independent redundancy multiplies failure probability down.
• CAP: during a partition choose consistency or availability; PACELC adds latency vs consistency in normal operation.
• Quorum reads see the latest write when R + W > N.
• Pick consistency per feature: strong for money and inventory, eventual for feeds and counts.
• L4 load balancers route by IP and port; L7 by HTTP content, with TLS termination and path routing.
• CDNs cache static and cacheable content at the edge; use content-hashed file names instead of purging.
• Cache-aside is the default; on writes, update the database then delete the cache key.
• Prevent cache stampedes with request coalescing, TTL jitter and stale-while-revalidate.
• LRU is O(1) with a hash map plus a doubly linked list.
• Choose the database from access patterns: relational for transactions and joins, wide-column for massive writes, KV for key lookups.
• Indexes speed reads to O(log n) but slow writes and use storage; composite indexes follow the leftmost prefix.
• Replication scales reads and availability; async replication means lag and possible data loss on failover.
• Sharding scales writes and storage; the shard key must spread load and match the main query.
• Consistent hashing moves only about 1/N of keys when a node is added; virtual nodes balance load.
• Queues decouple, buffer spikes and enable retries; they give at-least-once delivery and per-partition ordering.
• Exactly-once is at-least-once delivery plus idempotent processing.
• Idempotency keys make retried writes safe; the outbox pattern solves the dual-write problem.
• Token bucket allows bursts with an average rate; sliding window counter is accurate with O(1) memory.
• Rate limiter state lives in Redis updated atomically; return 429 with Retry-After.
• Every remote call needs a timeout; retry only idempotent calls, with exponential backoff and jitter.
• Circuit breakers fail fast on a sick dependency; bulkheads isolate resource pools.
• URL shortener: base62 of a unique ID, read-heavy KV store, cache and CDN, async analytics.
• News feed: hybrid fan-out, push for normal users and pull for celebrities.
• Chat: WebSocket gateways, persist before acknowledging, per-conversation sequence numbers, push when offline.
• File sync: content-hashed chunks, deduplication, metadata DB, pre-signed uploads, change cursors.
• Ride-hailing: in-memory geospatial index (geohash, quadtree, S2/H3) and exclusive trip assignment.
• OTA: signed payloads, A/B partitions with automatic fallback, staged rollout gated on telemetry, kill switch.
• Device design treats battery, memory, connectivity and privacy as first-class constraints; batch and defer work.
• Raft: elect a leader, replicate a log, commit on majority; 2f+1 nodes tolerate f failures. Keep it off the high-QPS data path.
• Bloom filter: maybe-present, never false-negative, no deletes; ~10 bits/item at 1% false positives. HyperLogLog for distinct counts, Count-Min for heavy hitters.
• Version vectors detect concurrent writes; do not order distributed events by wall-clock timestamps alone.
• Senior answers name alternatives, tie choices to requirements, state what is given up, and cover failure, operations and cost.

Glossary

A/B partitions

Two copies of system partitions so an update installs to the inactive slot and the device can fall back if it fails to boot.

ACID

Atomicity, consistency, isolation, durability: the transaction guarantees of relational databases.

Adaptive bitrate

Streaming technique where the player switches video quality segment by segment based on bandwidth (HLS, DASH).

API gateway

Entry point that handles authentication, rate limiting, routing and other cross-cutting concerns for backend services.

Availability

Fraction of time a system serves requests successfully, often expressed in nines.

Backpressure

Signalling producers to slow down when consumers cannot keep up.

BASE

Basically available, soft state, eventual consistency: the looser guarantees of many NoSQL systems.

Bloom filter

Compact probabilistic set that can say "definitely not present" or "probably present".

Bulkhead

Isolating resources (thread or connection pools) per dependency so one failure cannot exhaust all of them.

Cache-aside

Caching strategy where the application reads the cache and, on a miss, loads from the database and fills the cache.

CAP theorem

During a network partition a distributed system must choose between consistency and availability.

CDN

Content delivery network: edge servers that cache content close to users.

Change data capture

Streaming a database's committed changes (from its log) to other systems.

Circuit breaker

Pattern that stops calling a failing dependency for a while and fails fast, then probes for recovery.

Consensus

Protocol (Raft, Paxos) for a group of nodes to agree on a value or leader despite failures.

Consistent hashing

Mapping keys and nodes onto a ring so adding or removing a node moves only a small fraction of keys.

CQRS

Command query responsibility segregation: separate models for writes and for reads.

CRDT

Conflict-free replicated data type that merges concurrent updates automatically and deterministically.

Dead-letter queue

Queue that holds messages that repeatedly failed processing, for inspection.

Denormalisation

Storing redundant copies of data to make reads faster at the cost of more complex writes.

Error budget

The allowed amount of unreliability implied by an SLO, spent on launches and risk.

Eventual consistency

Guarantee that replicas converge to the same value if writes stop.

Fan-out

Delivering one event or request to many recipients or backends.

Fencing token

Monotonically increasing number issued with a lock so storage can reject writes from stale lock holders.

Geohash

Encoding of latitude and longitude into a string where shared prefixes mean nearby locations.

Hinted handoff

A replica temporarily accepts writes for an unavailable node and forwards them when it returns.

Hot key

A single key receiving a disproportionate share of traffic, overloading one shard or cache node.

Idempotency

Property that repeating an operation has the same effect as performing it once.

Leader-follower replication

Writes go to one leader that streams changes to read-only followers.

Linearizability

Strongest single-object consistency: operations appear instantaneous and in real-time order.

Load balancer

Component that distributes requests across healthy servers.

LSM tree

Log-structured merge tree: write-optimised storage that flushes sorted files and compacts them in the background.

Outbox pattern

Writing events to a table in the same transaction as business data, then publishing them reliably.

PACELC

Extension of CAP: under partition choose availability or consistency, else choose latency or consistency.

Quorum

Minimum number of replicas that must respond to a read or write; R + W > N gives overlapping reads and writes.

Rate limiting

Restricting how many requests a client may make in a time period.

Replication lag

Delay between a write on the leader and its appearance on followers.

Saga

A long-running transaction split into local steps with compensating actions on failure.

Sharding

Partitioning data across nodes by a key so each node holds a subset.

SLA, SLO, SLI

Contractual promise, internal target, and measured indicator of service quality.

Snowflake ID

64-bit roughly time-ordered unique ID built from a timestamp, machine ID and sequence number.

Split brain

Failure where two nodes both believe they are the leader and accept conflicting writes.

Stampede

Many requests missing the cache at once and overloading the backing store (thundering herd).

Tail latency

The slowest requests, measured by high percentiles such as p99.

Token bucket

Rate-limiting algorithm where tokens refill at a steady rate and each request consumes one, allowing bursts.

Raft

Consensus protocol: a leader replicates a log; an entry is committed when a majority has stored it.

Version vector

Per-replica counters used to tell whether two updates happen-before each other or conflict.

HyperLogLog

Tiny probabilistic structure that estimates the number of distinct items in a stream.

Write-ahead log

Append-only durable log of changes written before in-memory state is treated as committed; replayed after a crash.

Interview questions