65System Design Fundamentals

65.1 The interview structure

1. Clarify — users, scale, features. "Are we designing read-heavy or write-heavy? Global or single-region?"
2. Estimate — back-of-envelope. "1M DAU, 10 reads each = 10M reads/day = ~120 read QPS average, 1200 peak."
3. Data model — what entities, what relationships, primary keys.
4. API — endpoints with example request/response.
5. High-level diagram — client, LB, service, DB, cache, queue.
6. Deep dive — pick the hardest part, work it out.
7. Trade-offs — SQL vs NoSQL? Sync vs async? Strong vs eventual consistency?
8. Failures & scale — how does it handle 10× growth? A region outage?

65.2 Scaling fundamentals

Vertical vs horizontal

• Vertical — bigger machine. Easy, limited (you run out of CPUs/RAM at some point). Expensive at the top end.
• Horizontal — more machines. Harder (need load balancing, state coordination), but scales arbitrarily.

Stateless services + load balancer

Make app servers stateless (no session in process memory). Store state in DB or Redis. Now you can run N replicas behind a load balancer — round-robin or least-connections. Adding capacity = launching more instances.

Sharding (partitioning)

Split data across multiple DB instances by a key (user_id mod N, geographic region, hash range). Each shard handles 1/N of the load.

• Hash sharding — uniform load, hard to do range queries
• Range sharding — easy range queries, can hot-spot if data skews
• Directory-based — lookup service maps key → shard; more flexible, extra hop

Replication

• Leader-follower (primary-replica) — writes to leader, reads from replicas. Read scaling, async replication = eventual consistency on replicas.
• Multi-leader — writes can hit any leader; conflict resolution required. Used across regions for low write latency.
• Leaderless (Cassandra, Dynamo) — quorum reads/writes; tunable consistency.

65.3 Caching

Cache strategies

• Cache-aside (lazy) — app checks cache, on miss reads DB and stores in cache. Most common.
• Write-through — every write hits both cache and DB. Always fresh, slower writes.
• Write-back — writes go to cache; flushed to DB later. Fast, risky (cache loss = data loss).
• TTL eviction — entries expire after N seconds.

65.4 SQL vs NoSQL

65.5 Async patterns

Message queue (SQS, RabbitMQ)

Producer publishes message to a queue. Consumer pulls and processes. Decouples producer from consumer; smooths bursts; survives consumer crashes.

Pub-sub (Kafka, Redis Streams, Google Pub/Sub)

Producer publishes to a topic; many subscribers each get a copy. One event triggers many side effects (email + analytics + warehouse).

Event sourcing

Store every state change as an immutable event; current state is derived by replaying events. Auditable; complex; great for financial systems.

CQRS

Command Query Responsibility Segregation — different models for writes and reads. Writes go to a normalized DB; reads from a denormalized projection optimised for queries.

65.6 CAP theorem

In a distributed system, you can have at most two of:

• C — Consistency (all nodes see the same data)
• A — Availability (every request gets a response)
• P — Partition tolerance (works despite network partitions)

Since network partitions happen in real systems, you really choose CP or AP. SQL DBs default CP (refuse writes during partition); Dynamo / Cassandra default AP (accept writes, reconcile later).

65.7 Consistency models

• Strong — every read sees the latest write. Synchronous replication. Most expensive.
• Eventual — given enough time without writes, all replicas converge. Cheapest, common in NoSQL.
• Read-your-writes — a session sees its own writes immediately, even on replicas.
• Monotonic reads — once you see a value, you never see an older one.
• Causal — causally related events are ordered consistently.

65.8 Failure handling

• Timeouts — every external call has one. Choose carefully — too short = unnecessary failures, too long = cascade.
• Retries — with exponential backoff + jitter. Idempotency required for non-GET calls.
• Circuit breaker — after N failures, stop calling the service for a cooldown. Saves both sides.
• Bulkhead — isolate failure domains; one slow upstream doesn't starve all threads.
• Graceful degradation — return cached / partial data when fresh fetch fails.
• Dead letter queue — messages that can't be processed go to a DLQ for human review.

65.9 Quick walkthroughs

Design a URL shortener

• POST /shorten { url } → returns short slug (base62 of an id, 7 chars covers ~3.5T URLs)
• GET /:slug → 301 redirect to original URL
• Storage: KV store (slug → URL). Postgres or DynamoDB.
• Hot URLs cached in Redis with TTL
• Analytics: async event to Kafka per click → warehouse
• Rate limit per IP to prevent abuse

Design a chat app (1-1)

• WebSocket between client and connection-service
• Connection-service tracks userId → connectionId in Redis
• Message published to Kafka topic per channel
• Recipient's connection-service picks up and pushes via WS
• Persistence: write to Cassandra (chat history, append-heavy)
• Read receipts as separate events

