The classic fundamentals

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.