R26 · Week 26 Recall & Drill

Weekly revision · Week 26 · Covers 5 sessions from Mon–Fri.

Sessions covered

• S126 — System Design Framework — Reqs, Capacity, HLD, Deep-Dive
• S127 — Design a URL Shortener — the Classic Warm-Up
• S128 — Design a Chat System — WebSockets, Delivery, Presence
• S129 — Design a Newsfeed / Recommender — Pull vs Push, Ranking
• S130 — Design an AI Chat Product — RAG + Agents + Serving

90-min structure

Blank-page reconstruction · 30 min

S126 · The Framework

1. Name the four phases in order with their rough minute budgets.
2. Say why estimation precedes the architecture diagram.
3. Give three sentences that shift a conversation from knowledge to trade-offs.

Gotcha you probably forgot: the strongest signal you can give is naming what your own design costs before anyone asks. Two candidates can draw identical boxes and receive opposite outcomes, because one derived the design from the requirements and stated its price while the other asserted it. Volunteering the weakness of your choice is the behaviour being scored.

S127 · URL Shortener

1. Estimate request rate, storage, and identifier space in sixty seconds.
2. Compare counter-based, hash-based, and random-with-check generation.
3. Say why a permanent redirect is the wrong default.

Gotcha you probably forgot: a permanent redirect is cached by the browser and by intermediaries, so subsequent clicks never reach your service. That destroys analytics, and it makes the mapping effectively unchangeable — you cannot retarget or disable a link that clients no longer ask you about, which matters most exactly when a link turns out to be malicious.

S128 · Chat System

1. Say why balancing persistent connections differs from balancing stateless requests.
2. Describe the inbox-pull model and why it beats write-fanout for large groups.
3. Design a client's reconnection behaviour after a network loss.

Gotcha you probably forgot: the reconnection storm is self-inflicted. When a chat tier restarts, every client reconnects at once, and if they all retry immediately the tier is knocked over again by its own users. Randomised backoff is not politeness — it is what prevents a brief outage from becoming a sustained one.

S129 · Newsfeed

1. Draw the two-stage pipeline from memory.
2. Compare the fanout strategies on latency, write cost, and failure mode.
3. Name three feedback-loop failure modes and the defences.

Gotcha you probably forgot: a ranker trained on logged engagement learns from data its own previous version produced, so it reinforces whatever it already surfaced and never learns about content it stopped showing. A deliberate fraction of exploration traffic is what keeps the training data informative, and without it offline metrics improve while the product narrows.

S130 · AI Chat Product

1. Walk one turn end-to-end and time each hop roughly.
2. Say why a per-user budget beats a per-request rate limit here.
3. Give three anti-abuse controls beyond request rate limiting.

Gotcha you probably forgot: a request-rate limit does not bound cost, because requests differ in price by orders of magnitude depending on context length, output length, and which model handled them. A user well inside the rate limit can generate an enormous bill, which is why the control that actually protects you is a per-user spend budget.

Hands-on drill · 30 min

Task: estimate, collide, deduplicate, compare fanout, and budget a streamed turn.

mkdir -p ~/projects/w26-drill && cd ~/projects/w26-drill

Step 1 — estimation in sixty seconds (6 min)

# estimate.py
def summarise(name, daily_writes, read_ratio, bytes_per_record, years=5):
    wps = daily_writes / 86_400
    rps = wps * read_ratio
    records = daily_writes * 365 * years
    storage = records * bytes_per_record
    print(f"\n{name}")
    print(f"  writes/sec (avg)   {wps:>12,.0f}")
    print(f"  writes/sec (peak)  {wps*3:>12,.0f}   (3x for daily peak)")
    print(f"  reads/sec  (peak)  {rps*3:>12,.0f}")
    print(f"  records in {years}y    {records:>12,.0f}")
    print(f"  raw storage        {storage/1e12:>12,.1f} TB")
    print(f"  with replication   {storage*3/1e12:>12,.1f} TB (3 copies)")
 
summarise("URL shortener", 100e6/30, 100, 500)
summarise("Chat", 50e9/30, 1.2, 300)
 
print("\nThe purpose of this is not the numbers. It is that the numbers decide the")
print("architecture: a peak rate a single node can serve does not need sharding,")
print("and a storage figure that fits one machine does not need a distributed store.")
print("Estimating after drawing the diagram means the diagram was decoration.")

Expected outcome: each figure implies an architectural decision. If the peak rate fits comfortably on one node, sharding is unjustified complexity and saying so is a stronger answer than adding it. If storage over the retention window exceeds a single machine, partitioning is forced and you can name the partition key with a reason. This is the entire argument for the phase ordering: estimation before architecture makes the architecture derived, and estimation afterwards makes it decoration.

Step 2 — truncated hashes collide (8 min)

# ids.py
import hashlib, math
 
ALPHABET_SIZE = 62
 
def space(chars):
    return ALPHABET_SIZE ** chars
 
def birthday_threshold(n):
    """Roughly where collisions become likely."""
    return math.sqrt(n)
 
print(f"{'code length':>12} {'address space':>18} {'collisions likely at':>22}")
for chars in (6, 7, 8, 10):
    s = space(chars)
    print(f"{chars:>12} {s:>18,.0f} {birthday_threshold(s):>22,.0f}")
 
# Demonstrate it.
seen, collisions = {}, 0
for i in range(300_000):
    url = f"https://example.com/page/{i}"
    code = hashlib.sha256(url.encode()).hexdigest()[:5]      # short on purpose
    if code in seen:
        collisions += 1
    seen[code] = url