Design a news feed

• Fanout-on-write: when user posts, write to each follower's feed (good for small follower count)
• Fanout-on-read: compute feed when viewer requests (good for celebrities)
• Hybrid: fanout-on-write for normal users, fanout-on-read for accounts with > 1M followers
• Cache hot feeds in Redis
• Ranking: signals = recency, engagement, affinity

65.10 Capacity estimation cheat sheet (memorise)

65.11 Sharding strategies (deep)

65.12 Replication patterns (deep)

• Leader-follower (primary-replica) — writes go to leader, async replication to followers. Read scaling. Async = eventual consistency on followers.
• Synchronous replication — leader waits for N followers before ack. Strong consistency, slower writes.
• Multi-leader — writes can hit any leader; conflict resolution needed (last-write-wins, CRDTs, manual).
• Leaderless (Dynamo, Cassandra) — N replicas; tunable quorum (W + R > N for read-your-writes).

65.13 Consistency models (deep)

65.14 CAP + PACELC

• CAP: in a partition, choose Consistency or Availability (C or A; P is unavoidable). Most systems are CP or AP under partition.
• PACELC: extends CAP. When Partition: choose A or C. Else (no partition): choose Latency or Consistency. Better captures real trade-offs.
• Postgres = PC/EC (when partitioned: prioritises consistency; else: consistency)
• Cassandra = PA/EL (when partitioned: availability; else: latency)

65.15 Distributed system pitfalls

• Network is unreliable — every call can fail or hang
• Latency is non-zero — round trips add up
• Bandwidth is finite — design for it
• Network is not secure — TLS everywhere
• Topology changes — instances come and go
• There's an admin — humans cause incidents
• Transport cost is not zero — JSON serialization is real work
• The network is not homogeneous — different machines, different OS

(These are the "Fallacies of Distributed Computing".)

65.16 Common system-design walkthroughs (interview)

Rate limiter

• Token bucket: bucket holds N tokens; refill rate R; each request consumes 1. Smooths bursts.
• Sliding window log: store timestamps in a sorted set, count entries in window. Precise but memory-heavy.
• Sliding window counter: weighted average of current + previous fixed window. Approximate but cheap.
• Redis: SET counter EX window + INCR. Or Lua script for atomicity.
• Distributed: per-edge enforcement + central Redis source of truth.

Unique id generator (Twitter Snowflake)

• 64-bit: 1-bit sign + 41 timestamp + 10 node + 12 sequence
• ~69 years of timestamps; 1024 nodes; 4096 ids per ms per node
• Time-sortable, no central coord
• UUIDv7 is a modern alternative (time-prefix + random)

URL shortener

• POST /shorten {url} → 7-char base62 slug
• 62^7 ≈ 3.5T URLs. Generate from counter (base62 encode) or hash.
• KV store (slug → url), Redis cache hot, async analytics to Kafka
• Rate limit per IP, abuse detection

Chat (1-1 + group)

• WS edge cluster + sticky sessions + Redis pub/sub fanout
• Messages: Cassandra (write-heavy, append-only)
• Group: write once to topic, members subscribe
• Presence: Redis SET with TTL
• Read receipts: separate event

Distributed cache

• Consistent hash for shard selection
• Replication factor 2-3 for fault tolerance
• Eviction: LRU (default), LFU (frequency-aware)
• TTL on writes; lazy expiration on read
• Cache warming after restart, stampede control (single-flight)

Search autocomplete

• Trie of prefixes; precompute top-K results per prefix
• Or Elasticsearch completion suggester
• Cache hot prefixes in Redis
• Real-time: stream queries → reindex periodically
• Ranking signals: popularity, recency, personalization

News feed

• Fanout-on-write for normal users (small followers)
• Fanout-on-read for celebrities (millions of followers)
• Hybrid: precompute most, compute on read for celebs
• Cache feeds in Redis sorted set (score = post time)
• ML ranker re-orders on read

Distributed lock

• Redis SET NX PX with random value; Lua script to release only if value matches
• Redlock (multi-Redis quorum) for stronger guarantee
• ZooKeeper / etcd for genuine consensus (Paxos/Raft)
• Risks: clock skew, GC pause longer than TTL

Notification system

• Producer publishes notification intent → queue
• Worker picks channel (push/email/SMS/in-app) based on user prefs
• Rate limit per user; quiet hours; opt-out check
• Idempotency key dedupes retries
• Provider failures: fallback channel

65.17 Architectural styles

65.18 Failure handling toolkit

