Distributed systems

Before AI systems there was a standard vocabulary for making anything survive traffic: spread the work across machines, keep copies of the data, cache what is expensive, push slow work onto a queue. This section covers those pieces and, more usefully, what each one costs you, since a cache means stale data, a shard key is the decision you cannot undo, and a queue means handling the same message twice. The second half is what a design round is actually testing, and it is what makes the difference at scale.

Why this is still here#

Large companies run conventional system design rounds regardless of how AI-focused the team is. If your target list includes them, this is insurance rather than optional. If it does not, this is the topic to cut.

The one thing that makes this hard#

Inside a single process a function call has two outcomes: it returns, or it raises. Across a network it has three, and the third is the whole subject. The call can return, it can fail in a way you are told about, or it can produce no answer at all — and when there is no answer you cannot tell which of three very different things happened. The request never arrived. The request arrived, was executed, and the reply was lost on the way back. The request arrived and is still running. This is called partial failure, and every pattern in this topic is a response to it.

The consequence people miss is that a client's error rate is not the server's error rate. Put a small chance of a lost reply on top of a small chance of a lost request and count what each side believes.

import random

random.seed(7)
server_state = {"orders": 0}

def call_create_order():
    """Returns what the CLIENT observes, which is not what happened."""
    if random.random() < 0.05:
        return "connection refused"        # never arrived, no order created
    server_state["orders"] += 1            # the server did the work
    if random.random() < 0.10:
        return "timeout"                   # the reply was lost on the way back
    return "ok"

observed = {"ok": 0, "timeout": 0, "connection refused": 0}
for _ in range(10000):
    observed[call_create_order()] += 1

print(observed)
print(f"orders actually created: {server_state['orders']}")
failed = observed["timeout"] + observed["connection refused"]
print(f"calls the client saw as failures: {failed}")
print(f"of those, the work was done anyway: {observed['timeout']} "
      f"({observed['timeout']/failed:.0%})")

# {'ok': 8590, 'timeout': 918, 'connection refused': 492}
# orders actually created: 9508
# calls the client saw as failures: 1410
# of those, the work was done anyway: 918 (65%)

Say that sentence in a design round and you have made the point most candidates never get to: you cannot build reliability out of knowing what happened, because you do not know. You build it out of making it not matter whether it happened twice.

Scaling out#

• Load balancing: spread requests across instances. Health checks decide which are eligible.
• Replication: copies of the data. Reads scale; writes still go to one place, and replicas lag.
• Sharding: split the data across machines by a key. Scales writes, and makes queries that cross shards expensive.
• Choosing a shard key is the decision you cannot easily undo. Get the access pattern right first.

The shard key deserves more than a bullet, because it is where designs actually fail. Sharding by something meaningful, such as a user id, keeps everything about one user on one machine, so a query for that user's data is one round trip. It also hands your load distribution to your traffic distribution, and traffic is never uniform. Sharding by something random, such as a request id, balances perfectly and turns every per-user query into a scatter-gather across every shard.

import random, hashlib, collections

random.seed(3)
SHARDS = 8
users = [f"u{i}" for i in range(50000)]
weights = [1.0] * 50000
for i in range(3):
    weights[i] = 15000.0                     # three accounts with enormous traffic
traffic = random.choices(users, weights, k=100000)

def shard(key, n):
    return int(hashlib.sha256(key.encode()).hexdigest(), 16) % n

for label, keyfn in [("by user id", lambda r, i: r),
                     ("by request id", lambda r, i: f"{r}:{i}")]:
    load = collections.Counter(shard(keyfn(r, i), SHARDS) for i, r in enumerate(traffic))
    counts = [load[s] for s in range(SHARDS)]
    mean = sum(counts) / SHARDS
    print(f"{label:15} {counts}")
    print(f"{'':15} hottest shard {max(counts)/mean:.2f}x the mean, so the cluster "
          f"saturates at {mean/max(counts):.0%} of its nominal capacity")

# by user id      [22273, 22305, 6366, 6846, 22504, 6450, 6580, 6676]
#                 hottest shard 1.80x the mean, so the cluster saturates at 56% of its nominal capacity
# by request id   [12395, 12572, 12575, 12541, 12461, 12422, 12540, 12494]
#                 hottest shard 1.01x the mean, so the cluster saturates at 99% of its nominal capacity

Neither column is the right answer on its own, and saying so is the point. If your access pattern is per-user, shard by user and handle the whales specially — give the three biggest accounts their own shards, or split their data by a compound key such as user and month. If your access pattern is aggregate, shard randomly and accept the scatter-gather. What you must not do is pick a key because it is the obvious identifier and discover the skew in production, because re-sharding a live dataset is a migration measured in weeks.

Caching#

Caching is the cheapest performance win and the source of the most confusing bugs. The hard part is never storing the value, it is knowing when it stopped being true.

• Time-based expiry: simple, and serves stale data for up to the TTL.
• Invalidate on write: fresher, and easy to miss a path that writes.
• Cache stampede: many requests miss at once and all recompute. Use a lock or staggered expiry.
• Decide what stale means for each cached thing. Five minutes is fine for a product description and not for a balance.

Start with the arithmetic of a hit rate, because it is not linear and people reason about it as though it were. What reaches the database is one minus the hit rate, so the interesting region is all at the top.

FRONT = 10000        # requests per second arriving at the cache

