15. Applied System Design Case Studies

The previous fourteen chapters supplied the parts; this one assembles them under the constraints of concrete products, where every choice has a cost and no design is unambiguously right. Each case study follows the same path — clarify requirements, estimate scale, sketch a design, go deep on the one hard part, and name what the design gives up — because that path is both how real systems get built and how design interviews are assessed. The final subchapter covers communicating a design, which is the skill that determines whether any of the preceding work persuades anyone.

<a id="151-foundational-building-blocks"></a>

15.1 Foundational Building Blocks

These six systems are the primitives that appear inside almost every larger design, which is why they are the most commonly asked and the most reusable. Each is small enough to hold in your head completely, and each has exactly one genuinely hard part — uniqueness, ordering, coordination, replication, eviction, or politeness — that the rest of the design exists to support.

Design a URL Shortener

A URL shortener maps a long URL to a short key and redirects visitors when they request that key. It looks trivial, which is exactly why it is a good first design: the interesting engineering is not in the mapping but in the read/write asymmetry, the key generation, and the fact that a redirect must be fast enough that nobody notices it happened.

Requirements. Functional: create a short link for a URL, optionally with a custom alias and an expiry; redirect a short link to its target; report basic click analytics. Non-functional: redirects must be very fast (p99 under ~50 ms) and highly available — a broken redirect breaks every link ever shared — while link creation can be slower and less available. Links are effectively permanent unless expired, so the store only grows.

Estimates. Assume 100M new links per day and a 100:1 read/write ratio.

 writes: 100M/day  = ~1,160/s average, ~3,500/s peak (3x)
 reads : 10B/day   = ~116,000/s average, ~350,000/s peak
 storage: 100M/day x 500 bytes x 365 x 5 years = ~91 TB over five years
 key space: 7 chars of base62 = 62^7 = 3.5e12 keys -> ~100 years at this rate
 cache: top 20% of links serve ~80% of reads -> 20M links x 500 B = ~10 GB/day
        hot set; a modest cache tier absorbs almost all read traffic

The estimate immediately shapes the design: this is a read-dominated key-value workload with a tiny value size, so it is a caching and lookup problem, not a database problem.

Key generation is the one real decision. Hashing the URL (MD5/SHA truncated to 7 base62 chars) is stateless but collides, so it needs a read-check-retry loop on write. A counter encoded in base62 is collision-free and compact but makes keys sequential, which leaks volume and lets anyone enumerate every link. The common resolution is a distributed counter (14.x-style ID generation, see the next topic) whose output is passed through a bijective scrambling function, so keys are unguessable without a uniqueness check.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
BASE = len(ALPHABET)          # 62
KEY_LEN = 7
SPACE = BASE ** KEY_LEN

def encode(n: int) -> str:
    """Base62-encode an integer, left-padded to a fixed width."""
    out = []
    for _ in range(KEY_LEN):
        n, r = divmod(n, BASE)
        out.append(ALPHABET[r])
    return "".join(reversed(out))

# Feistel-style bijection: maps counter -> scrambled id with NO collisions,
# so keys look random but uniqueness is still guaranteed by the counter.
KNUTH = 2_654_435_761          # odd multiplier, coprime with SPACE
KNUTH_INV = pow(KNUTH, -1, SPACE)   # modular inverse: makes it reversible

def make_key(counter: int) -> str:
    return encode((counter * KNUTH) % SPACE)

def counter_from_key(key: str) -> int:
    n = 0
    for ch in key:
        n = n * BASE + ALPHABET.index(ch)     # decode base62
    return (n * KNUTH_INV) % SPACE            # undo the scramble

for c in (1, 2, 3, 1_000_000):
    k = make_key(c)
    print(f"{c:>9} -> {k} -> {counter_from_key(k)}")
#         1 -> 0000TCE9 style output: consecutive counters look unrelated,
#         2 -> ...      yet every key is unique and reversible.

Architecture. Reads dominate, so the redirect path is engineered to avoid the database entirely for hot links.

  create:  client -> API -> ID service (batched counter ranges)
                          -> KV store  PUT key -> {url, owner, expires_at}
                          -> cache warm (optional)

  redirect: client -> CDN/edge (cacheable 301 for stable links)
                   -> LB -> stateless redirect service
                          -> cache (Redis, ~99% hit rate)
                          -> KV store on miss (DynamoDB/Cassandra, key-partitioned)
                   <- 302 Location: <long url>
                   -> click event -> queue -> stream aggregation (14.2.3)

  Analytics NEVER blocks the redirect: emit an event and return immediately.

Trade-offs worth stating out loud. A 301 permanent redirect is cacheable by browsers and the CDN, which minimizes traffic but destroys per-click analytics and makes a link impossible to retarget; 302 keeps control and analytics at the cost of every click reaching your infrastructure. Custom aliases require a uniqueness check on a user-supplied string, which is the only strongly consistent write in the system. Expiry is best implemented as a TTL plus lazy deletion rather than a scanning job. And because the key space is public, abuse (phishing, malware) is a real operational concern: link scanning and takedown paths are part of the design, not an afterthought.

Key Takeaways

• The workload is extremely read-heavy and value-tiny: cache-first design with a simple partitioned key-value store behind it.
• Key generation must be unique and unguessable; a counter plus a bijective scramble gives both without collision checks.
• Base62 at 7 characters yields 3.5e12 keys — size the key length from the projected write rate.
• 301 maximizes cacheability but forfeits analytics and retargeting; 302 keeps both at the cost of traffic.
• Analytics must be asynchronous — never put a write on the redirect path.
• Custom aliases are the only place needing strong consistency.

🧪 Practice

1. Compute the key length required to support 500M new links per day for ten years without exhausting the space.
2. Design the custom-alias flow, including how you prevent two users claiming the same alias concurrently.
3. Interview: How do you support link expiry and deletion at 10B reads/day without a scanning job? (Hint: think about who discovers the expiry first, and what the read path already has to check anyway.)

Design a Unique ID Generator

Distributed systems constantly need identifiers: order IDs, message IDs, event IDs. A single database's auto-increment column gives uniqueness and ordering but also gives a single point of failure and a hard write ceiling. The design problem is producing IDs that are unique across many machines, generated without coordination on every call, and — usually — roughly sortable by time, because time-sortable IDs make range scans, pagination, and index locality dramatically better.

Requirements. Unique across the fleet, ideally 64 bits (fits a BIGINT, half the size of a UUID in every index), generated locally with no network call per ID, and monotonically increasing over time so that "newest first" is a primary-key sort rather than a secondary index.

The candidate approaches:

Approach	Coordination	Sortable	Size	Weakness
DB auto-increment	Every insert	Yes	64-bit	Single writer, write ceiling
UUIDv4 (random)	None	No	128-bit	Index fragmentation, size
UUIDv7 / ULID	None	Yes	128-bit	Size; still index-friendly
Ticket server	Every batch	Yes	64-bit	Central dependency
Snowflake	Worker ID only	Yes	64-bit	Clock dependency

Snowflake is the canonical answer because it buys time-sortability without per-ID coordination. A 64-bit integer is partitioned into a timestamp, a worker identifier, and a per-millisecond sequence counter. Uniqueness follows structurally: two IDs differ in time, or in worker, or in sequence.

 SNOWFLAKE 64-BIT LAYOUT

  0 | 41 bits timestamp (ms since epoch) | 10 bits worker | 12 bits sequence
  ^   ~69 years of range                   1024 workers     4096 ids/ms/worker
  |
  sign bit kept 0 so the value stays positive in signed 64-bit types

  Capacity: 4096 x 1024 = 4.2M IDs per millisecond fleet-wide.
  Sortability: the timestamp occupies the HIGH bits, so integer ordering is
  time ordering across the whole fleet (to millisecond granularity).

import time, threading

class Snowflake:
    EPOCH_MS   = 1_700_000_000_000     # custom epoch: buys back years of range
    WORKER_BITS, SEQ_BITS = 10, 12
    MAX_WORKER = (1 << WORKER_BITS) - 1
    MAX_SEQ    = (1 << SEQ_BITS) - 1

    def __init__(self, worker_id: int):
        assert 0 <= worker_id <= self.MAX_WORKER
        self.worker_id = worker_id
        self.last_ms = -1
        self.seq = 0
        self.lock = threading.Lock()

    def _now(self) -> int:
        return int(time.time() * 1000)

    def next_id(self) -> int:
        with self.lock:
            ts = self._now()
            if ts < self.last_ms:
                # CLOCK WENT BACKWARDS (NTP correction). Never emit an ID that
                # could duplicate one already issued: refuse until time catches up.
                raise RuntimeError(f"clock moved back {self.last_ms - ts} ms")
            if ts == self.last_ms:
                self.seq = (self.seq + 1) & self.MAX_SEQ
                if self.seq == 0:                  # 4096 IDs used this ms
                    while (ts := self._now()) <= self.last_ms:
                        pass                       # spin to the next millisecond
            else:
                self.seq = 0
            self.last_ms = ts
            return (((ts - self.EPOCH_MS) << (self.WORKER_BITS + self.SEQ_BITS))
                    | (self.worker_id << self.SEQ_BITS)
                    | self.seq)

gen = Snowflake(worker_id=7)
ids = [gen.next_id() for _ in range(3)]
print(ids, ids == sorted(ids))     # monotonically increasing

The two operational hazards are both about the assumptions the layout encodes. Worker ID assignment must guarantee no two live processes share an ID — take it from ZooKeeper/etcd leases, a Kubernetes StatefulSet ordinal, or a configuration service, never from a hash of the hostname or a random number. Clock skew breaks the uniqueness argument: if the clock jumps backwards, IDs can repeat, so the generator must refuse to issue during the regression rather than risk a duplicate, and the fleet should run NTP with slew rather than step corrections.

Where 128 bits are acceptable, UUIDv7 is now the pragmatic default: it embeds a millisecond timestamp in the high bits, so it sorts like Snowflake and indexes well, while needing no worker-ID coordination at all. Choose 64-bit Snowflake when index size and storage matter (billions of rows, IDs repeated as foreign keys); choose UUIDv7 when you want zero coordination and can afford the extra eight bytes.

Key Takeaways

• Centralized auto-increment gives ordering but caps write throughput and adds a single point of failure.
• Snowflake partitions 64 bits into time, worker, and sequence — uniqueness is structural and requires no coordination per ID.
• Putting the timestamp in the high bits is what makes IDs time-sortable, which is worth far more than it sounds for indexes and pagination.
• Worker IDs must come from a coordination service or stable ordinal, never a hash or a random draw.
• Backwards clock movement must block issuance; use NTP slewing.
• UUIDv7 gives sortability with zero coordination at 128 bits — the default unless index size dominates.

🧪 Practice

1. Compute the maximum IDs per second for a 10-bit worker, 12-bit sequence layout, and re-partition the bits for 4096 workers.
2. Implement worker-ID assignment using leases, including what happens when a lease expires while the process is still running.
3. Interview: Your ID generator emitted a duplicate. List the possible causes. (Hint: uniqueness rests on three assumptions in the layout — enumerate what breaks each one.)

Design a Rate Limiter

Any service exposed to the world will eventually be hit harder than it can serve — by an abusive client, a buggy retry loop, or a legitimate customer's traffic spike. A rate limiter enforces a quota so that the system degrades predictably for the offender instead of unpredictably for everyone. It is a protection mechanism first (9.x) and a monetization mechanism second.

Requirements. Limit requests per identity (API key, user, IP) per window; respond with 429 Too Many Requests plus headers telling the client its limit, remaining quota, and when to retry; work correctly across many application instances; and — crucially — add almost nothing to request latency, since it runs on every single request.

Algorithms. The choice is a trade between memory, burst behaviour, and boundary accuracy.

 FIXED WINDOW                        SLIDING WINDOW LOG
  [--- 60s ---][--- 60s ---]          keep a timestamp per request; count those
   99 reqs at 0:59                    within the last 60s. Exact, but O(requests)
   99 reqs at 1:00  -> 198 in 2s!     memory per identity.
   Cheap; boundary burst = 2x limit.

 TOKEN BUCKET                        SLIDING WINDOW COUNTER
  capacity 100, refill 10/s           weighted blend of previous and current
  +---------+                         fixed windows:
  | ******  | <- refill               count = prev * overlap + curr
  +----+----+                         approximates the log with O(1) memory,
       | take 1 per request           smoothing the boundary burst.
       v  empty -> reject
  Allows bursts up to capacity,
  then settles to the steady rate.

Token bucket is the usual production answer: it is O(1) in memory per identity, permits short bursts (which real clients need), and enforces an average rate. It is also what most gateways and cloud providers implement, so its semantics are familiar to clients.

import time

REFILL_LUA = """
-- Atomic token bucket in Redis. Atomicity matters: a read-modify-write from
-- the application would race across instances and let the limit be exceeded.
local key      = KEYS[1]
local rate     = tonumber(ARGV[1])   -- tokens per second
local capacity = tonumber(ARGV[2])
local now      = tonumber(ARGV[3])
local cost     = tonumber(ARGV[4])

local b = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(b[1]) or capacity
local ts     = tonumber(b[2]) or now

tokens = math.min(capacity, tokens + (now - ts) * rate)   -- lazy refill
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end

redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', key, math.ceil(capacity / rate) * 2) -- reclaim idle keys
return { allowed and 1 or 0, tokens }
"""

class LocalTokenBucket:
    """Per-instance bucket used as a fast path in front of the shared limiter."""

    def __init__(self, rate: float, capacity: float):
        self.rate, self.capacity = rate, capacity
        self.tokens, self.ts = capacity, time.monotonic()

    def allow(self, cost: float = 1.0) -> tuple[bool, float]:
        now = time.monotonic()
        # Refill lazily: no background timer, cost is O(1) per request.
        self.tokens = min(self.capacity, self.tokens + (now - self.ts) * self.rate)
        self.ts = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True, self.tokens
        retry_after = (cost - self.tokens) / self.rate
        return False, retry_after

b = LocalTokenBucket(rate=10, capacity=20)      # 10/s sustained, burst of 20
print([b.allow()[0] for _ in range(22)][-3:])   # [True, False, False]

Distributed enforcement is the hard part. A limit of 1000/minute across 50 instances cannot be enforced by each instance allowing 20/minute — traffic is not evenly balanced, so that both over- and under-limits real clients. The two viable designs are a shared store (Redis with an atomic script, as above: exact, but one network round trip per request) or local buckets that periodically sync their consumption to a central store (approximate, but nearly free per request). A common hybrid uses a local bucket sized to a fraction of the quota as a fast path and consults the shared store only when the local budget is exhausted.

Placement matters as much as the algorithm. Limiting at the API gateway or edge stops abusive traffic before it consumes application capacity, which is the whole point; limiting only inside the service means the attack still costs you connection handling, TLS, and authentication. Most systems run both — coarse limits at the edge, fine-grained per-endpoint limits in the service — and always return the standard headers so well-behaved clients can self-regulate.

 429 response headers (let clients cooperate rather than guess)
   RateLimit-Limit: 1000
   RateLimit-Remaining: 0
   RateLimit-Reset: 42            <- seconds until quota refreshes
   Retry-After: 42                <- clients must honour this, with jitter (13.3)

Key Takeaways

• Rate limiting protects capacity: the goal is predictable degradation for the offender, not fairness in the abstract.
• Token bucket is the practical default — O(1) memory, allows bursts, enforces an average rate.
• Fixed windows permit a 2x burst at the boundary; sliding window counters fix it cheaply, logs fix it exactly at higher memory cost.
• Distributed limits need atomic operations in a shared store, or local buckets with periodic sync; per-instance division of the quota is wrong.
• Enforce at the edge to reject before spending capacity, and again per endpoint for granularity.
• Always return limit, remaining, reset, and Retry-After headers.

🧪 Practice

1. Trace token bucket state through a burst of 30 requests at capacity 20 and refill 10/s, listing which are rejected and when they would succeed.
2. Design tiered limits (free/pro/enterprise) including how a key's tier change takes effect without restarting instances.
3. Interview: Your limiter's Redis becomes unavailable. What should happen? (Hint: think about which failure mode is worse for your service — letting everything through, or rejecting everything — and whether a local fallback can bound the damage.)

Design a Key-Value Store

Building a distributed key-value store is the exercise that forces every distributed-systems concept into one place: partitioning, replication, consistency, failure detection, and repair. The interface is deliberately tiny — get(key), put(key, value), delete(key) — so all the difficulty is in making those three operations work across hundreds of machines that fail independently.

Requirements. Store values by key with configurable durability; scale horizontally by adding nodes; survive node and rack failure; offer tunable consistency, because different callers legitimately want different points on the consistency/latency curve (3.x, CAP).

Partitioning. Naive hash(key) % N redistributes nearly every key when N changes. Consistent hashing places nodes and keys on a ring so that adding or removing a node moves only the keys between it and its neighbour; virtual nodes (many ring positions per physical node) smooth the load imbalance that a few random positions would otherwise produce.

import hashlib, bisect

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

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

    def add(self, node: str) -> None:
        for i in range(self.vnodes):          # many positions => even spread
            h = self._hash(f"{node}#{i}")
            self.ring[h] = node
            bisect.insort(self.sorted_keys, h)

    def remove(self, node: str) -> None:
        for i in range(self.vnodes):
            h = self._hash(f"{node}#{i}")
            del self.ring[h]
            self.sorted_keys.remove(h)

    def preference_list(self, key: str, n: int) -> list[str]:
        """The N distinct physical nodes that replicate this key: walk
        clockwise, skipping vnodes that map to a node already chosen."""
        h = self._hash(key)
        i = bisect.bisect(self.sorted_keys, h) % len(self.sorted_keys)
        out: list[str] = []
        for step in range(len(self.sorted_keys)):
            node = self.ring[self.sorted_keys[(i + step) % len(self.sorted_keys)]]
            if node not in out:
                out.append(node)
            if len(out) == n:
                break
        return out