• Timeout on every external call
• Retry with exponential backoff + jitter; only for idempotent ops
• Circuit breaker — open after N failures, half-open to test recovery
• Bulkhead — isolate failure domains (separate thread pools per downstream)
• Graceful degradation — serve cached/partial data when fresh fetch fails
• Fallback — alternative path (different provider, default value)
• Dead-letter queue — messages that can't be processed go to DLQ for human review
• Health check — liveness + readiness; orchestrator restarts unhealthy
• Chaos testing — verify mechanisms actually work

65.X Code Patterns

Cache-Aside Pattern — Python + Redis

import redis, json, hashlib
from functools import wraps

cache = redis.Redis(host="localhost", port=6379, decode_responses=True)

def cached(ttl: int = 300):
    def decorator(fn):
        @wraps(fn)
        def wrapper(*args, **kwargs):
            key = f"{fn.__name__}:{hashlib.md5(str(args).encode()).hexdigest()}"
            hit = cache.get(key)
            if hit:
                return json.loads(hit)
            result = fn(*args, **kwargs)
            cache.setex(key, ttl, json.dumps(result))
            return result
        return wrapper
    return decorator

@cached(ttl=60)
def get_user_profile(user_id: int) -> dict:
    # DB query here
    return {"id": user_id, "name": "Alice", "plan": "pro"}

Token Bucket Rate Limiter — Redis Lua

import redis, time

r = redis.Redis(host="localhost", port=6379)

RATE_LIMIT_SCRIPT = """
local key      = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local now      = tonumber(ARGV[3])
local tokens   = tonumber(redis.call("GET", key) or capacity)
local last_ts  = tonumber(redis.call("GET", key..":ts") or now)
local elapsed  = now - last_ts
local refill   = math.floor(elapsed * rate)
tokens = math.min(capacity, tokens + refill)
if tokens >= 1 then
    redis.call("SET", key, tokens - 1)
    redis.call("SET", key..":ts", now)
    redis.call("EXPIRE", key, 3600)
    return 1
else
    return 0
end
"""

rate_limit = r.register_script(RATE_LIMIT_SCRIPT)

def allow_request(user_id: str, capacity: int = 10, rate: float = 1.0) -> bool:
    allowed = rate_limit(
        keys=[f"rl:{user_id}"],
        args=[capacity, rate, int(time.time())]
    )
    return bool(allowed)

# Usage
if not allow_request("user_42", capacity=100, rate=10):
    raise Exception("429 Too Many Requests")

Circuit Breaker — Python

import time
from enum import Enum
from functools import wraps

class State(Enum):
    CLOSED = "closed"
    OPEN = "open"
    HALF_OPEN = "half_open"

class CircuitBreaker:
    def __init__(self, failure_threshold=5, recovery_timeout=30):
        self.state = State.CLOSED
        self.failure_count = 0
        self.failure_threshold = failure_threshold
        self.recovery_timeout = recovery_timeout
        self.opened_at = None

    def __call__(self, fn):
        @wraps(fn)
        def wrapper(*args, **kwargs):
            if self.state == State.OPEN:
                elapsed = time.time() - self.opened_at
                if elapsed > self.recovery_timeout:
                    self.state = State.HALF_OPEN
                else:
                    raise Exception("Circuit open — call blocked")
            try:
                result = fn(*args, **kwargs)
                if self.state == State.HALF_OPEN:
                    self.state = State.CLOSED
                    self.failure_count = 0
                return result
            except Exception as e:
                self.failure_count += 1
                if self.failure_count >= self.failure_threshold:
                    self.state = State.OPEN
                    self.opened_at = time.time()
                raise
        return wrapper

cb = CircuitBreaker(failure_threshold=3, recovery_timeout=60)

@cb
def call_payment_service(order_id: str):
    import requests
    return requests.post("https://payments.internal/charge", json={"order": order_id}, timeout=2)

Consistent Hashing — Python

import hashlib, bisect

class ConsistentHashRing:
    def __init__(self, nodes: list, replicas: int = 150):
        self.replicas = replicas
        self.ring: dict[int, str] = {}
        self.sorted_keys: list[int] = []
        for node in nodes:
            self.add_node(node)

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node: str):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            self.ring[h] = node
            bisect.insort(self.sorted_keys, h)

    def remove_node(self, node: str):
        for i in range(self.replicas):
            h = self._hash(f"{node}:{i}")
            del self.ring[h]
            self.sorted_keys.remove(h)

    def get_node(self, key: str) -> str:
        h = self._hash(key)
        idx = bisect.bisect(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]

ring = ConsistentHashRing(["db1", "db2", "db3", "db4"])
print(ring.get_node("user:42"))    # db2
print(ring.get_node("user:9999"))  # db1