print("hit rate   requests reaching the database   multiple of the 99% case")
for hit in [0.80, 0.90, 0.95, 0.99, 0.999]:
    back = FRONT * (1 - hit)
    print(f"{hit:7.1%}   {back:29,.0f}   {back/(FRONT*0.01):22.1f}x")
print(f"cache down {FRONT:29,}   {FRONT/(FRONT*0.01):22.1f}x")

# hit rate   requests reaching the database   multiple of the 99% case
#   80.0%                           2,000                     20.0x
#   90.0%                           1,000                     10.0x
#   95.0%                             500                      5.0x
#   99.0%                             100                      1.0x
#   99.9%                              10                      0.1x
# cache down                        10,000                    100.0x

That last row is the failure mode worth naming out loud, because it is the one that takes services down. Once the cache is carrying ninety-nine per cent of the reads, the database behind it has been sized for one per cent of them, and the cache is no longer an optimisation — it is a load-bearing dependency whose failure multiplies your database load by a hundred. Restarting the cache cluster, deploying a change that alters the key format, or an eviction storm all produce the same event. The defences are to keep enough database capacity to survive a cold cache, to warm a new cache before sending traffic to it, and to shed load rather than pass it all through.

The related failure is the stampede, and it is worth simulating because the obvious fix only fixes half of it. Two hundred keys, a sixty-second expiry, two thousand requests a second and half a second to rebuild one value.

import random

random.seed(11)
KEYS, TTL, RPS, SECONDS, REBUILD = 200, 60, 2000, 300, 0.5   # 0.5 s to rebuild a value