print(f"\n5 hex chars over 300,000 URLs -> {collisions:,} collisions")
print("A truncated hash is not an identifier scheme. It reintroduces the birthday")
print("problem at a scale you will actually reach, so every insert needs a read to")
print("check -- and at that point the determinism you wanted has bought you nothing.")
 
# A counter with base62 encoding: no collisions by construction.
def b62(n):
    chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    out = ""
    while n:
        n, r = divmod(n, 62)
        out = chars[r] + out
    return out or "0"
 
print(f"\ncounter-based codes: {[b62(n) for n in (1, 1000, 10**9, 10**12)]}")
print("Sequential and therefore guessable, which is why real systems either")
print("hand out non-contiguous ranges per node or permute the counter.")

Expected outcome: the threshold column shows collisions becoming likely far below the address space, and the demonstration produces real collisions at a modest corpus size. The consequence is that a truncated hash still requires a read before every insert, which eliminates the only advantage it had over a counter. The counter output shows the opposite trade: no collisions by construction, but sequential and therefore enumerable, which is why production systems partition ranges across nodes or permute the value.

Step 3 — delivery is above the transport (8 min)

# delivery.py
import random
random.seed(2)
 
class Link:
    """An open connection that silently drops some sends."""
    def __init__(self, loss=0.2):
        self.loss, self.delivered = loss, []
    def send(self, msg):
        if random.random() > self.loss:
            self.delivered.append(msg)
        return True          # send() succeeds regardless -- this is the trap
 
msgs = [{"id": f"m{i}", "body": f"message {i}"} for i in range(20)]
 
link = Link()
for m in msgs:
    link.send(m)
print(f"naive: sent {len(msgs)}, actually delivered {len(link.delivered)}")
print("send() returned success every time. It means the bytes entered a buffer,")
print("not that the peer received or processed them.\n")
 
# At-least-once: retry until acknowledged.
link = Link()
for m in msgs:
    for attempt in range(6):
        link.send(m)
        if m in link.delivered:
            break
print(f"with ACK + retry: delivered {len(set(x['id'] for x in link.delivered))}"
      f"/{len(msgs)} unique, {len(link.delivered)} total sends landed")
 
seen, final = set(), []
for m in link.delivered:
    if m["id"] not in seen:
        seen.add(m["id"]); final.append(m)
print(f"after client-side dedup by message id: {len(final)} messages shown")
print("\nAt-least-once plus idempotent dedup on a stable id is the standard pair.")
print("Exactly-once at the transport is not available; exactly-once as observed")
print("by the user is, and it is built at the application layer.")

Expected outcome: the naive run loses messages while every send reports success, which is the precise trap — a successful send means bytes entered a kernel buffer, not that the peer received or processed them, and connections die silently through address translation timeouts, radio handoffs, and sleeping devices. Acknowledgement with retry recovers delivery at the cost of duplicates, and deduplication on a stable message identifier removes those. That pair is how exactly-once as the user experiences it is built, since the transport cannot provide it.

Step 4 — fanout and the streaming budget (8 min)

# fanout.py
followers = [10] * 10_000 + [500] * 100 + [50_000_000] * 2
 
def cost_on_write(f): return sum(f)
def cost_on_read(f, reads_per_user=20): return len(f) * reads_per_user
 
print(f"write-fanout total writes per post-round : {cost_on_write(followers):>15,}")
print(f"read-fanout total reads per view-round   : {cost_on_read(followers):>15,}")
print(f"\nlargest single account forces            : {max(followers):>15,} writes")
print("for one post. That arrives as a synchronous burst that saturates the write")
print("path and delays everyone else's posts -- the tail breaks the median design.")
 
THRESHOLD = 100_000
hybrid = sum(f for f in followers if f < THRESHOLD)
print(f"\nhybrid (push below {THRESHOLD:,}, pull above): {hybrid:>13,} writes")
print(f"reduction: {1 - hybrid/cost_on_write(followers):.1%}")
print("Large accounts are merged in at read time from a small, hot, well-cached")
print("set. Hybrid is not a compromise -- it is the only design that survives a")
print("follower distribution with a heavy tail.\n")
 
budget = [("auth + rate limit", 5), ("history load", 20), ("retrieval", 120),
          ("safety pre-check", 40), ("first token from model", 600)]
total = 0
for name, ms in budget:
    total += ms
    print(f"  {name:<26} {ms:>5} ms   cumulative {total:>5} ms")
print(f"\ntime to first token: {total} ms")
print("Everything before the model is latency the user feels before anything moves.")
print("Streaming is mandatory because total generation takes seconds; the metric")
print("that matters is time to first token, not total duration.")

Expected outcome: the two largest accounts dominate the write-fanout total entirely, turning one post into an enormous synchronous burst that delays every other user's writes — the tail breaks a design that is correct for the median. The hybrid figure shows most of that cost disappearing by pulling large accounts in at read time from a small, hot, cacheable set. The latency table then makes the streaming argument concrete: every pre-model stage is time the user waits before anything appears, so time to first token is the metric to optimise and total duration is not.

Gap analysis + next week preview · 10 min

• Can you run the four phases with a clock? Time discipline is scored even when the content is right.
• Did the fanout numbers land? The tail breaking the median design is the general shape of most scaling failures.
• Could you name what your own design costs, unprompted? That habit is the difference between levels.

What comes after the plan: the twenty-six weeks are done, and the material only holds if it is used. Take the three canonical designs and write each as a real document with your own numbers. Rebuild one drill a week from a blank page rather than rereading. Pick one system you use daily and derive its architecture from its constraints. The revision posts stay useful as a spaced-repetition schedule — the recall prompts are the point, not the prose.

Part of the 6-month evergreen learning plan.