ring = ConsistentHashRing(["n1", "n2", "n3", "n4"])
print(ring.preference_list("user:42", n=3))     # e.g. ['n3', 'n1', 'n4']
moved = sum(ring.preference_list(f"k{i}", 1) != None for i in range(0))  # noop
ring.add("n5")
print(ring.preference_list("user:42", n=3))     # most keys keep their home

Replication and consistency. Each key is stored on the first N nodes of its preference list. Quorum parameters let callers choose their guarantee per operation: with N replicas, requiring W acknowledgements on write and R responses on read, R + W > N guarantees the read set intersects the write set and therefore sees the latest committed value.

 QUORUM CONFIGURATIONS (N = 3)

 W=3, R=1  fast reads, slow writes, no write availability if any replica is down
 W=1, R=3  fast writes, slow reads
 W=2, R=2  balanced; tolerates one node down for both reads and writes  <- default
 W=1, R=1  fastest, eventually consistent (R + W <= N: reads may be stale)

  write to A,B (W=2)          read from B,C (R=2)
   A[v2] B[v2] C[v1]           the overlap at B guarantees v2 is seen;
      \____/  \____/           C's stale v1 is repaired in the background
       write   read            (read repair) or by anti-entropy.

Conflict resolution is unavoidable once concurrent writes are allowed. Last write wins using timestamps is simple and lossy — a clock skew silently discards a write. Vector clocks capture causality instead: they can tell whether one version descends from another (safe to overwrite) or whether the two are concurrent (a genuine conflict the application must resolve, as Dynamo's shopping cart does by merging).

Locally, each node needs a storage engine. LSM trees (memtable plus sorted files, background compaction) suit write-heavy workloads and are what Cassandra and RocksDB use; B-trees suit read-heavy workloads with in-place updates. Add failure detection by gossip, hinted handoff so writes for a temporarily unavailable replica are buffered by a peer, and Merkle trees so replicas can compare and repair divergent ranges without shipping all their data.

Key Takeaways

• Consistent hashing with virtual nodes keeps rebalancing proportional to the change, not to the dataset.
• R + W > N guarantees read-your-writes; the specific split trades read latency against write latency and availability.
• Timestamp-based last-write-wins silently loses data under clock skew; vector clocks distinguish causality from true concurrency.
• Anti-entropy (Merkle trees) plus read repair and hinted handoff are what keep replicas converging.
• LSM for write-heavy, B-tree for read-heavy local storage.
• The API is trivial; all the engineering is in partitioning, replication, and repair.

🧪 Practice

1. Compute the fraction of keys that move when adding one node to a 10-node ring, with and without virtual nodes.
2. For N=5, list every (W, R) pair that guarantees strong consistency, and rank them by write availability.
3. Interview: Two clients write different values to the same key at the same moment. What does your store return on the next read? (Hint: the honest answers differ by conflict-resolution strategy — say which one you chose and what the application must then do.)

Design a Distributed Cache

A cache trades memory for latency and load: it keeps a small hot subset of data close to the application so the expensive backing store is consulted rarely. The distributed version adds the question of where a given key lives across a fleet of cache nodes, and — the part that bites in production — what happens when a node joins, leaves, or fails while traffic is flowing.

Requirements. Sub-millisecond get/set at very high throughput; horizontal scale by adding nodes; graceful behaviour on node loss (a cache miss, not an error); memory bounded by eviction; and optional replication for hot keys. A cache is by definition allowed to lose data — the design must never treat it as the source of truth.

Topology and placement. Client-side consistent hashing (the memcached model) keeps the cache tier dumb and stateless, with routing knowledge in a client library; a proxy or cluster-aware server (the Redis Cluster model) centralizes routing at a small latency cost. Either way, consistent hashing (previous topic) is what makes node membership changes cheap.

Caching patterns determine consistency behaviour more than any other choice:

Pattern	Read path	Write path	Note
Cache-aside	Miss -> load DB -> populate	Write DB, invalidate cache	Most common; app owns logic
Read-through	Cache loads from DB itself	—	Uniform, needs cache support
Write-through	—	Write cache and DB together	Consistent, slower writes
Write-behind	—	Write cache, flush DB async	Fast, can lose data on crash
Refresh-ahead	Refresh before TTL expiry	—	Hides latency for hot keys

import time, random, threading

class CacheAside:
    """Cache-aside with the three defences every production cache needs."""

    def __init__(self, cache, db, ttl: int = 300):
        self.cache, self.db, self.ttl = cache, db, ttl
        self.locks: dict[str, threading.Lock] = {}

    def get(self, key: str):
        hit = self.cache.get(key)
        if hit is not None:
            if hit == "__MISS__":            # NEGATIVE CACHING stops repeated
                return None                  # lookups for keys that don't exist
            return hit

        # STAMPEDE PROTECTION: on a miss for a hot key, thousands of requests
        # would hit the DB simultaneously. One loader wins; the rest wait.
        lock = self.locks.setdefault(key, threading.Lock())
        with lock:
            hit = self.cache.get(key)        # re-check: another thread may have
            if hit is not None:              # populated it while we waited
                return None if hit == "__MISS__" else hit
            value = self.db.get(key)
            # JITTERED TTL: identical TTLs make whole cohorts of keys expire in
            # the same second, producing a synchronised stampede later.
            ttl = int(self.ttl * random.uniform(0.9, 1.1))
            self.cache.set(key, value if value is not None else "__MISS__", ttl)
            return value

    def update(self, key: str, value) -> None:
        self.db.put(key, value)
        # Invalidate rather than update: writing the new value into the cache
        # races with concurrent readers repopulating it with the OLD value.
        self.cache.delete(key)

Eviction decides what the cache keeps once memory is full. LRU is the default and is right for recency-dominated access; LFU handles workloads where a few keys are persistently hot and a scan would otherwise evict them; TTL alone is appropriate when staleness, not memory, is the binding constraint. Modern engines use approximations (sampled LRU, TinyLFU) because exact ordering costs more than it returns.

Three failure behaviours deserve explicit design. Thundering herd on a popular key is handled by the single-flight lock above, or by serving stale data while one request refreshes. Cold cache after a restart can overwhelm the database — mitigate by warming the cache from a snapshot or by rolling restarts that never take out the whole tier at once. And hot keys overwhelm the single node that owns them; the standard fix is to replicate that key across several nodes and have clients pick randomly, or to keep a small local in-process cache in front of the shared tier.

 CACHE TIERS

  app process
   [ L1: in-process LRU, ~1000 keys, TTL seconds ]   <- absorbs hot keys, no
        | miss                                          network hop at all
        v
   [ L2: shared cache cluster, consistent hashing ]  <- the main tier, ~99% hits
        | miss
        v
   [ database ]  <- must be sized to survive the miss rate, not the hit rate

Key Takeaways

• A cache is never the source of truth: losing a node must produce misses, not errors.
• Consistent hashing bounds the disruption of membership changes.
• Cache-aside with invalidation-on-write is the default; updating the cache on write races with concurrent readers.
• Defend against stampedes with single-flight loading, jittered TTLs, and negative caching.
• Choose eviction by access pattern: LRU for recency, LFU for persistent hotness, TTL for staleness limits.
• Size the database for the miss rate, and add an in-process L1 for hot keys.

🧪 Practice

1. Compute the database load produced by a 95% hit rate at 200k requests/sec, then at 90%, and note what that means for capacity planning.
2. Implement single-flight loading and show how many database calls occur when 500 concurrent requests miss the same key.
3. Interview: After a cache cluster restart the database falls over. Why, and how do you prevent it? (Hint: think about what fraction of traffic the database was previously never seeing, and what a staged restart changes.)

Design a Web Crawler

A crawler discovers and downloads pages so a downstream system — a search index (14.3.1), an archive, a price monitor — can process them. The naive version is a breadth-first traversal, which is ten lines of code and immediately wrong at scale: it hammers individual hosts, re-fetches the same content endlessly, gets trapped by infinite URL spaces, and ignores the rules sites publish about automated access.

Requirements. Crawl billions of pages with bounded politeness per host, respect robots.txt, avoid duplicate fetches and duplicate content, prioritize important and frequently-changing pages, and recrawl at a rate matched to how often each page actually changes. Non-functional: horizontally scalable, robust to malformed responses, and restartable — a crawl that must begin again after a crash is unusable.

Estimates. One billion pages per month is ~385 pages/second sustained; at 100 KB per page that is ~100 TB of raw content per month, and the URL frontier itself will hold billions of entries, which is far too large for memory and must be a disk-backed queue.

 CRAWLER ARCHITECTURE

  seed URLs
     |
     v
  [ URL FRONTIER ]  two-level queue:
    front queues  = PRIORITY  (importance, freshness need)
    back queues   = POLITENESS (one queue per host; a worker holds a host lease
                                and waits the host's crawl delay between fetches)
     |
     v
  [ fetcher pool ] --robots.txt cache--> obey Disallow + Crawl-delay
     |  (DNS cache: DNS is a real bottleneck at this rate)
     v
  [ content processing ]
     |-- checksum / SimHash -> duplicate content detection
     |-- extract links -> normalize -> seen-URL filter (Bloom) -> frontier
     |-- store raw page -> object storage; metadata -> KV store
     v
  [ index / downstream consumer ]

The frontier is the heart of the design. Its two levels solve two different problems: front queues decide what to crawl next by priority, back queues ensure that no host receives concurrent or rapid-fire requests regardless of how many of its URLs are pending. Without the back-queue layer, a site with a million links gets crawled as a denial-of-service attack.

import time, heapq, hashlib
from collections import defaultdict, deque
from urllib.parse import urlsplit, urlunsplit, parse_qsl, urlencode

def normalize(url: str) -> str:
    """Canonicalize aggressively: the same page reached by different URLs must
    produce the same key, or the crawler re-fetches it forever."""
    p = urlsplit(url.strip())
    scheme = p.scheme.lower() or "https"
    host = p.hostname.lower() if p.hostname else ""
    if host.startswith("www."):
        host = host[4:]
    port = "" if p.port in (None, 80, 443) else f":{p.port}"
    path = (p.path or "/").rstrip("/") or "/"
    # Drop tracking parameters and sort the rest: ?b=2&a=1 == ?a=1&b=2
    drop = {"utm_source", "utm_medium", "utm_campaign", "gclid", "fbclid"}
    q = urlencode(sorted((k, v) for k, v in parse_qsl(p.query) if k not in drop))
    return urlunsplit((scheme, host + port, path, q, ""))   # fragment removed

class Frontier:
    def __init__(self, default_delay: float = 1.0):
        self.front: list[tuple[float, str]] = []             # (-priority, url)
        self.back: dict[str, deque] = defaultdict(deque)     # host -> urls
        self.next_ok: dict[str, float] = {}                  # host -> earliest fetch
        self.delay = default_delay

    def add(self, url: str, priority: float = 0.5) -> None:
        heapq.heappush(self.front, (-priority, normalize(url)))

    def _drain(self) -> None:
        while self.front:
            _, url = heapq.heappop(self.front)
            self.back[urlsplit(url).hostname].append(url)     # route by host

    def next_url(self) -> str | None:
        self._drain()
        now = time.monotonic()
        for host, q in self.back.items():
            if q and now >= self.next_ok.get(host, 0.0):
                self.next_ok[host] = now + self.delay   # politeness enforced here
                return q.popleft()
        return None                                      # everything is cooling down

def simhash(text: str, bits: int = 64) -> int:
    """Near-duplicate detection: pages differing only in a timestamp or an ad
    should collapse to the same fingerprint, which an exact checksum cannot do."""
    v = [0] * bits
    for token in text.split():
        h = int(hashlib.md5(token.encode()).hexdigest(), 16)
        for i in range(bits):
            v[i] += 1 if (h >> i) & 1 else -1
    return sum(1 << i for i in range(bits) if v[i] > 0)

def hamming(a: int, b: int) -> int:
    return bin(a ^ b).count("1")        # distance <= 3 => near-duplicate

print(normalize("HTTPS://WWW.Example.com/a/?utm_source=x&b=2&a=1#frag"))
# https://example.com/a?a=1&b=2

Deduplication happens twice. URL-level: a Bloom filter (or a sharded set) answers "have I already queued this?" in constant memory with a tunable false positive rate — acceptable because a false positive merely skips a page. Content-level: exact checksums catch identical pages, while SimHash or MinHash catch near-duplicates, which are extremely common (session IDs in URLs, printer views, syndicated articles).

Traps and politeness round out the design. Infinite spaces — calendars with "next month" links forever, faceted-search parameter explosions — need depth limits, per-host page caps, and pattern detection. robots.txt must be fetched, cached with a TTL, and honoured including Crawl-delay; a User-Agent should identify the crawler with a contact URL. Recrawl scheduling should be adaptive: estimate each page's change rate from its observed history and schedule proportionally, so news pages are revisited hourly and static pages monthly, rather than sweeping everything on one fixed cycle.

Key Takeaways

• The URL frontier is the core: front queues for priority, back queues for per-host politeness.
• Normalize URLs aggressively — canonicalization failures cause endless re-fetching of the same content.
• Deduplicate at both URL level (Bloom filter) and content level (checksum plus SimHash for near-duplicates).
• Respect robots.txt and crawl delays, and identify your crawler; politeness is a design requirement, not etiquette.
• Defend against infinite URL spaces with depth limits and per-host caps.
• Schedule recrawls from observed change rates, not on a uniform cycle.
• Cache DNS: at hundreds of fetches per second it becomes a bottleneck.

🧪 Practice

1. Size a Bloom filter for 5 billion URLs at a 1% false positive rate, and state what a false positive costs you.
2. Write normalization rules that collapse at least five different URL forms of one page into a single key.
3. Interview: Your crawler keeps re-downloading the same content under different URLs. Diagnose it. (Hint: consider both what your normalizer is not stripping and what the site itself is generating.)

<a id="152-communication-and-social-systems"></a>

15.2 Communication and Social Systems

Social systems share one structural problem: a single write by one user must reach an unpredictable number of readers, and the ratio between those two numbers decides the entire architecture. This subchapter works through chat, feeds, notifications, the social graph itself, and comment threads — five systems whose designs are mostly answers to the question of when to do the fan-out work.

Design a Chat Application

Messaging looks like a CRUD problem and is actually a connection-management problem. Requests do not initiate the interesting events: messages arrive from other people, so the server must push to clients that are connected right now, queue for clients that are not, and reconcile the two without losing or duplicating anything. Everything else follows from that.

Requirements. One-to-one and group messaging; delivery and read receipts; presence (online/last seen); message history with pagination; push notification when the recipient is offline; ordering that is consistent for all participants of a conversation. Non-functional: p99 delivery under ~200 ms for connected users, no message loss once accepted, and support for tens of millions of concurrent connections.

Estimates. 50M daily active users, 40 messages each = 2B messages/day (~23k/s average, ~70k/s peak). At 1 KB per message that is 2 TB/day of message data. Ten million concurrent WebSocket connections at ~10 KB of kernel and application state each is ~100 GB of memory across the connection tier — roughly 100 servers holding 100k connections apiece, which is what makes the connection tier a distinct service.

 CHAT ARCHITECTURE

  client --WebSocket--> [ gateway / connection tier ]   stateful: holds the socket
                              |     ^                    100k conns per node
                              |     | push
                              v     |
                        [ session registry ]   user -> gateway node (Redis, TTL)
                              |
                              v
   send ----------------> [ chat service ] --+--> message store (append-only,
                                             |     partitioned by conversation)
                                             +--> outbox/queue -> fan-out to
                                             |     recipients' gateway nodes
                                             +--> push service (APNs/FCM) if the
                                                   recipient has no live session

  The gateway is the ONLY stateful tier. Everything behind it is stateless and
  scales normally; the registry is what lets a stateless service find a socket.

Message flow. The client sends over its existing socket with a client-generated ID; the chat service persists the message first, then acknowledges the sender, then fans out. Persisting before acknowledging is what makes "accepted" mean "durable" — the reverse order loses messages on a crash between the two.

import time, uuid

class ChatService:
    def send(self, sender: str, conversation_id: str, body: str,
             client_msg_id: str) -> dict:
        # IDEMPOTENCY: the client retries on network failure using the SAME
        # client_msg_id, so a duplicate send must return the original result.
        existing = self.store.find_by_client_id(conversation_id, client_msg_id)
        if existing:
            return existing

        msg = {
            "message_id": self.ids.next_id(),        # Snowflake: time-sortable
            "conversation_id": conversation_id,
            "sender": sender,
            "body": body,
            "seq": self.store.next_seq(conversation_id),  # per-conversation order
            "created_at": time.time(),
            "client_msg_id": client_msg_id,
        }
        self.store.append(msg)                # 1. DURABLE first
        self.outbox.publish(msg)              # 2. then fan out asynchronously
        return msg                            # 3. ack the sender

    def deliver(self, msg: dict) -> None:
        for recipient in self.members(msg["conversation_id"]):
            if recipient == msg["sender"]:
                continue
            node = self.registry.get(recipient)        # which gateway holds them?
            if node:
                self.gateway_rpc(node).push(recipient, msg)
            else:
                # Offline: the message is already durable; queue a push
                # notification and let the client sync on reconnect.
                self.push.notify(recipient, msg)

Ordering and sync. Global ordering across all conversations is unnecessary and expensive; ordering within a conversation is what users perceive. A monotonically increasing per-conversation sequence number gives that cheaply and also gives clients a resumption cursor: on reconnect a client sends its last seen seq per conversation and receives everything after it, which handles missed messages, reordering, and duplicates in one mechanism. Client-side ordering should use the server sequence, never the device clock.

Storage. Messages are an append-heavy, range-read workload partitioned by conversation ID and clustered by sequence — exactly the shape a wide-column store (Cassandra, HBase) or a partitioned relational table serves well. Group conversations should store one copy of the message plus per-user read state, rather than a copy per recipient; the "copy per recipient" model only pays off when per-user mutation of the message is needed.

The hard sub-problems worth naming: presence at scale is a firehose (a user with 500 contacts going online produces 500 notifications, so batch and rate-limit it, and accept a few seconds of staleness); read receipts are per-user, per-conversation high-write-rate state that should be a single "last read seq" value rather than a row per message; and end-to-end encryption changes the design fundamentally, because the server can no longer read message content — search must happen client-side, and group key distribution becomes its own protocol.

Key Takeaways

• Chat is a connection-management problem: a stateful gateway tier plus a session registry that maps users to gateway nodes.
• Persist before acknowledging, then fan out asynchronously.
• Per-conversation sequence numbers give both perceived ordering and a reconnect cursor; global ordering is unnecessary.
• Client-supplied message IDs make retries idempotent and de-duplicate at the source.
• Store one message copy per conversation plus per-user read state, not a copy per recipient.
• Presence is a fan-out firehose — batch it and tolerate staleness.
• End-to-end encryption removes the server's ability to search or moderate.

🧪 Practice

1. Size the connection tier for 20M concurrent users at 100k connections per node, including the memory and the failover implications when one node dies.
2. Design the reconnect-and-sync protocol, specifying exactly what the client sends and what the server returns.
3. Interview: A user's messages sometimes appear out of order on one device. What causes this and how do you fix it? (Hint: think about what the client is sorting by, and which of the available timestamps or counters is authoritative.)

Design a News Feed System

A feed shows a user recent activity from the accounts they follow, ranked and paginated. The entire design reduces to one question with no universally correct answer: do you compute a user's feed when the content is written (fan-out on write) or when the feed is read (fan-out on read)? Every real system answers "both, depending on the author".

Requirements. Post an item; retrieve a ranked feed with stable pagination; see new posts within seconds; support follower counts ranging from 10 to 100 million. Non-functional: feed reads must be fast (p99 ~200 ms) and are enormously more frequent than writes.

Estimates. 300M daily active users checking the feed 10 times a day is 3B reads/day (~35k/s average, 100k/s peak). 50M posts/day is ~600/s. With an average of 200 followers, fan-out on write means 50M x 200 = 10B feed-entry writes per day (~115k/s) — expensive but tractable, until a celebrity with 100M followers posts and produces 100M writes from a single action.

 THE TWO STRATEGIES

 FAN-OUT ON WRITE (push)                FAN-OUT ON READ (pull)
  post -> for each follower:             post -> author's timeline only
            append to their feed list     read -> for each followed account:
  read -> one lookup. FAST.                        fetch recent, merge, rank
  write -> O(followers). EXPENSIVE.      read -> O(following). SLOW.
  Celebrity post = 100M writes.          write -> O(1). CHEAP.

 HYBRID (what production systems do)
  - normal authors  -> push into follower feeds at write time
  - celebrity authors -> not pushed; pulled at read time and merged
  - inactive users  -> not pushed at all; their feed is built on next login

  read path: precomputed_feed  MERGE  celebrity_recent  -> rank -> page

CELEBRITY_THRESHOLD = 100_000

class FeedService:
    def on_post(self, author_id: str, post: dict) -> None:
        self.posts.put(post["id"], post)
        self.author_timeline.prepend(author_id, post["id"])

        followers = self.graph.follower_count(author_id)
        if followers >= CELEBRITY_THRESHOLD:
            return          # do NOT fan out: 100M writes for one action.
                            # These posts are merged in at read time instead.

        for batch in self.graph.followers_batched(author_id, size=1000):
            active = self.activity.filter_recently_active(batch, days=30)
            # Skipping dormant users typically removes 60-80% of the fan-out
            # cost; their feed is rebuilt lazily when they next log in.
            self.feed_store.multi_prepend(active, post["id"], cap=800)

    def get_feed(self, user_id: str, cursor: str | None, limit: int = 20):
        precomputed = self.feed_store.range(user_id, cursor, limit * 3)
        celebs = self.graph.celebrities_followed(user_id)         # usually few
        pulled = [pid for c in celebs
                  for pid in self.author_timeline.recent(c, limit)]

        ids = self._dedupe(precomputed + pulled)
        posts = self.posts.multi_get(ids)                          # batch fetch
        ranked = self.ranker.score(user_id, posts)                 # 14.3.3 funnel
        page = ranked[:limit]
        # Cursor is (score, post_id), NOT an offset: offsets shift as new posts
        # arrive and cause users to see duplicates or skip items.
        next_cursor = f"{page[-1]['score']}:{page[-1]['id']}" if page else None
        return page, next_cursor

Ranking turns a chronological merge into a feed. It is the funnel from 14.3.3 in miniature: candidate generation (the merged set above, plus recommended content from accounts the user does not follow), scoring by a model over engagement and affinity features, then re-ranking for diversity and freshness so one prolific author cannot occupy the whole page.

Storage. Feeds are lists of post IDs, capped (nobody scrolls past a few hundred items) and held in a fast store — a Redis list or sorted set per user is the classic implementation, with the authoritative post content in a separate partitioned store. Storing IDs rather than content is what makes edits and deletions tractable: one write updates the post everywhere it appears.

Trade-offs to state. Fan-out on write burns storage and write throughput to buy read latency; fan-out on read does the reverse; the hybrid buys both at the cost of a more complex read path and a threshold that must be tuned. Deletion is asymmetric — with push, a deleted post lingers in millions of precomputed feeds, so the read path must filter against a tombstone rather than assume the feed entries are valid.

Key Takeaways

• Feed design is a choice about when fan-out happens; the hybrid is the production answer.
• Fan-out on write gives O(1) reads and O(followers) writes; celebrities break it, so exclude them and pull at read time.
• Skip fan-out to dormant users and rebuild their feed lazily — usually the single largest cost saving.
• Store post IDs in feeds, not content, so edits and deletes are one write.
• Cap feed length; nobody reads past a few hundred entries.
• Paginate by an opaque (score, id) cursor, never by offset.
• Ranking is the recommendation funnel: generate, score, then diversify.

🧪 Practice

1. Compute daily feed writes for 50M posts/day at an average of 300 followers, then recompute excluding accounts inactive for 30 days.
2. Design the read path for a user who follows 20 celebrities and 400 normal accounts, naming every store touched.
3. Interview: A user with 80M followers posts. Walk through what happens. (Hint: the answer is mostly about what does not happen at write time, and where the cost reappears instead.)

Design a Notification Service

Notifications are the system every other system depends on and nobody owns properly. The core requirement is deceptively simple — deliver a message to a user through email, SMS, push, or in-app — and the difficulty is entirely in the surrounding concerns: third-party providers that fail, user preferences that must be honoured, deduplication, rate limiting so people are not spammed, and the fact that sending is not idempotent from the recipient's point of view.

Requirements. Accept notification requests from many internal services; resolve the user's channel preferences and locale; render from templates; deliver via provider integrations with retries; track delivery status; enforce quiet hours, frequency caps, and unsubscribes; support both transactional (must arrive: password reset, payment receipt) and promotional (best-effort) traffic.

Estimates. 10M notifications/day is ~115/s average with sharp peaks — a marketing campaign to 5M users, or an incident alert, arrives as a burst orders of magnitude above average. That burst profile is why the design is queue-first: the API must accept work quickly and let workers drain at the rate providers allow.

 NOTIFICATION PIPELINE

  producer services
        |  POST /notifications {user, event_type, payload, dedupe_key}
        v
  [ API: validate, dedupe, enqueue ]      <- returns immediately (202 Accepted)
        |
        v
  [ preference & eligibility filter ]     <- channel opt-ins, quiet hours,
        |                                    frequency caps, unsubscribes,
        |                                    LEGAL: transactional bypasses
        v                                    promotional suppression
  [ template render (locale, i18n) ]
        |
        v
  [ per-channel queues: push | email | sms | in-app ]   <- separate queues so a
        |        |       |       |                          slow provider cannot
        v        v       v       v                          block another channel
  [ provider adapters: FCM/APNs, SES, Twilio ] -- circuit breakers (9.2),
        |                                          rate limits, failover provider
        v
  [ delivery status via webhooks ] -> analytics, bounce/complaint handling

from datetime import datetime, timedelta

class NotificationRouter:
    TRANSACTIONAL = {"password_reset", "payment_receipt", "security_alert"}

    def should_send(self, user, event_type: str, now: datetime) -> tuple[bool, str]:
        # Transactional notifications bypass preference suppression — they are
        # often a legal or security obligation, not a marketing choice.
        if event_type in self.TRANSACTIONAL:
            return True, "transactional"

        if not user.prefs.get(event_type, {}).get("enabled", True):
            return False, "user_opted_out"
        if user.globally_unsubscribed:
            return False, "unsubscribed"

        # Quiet hours are evaluated in the USER's timezone, not the server's.
        local_hour = now.astimezone(user.tz).hour
        if user.quiet_start <= local_hour or local_hour < user.quiet_end:
            return False, "quiet_hours_defer"          # defer, do not drop

        sent_today = self.counter.get(user.id, window=timedelta(days=1))
        if sent_today >= user.daily_cap:
            return False, "frequency_cap"
        return True, "ok"

    def enqueue(self, user, event_type: str, payload: dict, dedupe_key: str):
        # DEDUPLICATION: retries from producers, and duplicate upstream events,
        # must not produce two notifications. The key is the producer's
        # responsibility to make meaningful (e.g. "order-123-shipped").
        if not self.dedupe.set_if_absent(dedupe_key, ttl=86_400):
            return "duplicate_suppressed"
        ok, reason = self.should_send(user, event_type, datetime.utcnow())
        if not ok:
            return reason
        channel = self.pick_channel(user, event_type)   # push -> email fallback
        self.queues[channel].publish({
            "user_id": user.id, "event_type": event_type,
            "payload": payload, "attempt": 0, "dedupe_key": dedupe_key})
        return "queued"

Delivery reliability is at-least-once by construction: providers time out ambiguously, so a retry may produce a second delivery. That makes the dedupe key the primary defence, and it must be checked at the point of send, not only at enqueue. Retries need exponential backoff with jitter (13.3), a bounded attempt count, and a dead-letter queue that a human actually reviews. Provider failures should trip a circuit breaker and fail over to a secondary provider where the channel supports it.

Priority separation is non-negotiable in the queue design. A password reset must not sit behind a five-million-message marketing campaign, so transactional and promotional traffic get separate queues (and often separate provider credentials, since bulk sending damages sender reputation and can throttle transactional email).

Fan-out control is the other operational hazard: an incident that triggers one notification per affected entity can generate millions of messages, so the service needs aggregation ("3 new comments" rather than three notifications), per-user frequency caps as above, and a global kill switch for a campaign that is going wrong.

Key Takeaways

• Accept fast and queue: bursts are the normal traffic shape, not an anomaly.
• Separate queues per channel and per priority so bulk traffic cannot block transactional delivery.
• Preferences, quiet hours, and frequency caps are filters in the pipeline; transactional notifications legitimately bypass most of them.
• Delivery is at-least-once — deduplicate on a producer-supplied key at send time.
• Wrap every provider in a circuit breaker with retry backoff, a dead-letter queue, and a failover provider.
• Aggregate related notifications and keep a global kill switch.

🧪 Practice

1. Design the schema for user notification preferences supporting per-event, per-channel opt-outs plus quiet hours across timezones.
2. Work out the retry policy for push notifications, including backoff, attempt cap, and what lands in the dead-letter queue.
3. Interview: A bug caused 2 million duplicate emails. What in your design should have prevented it, and what limits the damage? (Hint: think about the two separate places a duplicate can be caught, and what caps the blast radius even when both fail.)

Design a Social Graph Service

The social graph answers questions that look simple and are computationally awkward at scale: who does this user follow, who follows them, are these two users connected, and what does a friend-of-a-friend traversal return. The difficulty is that the graph is enormous, extremely skewed (most users have hundreds of edges; some have hundreds of millions), and read at a rate far above the rate at which it changes.

Requirements. Follow and unfollow; list followers and following with pagination; test whether A follows B in a single-digit millisecond; compute mutual connections; produce follower counts. Non-functional: reads dominate writes by roughly 1000:1, and the "does A follow B" check sits on the critical path of nearly every other feature, so it must be fast enough to call unconditionally.

Storage model. A graph database is the obvious fit and is the wrong default at this scale for the common queries; the dominant production pattern is adjacency lists in a partitioned key-value or wide-column store, with each direction of the edge stored separately.

 EDGE STORAGE: STORE BOTH DIRECTIONS

  following:<user_id> -> sorted set of followee_ids   (partition by user_id)
  followers:<user_id> -> sorted set of follower_ids   (partition by user_id)

  follow(A, B) writes TWO records in different partitions:
     following:A += B      followers:B += A

  Why duplicate? Because "who follows B" would otherwise be a full scan of every
  user's following list. The cost is that a follow is a distributed write that
  must be made idempotent and eventually consistent (a queue-driven second write
  with retry is normal; a cross-partition transaction is usually not worth it).

 SKEW: followers:<celebrity> can hold 100M entries. It must be a paginated,
 partitioned structure — never a single value read in one operation.

class SocialGraph:
    def follow(self, follower: str, followee: str) -> str:
        if follower == followee:
            return "self_follow_rejected"
        if self.blocks.exists(followee, follower):     # blocks override follows
            return "blocked"

        # Idempotent: repeating a follow must not double-count anything.
        created = self.kv.zadd_if_absent(f"following:{follower}", followee)
        if not created:
            return "already_following"

        # Second write in another partition. Publish rather than write inline so
        # a partition failure retries instead of leaving one side missing.
        self.outbox.publish({"op": "add_follower", "user": followee,
                             "other": follower})
        self.counters.increment(f"following_count:{follower}")
        self.counters.increment(f"follower_count:{followee}")   # approximate
        return "ok"

    def is_following(self, a: str, b: str) -> bool:
        # The hottest query in the system. Cached aggressively; a Bloom filter
        # per user answers the overwhelmingly common NO case without a lookup.
        if not self.bloom(a).might_contain(b):
            return False                       # definitive negative, no I/O
        return self.kv.zscore(f"following:{a}", b) is not None

    def mutual_connections(self, a: str, b: str, limit: int = 10) -> list[str]:
        # Intersect the SMALLER set against the larger — never materialize both.
        sa, sb = self.kv.zcard(f"following:{a}"), self.kv.zcard(f"following:{b}")
        small, large = (a, b) if sa <= sb else (b, a)
        out = []
        for uid in self.kv.zscan(f"following:{small}"):        # streamed
            if self.kv.zscore(f"following:{large}", uid) is not None:
                out.append(uid)
                if len(out) == limit:
                    break
        return out

Counts deserve their own treatment. An exact follower count for a celebrity requires either a counter that becomes a write hotspot or a COUNT over 100M entries. The standard resolution is a sharded counter (increment a random one of N shards, sum on read) with a cached value refreshed periodically — and accepting that displayed counts are approximate and eventually consistent, which every large platform does.

Traversals beyond one hop are where the design must push back. Friend-of-a- friend across high-degree nodes explodes combinatorially, so second-degree queries are answered from precomputed, bounded results (a nightly job producing "people you may know" candidates, 14.3.3) rather than at request time. Interactive multi-hop traversal is a graph-database workload and belongs in a separate system fed asynchronously, not on the serving path.

Finally, privacy semantics must be part of the design rather than a filter bolted on top: blocks must be enforced on both read and write paths, private accounts turn follows into pending requests, and the visibility rule must be evaluated at read time because relationships change after content is created.

Key Takeaways

• Store adjacency lists in both directions; the duplicate write is what makes "who follows me" cheap.
• The double write is cross-partition — make it idempotent and drive the second side from a queue rather than a distributed transaction.
• "Does A follow B" is the hottest query: cache it, and use a per-user Bloom filter to answer the common negative without I/O.
• Degree skew is the defining constraint: celebrity follower lists must be paginated and never read whole.
• Counts are approximate at scale — shard the counters and cache the result.
• Precompute multi-hop results offline; do not traverse at request time.
• Blocks and privacy are read-time checks, not a one-off write-time filter.

🧪 Practice

1. Design the pagination scheme for a 100M-entry follower list, including a cursor that remains stable while new followers arrive.
2. Implement follower counts with sharded counters and quantify the read cost versus a single counter's write contention.
3. Interview: A user unfollows someone but still sees their posts for a few minutes. Is this acceptable? (Hint: think about which precomputed structures hold the stale relationship, and what it would cost to make the change immediate everywhere.)

Design a Comment and Reaction System

Comments and reactions attach user-generated content to any other entity — a post, a video, a product — and they are the highest-write-rate feature most products have. Two properties make them harder than they look: comments are a tree, not a list, and reactions are a counter update that concentrates on whatever is currently viral, producing extreme write hotspots on a small number of keys.

Requirements. Post a comment, optionally replying to another comment; list a thread with pagination and a sensible ordering (chronological, or ranked by engagement); react to a comment or a post; show aggregate reaction counts and whether the current user has reacted; edit and delete; moderate.

Estimates. 500M reactions/day is ~6k/s average, but a viral item can attract 50k reactions per second by itself — a single-row update rate no relational database will sustain. That number, not the average, dictates the design.

Storing the tree. Three representations, chosen by how deep threads go:

Model	Read a thread	Insert	Depth limit	Best for
Parent pointer	Recursive queries	O(1)	Unlimited	Shallow threads
Materialized path	One prefix range scan	O(1)	Path length	Deep, ordered trees
Nested set	One range query	O(n)	Unlimited	Read-only trees

Materialized paths are the usual production choice because a whole subtree is one sorted range scan, and correct display ordering falls out of the sort.

class CommentStore:
    """Materialized path: each comment stores the ordered path to its root.
    Path segments are fixed-width and zero-padded so lexical sort == tree order."""

    WIDTH = 10

    def create(self, entity_id: str, author: str, body: str,
               parent_id: str | None = None) -> dict:
        seq = self.counter.next(entity_id)          # monotonic per entity
        segment = str(seq).zfill(self.WIDTH)
        if parent_id:
            parent = self.get(parent_id)
            if parent["depth"] >= 6:
                # CAP DEPTH: unlimited nesting is unreadable on mobile and makes
                # paths unbounded. Deeper replies attach to the depth-6 ancestor.
                parent = self.get(parent["path"].split("/")[6])
            path, depth = f"{parent['path']}/{segment}", parent["depth"] + 1
        else:
            path, depth = segment, 0

        comment = {"id": self.ids.next_id(), "entity_id": entity_id,
                   "author": author, "body": body, "path": path, "depth": depth,
                   "created_at": time.time(), "deleted": False}
        self.db.insert(comment)                      # partition key: entity_id
        self.counters.increment(f"comments:{entity_id}")
        return comment

    def thread(self, entity_id: str, after_path: str | None, limit: int = 50):
        # ONE range scan returns a correctly ordered slice of the whole tree:
        # sorting by path yields parents immediately before their children.
        return self.db.scan(partition=entity_id, sort_key_gt=after_path,
                            limit=limit)

# path examples, sorted lexically -> exactly the display order:
#   0000000001                 top-level comment
#   0000000001/0000000004      reply to it
#   0000000001/0000000004/0000000009   reply to the reply
#   0000000002                 next top-level comment

Reactions are a different problem: a high-frequency counter plus a per-user membership set (so the UI can show "you reacted"). The naive UPDATE posts SET likes = likes + 1 serializes every reaction to a viral post on one row lock. The production pattern writes an immutable event and aggregates asynchronously, combined with a sharded counter for the live display value.

class ReactionService:
    SHARDS = 64

    def react(self, user_id: str, target_id: str, kind: str) -> str:
        # 1. Per-user membership: idempotent, and answers "did I react?"
        added = self.kv.set_if_absent(f"reacted:{target_id}:{user_id}", kind)
        if not added:
            return "already_reacted"

        # 2. Sharded counter: spreads 50k writes/s across 64 keys, so no single
        #    key is a hotspot. Read cost is one multi-get of 64 small values.
        shard = hash(user_id) % self.SHARDS
        self.kv.increment(f"count:{target_id}:{kind}:{shard}")

        # 3. Event for analytics and for rebuilding counts if they drift.
        self.events.publish({"user": user_id, "target": target_id, "kind": kind})
        return "ok"

    def counts(self, target_id: str, kind: str) -> int:
        cached = self.cache.get(f"count:{target_id}:{kind}")
        if cached is not None:
            return cached                    # hot items served from cache
        total = sum(self.kv.multi_get(
            [f"count:{target_id}:{kind}:{s}" for s in range(self.SHARDS)]))
        self.cache.set(f"count:{target_id}:{kind}", total, ttl=5)  # short TTL:
        return total                         # counts may lag by seconds — fine

Ranking and moderation complete the design. Ordering a large thread purely chronologically buries the good replies, so ranked ordering (engagement, author reputation, recency) is computed asynchronously and cached per thread. Deletion should be a tombstone rather than a physical delete, because removing an interior node would orphan its subtree — render deleted nodes as placeholders when they have children. Moderation hooks into the write path for synchronous blocking of obvious violations and into an asynchronous pipeline (15.3.5) for everything else.

Key Takeaways

• Comments are a tree: materialized paths turn subtree reads into a single ordered range scan.
• Cap nesting depth — unbounded threads are unreadable and make paths unbounded.
• Partition by the parent entity so a whole thread lives in one partition.
• Reactions concentrate writes on viral items: shard the counter and never increment a single row.
• Keep a per-user membership record for idempotency and for "you reacted".
• Counts are eventually consistent with a short cache TTL; the event log allows rebuilding them.
• Delete with tombstones so interior nodes do not orphan their subtrees.

🧪 Practice

1. Design the pagination cursor for a threaded view that loads top-level comments with two replies each, then expands on demand.
2. Compute the write rate on a single counter row for a post receiving 30k reactions/second, and show how 64 shards change it.
3. Interview: A post goes viral and reaction counts stop updating. What broke and how would you have prevented it? (Hint: think about which single key every one of those writes is contending for, and what the read path could tolerate instead.)

<a id="153-media-and-content-systems"></a>

15.3 Media and Content Systems

Media systems move bytes that are millions of times larger than the metadata describing them, which inverts the usual priorities: the database is trivial and the storage, encoding, and delivery paths are where the entire design lives. This subchapter covers video on demand, photo sharing, file sync, live streaming, and the moderation pipeline that every user-generated content platform eventually needs.

Design a Video Streaming Platform

A video platform accepts uploads, transforms them into a set of formats suitable for every device and network condition, and delivers them to millions of concurrent viewers. The volume asymmetry defines everything: a 4K source file is tens of gigabytes, while its metadata row is a few hundred bytes, and one upload may be watched a billion times. So the design is a pipeline plus a delivery network, with a small database off to the side.

Requirements. Upload large files reliably over unreliable connections; transcode into multiple resolutions and bitrates; stream adaptively so playback survives changing bandwidth; support seeking; and track view counts and watch progress. Non-functional: playback must start in under ~2 seconds, rebuffering must be rare, and the system must serve globally.

Estimates. 500 hours uploaded per minute at ~1 GB/hour source is ~500 GB/min of ingest (~8.5 TB/hour). Transcoding into 6 renditions typically produces 1.5-2x the source size in outputs. Viewing dominates by orders of magnitude: 1 billion watch-hours/day at an average 3 Mbps is ~1,350 Tbps-hours, which is why essentially all delivery must come from a CDN — origin serving at that scale is not financially or physically viable.

 VIDEO PIPELINE

 UPLOAD                        PROCESSING                       DELIVERY
 client                         [ queue ]                       viewer
   | pre-signed URL                 |                             |
   v (direct to object store,       v                             v
   | never through your API)  [ transcode workers ]          [ CDN edge ]
   | chunked + resumable       split into segments             | miss
   v                           -> parallel encode per          v
 [ object storage: raw ]          rendition                 [ origin / object
   |                           -> package HLS/DASH             storage: HLS
   +--> event ---------------> -> thumbnails, captions          segments ]
                               -> write manifest
                                    |
                                    v
                              [ metadata DB: status, durations,
                                rendition list, manifest URL ]

Upload must be resumable, because a 20 GB upload over a mobile connection will be interrupted. The client requests a pre-signed URL and uploads directly to object storage in parts, so bytes never traverse the application tier; the application only receives a completion event. This one decision removes the largest bandwidth cost and the largest source of request-timeout failures.

Transcoding is embarrassingly parallel if you split first. Cutting the source into segments at keyframe boundaries lets N workers encode N segments concurrently, turning a 4-hour serial job into a 5-minute parallel one.

LADDER = [                     # a standard adaptive bitrate ladder
    {"name": "240p",  "width": 426,  "bitrate_kbps": 400},
    {"name": "360p",  "width": 640,  "bitrate_kbps": 800},
    {"name": "480p",  "width": 854,  "bitrate_kbps": 1400},
    {"name": "720p",  "width": 1280, "bitrate_kbps": 2800},
    {"name": "1080p", "width": 1920, "bitrate_kbps": 5000},
    {"name": "2160p", "width": 3840, "bitrate_kbps": 15000},
]

def plan_transcode(source_width: int, duration_s: float, segment_s: int = 6):
    """Split into segments, then fan out over (segment x rendition) tasks.
    Never upscale: encoding 1080p source to 4K wastes storage and bandwidth
    for no visible gain."""
    renditions = [r for r in LADDER if r["width"] <= source_width]
    segments = int(duration_s // segment_s) + 1
    tasks = [(seg, r["name"]) for seg in range(segments) for r in renditions]
    serial_min = duration_s * len(renditions) * 0.5 / 60       # ~0.5x realtime
    return {"renditions": [r["name"] for r in renditions],
            "segments": segments, "parallel_tasks": len(tasks),
            "serial_estimate_min": round(serial_min, 1),
            "with_200_workers_min": round(serial_min / min(200, len(tasks)), 2)}

print(plan_transcode(source_width=1920, duration_s=3600))
# {'renditions': [...5 items...], 'segments': 601, 'parallel_tasks': 3005,
#  'serial_estimate_min': 150.0, 'with_200_workers_min': 0.75}

Adaptive bitrate streaming (HLS or DASH) is what makes playback robust. The video is packaged as short segments at every rendition, plus a manifest listing them; the player measures throughput and buffer level and picks the next segment's rendition itself. The server is stateless — it serves files — which is precisely why a CDN can absorb the entire load.

 HLS MANIFEST STRUCTURE

  master.m3u8
    #EXT-X-STREAM-INF:BANDWIDTH=800000,RESOLUTION=640x360   -> 360p/index.m3u8
    #EXT-X-STREAM-INF:BANDWIDTH=2800000,RESOLUTION=1280x720 -> 720p/index.m3u8

  720p/index.m3u8
    #EXTINF:6.0,  seg_00001.ts
    #EXTINF:6.0,  seg_00002.ts        <- player fetches these one at a time and
    ...                                  can switch ladder rungs at any boundary

  Player logic: buffer low or throughput dropping -> step DOWN a rung immediately;
  step UP only after sustained headroom, because oscillation is worse than a
  slightly lower resolution.

Delivery and cost. The CDN is not an optimization here, it is the architecture: origin egress at this scale would dominate every other cost line (13.4). Popular content is cached at the edge with very high hit rates, while the long tail is served from a mid-tier or origin. Storage tiering matters too — videos have a sharply decaying access curve, so old, rarely-watched renditions move to cold storage, and rarely-requested renditions can be deleted and re-encoded on demand.

Trade-offs worth naming: pre-transcoding every rendition costs storage and compute for videos nobody watches (mitigate by encoding only low renditions eagerly and the rest on first request); per-title encoding (choosing the ladder from content complexity) saves substantial bandwidth over a fixed ladder; and DRM plus signed URLs are required for licensed content, which constrains how much the CDN can cache.

Key Takeaways

• Upload directly to object storage with pre-signed, resumable, chunked uploads — never through the application tier.
• Split into segments first: transcoding is then embarrassingly parallel.
• Encode an adaptive ladder, never upscale beyond the source resolution.
• HLS/DASH keeps the server stateless and moves adaptation into the player, which is what makes CDN delivery possible.
• The CDN is the architecture, not an add-on; origin egress would dominate all other costs.
• Tier storage by access decay, and consider on-demand encoding for the long tail.

🧪 Practice

1. Compute storage for one hour of source video encoded into six renditions, then estimate the monthly cost of retaining 500 hours/minute of uploads.
2. Design the transcoding job graph so a single failed segment does not force a full re-encode.
3. Interview: A user in a poor network region reports constant buffering. Walk through the diagnosis. (Hint: think about what the player decides, what the manifest offers it, and how far the bytes are travelling.)

Design a Photo Sharing Service

Photo sharing sits between a social feed and a media pipeline: uploads are small relative to video but arrive in enormous numbers, each original spawns several derived sizes, and the read pattern is a feed of thumbnails punctuated by occasional full-size views. The design questions are how many derivatives to generate and when, and how to keep the feed fast when it renders dozens of images per screen.

Requirements. Upload photos with metadata; generate thumbnails and display sizes; serve them fast in feeds and albums; support albums, tags, and sharing permissions; handle EXIF (orientation matters, location often must be stripped).

Estimates. 100M photos/day at 3 MB average is 300 TB/day of originals. Derived sizes typically add 30-40% on top. Reads are far heavier: if each photo is viewed 20 times as a thumbnail and 2 times full size, thumbnail traffic dominates request count while full-size dominates bytes — which is why the two are tuned separately.

 PHOTO PIPELINE

  client --pre-signed PUT--> [ object storage: originals ]
     |                              |
     | POST metadata                +-- event --> [ derivative workers ]
     v                                              |-- 150px  square thumb
  [ metadata DB ]                                   |-- 640px  feed image
    photo_id, owner, album, caption,                |-- 1080px detail view
    dimensions, taken_at, visibility,               |-- WebP/AVIF variants
    derivative status                               '-- strip EXIF GPS
     |                                              |
     v                                              v
  [ feed / album service ] <----- URLs ----- [ object storage: derivatives ]
                                                    |
                                                    v
                                               [ CDN ]  <- all reads

  Alternative: an image-resizing CDN generates sizes ON DEMAND from the original
  and caches them. Fewer stored variants, more first-request latency.

Derivative generation is the main trade-off. Pre-generating every size gives uniform fast reads and costs storage for sizes nobody requests; on-demand resizing at the edge stores only the original and pays a one-time latency cost per (size, format) combination. The common compromise is to pre-generate the two or three sizes the product renders most (thumbnail and feed image) and derive the rest on demand.

from dataclasses import dataclass

@dataclass
class Derivative:
    name: str
    max_edge: int
    quality: int
    eager: bool          # generated at upload time vs on first request

DERIVATIVES = [
    Derivative("thumb",  150,  80, eager=True),   # every feed renders these
    Derivative("feed",   640,  82, eager=True),
    Derivative("detail", 1080, 85, eager=False),  # only on photo open
    Derivative("full",   2048, 88, eager=False),
]

def process_upload(photo_id: str, original_bytes: bytes, exif: dict) -> dict:
    # EXIF orientation must be APPLIED and then stripped: clients that ignore
    # the tag render sideways photos, and this is the classic "why is it rotated"
    # bug. GPS is stripped for privacy unless the user opted in (11.4).
    normalized = apply_orientation(original_bytes, exif.get("Orientation", 1))
    safe_exif = {k: v for k, v in exif.items()
                 if not k.startswith("GPS") and k != "SerialNumber"}

    outputs = {}
    for d in DERIVATIVES:
        if d.eager:
            outputs[d.name] = encode(normalized, d.max_edge, d.quality,
                                     formats=("avif", "webp", "jpeg"))
    return {"photo_id": photo_id, "exif": safe_exif, "derivatives": outputs,
            "lazy": [d.name for d in DERIVATIVES if not d.eager]}

def pick_url(photo_id: str, viewport_px: int, dpr: float, accepts: set[str]):
    """Serve the smallest derivative that still covers the rendered size, in the
    best format the client accepts. Serving a 2048px image into a 320px slot is
    the most common and most expensive mistake in image delivery."""
    needed = viewport_px * dpr
    choice = next((d for d in DERIVATIVES if d.max_edge >= needed),
                  DERIVATIVES[-1])
    fmt = ("avif" if "image/avif" in accepts else
           "webp" if "image/webp" in accepts else "jpeg")
    return f"https://cdn.example.com/{photo_id}/{choice.name}.{fmt}"

print(pick_url("p_123", viewport_px=320, dpr=2.0, accepts={"image/webp"}))
# https://cdn.example.com/p_123/feed.webp   (640px covers 320 x 2)

Metadata and permissions are an ordinary database problem, with one caveat: visibility must be enforced on the URL, not only in the API. Because images are served from a CDN by URL, a private photo protected only by an API check is public to anyone with the link. Private content needs signed URLs with short expiry, and the signature must be verified at the edge.

Feed rendering is the performance path. It should return a batch of URLs plus dimensions (so the client can reserve layout space and avoid reflow), use progressive or blurred placeholders for perceived speed, and let the client request only the sizes it will actually display. Deduplicate identical uploads by content hash — a surprising fraction of uploads are re-shares of the same bytes.

Key Takeaways

• Upload originals directly to object storage; process derivatives asynchronously from an event.
• Pre-generate the sizes the product renders constantly, derive the rest on demand.
• Apply and then strip EXIF: orientation must be baked in, GPS removed by default.
• Serve the smallest derivative that covers the rendered size, in the best format the client accepts.
• CDN URLs bypass API authorization — private photos need signed URLs verified at the edge.
• Return dimensions with feed URLs so clients avoid layout reflow.
• Deduplicate by content hash before storing.

🧪 Practice

1. Compute the storage overhead of four derivative sizes plus three formats per photo, and decide which combinations to make eager.
2. Design the signed-URL scheme for private albums, including expiry and what happens when a link is shared after revocation.
3. Interview: The mobile feed is slow on 3G despite a CDN. What do you investigate? (Hint: think about how many bytes are actually being sent per visible image, and which decision determines that.)

Design a File Storage and Sync Service

A sync service keeps a set of files identical across a user's devices and the cloud. It is deceptively hard because it is a distributed-consistency problem disguised as a file browser: devices go offline, edit the same file, run out of disk, and reconnect in any order, and the system must converge without silently destroying anyone's work.

Requirements. Upload and download files; sync changes to all devices quickly; work offline and reconcile on reconnect; version history; sharing with permissions; efficient handling of large files and small edits. Non-functional: minimize bandwidth (users edit a 2 GB file by changing 40 KB), never lose data, and detect conflicts explicitly rather than resolving them by luck.

Chunking is the core mechanism. Files are split into content-defined chunks, each identified by its hash. Sync then transfers only chunks the other side lacks, which delivers deduplication (across versions, files, and users) and delta transfer from one idea.

 CONTENT-DEFINED CHUNKING vs FIXED-SIZE

 fixed 4 MB blocks:  [A][B][C][D]
   insert 1 byte at the start -> every block shifts -> ALL blocks change
   -> full re-upload of a 2 GB file for a one-byte edit

 content-defined (rolling hash picks boundaries at data-dependent points):
   [A][B][C][D]
   insert 1 byte -> [A'][B][C][D]   only the affected chunk changes
   -> upload one ~4 MB chunk. This property is why sync services use it.

import hashlib

WINDOW, MIN_CHUNK, MAX_CHUNK = 48, 2 << 20, 8 << 20
MASK = (1 << 22) - 1                 # ~4 MB average chunk size

def content_defined_chunks(data: bytes):
    """Split at data-dependent boundaries so an insertion shifts only ONE chunk.
    (A production implementation uses a proper rolling hash such as Buzhash;
    this shows the boundary condition.)"""
    chunks, start, h = [], 0, 0
    for i in range(len(data)):
        h = ((h << 1) + data[i]) & 0xFFFFFFFF           # cheap rolling value
        size = i - start + 1
        if size >= MIN_CHUNK and (h & MASK) == 0 or size >= MAX_CHUNK:
            chunks.append(data[start:i + 1])            # boundary found
            start, h = i + 1, 0
    if start < len(data):
        chunks.append(data[start:])
    return chunks

def sync_plan(local: list[bytes], remote_hashes: set[str]):
    """Upload only chunks the server does not already hold — from ANY user,
    since chunks are content-addressed and therefore globally deduplicated."""
    manifest, to_upload = [], []
    for c in local:
        h = hashlib.sha256(c).hexdigest()
        manifest.append(h)
        if h not in remote_hashes:
            to_upload.append((h, len(c)))
    return {"manifest": manifest, "upload_chunks": len(to_upload),
            "upload_bytes": sum(n for _, n in to_upload)}

Change propagation uses a per-account monotonically increasing cursor. Each device stores its last-seen cursor; on reconnect it asks for everything after it, which handles offline periods, missed notifications, and duplicates uniformly. Live notification (a long-lived connection or push) is an optimization on top of the cursor, not a replacement for it — the cursor is what guarantees eventual convergence.

 SYNC PROTOCOL

  device                                 server
    |-- GET /delta?cursor=1041 --------->|
    |<-- {changes:[...], cursor:1073} ---|   changes since the device last synced
    |                                    |
    |-- PUT /commit {path, base_rev,     |   base_rev = the revision the edit
    |     manifest:[chunk hashes]} ----->|   was made against
    |<-- 409 CONFLICT {server_rev} ------|   someone else committed meanwhile
    |                                    |
    |-- creates "file (conflicted copy   |   NEVER silently pick a winner for
    |   from Ana's laptop).docx" ------->|   opaque binary content

Conflict handling must be explicit. Last-write-wins on a document silently destroys work; the standard behaviour is optimistic concurrency (commit against a base revision, reject if the server moved) followed by preserving both versions as a conflicted copy for the user to resolve. Structured formats can do better — operational transformation or CRDTs merge concurrent edits automatically — but that only applies where the system understands the file's internal structure.

Metadata versus data should scale separately: the metadata service (file tree, revisions, permissions, cursors) is a transactional database sharded by account, while the chunk store is a content-addressed blob store that is append-only and trivially cacheable. Deletion then requires reference counting before a chunk can be reclaimed, since many files and users may share it.

Key Takeaways

• Content-defined chunking gives delta transfer and global deduplication from one mechanism; fixed-size blocks break on insertion.
• Content-addressed chunks let the server skip any chunk it already holds, from any user.
• A per-account monotonic cursor is what makes offline reconnection converge; push notification is only an optimization.
• Use optimistic concurrency with a base revision, and preserve conflicted copies rather than picking a winner.
• Separate the transactional metadata service from the append-only chunk store.
• Deleting shared chunks requires reference counting.

🧪 Practice

1. Compute the bytes transferred when a 2 GB file changes by 100 KB in the middle, under fixed 4 MB blocks versus content-defined chunking.
2. Design the offline queue on the client, including ordering, retry, and what happens when the local queue conflicts with itself.
3. Interview: Two users edit the same file offline and reconnect. What does your system do? (Hint: the honest answer depends on whether the system can parse the file — say what you do when it cannot.)

Design a Live Streaming System

Live streaming shares its vocabulary with video on demand and almost none of its constraints. The content does not exist before it is requested, so nothing can be precomputed; latency is a product requirement rather than a nicety; and viewer count can go from zero to a million in the seconds after a notification fires. Every design decision trades latency against scale and robustness.

Requirements. Ingest a live feed from a broadcaster; transcode to multiple renditions in real time; deliver to a large, spiky audience; keep glass-to-glass latency within the product's tolerance; optionally record for later VOD; support chat or reactions alongside.

Latency tiers determine the protocol, and this is the first thing to establish, because it constrains everything downstream:

Tier	Latency	Technology	Use case
Standard	30-60 s	HLS/DASH, 6-10 s segments	Large broadcasts
Low latency	5-15 s	LL-HLS/LL-DASH, chunks	Sports, live events
Ultra-low	1-3 s	LL-HLS tuned, CMAF	Auctions, betting
Real-time	< 500 ms	WebRTC	Video calls, interaction

The relationship is mechanical: HLS latency is roughly the segment duration times the number of segments the player buffers, so cutting latency means smaller segments — more requests, more overhead, and less resilience to a network hiccup.

 LIVE PIPELINE

  broadcaster --RTMP/SRT/WebRTC--> [ ingest edge ]
                                        |  (authenticate stream key,
                                        |   pick nearest POP)
                                        v
                                  [ live transcoder ]  real-time, no retries:
                                        |  a late frame is a dropped frame
                                        |  -> renditions + CMAF/LL-HLS packaging
                                        v
                                  [ origin: rolling window of segments,
                                    typically only the last 1-5 minutes ]
                                        |
                          +-------------+-------------+
                          v             v             v
                     [ CDN edge ]  [ CDN edge ]  [ CDN edge ]
                          |             |             |
                       viewers       viewers       viewers

  KEY PROPERTY: every viewer requests the SAME newest segment at nearly the same
  time, so CDN cache hit rates are extremely high — one origin fetch serves a
  million viewers. This is what makes live scale at all.

def latency_budget(segment_s: float, buffer_segments: int,
                   encode_s: float = 1.0, network_s: float = 0.5) -> dict:
    """Glass-to-glass latency for segmented live streaming."""
    packaging = segment_s                  # cannot publish a partial segment
    player_buffer = segment_s * buffer_segments
    total = encode_s + packaging + network_s + player_buffer
    return {"segment_s": segment_s, "buffer_segments": buffer_segments,
            "glass_to_glass_s": round(total, 1)}

for seg, buf in ((6, 3), (2, 3), (1, 2)):
    print(latency_budget(seg, buf))
# {'segment_s': 6, 'buffer_segments': 3, 'glass_to_glass_s': 25.5}
# {'segment_s': 2, 'buffer_segments': 3, 'glass_to_glass_s': 9.5}
# {'segment_s': 1, 'buffer_segments': 2, 'glass_to_glass_s': 4.5}
# Smaller segments cut latency but multiply request count and leave the player
# less buffer to absorb a network stall — the trade is explicit, not free.

Ingest needs its own resilience story. The broadcaster's uplink is the least reliable component in the system, so the ingest tier should accept a reconnect without terminating the stream, support a backup ingest URL, and apply adaptive bitrate on the contribution side. Transcoding is real time and cannot retry: if a worker falls behind, it must drop frames or degrade quality rather than queue, because queued live video is just late video.

Scale-up is the other distinctive problem. A notification to millions of followers produces a near-instantaneous viewer surge, and every one of those players requests the manifest and the same segment at once. Mitigations are manifest caching with very short TTLs, jittered client polling so requests do not synchronize, and CDN pre-warming for scheduled events. Where interactivity is not required, a DVR window (a rolling recording) lets late joiners start slightly behind live, which spreads their requests across segments.

Companion features have their own scaling shape: live chat at a million concurrent viewers cannot show every message to everyone, so it is sampled or sharded into rooms; reaction counts use the sharded-counter pattern from 15.2.5.

Key Takeaways

• Nothing can be precomputed: content is created as it is consumed.
• Latency is set by segment duration times player buffer — pick the tier first, since it constrains protocol and architecture.
• WebRTC is the only sub-second option and does not scale like HTTP segments; segmented protocols scale via the CDN.
• Every viewer wants the same newest segment, giving extremely high CDN hit rates — this is why live scales.
• Real-time transcoding must drop rather than queue; queued live video is late video.
• Handle ingest reconnection and provide a backup ingest path.
• Surges are the normal traffic shape: jitter client polling and pre-warm for scheduled events.

🧪 Practice

1. Compute glass-to-glass latency for 4-second segments with a 3-segment buffer, then find the configuration that reaches under 5 seconds.
2. Design the failover path for a broadcaster whose connection drops for 20 seconds mid-stream.
3. Interview: A stream with 2 million viewers has 30-second latency and you need 5. What changes and what does it cost? (Hint: identify each additive term in the latency budget and what shrinking it does to request volume and stall resilience.)

Design a Content Moderation Pipeline

Any platform accepting user-generated content must decide what to allow. The engineering problem is that volume makes full human review impossible, accuracy requirements differ enormously by category, and the cost of both error types is high — leaving harmful content up damages users, while removing legitimate content damages trust. The pipeline design is fundamentally about routing decisions to the cheapest mechanism that can make them reliably.

Requirements. Screen text, images, and video at upload and post-publication; enforce policy categories with different severity; support automated action, human review, and user appeals; keep an audit trail; adapt as policies and adversaries change. Non-functional: synchronous checks must fit the upload latency budget, and the queue must be prioritized so severe content is reviewed first.

The tiered funnel is the standard architecture, and it mirrors the recommendation funnel of 14.3.3: cheap filters first, expensive judgement last.

 MODERATION FUNNEL

  upload ---> [ TIER 0: deterministic checks ]      microseconds, synchronous
              hash matching against known-bad
              (PhotoDNA/CSAM, terrorism hashes),
              blocklists, banned domains
                 | match -> BLOCK immediately + mandatory reporting
                 v no match: publish (or hold, by policy)
              [ TIER 1: ML classifiers ]            ~100 ms, asynchronous
              nudity, violence, spam, hate speech
                 | score > high_threshold  -> auto-remove
                 | score in grey band      -> queue for humans
                 | score < low_threshold   -> allow
                 v
              [ TIER 2: human review ]              minutes to hours
              prioritized by severity x reach
                 |
                 v
              [ decision: allow / remove / restrict / escalate ]
                 |-- notify user, offer appeal
                 '-- feed labelled outcome back into training data (14.4.6)

  USER REPORTS enter at Tier 1 or 2 directly, weighted by reporter reliability.

from dataclasses import dataclass

@dataclass
class Policy:
    category: str
    auto_remove_at: float     # score above this: remove without human review
    review_at: float          # score above this: send to humans
    severity: int             # drives queue priority

POLICIES = [
    Policy("csam",       0.50, 0.30, severity=100),   # low threshold on purpose:
    Policy("violence",   0.95, 0.70, severity=80),    # false positives are far
    Policy("nudity",     0.92, 0.60, severity=40),    # cheaper than misses here
    Policy("spam",       0.98, 0.85, severity=10),    # opposite trade-off
]

def route(scores: dict[str, float], reach: int) -> dict:
    for p in sorted(POLICIES, key=lambda x: -x.severity):
        s = scores.get(p.category, 0.0)
        if s >= p.auto_remove_at:
            return {"action": "remove", "category": p.category,
                    "appealable": True, "audit": {"score": s, "auto": True}}
        if s >= p.review_at:
            # Priority mixes severity with exposure: a borderline item seen by
            # 2M people outranks a worse item nobody has seen.
            priority = p.severity * (1 + min(reach, 1_000_000) / 100_000)
            return {"action": "queue_review", "category": p.category,
                    "priority": round(priority, 1),
                    "visibility": "restricted" if p.severity >= 50 else "normal"}
    return {"action": "allow"}

print(route({"nudity": 0.65, "spam": 0.20}, reach=2_000_000))
# {'action': 'queue_review', 'category': 'nudity', 'priority': 440.0,
#  'visibility': 'restricted'}

Thresholds encode policy, not accuracy. The same classifier is deployed at different operating points per category because the cost asymmetry differs: for the most severe categories a false positive (removing legitimate content) is far cheaper than a false negative, so thresholds are low and appeals matter; for spam the reverse holds. Making this explicit in configuration — rather than burying it in a model — is what lets policy change without retraining.

Human review is a system, not a step. It needs prioritized queues, reviewer tooling that shows only what is necessary (with blurring and rotation limits for wellbeing), inter-rater agreement sampling to measure quality, and a feedback loop that turns decisions into labelled training data. Reviewer capacity is the binding constraint, so anything that reduces queue volume without reducing safety — better thresholds, deduplication by content hash, batching identical items — has outsized value.

Appeals and auditability close the loop and are increasingly a regulatory requirement: every automated action needs a recorded reason, a notification, an appeal path, and a retention policy for the evidence. Adversarial adaptation is constant — obfuscated text, cropped or re-encoded images, coded language — so the pipeline needs perceptual hashing rather than exact hashing, continuous evaluation on fresh samples, and the drift monitoring of 14.4.6 pointed at the classifiers.

Key Takeaways

• Tier the pipeline: deterministic hash matching, then classifiers, then humans, in increasing cost order.
• Thresholds encode policy and cost asymmetry per category — keep them in configuration, not in the model.
• Prioritize the human queue by severity times reach, not by arrival order.
• Human reviewers are the binding constraint: deduplicate, batch, and tune thresholds to protect their capacity.
• Feed human decisions back as labelled training data.
• Appeals, notification, and audit trails are requirements, not extras.
• Adversaries adapt: use perceptual hashing and monitor classifiers for drift.

🧪 Practice

1. Set thresholds for three categories with different cost asymmetries, and justify each operating point.
2. Design the review queue's priority function and show how it orders four example items with differing severity and reach.
3. Interview: Your classifier flags 5% of uploads for review, which is ten times your reviewer capacity. What do you do? (Hint: think about which dimension of the funnel you can move — the threshold, the queue, or what happens to items while they wait.)

<a id="154-transactional-and-real-time-systems"></a>

15.4 Transactional and Real-Time Systems

These systems share a property the previous ones did not: being wrong costs money or safety, not just engagement. Double-charging a card, selling the same seat twice, or dispatching two drivers to one rider are failures no amount of eventual consistency excuses — so this subchapter is largely about where to spend the expensive coordination, and how to stay correct under retries, partitions, and extreme write concentration.

Design a Payment System

Payments are the canonical correctness-critical system: money must not be created or destroyed, a customer must not be charged twice, and every state change must be explainable months later during a dispute. The complication is that the authoritative action happens in someone else's system — a card network or bank that can time out ambiguously, leaving you unsure whether the charge succeeded. The design is therefore built around idempotency, explicit state machines, and reconciliation.

Requirements. Charge a customer via a payment provider; support refunds and partial refunds; handle asynchronous webhook confirmations; maintain an auditable ledger; reconcile against provider settlement reports; never double-charge, even under client retries and network failures.

The ledger is the source of truth, not the account balance. Double-entry bookkeeping makes correctness a checkable invariant rather than a hope: every transaction writes balanced entries whose sum is zero, and a balance is derived by summing entries rather than being mutated in place. A mutated balance can be wrong silently; an unbalanced ledger cannot.

 DOUBLE-ENTRY LEDGER: charge a customer 100.00, of which 3.20 is fee

  transaction_id  account                    debit     credit
  txn_9001        customer_receivable       100.00
  txn_9001        merchant_payable                     96.80
  txn_9001        platform_revenue_fees                 3.20
                                            -------   -------
                                            100.00    100.00   <- MUST balance

 Entries are IMMUTABLE and append-only. A refund is a NEW transaction with the
 opposite entries, never an edit or a delete of the original. This is what makes
 history reconstructible and audits possible.

from dataclasses import dataclass
from decimal import Decimal          # NEVER float: 0.1 + 0.2 != 0.3 in binary
from enum import Enum

class PaymentState(Enum):
    CREATED = "created"
    AUTHORIZING = "authorizing"      # provider call in flight: outcome UNKNOWN
    AUTHORIZED = "authorized"
    CAPTURED = "captured"
    FAILED = "failed"
    REFUNDED = "refunded"

# Explicit transitions: anything not listed is a bug, and the state machine
# rejects it rather than silently corrupting the record.
ALLOWED = {
    PaymentState.CREATED:     {PaymentState.AUTHORIZING},
    PaymentState.AUTHORIZING: {PaymentState.AUTHORIZED, PaymentState.FAILED},
    PaymentState.AUTHORIZED:  {PaymentState.CAPTURED, PaymentState.FAILED},
    PaymentState.CAPTURED:    {PaymentState.REFUNDED},
    PaymentState.FAILED:      set(),
    PaymentState.REFUNDED:    set(),
}

class PaymentService:
    def charge(self, idempotency_key: str, customer: str,
               amount: Decimal, currency: str) -> dict:
        # 1. IDEMPOTENCY: the client retries on timeout with the SAME key.
        #    Store the key with the request fingerprint BEFORE calling out.
        existing = self.db.get_by_key(idempotency_key)
        if existing:
            if existing["fingerprint"] != self._fp(customer, amount, currency):
                raise ValueError("idempotency key reused with different params")
            return existing            # replay the original outcome, do not charge

        payment = self.db.create(idempotency_key=idempotency_key,
                                 fingerprint=self._fp(customer, amount, currency),
                                 state=PaymentState.CREATED, amount=amount)

        # 2. Record the ATTEMPT before the external call. If we crash here, the
        #    row exists in AUTHORIZING and reconciliation resolves it later.
        self.db.transition(payment.id, PaymentState.AUTHORIZING)
        try:
            result = self.provider.authorize(
                customer, amount, currency,
                idempotency_key=idempotency_key)   # providers honour this too
        except TimeoutError:
            # 3. AMBIGUOUS: the charge may have succeeded. Do NOT retry blindly
            #    and do NOT mark failed — leave it pending for reconciliation.
            self.db.mark_needs_reconciliation(payment.id)
            return {"state": "pending", "payment_id": payment.id}

        state = (PaymentState.AUTHORIZED if result.approved
                 else PaymentState.FAILED)
        self.db.transition(payment.id, state)
        if state is PaymentState.AUTHORIZED:
            self.ledger.post(payment.id, entries=self._entries(payment))
        return {"state": state.value, "payment_id": payment.id}

Ambiguous failures are the defining problem. A timeout means the outcome is unknown, not that it failed — the money may already have moved. Three mechanisms resolve it together: an idempotency key that both you and the provider honour so a retry cannot double-charge; a pending state that is never guessed into success or failure; and a reconciliation job that compares your ledger against the provider's settlement report daily and flags every discrepancy for investigation. Reconciliation is not optional cleanup — it is the control that proves the system is correct.

Webhooks carry the asynchronous outcomes (capture confirmed, dispute opened, payout settled). They arrive out of order, more than once, and occasionally not at all, so handlers must verify the signature, be idempotent on the event ID, ignore events older than the current state, and be backed by a polling fallback for the ones that never arrive.

Two further requirements shape the schema. Money is never a float — use integer minor units or a decimal type, and store the currency alongside every amount, because a bare number is meaningless. And compliance is structural: card data should never touch your servers (use provider tokenization to stay out of PCI scope), while audit trails, retention rules, and access controls follow from 11.x rather than being added later.

Key Takeaways

• The double-entry ledger is the source of truth; balances are derived, and entries are immutable and append-only.
• Idempotency keys, honoured end to end, are what make client retries safe.
• Timeouts are ambiguous: never guess the outcome — record pending and resolve by reconciliation.
• Model payment lifecycle as an explicit state machine that rejects illegal transitions.
• Webhooks are duplicated, out of order, and occasionally lost: verify, deduplicate, and poll as a fallback.
• Store money as integers or decimals with an explicit currency, never floats.
• Tokenize card data so it never enters your systems.

🧪 Practice

1. Write the ledger entries for a 100.00 charge with a 2.9% + 0.30 fee, then for a 40.00 partial refund of it.
2. Design the reconciliation job: inputs, comparison keys, and the categories of discrepancy it must report.
3. Interview: Your service times out calling the payment provider. What do you do? (Hint: enumerate the states the world could actually be in, and pick the action that is safe in all of them.)

Design a Ticket Booking System

Selling assigned seats is a scarce-inventory problem with an ugly traffic profile: demand is near zero until a sale opens, then a hundred thousand people try to buy a few thousand seats within seconds. Overselling is unacceptable, but so is locking inventory so conservatively that the system serializes and nobody can buy anything. The design is about holding scarce resources briefly and correctly under extreme contention.

Requirements. Browse events and seat availability; hold selected seats for a short window while the user pays; confirm the booking on payment; release abandoned holds automatically; never sell one seat twice. Non-functional: survive a 1000x traffic spike at sale opening and keep the purchase path correct even if the browse path degrades.

Estimates. A 50,000-seat venue with 500,000 people attempting to buy means the system must reject or queue 90% of arrivals — which reframes the problem: the dominant design goal is admission control, not throughput. The seat inventory itself is tiny (50,000 rows) and fits comfortably in one database, so the temptation to distribute it should be resisted; a single partition per event is what makes the correctness argument simple.

 BOOKING FLOW

  user --> [ virtual waiting room ]   <- admission control: only N users per
              |  queue position,         second reach the seat map, which keeps
              |  estimated wait          the inventory service inside its
              v                          concurrency limits
        [ seat map (cached, slightly stale — fine for BROWSING) ]
              |
              v  select seats
        [ HOLD: conditional write, 10-minute TTL ]  <- the only strongly
              |  success -> proceed to payment         consistent step
              |  conflict -> "seats just taken", re-render
              v
        [ payment (15.4.1) ]
              |  success -> CONFIRM: hold -> booked, issue tickets
              |  failure/timeout -> hold expires -> seats return automatically
              v
        [ booking record + ticket delivery ]

import time
from datetime import datetime, timedelta

HOLD_SECONDS = 600

class SeatInventory:
    """Seat state lives in ONE partition per event so a multi-seat hold is a
    single-partition transaction. This is the whole correctness argument."""

    def hold(self, event_id: str, seat_ids: list[str], user_id: str) -> dict:
        now = datetime.utcnow()
        with self.db.transaction() as tx:
            rows = tx.select_for_update(
                "SELECT seat_id, state, hold_expires_at FROM seats "
                "WHERE event_id = %s AND seat_id = ANY(%s)", event_id, seat_ids)

            unavailable = [
                r["seat_id"] for r in rows
                if r["state"] == "booked"
                # An expired hold is available again — checked lazily on read
                # rather than by a sweeper job, so there is no race with expiry.
                or (r["state"] == "held" and r["hold_expires_at"] > now)]
            if unavailable:
                return {"ok": False, "unavailable": unavailable}

            hold_id = self.ids.next_id()
            tx.execute(
                "UPDATE seats SET state='held', hold_id=%s, held_by=%s, "
                "hold_expires_at=%s WHERE event_id=%s AND seat_id = ANY(%s)",
                hold_id, user_id, now + timedelta(seconds=HOLD_SECONDS),
                event_id, seat_ids)
            # All-or-nothing: a partial hold would strand seats and confuse
            # the user. The transaction gives us that for free.
            return {"ok": True, "hold_id": hold_id,
                    "expires_at": now + timedelta(seconds=HOLD_SECONDS)}

    def confirm(self, hold_id: str, payment_id: str) -> dict:
        with self.db.transaction() as tx:
            rows = tx.select_for_update(
                "SELECT seat_id FROM seats WHERE hold_id=%s AND state='held' "
                "AND hold_expires_at > NOW()", hold_id)
            if not rows:
                # The hold expired while the user was paying: refund, do not
                # book. Taking money for seats you cannot deliver is worse.
                return {"ok": False, "reason": "hold_expired", "refund": payment_id}
            tx.execute("UPDATE seats SET state='booked', payment_id=%s "
                       "WHERE hold_id=%s", payment_id, hold_id)
            return {"ok": True, "seats": [r["seat_id"] for r in rows]}

Why a hold rather than a lock at payment time. The user needs minutes to enter card details, and holding a database lock for minutes would serialize the entire event. A hold is a short-lived state in the row with an expiry, checked lazily on the next read — no sweeper job, no race between the sweeper and a confirmation. The trade-off is that seats can appear unavailable to others while a user abandons checkout, which is why hold windows are short and clearly communicated.

The waiting room is what actually makes the sale survivable. It is a queue in front of the application that admits users at a rate the inventory service can serve, gives each a position and estimate, and enforces a signed token so nobody can skip it. Without it, every mitigation downstream is fighting a load the system was never sized for.

Consistency trade-offs to state explicitly. Browsing availability can be stale and cached — showing a seat that was taken half a second ago is acceptable because the hold step is authoritative. General-admission events (no assigned seats) reduce to a counter and can use optimistic decrements with a reservation token, which scales far better than row locking. And every downstream integration — payment, ticket delivery, email — must be idempotent, because retries in this system are certain.

Key Takeaways

• Keep an event's inventory in a single partition so holds and confirmations are single-partition transactions.
• Use short TTL holds, not long-lived locks, and check expiry lazily on read.
• Make multi-seat holds all-or-nothing.
• A virtual waiting room is admission control — it is the primary defence against the sale-opening spike.
• Browse paths may be stale and cached; only the hold step needs strong consistency.
• If the hold expires during payment, refund rather than book.
• General admission is a counter problem and scales differently from assigned seating.

🧪 Practice

1. Choose a hold duration and justify it against abandonment rate and inventory turnover.
2. Design the waiting room token: contents, signature, expiry, and how it stops queue-jumping.
3. Interview: 100,000 users try to buy 5,000 seats at 10:00:00 exactly. Walk through what your system does. (Hint: think about what has to happen before any of that traffic reaches the inventory table.)

Design a Ride-Hailing Service

Ride-hailing joins two moving populations in real time: riders who want a car now and drivers whose positions change every few seconds. The system must ingest a continuous stream of location updates, answer "which drivers are near this point" in milliseconds, and — the genuinely hard part — assign each driver to exactly one rider despite many concurrent matching attempts.

Requirements. Drivers publish location continuously; riders request a trip from a pickup point; the system matches a nearby suitable driver; both parties track the trip live; pricing and payment on completion. Non-functional: matching within seconds, location writes at very high volume, and no double-assignment of a driver.

Estimates. 1M active drivers reporting every 4 seconds is 250k location writes/second — a write rate that rules out a conventional indexed table and argues for an in-memory geospatial store with periodic durable snapshots. Trip requests are far rarer (perhaps 5k/s at peak), so reads and matching are cheap compared with ingest.

Geospatial indexing is the enabling technique. Latitude/longitude pairs cannot be range-scanned in two dimensions efficiently, so systems map 2D space onto a 1D key that preserves locality — geohash, S2 cells, or H3 hexagons. Nearby points then share a key prefix, and a proximity query becomes a handful of prefix lookups.

import math

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"

def geohash(lat: float, lon: float, precision: int = 7) -> str:
    """Interleave latitude and longitude bits so spatial proximity becomes
    string-prefix proximity. Precision 7 is roughly a 150 x 150 m cell."""
    lat_r, lon_r = [-90.0, 90.0], [-180.0, 180.0]
    bits, bit, ch, out = [], 0, 0, []
    even = True
    while len(out) < precision:
        if even:
            mid = sum(lon_r) / 2
            if lon > mid: ch = (ch << 1) | 1; lon_r[0] = mid
            else:         ch = ch << 1;       lon_r[1] = mid
        else:
            mid = sum(lat_r) / 2
            if lat > mid: ch = (ch << 1) | 1; lat_r[0] = mid
            else:         ch = ch << 1;       lat_r[1] = mid
        even = not even
        bit += 1
        if bit == 5:
            out.append(BASE32[ch]); bit, ch = 0, 0
    return "".join(out)

def haversine_km(a: tuple, b: tuple) -> float:
    R = 6371.0
    dlat, dlon = math.radians(b[0] - a[0]), math.radians(b[1] - a[1])
    x = (math.sin(dlat / 2) ** 2
         + math.cos(math.radians(a[0])) * math.cos(math.radians(b[0]))
         * math.sin(dlon / 2) ** 2)
    return 2 * R * math.asin(math.sqrt(x))

class DriverLocationIndex:
    def __init__(self, precision: int = 6):          # ~1.2 km cells
        self.precision = precision
        self.cells: dict[str, dict[str, tuple]] = {}
        self.driver_cell: dict[str, str] = {}

    def update(self, driver_id: str, lat: float, lon: float) -> None:
        cell = geohash(lat, lon, self.precision)
        old = self.driver_cell.get(driver_id)
        if old and old != cell:
            self.cells[old].pop(driver_id, None)     # moved to a new cell
        self.cells.setdefault(cell, {})[driver_id] = (lat, lon)
        self.driver_cell[driver_id] = cell

    def nearby(self, lat: float, lon: float, radius_km: float = 3.0):
        # Query the cell PLUS its neighbours: a rider near a cell edge would
        # otherwise miss the closest driver, sitting just across the boundary.
        centre = geohash(lat, lon, self.precision)
        candidates = []
        for cell in [centre] + self._neighbours(centre):
            for did, pos in self.cells.get(cell, {}).items():
                d = haversine_km((lat, lon), pos)
                if d <= radius_km:                   # exact filter after prefix
                    candidates.append((d, did))      # scan
        return sorted(candidates)

Matching must guarantee exclusivity. Several riders can be matched concurrently to the same nearby driver, so the assignment step needs an atomic compare-and-set on driver state (available -> assigned); losers re-run matching against the remaining candidates. Batched matching — collecting requests over a 2-3 second window and solving the assignment jointly — produces measurably better global outcomes than greedy first-come matching, at the cost of a small delay.

 MATCHING

  request -> [ candidate drivers from geo index: ~20 within 3 km ]
                |
                v  score: ETA (road network, not straight line), rating,
                |         vehicle class, driver acceptance history
                v
          [ atomic claim: CAS driver.state available -> assigned ]
                |  success -> offer to driver, start trip lifecycle
                |  lost race -> next candidate
                v
          [ driver declines / times out -> return to pool, offer next ]

  Trip state machine: requested -> matched -> accepted -> arriving ->
                      in_progress -> completed -> paid
  Every transition is persisted; a phone dying mid-trip must not lose the trip.

Surge pricing is a control loop, not a pricing feature: it measures the demand/supply ratio per geographic cell over a short window and raises the multiplier to suppress demand and attract drivers. It must be smoothed and capped, because rapid oscillation produces both user outrage and unstable driver behaviour.

The remaining engineering is ordinary but load-bearing: location updates go to an in-memory store with a durable stream behind them (losing the last few seconds of positions is fine; losing trip state is not); ETAs come from a routing service over real road networks rather than straight-line distance; and trip state must be persisted at every transition so an app crash or a dead battery does not lose an in-progress ride.

Key Takeaways

• Map 2D coordinates to 1D locality-preserving keys (geohash, S2, H3) so proximity queries are prefix lookups.
• Always query neighbouring cells — a rider at a cell boundary would otherwise miss the nearest driver.
• Filter candidates by exact distance after the prefix scan.
• Location writes dominate: keep them in memory with a durable stream behind, and accept losing the last few seconds.
• Assignment needs an atomic state transition; batched matching beats greedy matching at a small latency cost.
• Rank by road-network ETA, not straight-line distance.
• Persist every trip state transition; surge pricing must be smoothed and capped.

🧪 Practice

1. Choose a geohash precision for a dense city and justify it against expected drivers per cell.
2. Design the driver-decline flow, including timeouts and how you avoid offering the same trip repeatedly to unresponsive drivers.
3. Interview: Two riders are matched to the same driver simultaneously. How do you prevent it? (Hint: think about what must be atomic, and what the loser of the race should experience.)

Design a Proximity and Geospatial Service

The previous system needed moving points; this one generalizes to the static case — "what is near me?" for restaurants, stores, chargers, or listings. The data changes rarely and is read constantly, which inverts the trade-offs: you can afford heavy precomputation and rich indexes, and the interesting questions become boundary correctness, density skew, and how to combine spatial filtering with everything else the query asks for.

Requirements. Find places within a radius or a viewport, ranked by distance and relevance; filter by attributes (open now, category, rating, price); paginate stably; support tens of thousands of queries per second over tens of millions of places.

Indexing options differ in how they behave under uneven density, which is the defining property of real geographic data — a city block may hold 500 restaurants while a rural cell holds none.

Structure	Idea	Strength	Weakness
Geohash prefix	Interleaved bits -> string prefix	Simple, works in any KV store	Fixed grid; edge cases
Quadtree	Recursive subdivision	Adapts to density	Rebalancing on updates
S2 cells	Sphere -> Hilbert curve cells	No pole distortion, ranges	Conceptually heavier
H3 hexagons	Hexagonal grid	Uniform neighbour distance	No perfect parent nesting
R-tree / PostGIS	Bounding-box tree	Rich queries, polygons	Single-node scaling limits

For most products the honest answer is PostGIS (or an equivalent spatial index) until it stops scaling, then a cell-based scheme in a distributed store. The migration is easier than starting with the complex option.

class GeoSearchService:
    """Cell-indexed places with an adaptive search radius, so both dense city
    centres and sparse rural areas return useful results."""

    def search(self, lat: float, lon: float, filters: dict,
               limit: int = 20, max_radius_km: float = 40.0):
        radius = 1.0
        seen: dict[str, tuple] = {}
        while radius <= max_radius_km:
            # Choose the cell precision from the radius: coarse cells for wide
            # searches, fine cells for tight ones. Using one fixed precision
            # either scans too much in cities or too little in the countryside.
            precision = self._precision_for(radius)
            for cell in self._cover(lat, lon, radius, precision):
                for place in self.index.get(cell, []):
                    if place.id in seen:
                        continue
                    d = haversine_km((lat, lon), (place.lat, place.lon))
                    if d <= radius and self._matches(place, filters):
                        seen[place.id] = (d, place)
            if len(seen) >= limit:
                break
            radius *= 2          # expand only when the tight search came up short
        ranked = sorted(seen.values(),
                        key=lambda dp: self._score(dp[0], dp[1]))
        return ranked[:limit]

    def _score(self, distance_km: float, place) -> float:
        # Pure distance ranking surfaces a bad place next door over an excellent
        # one 400 m away. Blend distance with quality and popularity.
        return (distance_km * 1.0
                - place.rating * 0.15
                - min(place.review_count, 500) / 500 * 0.10)

    def _matches(self, place, filters: dict) -> bool:
        # Attribute filters are applied AFTER the spatial narrowing: the spatial
        # index is the selective one, so it should run first.
        return all(getattr(place, k, None) == v for k, v in filters.items())

 THE BOUNDARY PROBLEM (why single-cell lookup is always wrong)

   +--------+--------+           query point Q sits near the right edge of its
   |        |   B    |           cell. Driver/place B is 80 m away but lives in
   |    Q --+--> B   |           the NEIGHBOURING cell. Searching only Q's cell
   |        |        |           misses it entirely.
   +--------+--------+
                                 Fix: search the covering set of cells that
   Always query the covering     intersects the query circle, then filter by
   set, then filter exactly.     exact distance.

Three practical concerns complete the design. Density skew means a fixed precision is wrong everywhere: use adaptive precision (as above) or a structure that subdivides by density. Caching works unusually well here because queries cluster — round the query point to a coarse grid before building the cache key so that nearby users share a cache entry, at the cost of slight ranking imprecision. And stable pagination requires a deterministic sort key including a tiebreaker (distance, then place ID), because floating-point distances tie often enough to reorder pages otherwise.

Key Takeaways

• Spatial indexes map 2D to 1D so proximity becomes a range or prefix query.
• Always search a covering set of cells and then filter by exact distance — single-cell lookup misses near neighbours across boundaries.
• Real geographic density is wildly uneven: use adaptive precision or a density-adaptive structure.
• Apply the spatial filter first — it is the selective one — then attribute filters.
• Rank by a blend of distance and quality; pure distance surfaces bad results.
• Round query points onto a coarse grid for cache keys so nearby users share entries.
• Paginate on a deterministic sort key with an explicit tiebreaker.

🧪 Practice

1. Compute how many cells a 5 km radius query must cover at two different geohash precisions, and pick one.
2. Design the cache key for proximity search including location rounding, filters, and what TTL you would use.
3. Interview: Users in dense city centres get slow responses while rural users get empty ones. Diagnose it. (Hint: one fixed cell size is being asked to serve two very different densities — think about what each case is scanning.)

Design an Ad Serving and Click Aggregation System

Ad systems combine two subsystems with opposite characteristics: serving, which must choose and return an ad within a few tens of milliseconds, and click/impression aggregation, which must count enormous event volumes accurately enough to bill advertisers. The first is a latency problem, the second is a correctness-at-scale problem, and conflating them is the classic design mistake.

Requirements. Serve a relevant ad for a request within a strict latency budget; enforce targeting rules and budget caps; record impressions and clicks; aggregate them into reporting and billing; detect fraudulent traffic. Non-functional: serving p99 under ~50 ms, no material overspend of an advertiser's budget, and counts accurate enough to invoice.

Estimates. 1M ad requests/second at peak with a 1% click-through rate gives 1M impressions/s and 10k clicks/s. At 200 bytes per event that is ~200 MB/s of impression events — far too much to write synchronously to a database, which is why events go to a log and are aggregated by a stream processor (14.2.3).

 TWO SUBSYSTEMS, DELIBERATELY SEPARATED

 SERVING PATH (must be fast)            EVENT PATH (must be accurate)
  request                                impression/click beacon
    | targeting: geo, device,              |
    |  segment, context                    v
    v                                 [ append to log: Kafka ]
  [ candidate ads from in-memory        |          |
    index, ~50 ms budget ]              |          +--> raw archive (replayable
    | filter: budget remaining,         |               source of truth)
    |  frequency cap, brand safety      v
    v                              [ stream aggregation: dedupe by event_id,
  [ rank by eCPM = bid x pCTR ]      windowed counts by campaign/hour ]
    |                                    |
    v                                    +--> near-real-time budget counters
  [ return ad + tracking URLs ]          |     (fed BACK to the serving path)
                                         +--> billing tables (exactly-once,
                                               reconciled daily)

class AdServer:
    BUDGET_SAFETY = 0.95        # stop serving at 95% of budget: counters lag

    def serve(self, request) -> dict | None:
        # 1. Candidate selection from an in-memory index. Everything on this
        #    path is precomputed or local — no database call fits the budget.
        candidates = self.index.match(
            geo=request.geo, device=request.device,
            segments=request.user_segments, context=request.page_category)

        eligible = []
        for ad in candidates:
            # 2. Budget check against a CACHED counter. It lags by seconds, so
            #    the safety margin is what prevents overspend, not precision.
            spent = self.budget_cache.get(ad.campaign_id)
            if spent >= ad.daily_budget * self.BUDGET_SAFETY:
                continue
            if self.freq_cap.count(request.user_id, ad.campaign_id) >= ad.cap:
                continue
            if not self.brand_safety.allows(ad, request.page_category):
                continue
            eligible.append(ad)

        if not eligible:
            return None

        # 3. Rank by expected value, not raw bid: a high bid on an ad nobody
        #    clicks is worth less than a modest bid that converts.
        for ad in eligible:
            ad.ecpm = ad.bid * self.ctr_model.predict(ad, request) * 1000
        winner = max(eligible, key=lambda a: a.ecpm)

        # 4. Second-price auction: the winner pays just above the runner-up,
        #    which makes honest bidding the optimal strategy for advertisers.
        runner_up = sorted((a.ecpm for a in eligible), reverse=True)
        price = (runner_up[1] / 1000 if len(runner_up) > 1 else winner.bid * 0.5)

        impression_id = self.ids.next_id()
        self.events.emit({"type": "impression", "id": impression_id,
                          "campaign": winner.campaign_id, "price": price,
                          "ts": time.time()})          # async, never blocking
        return {"ad": winner.creative,
                "click_url": self.sign(impression_id, winner.landing_url)}

Counting accurately is the harder half. Events are delivered at least once, arrive late from mobile devices, and include a meaningful volume of fraudulent traffic. The pipeline therefore deduplicates on an event ID, uses event-time windows with watermarks and allowed lateness (14.2.5), keeps the raw log as a replayable source of truth, and treats the streaming counters as fast-but- approximate while a daily batch recomputation produces the billable numbers. That combination — fast approximate counters for pacing, exact recomputation for billing — is the pragmatic resolution of the accuracy/latency tension.

Budget pacing deserves attention because it is where money leaks. Counters that lag by seconds mean a popular campaign can overspend during the lag, so serving stops at a safety threshold below the true budget, and pacing spreads spend across the day rather than exhausting it in the first hour. Fraud detection runs both inline (obvious bot signatures, impossible click timing) and offline (behavioural clustering), with the offline results producing clawbacks — which is another reason billing must be recomputable rather than incremental only.

Key Takeaways

• Separate the latency-critical serving path from the accuracy-critical event pipeline.
• Everything on the serving path must be in memory or precomputed; there is no budget for a database call.
• Rank by expected value (bid x predicted CTR), not raw bid; second-price auctions make honest bidding optimal.
• Budget counters lag, so stop serving below the true cap and pace spend across the day.
• Deduplicate events by ID, use event-time windows with allowed lateness, and keep the raw log replayable.
• Serve reporting from fast approximate counters; bill from a daily exact recomputation.
• Fraud detection is inline plus offline, with clawbacks — so billing must be recomputable.

🧪 Practice

1. Compute the daily event volume and storage for 1M impressions/second at 200 bytes per event, with 90-day retention.
2. Design the budget-pacing algorithm so a campaign spends evenly across a day instead of exhausting its budget by 09:00.
3. Interview: An advertiser says your click count is 8% higher than their landing-page analytics. How do you investigate? (Hint: the two systems are counting different events at different points — enumerate everything that can happen between a click and a page load.)

Design a Metrics and Monitoring System

A monitoring system is the one piece of infrastructure that must keep working while everything else fails, and it must do so while absorbing one of the highest write rates in the company. Its data has a distinctive shape — timestamped numeric series identified by a metric name plus labels — and exploiting that shape is what makes storing billions of points per day affordable.

Requirements. Ingest metrics from thousands of hosts and services; store them with a retention policy; support aggregation queries over arbitrary time ranges and label filters; evaluate alerting rules continuously; render dashboards quickly. Non-functional: ingest must not lose data during bursts, queries over a day of data must return in seconds, and the system must not depend on the systems it monitors.

Estimates. 10,000 hosts x 1,000 series each, scraped every 15 seconds, is ~667k data points per second. Naively at 16 bytes per point that is ~920 GB/day — and this is where the specialized storage earns its place: time-series compression routinely reduces this by 10-20x.

 TIME-SERIES COMPRESSION (the reason TSDBs exist)

  raw:  (t=1693526400, v=42.5) (t=1693526415, v=42.7) (t=1693526430, v=42.6)
        16 bytes each

  DELTA-OF-DELTA on timestamps: intervals are almost always identical, so the
  second difference is almost always ZERO -> a few BITS per point.
     1693526400, +15, +0, +0, +0, ...

  XOR on values: consecutive float values share most of their bits, so the XOR
  is mostly zeros -> store only the differing window.
     42.5 ^ 42.7 -> a handful of significant bits

  Result: ~1.3 bytes per point instead of 16 (Gorilla-style encoding).
  920 GB/day -> ~75 GB/day.

class TimeSeriesIngest:
    """Two-tier storage: recent data in memory for fast queries and alert
    evaluation, older data compressed into immutable blocks on disk."""

    def __init__(self, block_minutes: int = 120):
        self.head: dict[str, list[tuple[int, float]]] = {}   # series -> points
        self.block_seconds = block_minutes * 60

    def series_key(self, name: str, labels: dict[str, str]) -> str:
        # Labels are part of the identity: high-cardinality labels (user_id,
        # request_id, full URLs) create MILLIONS of series and are the single
        # most common way to destroy a metrics system.
        label_str = ",".join(f"{k}={v}" for k, v in sorted(labels.items()))
        return f"{name}{{{label_str}}}"

    def write(self, name: str, labels: dict[str, str], ts: int, value: float):
        key = self.series_key(name, labels)
        if len(self.head) > 2_000_000 and key not in self.head:
            raise MemoryError("series cardinality limit — reject, do not OOM")
        self.head.setdefault(key, []).append((ts, value))

    def flush_block(self, now: int) -> dict:
        """Seal the head into an immutable, compressed, indexed block."""
        cutoff = now - self.block_seconds
        block = {k: [p for p in pts if p[0] < cutoff]
                 for k, pts in self.head.items()}
        for k in list(self.head):
            self.head[k] = [p for p in self.head[k] if p[0] >= cutoff]
        return {"series": len(block),
                "points": sum(len(v) for v in block.values())}

def downsample(points: list[tuple[int, float]], interval_s: int):
    """Retention tiering: keep raw data briefly, then roll up. Nobody queries
    15-second resolution from six months ago, but they do query the trend."""
    buckets: dict[int, list[float]] = {}
    for ts, v in points:
        buckets.setdefault(ts - ts % interval_s, []).append(v)
    return [{"ts": b, "min": min(vs), "max": max(vs),
             "avg": sum(vs) / len(vs), "count": len(vs)}
            for b, vs in sorted(buckets.items())]

Push versus pull is the classic architectural fork. Pull (Prometheus-style scraping) gives the monitoring system control over rate and an implicit liveness check — a target that cannot be scraped is itself a signal — but needs service discovery and struggles with short-lived jobs and networks it cannot reach. Push (StatsD, OpenTelemetry-style) handles ephemeral jobs and NAT boundaries naturally but lets a misbehaving client flood the system, so it needs its own rate limiting. Most large deployments use pull for infrastructure and push for batch jobs and client-side telemetry.

Cardinality is the defining failure mode. Every distinct label combination is a separate series, so adding a user_id label to a metric turns one series into millions, and the system dies of memory rather than of write volume. Defences are structural: limit labels at the client library, reject high-cardinality writes at ingest, and monitor series counts as a first-class metric.

Alerting and retention complete the picture. Alert rules evaluate over recent data on a schedule; they need for durations to avoid flapping, grouping and deduplication so one incident does not produce 400 pages, and an evaluation path that does not depend on the long-term store. Retention is tiered: raw resolution for days, downsampled rollups for months, and aggregated summaries for years. And the monitoring system must be independently deployed and independently alerted on — often by a small external watchdog — because a monitoring system that fails silently is worse than none at all.

Key Takeaways

• Time-series data compresses enormously via delta-of-delta timestamps and XOR values — roughly 1-2 bytes per point.
• Two-tier storage: a recent in-memory head for queries and alerting, immutable compressed blocks for history.
• Label cardinality, not write volume, is what kills metrics systems — limit it at the client and reject it at ingest.
• Pull gives rate control and implicit liveness; push handles ephemeral jobs and NAT; most systems use both.
• Downsample on a retention ladder: raw for days, rollups for months.
• Alerts need for durations, grouping, and deduplication to stay actionable.
• Monitoring must not depend on what it monitors, and needs an external watchdog of its own.

🧪 Practice

1. Compute daily storage for 500k points/second at 16 bytes raw and at 1.3 bytes compressed, then apply a 3-tier retention policy.
2. Identify three labels that would explode cardinality in a web service, and propose what to record instead.
3. Interview: Your metrics system falls over during an incident — exactly when you need it. What went wrong and how do you prevent it? (Hint: think about what changes in the metric stream during an incident, and which dimension of the data grows fastest.)

<a id="155-communicating-a-design"></a>

15.5 Communicating a Design

A design that nobody understands does not get built, and a design nobody can critique gets built wrong. This subchapter covers the communication half of the discipline — structuring a discussion under time pressure, drawing diagrams that carry information, defending trade-offs honestly, absorbing new constraints mid-conversation, avoiding the failure patterns that reliably sink designs, and writing the document that outlives the meeting.

Interview Framework and Time Allocation

A system design discussion is not a quiz with a correct answer; it is a simulation of a design meeting, and it is assessed on how you navigate ambiguity, justify choices, and manage scope. The most common failure is not ignorance — it is spending thirty minutes on a beautiful database schema and never reaching the part of the system that was actually hard. A time budget prevents that, in the same way a latency budget prevents one service consuming the whole request (13.1.1).

The framework is a sequence, and the discipline is finishing each step before moving on.

 45-MINUTE DESIGN DISCUSSION

 +------+------------------------+---------------------------------------------+
 | Time | Phase                  | What you must produce                       |
 +------+------------------------+---------------------------------------------+
 | 5m   | Requirements           | 3-5 functional bullets, 3-4 non-functional; |
 |      | clarification          | ONE sentence stating what is out of scope   |
 | 5m   | Scale estimation       | QPS, storage, bandwidth — and the ONE       |
 |      |                        | number that drives the architecture         |
 | 5m   | API + data model       | 3-4 endpoints, core entities, access        |
 |      |                        | patterns (the queries decide the store)     |
 | 10m  | High-level design      | Boxes and arrows end to end; the request    |
 |      |                        | path traced aloud for one operation         |
 | 15m  | Deep dive              | The 1-2 genuinely hard parts, in detail     |
 | 5m   | Bottlenecks + wrap     | What breaks at 10x, what you would monitor  |
 +------+------------------------+---------------------------------------------+

 If you are at 20 minutes with no boxes drawn, you are behind. State that you
 are moving on and move on — the interviewer wants to see you manage the clock.

Requirements first, always. The single highest-value five minutes is spent narrowing the problem, because "design Twitter" has no answer while "design the feed for 300M users with a 200 ms read budget, ignoring DMs and search" does. Ask about scale, read/write ratio, consistency needs, and latency targets — then state explicitly what you are excluding, which shows judgement rather than omission.

# The estimation habit worth memorizing: convert to per-second, then to bytes.
def back_of_envelope(daily_active_users: int, actions_per_user: int,
                     bytes_per_action: int, read_write_ratio: int,
                     peak_multiplier: float = 3.0):
    writes_per_day = daily_active_users * actions_per_user
    write_qps = writes_per_day / 86_400
    return {
        "write_qps_avg": round(write_qps),
        "write_qps_peak": round(write_qps * peak_multiplier),
        "read_qps_peak": round(write_qps * read_write_ratio * peak_multiplier),
        "storage_per_day_gb": round(writes_per_day * bytes_per_action / 1e9, 1),
        "storage_5y_tb": round(writes_per_day * bytes_per_action * 365 * 5 / 1e12, 1),
    }

print(back_of_envelope(300_000_000, 2, 1_000, read_write_ratio=100))
# {'write_qps_avg': 6944, 'write_qps_peak': 20833, 'read_qps_peak': 2083333,
#  'storage_per_day_gb': 600.0, 'storage_5y_tb': 1095.0}
# The read QPS is the number that dictates the architecture here — say so, and
# let the rest of the design follow from it.

Numbers matter less for their precision than for what they rule out. Two million reads per second immediately implies caching and CDN tiers, and rules out a single database. Say that consequence out loud — the estimate exists to justify a decision, and an estimate you do not use is wasted time.

Driving the conversation is part of the assessment. Narrate your reasoning ("I am choosing a queue here because the write burst is 50x the average"), offer the trade-off before being asked, and check in at phase boundaries ("that is the high-level design — shall I go deep on the fan-out, or would you rather discuss storage?"). Silence while thinking is fine if you announce it; ten minutes of silent drawing is not.

Key Takeaways

• Budget the time explicitly and move on at each boundary, even mid-thought.
• Spend the first five minutes narrowing scope and stating what is excluded.
• Estimate to justify a decision — name the one number that drives the architecture.
• Design the API and access patterns before choosing a datastore.
• Reserve a third of the time for the genuinely hard part.
• Narrate reasoning and check in at phase boundaries; do not design in silence.

🧪 Practice

1. Write the requirements-clarification questions you would ask for "design a food delivery app", limited to eight.
2. Do the back-of-envelope for 50M daily users posting twice a day at 2 KB, with a 50:1 read ratio, and state which number drives the design.
3. Interview: You are 25 minutes in and have not drawn the architecture. What do you do? (Hint: the recovery is a explicit act of scope management, not faster talking.)

Drawing Effective Architecture Diagrams

A diagram is a compression format for a design. A good one lets someone follow a request through the system without narration; a bad one is a bag of labelled rectangles that requires the author standing next to it. The difference is almost entirely about whether the arrows carry meaning and whether the boxes are at one level of abstraction.

One diagram, one level. The single most common flaw is mixing altitudes — a box labelled "Kubernetes" beside a box labelled "the parseUserToken() helper". The C4 model is a useful discipline: context (systems and external actors), container (deployable units and datastores), component (major pieces inside one container), and code (rarely worth drawing). Pick a level and stay there; drop a level only in a separate diagram.

Arrows are the information. An unlabelled arrow says only "these are connected", which the reader had probably assumed. A labelled arrow says what flows, in which direction, by what protocol, and whether it is synchronous.

 WEAK                                 STRONG

 +------+     +------+                +----------+  POST /orders (sync, 50ms)
 | app  |---->|  db  |                |  client  |------------------------+
 +------+     +------+                +----------+                        |
     |                                                                    v
     v                                +---------------------------------------+
 +-------+                            | order-service (3 replicas, stateless) |
 | cache |                            +----+--------------------+-------------+
 +-------+                                 | SQL (sync)         | publish (async)
                                           v                    v
 Everything is a box. Nothing says   +-------------+      +--------------+
 what flows, what is synchronous,    | orders DB   |      | order.created|
 or what happens when a box dies.    | (Postgres,  |      | (Kafka, 7d)  |
                                     | sharded x4) |      +------+-------+
                                     +-------------+             |
                                                                 v
                                                          +--------------+
                                                          | fulfilment,  |
                                                          | email, search|
                                                          +--------------+

Four conventions do most of the work:

• Solid arrow = synchronous call; dashed = asynchronous/event. This one distinction answers most "what happens if it is down?" questions before they are asked.
• Label every edge with protocol and the operation, not just a technology name.
• Annotate boxes with the property that matters — replica count, shard count, whether it is stateful, retention.
• Left to right, or top to bottom, following the request. A reader should be able to trace the primary flow without their eye jumping backwards.

For whiteboards and interviews specifically: draw the happy path first and get agreement on it before adding replication, caching, and failure handling. Layering detail onto an agreed skeleton reads as structured thinking; drawing everything at once reads as noise. Use numbered steps (1, 2, 3) along the primary flow when the order is not visually obvious, and keep a legend if you use more than two line styles.

Finally, draw the failure story somewhere. A design diagram that only shows the happy path hides exactly the parts reviewers most need to evaluate: what is replicated, what is queued, what degrades, and what has a fallback. That can be annotation on the main diagram or a second one, but it should exist.

Key Takeaways

• Keep one diagram at one level of abstraction; C4 is a useful ladder.
• Arrows carry the information: label protocol, operation, and direction.
• Distinguish synchronous from asynchronous visually — it answers most failure questions implicitly.
• Annotate boxes with the property that matters: replicas, shards, retention, statefulness.
• Lay the diagram out along the request flow, and number the steps.
• Draw the happy path first, then layer on failure handling.
• A diagram with no failure story hides what reviewers most need to see.

🧪 Practice

1. Redraw a system you know at the container level, labelling every arrow with protocol and synchronicity.
2. Take an existing diagram and mark every place where two levels of abstraction are mixed.
3. Interview: Draw the read path for a cached, sharded service and mark what happens on a cache miss and on a shard failure. (Hint: the failure paths are additional arrows from existing boxes, not new boxes.)

Justifying Trade-offs Out Loud

The claim that separates a senior design from a junior one is not "I chose Cassandra" but "I chose Cassandra because the write rate is 200k/s and I can accept eventual consistency for this data, giving up multi-row transactions, which this workload does not need." Every meaningful architectural decision costs something; a design presented as free is a design that has not been thought through, and reviewers read the absence of trade-offs as inexperience rather than as elegance.

The structure of a defensible claim has four parts, and stating them in order takes about fifteen seconds:

 1. DECISION   "I will fan out the feed at write time..."
 2. BECAUSE    "...because reads outnumber writes 100:1 and read latency is the
                product requirement."
 3. GIVING UP  "This costs write amplification — one post becomes 300 writes —
                and makes deletion expensive."
 4. BOUNDARY   "It breaks down above ~100k followers, so celebrities are handled
                by read-time merge instead."

 Part 4 is what distinguishes analysis from recitation: knowing WHERE your own
 choice stops working is the strongest signal you can give.

Name the axis you are trading on. Most architectural decisions move along one of a small number of well-known axes, and naming the axis makes the discussion concrete rather than aesthetic:

Axis	Buying	Paying with
Consistency vs availability	Correctness under partition	Uptime, or higher latency
Latency vs cost	Speed (cache, CDN, replicas)	Money, staleness, complexity
Read vs write optimization	Fast reads (precompute)	Write amplification, storage
Normalization vs duplication	Update simplicity	Join cost at read time
Sync vs async	Immediate feedback	Coupling, tail latency
Simplicity vs flexibility	Fewer failure modes	Rework when requirements shift

Quantify wherever you can. "Caching will help" is an opinion; "a 95% hit rate turns 200k reads/second into 10k database reads/second, which one primary can serve" is an argument. Rough numbers used to support a decision are far more persuasive than precise numbers used decoratively.

def justify_cache(read_qps: int, hit_rate: float, db_capacity_qps: int):
    """Turn a hand-wave into a defensible claim — and notice when it fails."""
    db_load = read_qps * (1 - hit_rate)
    return {
        "db_qps_without_cache": read_qps,
        "db_qps_with_cache": round(db_load),
        "within_capacity": db_load <= db_capacity_qps,
        # The sentence that shows you understand the failure mode, not just the
        # happy path: what does a cold or failed cache do to the database?
        "cold_cache_risk": f"{read_qps // db_capacity_qps}x over capacity "
                           f"if the cache is empty",
    }

print(justify_cache(read_qps=200_000, hit_rate=0.95, db_capacity_qps=15_000))
# {'db_qps_without_cache': 200000, 'db_qps_with_cache': 10000,
#  'within_capacity': True, 'cold_cache_risk': '13x over capacity if the cache
#  is empty'}

Handle disagreement as analysis, not defence. When someone challenges a choice, the productive response identifies the assumption the disagreement rests on: "That works if writes stay under 10k/s — do you expect them higher?" If the challenge is right, change the design and say why, which reads as strength rather than concession. If you genuinely do not know something, say so and state how you would find out; inventing a number is the one move that ends the credibility of everything else you said.

Finally, avoid absolutes. "SQL does not scale" and "microservices are always better" are both false and both signal shallow familiarity. The honest form is conditional: it scales to this point, under these access patterns, at this cost.

Key Takeaways

• State decision, reason, cost, and breaking point — the breaking point is the strongest signal.
• Name the axis you are trading on; it turns aesthetics into engineering.
• Quantify claims: rough numbers supporting a decision beat precise numbers used as decoration.
• Treat challenges as a search for the disagreeing assumption, and change your mind visibly when the challenge is right.
• Say "I do not know, here is how I would find out" rather than inventing facts.
• Avoid absolutes; every scaling claim is conditional on access pattern and cost.

🧪 Practice

1. Write four-part justifications for three decisions in a system you have built, including each one's breaking point.
2. Take a decision you made by default and argue the opposite case as convincingly as you can.
3. Interview: An interviewer says "why not just use Postgres for all of this?" Respond. (Hint: the strong answer usually starts by agreeing further than expected, then identifying the specific workload property that eventually breaks it.)

Handling Follow-Up Constraints

Design conversations do not end at the first working design; they continue with "now it needs to be globally available", "now the write rate is 50x", or "now this data is regulated". These are not attempts to invalidate your work. They test whether you understand your own design well enough to know which part breaks first, and whether you can extend it rather than restart.

The response pattern is diagnostic, not architectural. Before proposing anything, identify what the new constraint actually breaks. Most follow-ups invalidate exactly one assumption, and locating it converts a vague "redesign everything" into a bounded change.

 RESPONDING TO A NEW CONSTRAINT

 1. RESTATE      "So we need to serve users in Europe with the same 200 ms
                  budget, and data must stay in the EU."
 2. LOCATE       "That breaks two things: the single-region database — a
                  cross-Atlantic round trip is 80-140 ms on its own — and the
                  assumption that any replica may hold any user's data."
 3. OPTIONS      "Two directions: read replicas per region with writes still
                  centralised, or full regional sharding by user residency."
 4. RECOMMEND    "I would shard by residency: it satisfies the legal constraint
                  outright, and cross-region access is rare for this workload."
 5. CONSEQUENCE  "It costs us global aggregate queries, which now need an
                  offline pipeline, and migrating a user between regions
                  becomes an explicit operation."

 Skipping step 2 is what produces panicked redesigns of components that were
 never affected.

The common follow-ups and where they land are worth knowing in advance, because they recur across almost every design:

Follow-up	First thing it breaks	Usual direction
"10x the traffic"	The single-writer or hottest partition	Shard the hot key; add async paths
"Make it globally available"	Cross-region latency and data residency	Regional shards, or replicas + local reads
"Now it must be strongly consistent"	Caches and async replication	Move consistency to one boundary, not all
"The dependency is down"	Synchronous coupling	Circuit breakers, queues, degraded modes
"Data must be deletable (GDPR)"	Denormalized copies and derived stores	Reference indirection, crypto-shredding
"Halve the cost"	Over-provisioned always-on capacity	Tiering, autoscaling, sampling

Scale increases deserve a specific habit: work out which component saturates first rather than scaling everything. A 10x traffic increase usually breaks one thing — a single database primary, a hot partition, a synchronous fan-out — and the useful answer names it, then proposes the targeted change and what it costs.

Constraint conflicts should be surfaced, not silently resolved. If asked for strong consistency, global availability, and partition tolerance simultaneously, the correct response is to say that all three cannot hold at once (3.x) and to ask which one bends — usually by identifying the small subset of operations that truly need strong consistency (payments, inventory) while the rest tolerate eventual consistency. That framing turns an impossible request into a scoped design.

Finally, when a follow-up genuinely does invalidate the design, say so plainly. "That changes the fundamental shape — with strict per-user data residency I would not build a single global cluster at all, I would build regional stacks with a thin routing layer" is a much stronger answer than patching a design you no longer believe in.

Key Takeaways

• Locate what the constraint breaks before proposing changes; usually it is one assumption, not the whole design.
• Restate the constraint to confirm you are solving the right problem.
• Offer two options with a recommendation and its consequence, rather than one answer or an unranked list.
• For scale increases, identify the component that saturates first instead of scaling uniformly.
• Apply strong consistency to the narrow set of operations that need it, not the whole system.
• Surface conflicting constraints explicitly and ask which one bends.
• If a constraint genuinely invalidates the design, say so instead of patching.

🧪 Practice

1. Take a design from this chapter and work through what breaks first at 10x, then at 100x.
2. Add a data-residency requirement to one design and list every component that must change.
3. Interview: "Now make it work offline." Respond for a note-taking app. (Hint: identify which operations can be queued locally, and what happens when two devices queued conflicting operations.)

Common Design Anti-Patterns

Most weak designs fail in a small number of recognisable ways, and the patterns repeat across products and experience levels. Learning to spot them in your own work is faster than learning every good pattern, because avoiding these removes most of the risk on its own.

Premature distribution. Splitting into microservices, sharding a database, or adding a message bus before there is a load or organizational problem that requires it buys distributed-systems failure modes — partial failures, eventual consistency, distributed debugging — in exchange for nothing. A single well-indexed Postgres instance on modern hardware serves tens of thousands of queries per second and holds terabytes; most systems never outgrow it. Design for 10x current scale, not 1000x.

Ignoring failure. A design that only describes the happy path is incomplete, because every remote call has at least four outcomes — success, failure, timeout, and ambiguity — and the fourth is the one that corrupts state (15.4.1). The question "what happens when this dependency is slow?" should be answered for every arrow in the diagram, and the answer must not be "we wait".

 THE ANTI-PATTERN CHECKLIST

  [ ] Single point of failure with no failover path
  [ ] Synchronous call chain > 3 deep (latency and failure both multiply)
  [ ] No timeout, or a timeout longer than the caller's own budget
  [ ] Retries without exponential backoff and jitter (retry storms, 13.3)
  [ ] Unbounded queue or unbounded in-memory collection
  [ ] Cache with no stampede protection and no TTL jitter
  [ ] A hot key or hot partition nobody has looked for
  [ ] Non-idempotent write behind an at-least-once delivery path
  [ ] Offset/page-number pagination over data that changes
  [ ] Money in floating point
  [ ] Distributed transaction where a saga or idempotent retry would do
  [ ] Analytics query running against the production OLTP primary
  [ ] Metrics labelled with unbounded-cardinality values
  [ ] "We'll add monitoring later"

Chatty synchronous chains. Service A calls B, which calls C, which calls D, all synchronously. Latency adds, availability multiplies (four services at 99.9% each give 99.6% combined), and one slow dependency stalls the whole chain. The fixes are structural: collapse the chain, parallelize independent calls, or make the tail asynchronous through an event.

The unbounded everything. Unbounded queues turn a temporary slowdown into an out-of-memory crash and hide backpressure until it is too late; unbounded result sets work in development and time out in production; unbounded retries amplify an outage into an outage-plus-retry-storm. Every buffer, page, and retry loop needs an explicit limit and a defined behaviour when it is reached.

Consistency theatre. Two opposite errors, equally common: demanding strong consistency everywhere, which forces coordination onto paths that never needed it and destroys availability; and assuming eventual consistency is harmless everywhere, which produces double-charged customers and oversold inventory. The discipline is to identify the specific operations where a stale read causes real harm, spend the coordination there, and be explicit that everything else is eventually consistent.

Resume-driven design. Choosing a technology for its novelty rather than for the workload — a graph database for a system with no traversals, Kubernetes for three services, a streaming platform for a nightly job. The tell is a design where the justification is a property of the technology rather than a requirement of the system.

Key Takeaways

• Distribute only when load or organizational structure forces it; design for 10x, not 1000x.
• Every remote call has four outcomes, and ambiguity is the dangerous one.
• Deep synchronous chains multiply both latency and failure probability.
• Bound every queue, page, retry, and in-memory collection explicitly.
• Spend consistency where staleness causes real harm; be explicit that the rest is eventual.
• Never put money in floats or analytics on the OLTP primary.
• Choose technology from the workload, not from the technology's properties.

🧪 Practice

1. Run the checklist above against a system you work on and list every item it fails.
2. Take a synchronous four-service chain and redesign it to two hops plus an event, stating what becomes eventually consistent.
3. Interview: A candidate proposes microservices, Kafka, and Kubernetes for a product with 100 users. What do you say? (Hint: the useful critique is about which specific problem each component was intended to solve, not about the components themselves.)

Writing a Design Document

An interview lasts an hour; a design document lasts for years. It is the artefact that gets a design reviewed before it is built, records why decisions were made for the people who inherit them, and turns a discussion involving five people into one that scales to fifty. Writing it is also the most reliable way to discover that a design does not actually work — vagueness survives conversation but not prose.

Structure follows the reader's questions, and most readers will read only the first page, so the document must front-load the answer:

 DESIGN DOCUMENT STRUCTURE

 1. Summary            3-5 sentences: what, why, and the chosen approach.
                       Written LAST, read FIRST, and by most readers ONLY.
 2. Context & problem  What exists today, what is wrong, why now. Include the
                       evidence — metrics, incidents, requests — not adjectives.
 3. Goals / non-goals  Explicit scope. Non-goals prevent the review from
                       expanding into everything the system could ever do.
 4. Requirements       Functional plus measurable non-functional targets
                       ("p99 < 200 ms at 50k rps"), not "must be fast".
 5. Proposed design    Architecture, data model, APIs, request flows, failure
                       behaviour, migration path.
 6. Alternatives       2-3 real options with why each was rejected. This is the
                       section reviewers judge the document by.
 7. Risks & unknowns   What could go wrong, what you have not resolved, and
                       what would change your mind.
 8. Rollout & ops      Migration, feature flags, monitoring, rollback plan,
                       and the cost estimate.
 9. Open questions     Explicit asks, each with a named owner.

The alternatives section carries the most weight. A document with one design reads as a decision already made and invites only superficial comments; a document with three options and clear reasoning invites engagement with the reasoning. Each alternative needs to be presented as genuinely plausible — a straw man that was obviously never considered damages credibility more than omitting the section.

 ALTERNATIVES, WRITTEN WELL

  Option A: Fan-out on write (CHOSEN)
    + O(1) reads, which is the product requirement
    - 300 writes per post; celebrity posts need a separate path
    Chosen because reads outnumber writes 100:1 and read latency is the SLO.

  Option B: Fan-out on read
    + O(1) writes, trivially handles celebrities, no fan-out storage
    - Read latency scales with following count; p99 measured at 900 ms in a
      prototype against 400 followed accounts
    Rejected: fails the 200 ms read SLO at the 90th percentile of following count.

  Option C: Buy a managed feed service
    + Fastest to ship, no operational burden
    - $340k/year at our volume; ranking is not customisable
    Rejected on cost and on the ranking requirement, not on capability.

  Note that B and C are rejected with NUMBERS and against STATED requirements.
  "Too slow" and "too expensive" are not reasons; they are conclusions.

Write for the reader who arrives in two years. That reader needs the constraints that applied at the time — traffic, team size, deadlines, what the alternatives cost — because without them every decision looks arbitrary or stupid. Record the context that made the choice reasonable, and record what you would need to see to revisit it. A short "revisit this if X" line is one of the highest-value sentences in any design document.

Keep it proportional and reviewable. A two-page document that gets read beats a twenty-page one that does not. Use diagrams instead of paragraphs describing diagrams, tables for comparisons, and concrete numbers throughout. Circulate it asynchronously before any meeting so the meeting resolves disagreements rather than transmitting information, and record the outcome of that discussion in the document itself — including the objections that were raised and not adopted, which is exactly the context the future reader will want.

Key Takeaways

• Front-load the summary: most readers read only the first page.
• State non-goals explicitly to keep the review bounded.
• Make non-functional requirements measurable, not adjectival.
• The alternatives section is what reviewers judge; present each option fairly and reject it with numbers against stated requirements.
• Record the constraints and context that made the decision reasonable at the time, plus what would justify revisiting it.
• Include rollout, monitoring, rollback, and cost — a design without an operational plan is incomplete.
• Circulate before the meeting and record the discussion's outcome in the document.

🧪 Practice

1. Write the summary and goals/non-goals sections for a change you are currently working on, in under 300 words.
2. Take a decision already made in your codebase and write the alternatives section that should have accompanied it.
3. Interview: A reviewer says your document is "too long to read". How do you respond? (Hint: think about what the first page is currently doing, and who each subsequent section is actually written for.)