Day 46 · Many kitchens, one restaurant

Distributed Systems Fundamentals

You will be able to

Explain why systems distribute (scale, fault tolerance) and what it costs (consistency, complexity)
Distinguish horizontal from vertical scaling and explain why stateless services enable the former
Compare replication and partitioning and say what problem each solves
State the CAP intuition honestly and apply it to a concrete failure
Make any retried operation safe with idempotency keys

Today's ~120 minutes

Spaced-rep warm-up: due flashcards (Days 43–45)	10 min
ELI5 + tech read + dist-sys visualizer	20 min
Guided: duplicate-cake fix + replication lag	40 min
Practice: stateless audit + CAP call	20 min
Project: idempotency + scaling memo	20 min
Quiz + flashcards	10 min

Builds on: Day 45 — Web service architecture & statelessness pressure · Day 40 — Concurrency & race conditions · Day 38 — Transactions & ACID

The analogy

🧸 ELI5⚙ Tech

A beloved single-kitchen restaurant hits its limit: one kitchen can only cook so fast, and when the stove breaks, dinner is over for everyone. So the owner opens three kitchens behind one host stand. The host (load balancer) sends each arriving order to whichever kitchen is free. For this to work, no kitchen can keep anything special in its own head — if kitchen A remembers "table 9 wants no onions" and the next course routes to kitchen B, the dish comes out wrong. Every kitchen must read the shared order board (stateless workers, shared state).

Now the recipes: photocopy the master cookbook into every kitchen (replication) and any kitchen can cook anything — but when a recipe changes, for a few minutes some copies are stale (eventual consistency). Or split the menu — kitchen A does starters, B mains, C desserts (partitioning) — no copies to sync, but lose kitchen B and nobody eats a main. And when a waiter is unsure whether kitchen heard "one birthday cake," they repeat the order with the same ticket number, and the kitchen ignores duplicates (idempotency) — otherwise uncertainty produces two cakes.

Why this matters on the job

Every serious AI deployment is distributed on day one: multiple API replicas behind a load balancer, a replicated database, a model provider that is ITSELF a giant distributed system handing you timeouts and 429s. Idempotency is the difference between "retried the charge" and "charged twice" — and LLM clients retry constantly (you will bake retries into your wrapper on Day 107, and agent tool safety on Day 125 leans on idempotent tools). CAP and replication-lag reasoning show up in system design interviews (Day 160) and in real customer conversations: "why did my colleague see the old document?" is an eventual-consistency question.

Watch it happen

Many kitchens, one restaurant — a request rides through, and survives a crash

step 1 / 6

Client→Load balancertraffic cop→Replica1 of 3, stateless→CacheRedis→Databasesource of truth

✉ GET /orders/7

One server can't handle the lunch rush, so we run three identical STATELESS replicas behind a load balancer. Stateless is the key word: any replica can serve any request, because no user data lives in replica memory.

🎯 Predict modespeed1×

Guided practice

guided 1

Simulate the duplicate-cake disaster, then fix it

25 min

Run part 1 of the starter: a client calls charge() over a flaky network that times out 30% of the time AFTER the server already processed. The client retries on timeout. Run 3 times and record how much was over-charged.
Read the log: every double-charge is a timeout where the work HAD succeeded. The client cannot know — that is the ambiguity, not a bug in the client.
Part 2 adds an idempotency key: the server remembers processed keys and replays the stored result for duplicates. Re-run — balance is now exact every time, despite identical network chaos.
In one sentence in your notes: why must the SERVER dedupe rather than the client "retry more carefully"? (The client can never distinguish lost-request from lost-response.)

🐍 python — editable, runs in your browser

import random, uuid

random.seed()  # run several times: chaos differs

# --- 1. naive retry over a flaky network -----------------
class Bank:
    def __init__(self): self.balance = 0
    def charge(self, amount):
        self.balance += amount          # work happens...
        if random.random() < 0.3:
            raise TimeoutError          # ...but the ACK is lost

def client_naive(bank, amount, max_tries=4):
    for attempt in range(max_tries):
        try:
            bank.charge(amount); return
        except TimeoutError:
            print(f"  timeout on attempt {attempt+1} -> retrying")

bank = Bank()
for _ in range(5): client_naive(bank, 10)
print(f"charged {bank.balance} (should be 50) "
      f"-> over by {bank.balance - 50}\n")

# --- 2. idempotency keys: server dedupes ------------------
class SafeBank:
    def __init__(self): self.balance = 0; self.seen = {}
    def charge(self, amount, key):
        if key in self.seen:            # duplicate: replay result
            result = self.seen[key]
        else:
            self.balance += amount
            result = self.seen[key] = "ok"
        if random.random() < 0.3:
            raise TimeoutError          # ACK still flaky!
        return result

def client_safe(bank, amount, max_tries=4):
    key = str(uuid.uuid4())             # ONE key per logical op
    for _ in range(max_tries):
        try:
            return bank.charge(amount, key)
        except TimeoutError:
            pass

safe = SafeBank()
for _ in range(5): client_safe(safe, 10)
print(f"charged {safe.balance} (should be 50) -> exact")

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

guided 2

Replication lag you can watch

15 min

Run the starter: a leader takes writes; two followers apply them with random delay. The client writes a profile update, then immediately reads from a random replica (that is what a load balancer does).
Count the stale reads across 20 rounds. This is eventual consistency happening on your screen.
Fix "read your own writes" the standard way: after a write, route THAT user's reads to the leader for a few seconds. Implement the two-line change (route by recently_wrote) and confirm stale reads for the writer drop to zero.
Note the trade you just made: the leader now carries extra read load — consistency purchased with capacity.