def simulate(stagger, single_flight):
    valid_until = {k: random.uniform(0, TTL) if stagger else TTL for k in range(KEYS)}
    finishes = {}                       # key -> when its in-flight rebuild completes
    total, peak = 0, 0
    for tick in range(SECONDS * 10):    # 100 ms ticks
        now = tick / 10
        for k, done in list(finishes.items()):
            if done <= now:             # rebuild landed, value is fresh again
                valid_until[k] = done + TTL
                del finishes[k]
        started = 0
        for _ in range(RPS // 10):
            k = random.randrange(KEYS)
            if now < valid_until[k]:
                continue                                  # hit
            if single_flight and k in finishes:
                continue                                  # someone is already rebuilding
            finishes[k] = now + REBUILD
            started += 1
        total += started
        peak = max(peak, started * 10)                    # per second
    return total, peak

print(f"{KEYS} keys, {RPS}/s, {TTL} s TTL, {REBUILD} s to rebuild one value")
for label, stagger, sf in [("expire together, no lock", False, False),
                           ("expire together, single flight", False, True),
                           ("staggered TTL, single flight", True, True)]:
    total, peak = simulate(stagger, sf)
    print(f"  {label:32} rebuilds {total:7,}   peak {peak:6,}/s")

# 200 keys, 2000/s, 60 s TTL, 0.5 s to rebuild one value
#   expire together, no lock         rebuilds  70,021   peak  2,000/s
#   expire together, single flight   rebuilds     800   peak  1,290/s
#   staggered TTL, single flight     rebuilds     995   peak     40/s

The two fixes address different problems and you generally want both. A single-flight lock stops N concurrent misses on one key becoming N rebuilds. Jittered expiry — a TTL of sixty seconds plus a random few, rather than exactly sixty — stops every key expiring at the same moment, which is what happens whenever a cache is populated in bulk. If you have ever seen a service that is fine for an hour and then falls over at precisely the hour mark, this is why.

Queues#

A queue decouples accepting work from doing it. Essential for anything slow, which includes most AI work. Accept the request, return immediately, process in the background, notify when done.

Client -> API (returns a job id immediately)
              |
              v
           Queue -> Worker -> result store
              |
        Client polls or receives a webhook

• At-least-once delivery is the norm, so handlers must be idempotent.
• A dead letter queue holds what failed repeatedly, so one bad message does not block the rest.
• Backpressure: decide what happens when the queue grows faster than workers drain it.

That last bullet is the one that is usually written down and never designed, so it is worth working properly. Two facts about queues are not obvious, and both are arithmetic. The first is that waiting time explodes long before capacity runs out. For a queue with random arrivals and one server, the mean time a job spends in the system is one over the service rate minus the arrival rate, which means the wait is governed by the headroom, not by the load.

SERVICE_MS = 10.0                       # one job takes 10 ms of work
mu = 1000 / SERVICE_MS                  # 100 jobs a second

print("utilisation   arrivals/s   mean time in system   multiple of the work itself")
for rho in [0.5, 0.7, 0.8, 0.9, 0.95, 0.99]:
    lam = rho * mu
    wait_ms = 1000 / (mu - lam)         # M/M/1: mean time in system is 1/(mu - lambda)
    print(f"{rho:11.0%}   {lam:10.0f}   {wait_ms:16.0f} ms   {wait_ms/SERVICE_MS:22.0f}x")

# utilisation   arrivals/s   mean time in system   multiple of the work itself
#         50%           50                 20 ms                        2x
#         70%           70                 33 ms                        3x
#         80%           80                 50 ms                        5x
#         90%           90                100 ms                       10x
#         95%           95                200 ms                       20x
#         99%           99               1000 ms                      100x

The second fact is worse. Past a hundred per cent there is no equilibrium at all: an unbounded queue converts a small, temporary overload into a latency that grows without limit for as long as the overload lasts. Five per cent too much traffic is not five per cent slower.

import random, collections

def run(arrival_rate, capacity, seconds=600, service_rate=100.0, queue_limit=None):
    random.seed(5)
    queue = collections.deque()
    rejected, done, latencies = 0, 0, []
    for tick in range(seconds * 10):                     # 100 ms ticks
        now = tick / 10
        for _ in range(max(0, round(random.gauss(arrival_rate / 10, 1)))):
            if queue_limit is not None and len(queue) >= queue_limit:
                rejected += 1
            else:
                queue.append(now)
        for _ in range(int(service_rate / 10 * capacity)):
            if queue:
                latencies.append(now - queue.popleft())
                done += 1
    return queue, latencies, rejected, done

print("600 s, one worker pool that can finish 100 jobs a second")
for label, rate, limit in [("arrivals 90/s, unbounded queue", 90, None),
                           ("arrivals 105/s, unbounded queue", 105, None),
                           ("arrivals 105/s, queue capped at 200", 105, 200)]:
    q, lat, rej, done = run(rate, 1.0, queue_limit=limit)
    p50 = sorted(lat)[len(lat) // 2] if lat else 0
    worst = max(lat) if lat else 0
    print(f"{label:36} queue at end {len(q):6,}  median wait {p50:6.1f} s  "
          f"worst {worst:7.1f} s  rejected {rej:,}")

print()
print("the same 5 per cent overload, left running longer")
for seconds in [600, 1800, 3600]:
    q, lat, rej, done = run(105, 1.0, seconds=seconds)
    print(f"  after {seconds:5} s   queue {len(q):7,}   worst wait {max(lat):7.1f} s")

# 600 s, one worker pool that can finish 100 jobs a second
# arrivals 90/s, unbounded queue       queue at end      0  median wait    0.0 s  worst     0.1 s  rejected 0
# arrivals 105/s, unbounded queue      queue at end  2,866  median wait   14.0 s  worst    27.4 s  rejected 0
# arrivals 105/s, queue capped at 200  queue at end    190  median wait    1.9 s  worst     1.9 s  rejected 2,676
#
# the same 5 per cent overload, left running longer
#   after   600 s   queue   2,866   worst wait    27.4 s
#   after  1800 s   queue   8,825   worst wait    84.0 s
#   after  3600 s   queue  17,779   worst wait   169.3 s

That is what backpressure means, and the bounded run is what it looks like. The system has three options when work arrives faster than it can be done: queue it, reject it, or slow the producer down. Queueing is the only one that feels polite and it is the only one that is a lie, because the job is still going to fail — it will just fail after two minutes of the user waiting, by which time they have retried and added another. Rejecting quickly with a 429 and a retry-after is a better experience and a far better system, and it is the answer the interviewer is listening for.

• Bound every queue. An unbounded queue is an unbounded latency, and in a memory-backed broker it is also an out-of-memory kill.
• Reject at the edge, not at the worker. Work that is going to be dropped should be dropped before it costs anything.
• Shed by priority where you can: a checkout goes through, a recommendation refresh does not.
• Give the queue a deadline as well as a length. A job that has been waiting longer than the caller's timeout is already worthless, so drop it rather than run it.
• Alarm on queue depth and on age, not on throughput. Throughput looks perfect right up until the moment it does not.

Consistency#

Under a network partition you choose between consistency and availability. Most systems choose availability and accept eventual consistency, which means a read after a write may briefly show the old value. That is a product decision as much as a technical one.

Underneath that headline is a ladder of guarantees, and the vocabulary matters because the weaker ones are what you actually get and the differences between them are exactly what a user notices. In plain words, with the failure each one still permits:

• Strong (linearizable): every read sees the most recent write, as though there were one copy. You bought this with a round trip to a quorum on every operation, and you lose availability when the network splits. Right for account balances and inventory counts.
• Eventual: replicas converge if writes stop. Nothing else is promised. Two users refreshing the same page can see different answers, and one of them can see an older answer than they saw a minute ago. Fine for a like count, not for anything a user is about to act on.
• Read-your-writes: you always see your own writes; other people's may lag. This is the one users actually demand, because the failure without it is posting a comment and not seeing it.
• Monotonic reads: you never see time go backwards. Without it, two refreshes hitting different replicas can show a comment appearing, then vanishing, then appearing again.
• Causal: if B was written after reading A, nobody sees B without A. Without it, a reply shows up before the message it replies to.

Read-your-writes is worth a measurement because it is the one you will be asked to fix and the fix is so cheap. A user posts something, the write goes to the primary, the replicas catch up a moment later, and the user's own reload lands on a replica.

import random

def experiment(sticky_ms):
    random.seed(2)
    stale = 0
    for _ in range(20000):
        write_at = 0.0
        replica_lag = random.expovariate(1 / 0.15)      # mean 150 ms, long tail
        read_at = random.expovariate(1 / 0.30)          # user reloads soon after
        if read_at * 1000 < sticky_ms:
            continue                                     # read went to the primary
        if read_at < write_at + replica_lag:
            stale += 1
    return stale

for sticky in [0, 500, 1000, 2000]:
    stale = experiment(sticky)
    label = "no sticky read" if sticky == 0 else f"read primary for {sticky} ms"
    print(f"{label:26} users who did not see their own write: {stale:5}  "
          f"({stale/20000:.2%})")

# no sticky read             users who did not see their own write:  6686  (33.43%)
# read primary for 500 ms    users who did not see their own write:    43  (0.21%)
# read primary for 1000 ms   users who did not see their own write:     0  (0.00%)
# read primary for 2000 ms   users who did not see their own write:     0  (0.00%)

What to keep and what to skip#

• Keep: partial failure, and that a client-observed failure is usually a server-side success. Everything else here follows from it.
• Keep: capacity is set by the hottest shard, latency is set by headroom rather than load, and an unbounded queue converts overload into unbounded latency.
• Keep: a cache above about 95 per cent hit rate is a dependency, not an optimisation.
• Keep: the five consistency guarantees in plain words, each with the user-visible failure it still allows.
• Skip: reciting CAP as a theorem. Say what you give up under a partition and for which piece of data; the letters add nothing.
• Skip: consensus algorithm internals. Knowing that Raft exists, that it needs a majority, and that you should use an implementation rather than write one is the right depth unless you are interviewing to work on a database.
• Skip: memorising cache eviction policies. LRU is the default and the alternatives matter only when you have measured that it is wrong.

System design interviews reuse a small set of problems, and working through them is the fastest way to find which parts of your model of distributed systems are vague. This section does three: a URL shortener, a rate limiter and a news feed. The rate limiter is not only an exercise — every model API has one, and you will be writing the client side of it. Underneath, each asks the same questions about reads against writes, where state lives, and what happens when one component disappears.

A URL shortener#

The standard warm-up, because it exercises the basics without complication. Generate a short key, store the mapping, redirect on lookup. The interesting parts are key generation without collisions, and the read-heavy traffic, which makes caching the dominant design decision.

Key generation is where the arithmetic lives, and it is worth doing rather than asserting, because the usual answer — seven base-62 characters, three and a half trillion combinations, plenty — is wrong in a specific and instructive way. Collisions between random keys follow the birthday pattern: what matters is not the keyspace against one key, but the keyspace against the square of how many keys you have already stored.

import math

ALPHABET = 62          # a-z A-Z 0-9

print("key length   keyspace        after 1 billion URLs: expected collisions")
for length in [5, 6, 7, 8, 10]:
    space = ALPHABET ** length
    n = 1e9
    expected = n * n / (2 * space)                 # birthday approximation
    print(f"{length:10}   {space:.3e}   {expected:38,.1f}")

print()
print("chance the NEXT random key collides, at 1 billion keys already stored")
for length in [6, 7, 8]:
    space = ALPHABET ** length
    print(f"  {length} chars: {1e9/space:.2e}  ->  one retry every "
          f"{space/1e9:,.0f} inserts on average")

print()
print("counter-based keys instead: no collisions by construction")
for n in [1e6, 1e9, 1e12]:
    print(f"  {n:.0e} URLs needs {math.ceil(math.log(n, ALPHABET))} base-62 characters")

# key length   keyspace        after 1 billion URLs: expected collisions
#          5   9.161e+08                            545,772,384.2
#          6   5.680e+10                              8,802,780.4
#          7   3.522e+12                                141,980.3
#          8   2.183e+14                                  2,290.0
#         10   8.393e+17                                      0.6
#
# chance the NEXT random key collides, at 1 billion keys already stored
#   6 chars: 1.76e-02  ->  one retry every 57 inserts on average
#   7 chars: 2.84e-04  ->  one retry every 3,522 inserts on average
#   8 chars: 4.58e-06  ->  one retry every 218,340 inserts on average
#
# counter-based keys instead: no collisions by construction
#   1e+06 URLs needs 4 base-62 characters
#   1e+09 URLs needs 6 base-62 characters
#   1e+12 URLs needs 7 base-62 characters

So the answer has two halves. Either generate randomly and insert with a uniqueness constraint, retrying on conflict — cheap, because the retry rate is one in a few thousand, and safe, because the database and not your code decides who won. Or drop randomness and encode an incrementing counter in base 62, which cannot collide at all and needs only six characters for a billion URLs. The counter version costs you a coordination point for the counter and makes your keys guessable and your total volume public, which is a real product objection and the reason the random version is common despite needing the retry.

A rate limiter#

Directly relevant to AI work, since every model API has one. The token bucket algorithm refills tokens at a fixed rate and spends one per request, allowing bursts up to the bucket size. The distributed version needs shared state, usually in a fast store, and has to handle the race between checking and decrementing.

Token bucket
  capacity 100, refill 10 per second
  request arrives: if tokens >= 1, spend one and allow
                   otherwise reject with 429

Allows a burst of 100, then sustains 10 per second.

Written out, it is about ten lines, and the one subtlety is that you never run a timer. You store the token count and the timestamp of the last request, and refill lazily by multiplying the elapsed time by the rate when the next request arrives. That is what makes it cheap enough to run per tenant across millions of keys.

class TokenBucket:
    def __init__(self, capacity, refill_per_second, now=0.0):
        self.capacity, self.rate = capacity, refill_per_second
        self.tokens, self.stamp = float(capacity), now

    def allow(self, now):
        self.tokens = min(self.capacity, self.tokens + (now - self.stamp) * self.rate)
        self.stamp = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

bucket = TokenBucket(capacity=100, refill_per_second=10)
allowed = []
for second in range(6):
    n = sum(bucket.allow(second + i * 0.004) for i in range(200))   # 200 requests/s
    allowed.append(n)
print("200 requests a second, bucket capacity 100, refill 10/s")
print("  allowed per second:", allowed)
print("  total allowed", sum(allowed), "of 1200; the first second spends the burst,")
print("  after that the caller gets the refill rate and nothing more")

# 200 requests a second, bucket capacity 100, refill 10/s
#   allowed per second: [107, 10, 10, 10, 10, 10]
#   total allowed 157 of 1200; the first second spends the burst,
#   after that the caller gets the refill rate and nothing more

Now the distributed part, which is where the question is actually decided. With several API servers the bucket has to live in a shared store, and the naive implementation reads the count, compares it to the limit and writes the new value — three steps with a network round trip between them, during which every other server is doing the same thing.

import threading, time

LIMIT = 100

class Store:
    """Stands in for Redis. Every operation pays a small network delay."""
    def __init__(self):
        self.n = 0
        self.lock = threading.Lock()
    def get(self):
        time.sleep(0.0005)
        return self.n
    def set(self, v):
        time.sleep(0.0005)
        self.n = v
    def incr_if_below(self, limit):        # one atomic server-side operation
        with self.lock:
            time.sleep(0.001)
            if self.n < limit:
                self.n += 1
                return True
            return False

def race(store, atomic):
    allowed = []
    def worker():
        for _ in range(20):
            if atomic:
                ok = store.incr_if_below(LIMIT)
            else:
                n = store.get()            # read
                ok = n < LIMIT
                if ok:
                    store.set(n + 1)       # write, after someone else may have read
            allowed.append(ok)
    threads = [threading.Thread(target=worker) for _ in range(20)]
    for t in threads: t.start()
    for t in threads: t.join()
    return sum(allowed)

for label, atomic in [("read then write", False), ("atomic check-and-increment", True)]:
    s = Store()
    n = race(s, atomic)
    print(f"{label:28} allowed {n:4} of 400 requests against a limit of {LIMIT}"
          f"   {'OVER BY ' + str(n - LIMIT) if n > LIMIT else 'exact'}")

# read then write              allowed  400 of 400 requests against a limit of 100   OVER BY 300
# atomic check-and-increment   allowed  100 of 400 requests against a limit of 100   exact

The fix is to make the check and the decrement one operation the store executes itself — an atomic counter, a compare-and-set, or a small script run server-side. Then answer the follow-up before it is asked: if that store is unavailable, you choose between failing open, which drops the limit entirely and lets a caller overwhelm you, and failing closed, which rejects everyone because your limiter is down. The usual answer is to fail open for a short window with a conservative local limit per server, on the reasoning that a rate limiter exists to protect you from overload and should not itself become the outage.

A news feed#

The key decision is when to assemble a user's feed. Fan-out on write pushes each new post into followers' feeds immediately, making reads fast and writes expensive. Fan-out on read assembles at request time, the opposite trade. Real systems do both, with fan-out on read for accounts with enormous follower counts.

Why the hybrid exists is a distribution argument, and putting numbers on it is what separates a memorised answer from a designed one. Follower counts follow a heavy-tailed distribution, so the mean is meaningless and a tiny number of accounts dominate the write volume.

import random

random.seed(4)
USERS = 1_000_000
# A realistic shape: nearly everyone small, a thin tail of enormous accounts.
followers = [int(random.paretovariate(1.2) * 30) for _ in range(USERS)]
followers[0] = 50_000_000                       # one celebrity

posts_per_user_per_day = 0.5

write_cost = sum(f * posts_per_user_per_day for f in followers)
print(f"fan-out on write: {write_cost:,.0f} feed rows written a day")
print(f"  the single largest account is "
      f"{followers[0]*posts_per_user_per_day/write_cost:.0%} of that")

# Hybrid: anyone above the threshold is pulled at read time instead.
for threshold in [10_000, 100_000, 1_000_000]:
    written = sum(f * posts_per_user_per_day for f in followers if f <= threshold)
    big = sum(1 for f in followers if f > threshold)
    print(f"  threshold {threshold:>9,}: {written:15,.0f} rows written a day, "
          f"{big:3} accounts pulled at read time")

print(f"average account follows {sum(followers)/USERS:.0f} others, so a read-time "
      f"assembly touches that many timelines")

# fan-out on write: 124,530,152 feed rows written a day
#   the single largest account is 20% of that
#   threshold    10,000:      61,457,893 rows written a day, 919 accounts pulled at read time
#   threshold   100,000:      71,206,486 rows written a day,  58 accounts pulled at read time
#   threshold 1,000,000:      77,776,094 rows written a day,   6 accounts pulled at read time
# average account follows 249 others, so a read-time assembly touches that many timelines

Say the threshold out loud and say what it costs, because that is the graded part. Below it, push on write and reads are one range scan. Above it, pull on read and merge. The reader's request then does one lookup for the pushed part plus a merge over however many large accounts they follow, which is a handful rather than the 249 timelines a pure read-time assembly would touch. And note the ordering problem the hybrid creates: two sources of posts have to be merged into one ranked list, so whatever ordering key you use has to be comparable across both.

All three designs above answer those four questions and nothing else. The shortener is overwhelmingly reads, nothing needs to be consistent beyond the mapping existing, the hot path is the redirect, and a cache miss is the failure. The rate limiter is balanced, the counter must be atomic, the hot path is the shared store, and that store dying is the failure you must have an answer for. The feed is read-heavy with a pathological write tail, staleness of seconds is fine, the hot path is the read, and the failure is a celebrity posting. Once you can produce those four sentences for a problem you have not seen before, you are doing the round properly.

What to keep and what to skip#

• Keep: the four questions, and ask them before naming a single component.
• Keep: random keys collide at a rate you can compute, so the insert must handle a conflict rather than assume one away.
• Keep: a distributed rate limiter needs one atomic operation, and needs a stated behaviour when its store is down.
• Keep: the hybrid feed threshold and roughly why it is where it is.
• Skip: memorising a canonical architecture diagram per problem. Interviewers change one constraint to find out whether you memorised it.
• Skip: naming specific products. Say what the component must do; the brand adds nothing and invites a question about internals you do not need.

In a design discussion someone will ask how much traffic, how much storage, how much bandwidth, and expect an answer in under a minute. This section is the small set of arithmetic and reference numbers that lets you give one: turning users into requests per second, requests into bytes per year, and knowing roughly how long a memory read, a cross-continent round trip and a model call each take. Rounding hard and saying your assumptions out loud is the skill being tested; precision is not.

Users to load#

10 million daily users x 20 requests each = 200 million requests/day
a day is about 86,400 s, call it 100,000 for easy maths
  average = 2,000 requests/s
  peak    = 2 to 5 x average, say 10,000 requests/s

Three habits in that block are the whole technique. A day is 100,000 seconds, not 86,400, because you are estimating and the extra fifteen per cent is far inside your other error bars. Peak is a multiple of average rather than a separate calculation, and the multiple is two to five for a consumer product with one big timezone and can be ten or more for anything with a scheduled event in it. And you size for peak, because the average never took a service down.

Storage#

each chat message about 1 KB with metadata
10 million users x 20 messages x 365 days = 73 billion messages/year
  x 1 KB = 73 TB/year, before replication (x3) and indexes

The two multipliers at the end are where estimates are usually wrong, and both are worth saying unprompted. Replication is three copies by default, so the disk you buy is three times the data you have. Indexes and metadata commonly add another twenty to fifty per cent on top of that, and for anything with embeddings in it the vectors can exceed the text they were made from — a thousand-dimensional float32 vector is 4 KB, four times the 1 KB message it represents. Say which assumption the answer is most sensitive to and you have demonstrated the thing being tested.

Latency, in orders of magnitude#

read from memory                          ~100 ns
read 1 MB sequentially from memory        ~tens of microseconds
random read from an SSD                   ~tens to hundreds of microseconds
round trip within a data centre           ~0.5 ms
round trip across a continent             ~tens of ms
round trip between continents             ~100 to 200 ms
LLM time to first token                   ~hundreds of ms to seconds

The use of that table is subtraction. Given a latency budget, spend it. A 300 ms budget for a page load, minus a hundred milliseconds for a user on another continent, minus a few milliseconds per internal hop, leaves under two hundred milliseconds of real work — which a single model call will consume entirely, and which three sequential model calls cannot fit into at all. That is why a design with a chain of model calls has to stream, cache or run them in parallel, and noticing it from the arithmetic rather than from a production incident is the point.

The arithmetic of availability#

Availability multiplies along a dependency chain, and almost nobody's intuition does. If your request needs ten services and each is up 99.9 per cent of the time, you are not up 99.9 per cent of the time. You are up 0.999 to the tenth, and the difference is the gap between an afternoon of downtime a year and most of a working week.

YEAR = 365 * 24 * 60          # minutes

print("dependencies   each 99.9%    each 99.99%    downtime/year at 99.9% each")
for n in [1, 3, 5, 10, 30]:
    a3, a4 = 0.999 ** n, 0.9999 ** n
    print(f"{n:12}   {a3:9.4%}    {a4:10.4%}    {(1-a3)*YEAR:12,.0f} minutes")

print()
print("one flaky dependency at 99% inside an otherwise 99.99% chain of 10:")
chain = 0.9999 ** 9 * 0.99
print(f"  combined {chain:.4%}  ->  {(1-chain)*YEAR:,.0f} minutes a year")

print()
print("making that one redundant instead of fixing it:")
for copies in [1, 2, 3]:
    dep = 1 - 0.01 ** copies
    combined = 0.9999 ** 9 * dep
    print(f"  {copies} independent copies at 99%: dependency {dep:.4%}, "
          f"chain {combined:.4%}, {(1-combined)*YEAR:,.0f} minutes")

# dependencies   each 99.9%    each 99.99%    downtime/year at 99.9% each
#            1    99.9000%      99.9900%             526 minutes
#            3    99.7003%      99.9700%           1,575 minutes
#            5    99.5010%      99.9500%           2,623 minutes
#           10    99.0045%      99.9000%           5,232 minutes
#           30    97.0431%      99.7004%          15,541 minutes
#
# one flaky dependency at 99% inside an otherwise 99.99% chain of 10:
#   combined 98.9109%  ->  5,724 minutes a year
#
# making that one redundant instead of fixing it:
#   1 independent copies at 99%: dependency 99.0000%, chain 98.9109%, 5,724 minutes
#   2 independent copies at 99%: dependency 99.9900%, chain 99.9000%, 525 minutes
#   3 independent copies at 99%: dependency 99.9999%, chain 99.9099%, 473 minutes

Two escapes from the multiplication are worth naming. Make the dependency optional: a recommendation service that is down should produce a page without recommendations, not a 500, and a dependency you can degrade past has left the chain entirely. Or make it redundant, as the last block does — but redundancy only multiplies if the copies fail independently, and two instances in the same rack behind the same deploy pipeline do not. The correlated-failure caveat is worth saying out loud, because every real outage of a redundant system is a correlated failure.

Tail latency and fan-out#

The last piece of arithmetic is the one that explains why big systems feel slow in ways their dashboards do not show. If a request fans out to many backends and waits for all of them, its latency is the maximum of theirs, not the average, so a rare slow response becomes a common slow request.

print("a request that fans out to N shards, each with a 1-in-100 chance of being slow")
print("shards   requests hitting at least one slow shard")
for n in [1, 5, 10, 20, 100]:
    print(f"{n:6}   {1 - 0.99 ** n:38.1%}")

print()
print("hedging: send to two replicas and take whichever answers first")
for n in [10, 20, 100]:
    one, two = 1 - 0.99 ** n, 1 - (1 - 0.01 ** 2) ** n
    print(f"{n:4} shards   one copy {one:6.1%}   hedged {two:6.1%}")

# a request that fans out to N shards, each with a 1-in-100 chance of being slow
# shards   requests hitting at least one slow shard
#      1                                     1.0%
#      5                                     4.9%
#     10                                     9.6%
#     20                                    18.2%
#    100                                    63.4%
#
# hedging: send to two replicas and take whichever answers first
#   10 shards   one copy   9.6%   hedged   0.1%
#   20 shards   one copy  18.2%   hedged   0.2%
#  100 shards   one copy  63.4%   hedged   1.0%

What to keep and what to skip#

• Keep: a day is 100,000 seconds, peak is two to five times average, replication is three times, and a millisecond is a data-centre round trip.
• Keep: availability multiplies, so count the dependencies before quoting a target.
• Keep: fan-out turns a tail percentile into a common case.
• Skip: precise arithmetic. Round hard, say the assumption, and move on; nobody is checking your long division.
• Skip: memorising the full latency table to three significant figures. The orders of magnitude and their ratios are the whole of it.

Every call from one service to another can be slow, can fail, or can succeed in a way the caller never hears about. This section is the standard set of defences: a timeout on every call, retries only where repeating the work is safe, idempotency keys to make it safe, and a circuit breaker so a struggling dependency is not hammered while it tries to recover. It also settles the exactly-once question, which is that you cannot have it over a network, so real systems deliver at least once and make the handler tolerate a duplicate.

Timeouts#

A call without a timeout can wait forever, holding a thread, a connection and a user. Set timeouts on every network call, and make them fit inside the caller's own deadline, so a request with a 10 second budget does not make three sequential calls with 10 second timeouts each.

Retries#

• Retry on timeouts, connection errors and explicit 'try again' responses such as 429 and 503.
• Do not retry on 400-type errors; the request is wrong and will stay wrong.
• Use exponential backoff with jitter, and a limit.
• Only retry operations that are safe to repeat, which usually means making them idempotent.

There is a fifth rule that is missing from most lists and causes most retry-related outages: cap the total retry traffic, not just the retries per request. Retries are demand, and they are demand that appears exactly when the system has least capacity to serve it. A service that fails under a brief spike, whose clients then retry, faces a load made of the original traffic plus everything that failed, which fails too, and retries again.

import collections

CAPACITY = 100                 # requests a second the server can actually complete

def simulate(retries, budget, seconds=600):
    pending = collections.defaultdict(int)
    trace = []
    for t in range(seconds):
        base = 140 if 60 <= t < 120 else 80     # a one-minute spike, then it is over
        offered = base + pending.pop(t, 0)
        trace.append(offered)
        failed = max(0, offered - CAPACITY)
        if retries:
            pending[t + 2] += min(failed, int(CAPACITY * budget))
    return trace

print("the spike itself lasts 60 s and is 1.4x capacity")
for label, retries, budget in [("no retries", 0, 0.0),
                               ("retry, no budget", 1, 10.0),
                               ("retry budget 10% of capacity", 1, 0.10)]:
    trace = simulate(retries, budget)
    recovered = next((t for t in range(120, 600) if trace[t] <= CAPACITY), None)
    print(f"{label:30} peak offered {max(trace):5}/s   "
          f"still overloaded at t=150: {trace[150]:4}/s   "
          f"recovered at t={recovered}")

# the spike itself lasts 60 s and is 1.4x capacity
# no retries                     peak offered   140/s   still overloaded at t=150:   80/s   recovered at t=120
# retry, no budget               peak offered  1140/s   still overloaded at t=150:  780/s   recovered at t=218
# retry budget 10% of capacity   peak offered   150/s   still overloaded at t=150:   80/s   recovered at t=120

The fix is a retry budget: the client tracks its own ratio of retries to first attempts and stops retrying once it passes some small fraction, typically around ten per cent. The third row is that, and it barely registers the spike. The related habit is to make retries decorrelated — exponential backoff with full jitter, meaning a random wait between zero and the current backoff rather than the backoff itself, so a thousand clients that failed together do not come back together.

Idempotency keys#

The client generates a unique key per logical operation and sends it with every attempt. The server records the key with the result, and a repeated key returns the stored result instead of acting again. This is how payment APIs make 'charge the card' safe to retry.

The word doing the work in that paragraph is 'per logical operation', and it is where the implementation goes wrong. The key must be generated once, outside the retry loop, and reused by every attempt at the same payment. Generate it inside the loop and you have a unique key per attempt, which is the same as having no key at all — and the code looks correct, because it does use idempotency keys.

import random, uuid

class Ledger:
    def __init__(self):
        self.charges, self.by_key = [], {}

    def charge(self, account, pence, key):
        if key in self.by_key:                 # replay, not a new instruction
            return self.by_key[key], "replayed"
        charge_id = len(self.charges)
        self.charges.append((account, pence))  # must be one transaction with the line below
        self.by_key[key] = charge_id
        return charge_id, "charged"

def flaky_call(ledger, account, pence, key):
    result = ledger.charge(account, pence, key)
    if random.random() < 0.4:
        raise TimeoutError("reply lost, the charge may or may not have happened")
    return result

random.seed(9)
for label, fresh_key_each_try in [("new key on every retry", True),
                                  ("one key per payment", False)]:
    ledger = Ledger()
    for payment in range(100):
        key = str(uuid.uuid5(uuid.NAMESPACE_OID, f"payment-{payment}"))
        for attempt in range(4):
            try:
                if fresh_key_each_try:
                    key = str(uuid.uuid4())
                flaky_call(ledger, "acct-1", 999, key)
                break
            except TimeoutError:
                continue
    total = sum(p for _, p in ledger.charges)
    print(f"{label:24} 100 payments of 999p -> charged {total:7,}p "
          f"in {len(ledger.charges):3} rows  "
          f"({'OVERCHARGED' if total > 99900 else 'correct'})")

# new key on every retry   100 payments of 999p -> charged 172,827p in 173 rows  (OVERCHARGED)
# one key per payment      100 payments of 999p -> charged  99,900p in 100 rows  (correct)

Circuit breakers#

When a dependency is failing, retrying hard makes it worse. A circuit breaker counts failures and, past a threshold, fails fast for a cool-down period without calling the dependency, then lets a few test requests through. Your service degrades instead of hanging.

It has three states and the third is the one people forget. Closed means calls go through and failures are counted. Open means calls fail immediately without touching the dependency. Half-open, after the cool-down, means one probe is allowed: if it succeeds the breaker closes, and if it fails the breaker reopens at once rather than waiting for another five failures.

TIMEOUT = 2.0        # seconds a call to a dead dependency burns before giving up

class CircuitBreaker:
    def __init__(self, threshold=5, cooldown=10.0):
        self.threshold, self.cooldown = threshold, cooldown
        self.failures, self.opened_at = 0, None

    def state(self, now):
        if self.opened_at is None:
            return "closed"
        return "half-open" if now - self.opened_at >= self.cooldown else "open"

    def call(self, now, dependency_alive):
        state = self.state(now)
        if state == "open":
            return 0.0, "fast fail"                  # no thread held, no wait
        if dependency_alive:
            self.failures, self.opened_at = 0, None  # a probe that works closes it
            return 0.01, "ok"
        if state == "half-open":
            self.opened_at = now                     # one bad probe reopens it at once
            return TIMEOUT, "timed out"
        self.failures += 1
        if self.failures >= self.threshold:
            self.failures, self.opened_at = 0, now
        return TIMEOUT, "timed out"

def run(threshold):
    cb = CircuitBreaker(threshold=threshold)
    waited, reached = 0.0, 0
    for tick in range(600):                          # 60 s at 10 calls a second
        now = tick / 10
        alive = not (10.0 <= now < 40.0)             # the dependency is down for 30 s
        cost, what = cb.call(now, alive)
        waited += cost
        if what == "timed out":
            reached += 1
    return waited, reached

for label, threshold in [("no breaker", 10 ** 9),
                         ("breaker: 5 failures, 10 s open", 5)]:
    waited, reached = run(threshold)
    print(f"{label:32} thread-seconds waiting {waited:7.1f}   "
          f"calls that hit the dead dependency {reached:3} of 300")

# no breaker                       thread-seconds waiting   603.0   calls that hit the dead dependency 300 of 300
# breaker: 5 failures, 10 s open   thread-seconds waiting    17.0   calls that hit the dead dependency   7 of 300

Two things to say when this comes up. A breaker is only useful if there is something sensible to do when it is open — serve stale data, return a partial response, queue the work for later — because failing fast is still failing, and a breaker in front of a dependency you cannot do without just converts a slow outage into a quick one. And the threshold should be a failure rate over a window rather than a raw count, or a low-traffic endpoint trips on five failures spread across an hour.

Exactly once is a myth; idempotent is not#

Over a network you cannot guarantee a message is delivered exactly once: an acknowledgement can be lost after the work was done. Real systems deliver at least once and make handlers idempotent, so a duplicate does no harm.

The outbox pattern#

You need to save an order and publish an 'order created' event. Doing both separately means one can succeed and the other fail. Instead, write the event to an outbox table in the same database transaction as the order; a separate process publishes outbox rows and marks them sent. The event may be published twice, which idempotent consumers handle.

Trace the crash to see why it works. Crash before the transaction commits and neither the order nor the event exists, which is consistent. Crash after the commit and both exist, with the event unsent, and the publisher picks it up on its next pass. Crash after publishing but before marking the row sent, and the event is published a second time — which is the case you deliberately chose, because a duplicate delivered to an idempotent consumer costs nothing and a lost event costs an order nobody ever hears about. That is the whole design principle of this section: you cannot remove uncertainty, so you arrange for the surviving failure to be the harmless one.

What to keep and what to skip#

• Keep: a timeout on every call, sized to fit inside the caller's own deadline.
• Keep: retries are demand, so cap the total retry rate and jitter the backoff. Unbudgeted retries turn a spike into an outage that outlives its cause.
• Keep: one idempotency key per logical operation, generated outside the retry loop, and stored atomically with the effect.
• Keep: exactly-once delivery does not exist over a network. At-least-once plus an idempotent handler is the answer.
• Keep: the outbox pattern and the three crash points that make it correct.
• Skip: tuning circuit breaker constants in the abstract. Five failures and thirty seconds is a fine starting point; the numbers come from your dependency's recovery time.
• Skip: arguing about which broker gives exactly-once semantics. Say where the boundary of that claim is and move on.