🐍 python — editable, runs in your browser

import random

class Leader:
    def __init__(self): self.data = {}; self.log = []
    def write(self, k, v):
        self.data[k] = v; self.log.append((k, v))

class Follower:
    def __init__(self, leader): self.leader = leader; self.data = {}; self.pos = 0
    def maybe_catch_up(self):
        # applies 0-2 pending log entries per tick: replication lag
        for _ in range(random.randint(0, 2)):
            if self.pos < len(self.leader.log):
                k, v = self.leader.log[self.pos]
                self.data[k] = v; self.pos += 1
    def read(self, k): return self.data.get(k)

leader = Leader()
followers = [Follower(leader), Follower(leader)]
stale = 0
for round_no in range(20):
    leader.write("bio", f"version-{round_no}")
    for f in followers: f.maybe_catch_up()
    replica = random.choice(followers)       # LB picks any replica
    seen = replica.read("bio")
    if seen != f"version-{round_no}":
        stale += 1
        print(f"round {round_no:2d}: STALE read -> {seen}")
print(f"\n{stale}/20 reads were stale (eventual consistency)")

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

On your own

The stateless audit + CAP call

20 min

Part 1: audit your Day 45 service for horizontal-scale blockers. Find every piece of in-process state (the rate-limiter dict is one — find at least two more candidates: anything cached in module scope, anything written to local disk, any assumption that "the" process sees all requests). For each: where should that state live so two replicas behave as one?

Part 2: your notes service goes multi-region and a partition cuts the regions apart. A user edits a note in region A; their teammate reads it in region B during the partition. Write the CP answer and the AP answer as one honest sentence each, then choose for THIS product and defend in two sentences.

Hints: CP = teammate waits or errors; AP = teammate reads stale. Which failure does a notes app tolerate better?

Ship before you stop

Idempotent + stateless upgrade

Two upgrades to your notes service, committed. (1) Idempotency: POST /v1/notes accepts an Idempotency-Key header; the server stores completed keys with their response (SQLite table: key, response_json, created_at) and replays the stored response on duplicates. Test: two identical keyed POSTs create ONE note and return identical bodies. (2) Statelessness memo: scaling_notes.md documenting your stateless audit — every piece of in-process state found, where it must move (shared DB/cache), plus a 6-line ASCII diagram of the target: load balancer → 2 replicas → shared SQLite/cache. End with three sentences on what today's replication-lag demo means for a RAG index that is updated while users query it (Day 118 revisits this as freshness).

Rubric — check what you completed (0/6)

Duplicate keyed POST provably creates one row and replays the stored responseMissing Idempotency-Key still works (documented as at-most-once NOT guaranteed)Audit names ≥ 3 pieces of in-process state with a new home for eachCAP paragraph states the forced trade during partitions correctly (not "pick 2 of 3 always")ASCII target diagram shows LB, replicas, and shared stateTests pass; committed with a descriptive message

Common mistakes & misconceptions

Reading CAP as "pick two, always." The trade is forced only during partitions; in normal operation the real dial is latency vs consistency.
Believing retries are safe because "the request failed." A timeout means UNKNOWN — the work may have completed. Only idempotency makes retries safe.
Making services stateless in theory while a module-level dict quietly holds sessions or counters. Two replicas = two disagreeing dicts. Audit for hidden state.
Treating replication as a backup strategy. Followers replicate deletes and corruption within seconds. Replication is availability; backups are time travel.
Sharding before measuring. Partitioning complicates every query and transaction; a bigger instance, an index (Day 38), or a cache (Day 47) usually buys years first.
Assuming "eventually consistent" means seconds of drift at most. Lag is unbounded under load or partition — design for the stale read, not the happy case.

Knowledge check

Q1. A payment POST times out and the client retries with the same idempotency key. The server had already processed it. What should the server do?

Q2. Your service keeps its rate-limit counters in a module-level dict. You scale to 3 replicas behind a load balancer. What happens?

Q3. Right after updating their profile, a user reloads and sees the OLD version. The likeliest cause in a leader-follower setup?

Go deeper — curated resources

repoSystem Design Primer — scalability, CAP, replication ↗35 min courseMIT 6.824 — Distributed Systems (lecture 1) ↗30 min repoDDIA references — Designing Data-Intensive Applications ch. 5 ↗15 min articleByteByteGo — load balancing & idempotency explainers ↗15 min

If you have a third hour

MIT 6.824 lecture 2 — RPC and threads ↗ — The lab-grade version of today's toy simulations, in Go. Watch lecture 1–2 if you want the full course flavor.

Done means

Naive-retry over-charge observed and explained; keyed version exact
Replication-lag sim run; read-your-writes fix implemented
Idempotency-Key endpoint passes the duplicate test
scaling_notes.md committed with audit, CAP paragraph, diagram
Quiz ≥ 2/3

How this connects

← Back: The race conditions of Day 40 return at machine scale — retries and replicas instead of threads. Day 38's transactions gave you single-node atomicity; today you saw why it does not stretch across the network, and why Day 45's in-memory rate limiter cannot survive a second replica.

Forward →: Day 47 gives shared state a fast home (Redis) and decouples work with queues. Day 48's design method uses today's vocabulary in every deep dive, and the Day 49 URL shortener is your first build with these trade-offs. Day 107's LLM client retries lean on idempotency; Day 158 turns partial failure into incident practice.

Unlocks: D47 Caching & Queues · D48 System Design Method · D150 Cloud Fundamentals · D158 Reliability & Incident Response