R26 · Week 26 Recall & Drill

Assessment scope

This closing revision connects requirements, capacity, identifier allocation, durable message handling, feed work and AI-product budgets. It restores complete worked answers and safe local models, not live infrastructure. Four Python blocks use the standard library and in-memory SQLite. No network, cloud account, model, dataset or new package is needed. Timings are optional practice budgets, not an interview scoring standard or evidence of mastery.

Sessions covered

• S126 — System Design Framework
• S127 — URL Shortener
• S128 — Chat System
• S129 — Newsfeed and Recommender
• S130 — AI Chat Product

Aim to derive a design under explicit requirements, compute rates/storage/identifier risk, use atomic uniqueness, distinguish send/receipt/commit acknowledgements, compare feed strategies on the same workload, and enforce request plus token/cost budgets. A hub link or remembered diagram is not an answer to these objectives.

90-min structure

The sum is 90 minutes. A larger implementation takes separate time; do not mark it complete when a timer expires.

Blank-page reconstruction · 30 min

S126 · The Framework

Prompts: give four phases and rough budgets; explain why estimates should inform architecture; offer three tradeoff sentences.

A useful 45-minute practice format is requirements (5), capacity (5), high-level design (15), deep dive/failure review (20). First define actors, operations, correctness, scale, latency, availability, retention and abuse constraints. Estimate orders of magnitude before committing to expensive components; then sketch a request/data path and investigate its riskiest assumption. Iterate: discovering a payload size or consistency constraint later should revise both the estimate and design. No universal rubric requires one exact order or time split.

For a shortener, a small average rate does not alone establish that one node suffices. Test peak distribution, disk growth, query patterns, backup/recovery, fault tolerance and operational margin. Storage exceeding one chosen machine motivates alternatives—retention changes, compression, a larger machine, tiering or partitioning—not a theorem that one particular shard key follows from the byte count.

Three useful sentences are: “I choose a unique insert so concurrent writers cannot claim one code, at the cost of conflict retries”; “I choose asynchronous fanout, accepting delayed feed visibility to avoid blocking post creation”; and “I reserve worst-case token cost before admission, trading some utilization for a spend bound.” Naming a cost demonstrates reasoning, but this page does not claim that every employer scores it the same way.

S127 · URL Shortener

Prompts: estimate rates/storage/space; compare ID allocation; decide redirect semantics.

At 100 million new links per assumed 30-day month, average writes are about 38.58/s. With 100 reads per write and an assumed 3× peak, peak reads are about 11,574/s. Five 365-day years at 500 bytes per record give about 3.042 TB raw or 9.125 TB with three full copies, excluding indexes, logs and backups. These are assumptions to challenge, not traffic measurements.

A globally unique counter encoded in base62 has no collisions if allocation and exhaustion are handled correctly; it is enumerable. Partitioned ranges need disjoint ownership across restarts. A random code with atomic unique insert/retry handles collisions while making prediction harder if generated with a suitable cryptographic source, but still needs authorization and rate limits. A truncated content hash provides deterministic candidate codes and may aid deduplication, but collisions need resolution. Identical URLs may need distinct owner/expiry/analytics records, so define identity before choosing content addressing. A check-then-insert sequence races; a unique constraint is the boundary.

For uniform independent codes from N possibilities, no-collision probability after k allocations is the product of (1-i/N) for i=0..k-1. The approximation 1-exp(-k*(k-1)/(2*N)) estimates collision probability in the sparse regime. sqrt(N) is an order-of-magnitude scale (about 39.3% probability asymptotically), not a sharp threshold or the exact 50% point. Counters and adversarial/nonuniform hashes do not follow this independent-random model.

RFC 9110 gives 301 permanent redirects heuristic cacheability. Cached redirects can bypass later shortener analytics or retargeting checks. Choose status and explicit cache controls from whether mappings are permanent, mutable or revocable; a temporary status alone is not a complete no-cache policy. Malicious-link revocation must consider already cached clients. Do not claim that every permanent redirect is always cached forever or universally wrong.

S128 · Chat System

Prompts: explain persistent-connection balancing, inbox pull and reconnection behavior.

A persistent connection consumes a file descriptor, buffers and connection-state resources over time; a request balancer’s per-request distribution does not automatically balance those costs. Plan connection draining, maximums, backpressure and routing to the node that holds a user’s connection. Presence is a best-effort lease/heartbeat observation, not proof a person is watching.

For a large group, append one message to a durable group log and let members fetch from a sequence cursor. This reduces per-message write amplification compared with eagerly copying the body to every recipient, but reads, permissions, unread counts, retention and slow-reader catch-up still cost work. Push notifications and selective inbox materialization can coexist with the log. Neither pull nor push is universally best.

After disconnect, reconnect using randomized backoff with a cap, reauthenticate, resume from the last durably applied sequence and deduplicate stable message IDs. RFC 6455 §7.2.3 explicitly discusses backoff after abnormal closure. Sequence gaps require fetching missing messages, not silently advancing the cursor. Persist deduplication/effect state atomically within the guarantee’s scope, and define retention and ID-reuse policy.

Gotcha correction: TCP reliability is not a promise that a successful application send has been processed or committed by the peer. The Python socket HOWTO describes network buffers and partial sends/receives. An application ACK means only what your protocol defines: receipt, validation, commit and display are different milestones. Even a commit ACK cannot prove a human read the message. Lost ACKs create retries and duplicates; bounded retries can still end in an unknown outcome.

S129 · Newsfeed

Prompts: reconstruct the two-stage pipeline; compare fanout choices; name feedback failures and defenses.

Candidate generation and scoring form a common recommendation pipeline. Candidate generation retrieves a manageable set from follow edges, recent content and other sources. Ranking scores those candidates under product and safety constraints, then a final policy can deduplicate, diversify and apply access checks. A ranker cannot rescue relevant items omitted from the candidate set; measure retrieval coverage and ranking separately.

Push precomputes recipient entries on a post, reducing some read work but adding writes/storage and delayed fanout failure handling. Pull gathers eligible posts at view time, reducing precomputation but increasing query/merge work. Hybrid materializes selected sources and merges others at read time. High follower counts motivate examining hybrid policies, but active-reader fraction, post/view frequency, freshness, cacheability and infrastructure decide the threshold. Fanout is commonly asynchronous in a design; a celebrity post need not be one synchronous database burst. A sufficiently provisioned pull or push design can also be valid.

Failure comparison on the same feed contract:

These are design obligations, not measured latency rankings. The two-stage sketch is candidate generation followed by scoring, with a final policy rerank/access-check stage before display; each stage must preserve the permitted source IDs.

Three feedback risks are exposure bias (unshown items have little response data), popularity reinforcement (repeated exposure creates further clicks) and proxy gaming/narrowing (clickbait or short-term clicks displace long-term value). Possible defenses include policy-safe randomized exploration with recorded propensities, diversity/coverage constraints and longer-term holdouts/product metrics. Exploration has user and safety costs; it is not the only way to obtain informative data. Offline engagement improvements alone do not establish better outcomes. The work-count exercise below models fanout mechanics, not user behavior or a trained recommender.

S130 · AI Chat Product

Prompts: trace and budget one turn; compare spend and request limits; give three additional abuse controls.

Authenticate/authorize → admit under request, token, concurrency and spend limits → load permitted history → retrieve authorized evidence → construct a bounded prompt → perform applicable input checks → queue/serve the model → validate or gate outputs/tools → stream permitted output → account for usage and monitor quality. User text, retrieved content and images are untrusted; use least-privilege tools and approval gates, not a prompt claiming to make injection impossible. OWASP’s prompt-injection guidance motivates layered controls.

A hypothetical serial first-token budget of 5+20+120+40+600 ms is 785 ms. If 100 output tokens arrive with 20 ms between tokens after the first, full response latency is 785 + 99*20 = 2765 ms. Actual retrieval overlap, queues, buffering, safety gates and variable token speed change both. Track TTFT, inter-token stalls, end-to-end latency, cancellation, successful completion and correctness. Streaming is useful for many chat experiences, but not mandatory for all tasks and not a substitute for safe output handling.

One request can contain a long prompt, long output or expensive tool loop. Request-rate limits alone do not bound spend; spend alone does not protect connection count or a free-but-expensive backend. Combine dimensions. Reserve a conservative per-user cost budget atomically before work, enforce token/tool/time ceilings while running, and reconcile actual usage without releasing unaccounted reservations on ambiguous failures. History truncation reduces cost but can remove a required instruction or evidence; preserve required context or ask for clarification.

Beyond rate limiting, enforce input/output size and concurrency caps, restrict tools/network egress by capability, require authorization for retrieved objects, bound retries/delegations, and route consequential actions for approval. Ordinary deterministic regression tests still apply to those controls. Add golden sets, repeated model evaluations and output-level monitoring for variable quality; a 200 response and healthy process do not imply a grounded answer.

Hands-on drill · 30 min

The scripts keep the original estimation, collision, delivery and fanout objectives, while correcting race-prone insert advice, unobservable ACKs and incomparable workload totals.

Step 1 — estimation in sixty seconds (6 min)

Use rational arithmetic so the assumptions are visible before formatting. A 30-day accounting month and a 365-day retention year are intentionally different conventions; replace them for a calendar-exact forecast.

from fractions import Fraction as F
 
def estimate(monthly_writes, read_ratio, bytes_per_record, years=5, peak=3):
    if min(monthly_writes, read_ratio, bytes_per_record, years, peak) < 0:
        raise ValueError("nonnegative inputs required")
    daily = F(monthly_writes, 30)
    wps = daily / 86400
    records = daily * 365 * years
    raw = records * bytes_per_record
    return dict(wps=wps, peak_wps=wps*peak, peak_rps=wps*read_ratio*peak,
                records=records, raw_bytes=raw, replicated_bytes=raw*3)
 
short = estimate(100_000_000, 100, 500)
chat = estimate(50_000_000_000, F(6,5), 300)
assert short['wps'] == F(3125,81)
assert short['replicated_bytes'] == 9_125_000_000_000
assert chat['replicated_bytes'] == 2_737_500_000_000_000
assert estimate(0, 100, 500)['raw_bytes'] == 0
for name, values in [('shortener', short), ('chat', chat)]:
    print(name, 'avg writes/s', round(float(values['wps']), 3),
          'peak reads/s', round(float(values['peak_rps']), 3),
          'raw TB', round(float(values['raw_bytes']/10**12), 6),
          'three-copy TB', float(values['replicated_bytes']/10**12))

Answer: the shortener’s three-copy total is 9.125 TB; chat’s is 2,737.5 TB under its much larger assumed write volume. None includes indexes, compaction, logs, tombstones or backups. Peak=3 and replicas=3 are separate assumptions. The numbers guide load tests and design choices; they do not prove a particular machine’s capacity or availability.

Step 2 — truncated hashes collide (8 min)

Base62 length c has 62**c codes. The bounded collision demonstration deliberately uses two hexadecimal characters, only 256 codes, and 257 distinct input URLs. A collision is guaranteed by pigeonhole, independent of how SHA-256 distributes this small fixture. This is not an attack on full SHA-256.

import hashlib
import math
import sqlite3
from fractions import Fraction as F
 
def collision_probability(space, draws):
    if type(space) is not int or space <= 0 or type(draws) is not int or draws < 0:
        raise ValueError("invalid space/draws")
    if draws > space:
        return F(1)
    none = F(1)
    for i in range(draws):
        none *= F(space-i, space)
    return 1-none
 
assert collision_probability(4, 2) == F(1,4)
assert collision_probability(4, 5) == 1
assert collision_probability(4, 0) == 0
codes = [hashlib.sha256(f'https://example.test/{i}'.encode()).hexdigest()[:2]
         for i in range(257)]
assert len(set(codes)) < len(codes)
 
def b62(n):
    if type(n) is not int or n < 0:
        raise ValueError("nonnegative integer required")
    alphabet = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    out = ''
    while n:
        n, remainder = divmod(n, 62)
        out = alphabet[remainder] + out
    return out or '0'
 
assert [b62(n) for n in (0, 61, 62, 63)] == ['0', 'Z', '10', '11']
assert len({b62(n) for n in range(10000)}) == 10000
with sqlite3.connect(':memory:') as db:
    db.execute('CREATE TABLE links(code TEXT PRIMARY KEY, owner TEXT, url TEXT)')
    def allocate(owner, url, candidates):
        for code in candidates:
            try:
                db.execute('INSERT INTO links VALUES (?, ?, ?)', (code, owner, url))
                return code
            except sqlite3.IntegrityError:
                continue
        raise ValueError('candidate budget exhausted')
    assert allocate('a','https://example.test/same',['X']) == 'X'
    assert allocate('b','https://example.test/same',['X','Y']) == 'Y'
    assert db.execute('SELECT COUNT(*) FROM links').fetchone()[0] == 2
    try:
        allocate('c','https://example.test/new',['X','Y'])
    except ValueError:
        pass
    else:
        raise AssertionError('exhaustion not reported')
print('2-hex collisions:', len(codes)-len(set(codes)))
print('base62 length-6 space:', 62**6, 'sqrt scale:', round(math.sqrt(62**6)))
print('atomic unique insert preserves separate owners; exhaustion is explicit')

Answer: unique insert rejects the conflicting X without overwriting owner A, then B receives Y even for the same URL. SQLite’s conflict documentation describes the default ABORT behavior used here. A distributed allocator still requires atomic uniqueness in its real store; this sequential in-memory test is not a concurrent database benchmark. Random candidates need a cryptographic generator in a real system, and neither a permuted counter nor a hard-to-guess code replaces access control.

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

Make the ACK visible as a protocol result rather than peeking into the receiver’s private list. Model send loss, lost commit ACK, and receiver reconstruction over retained state. Deduplication and the visible effect occur together in one local transaction; external side effects would need a different atomicity boundary.

import sqlite3
 
class Receiver:
    def __init__(self, db):
        self.db = db
    def receive(self, msg_id, body):
        with self.db:
            old = self.db.execute('SELECT body FROM inbox WHERE id=?', (msg_id,)).fetchone()
            if old is not None and old[0] != body:
                raise ValueError('ID reused with different body')
            if old is None:
                self.db.execute('INSERT INTO inbox VALUES (?, ?)', (msg_id,body))
                self.db.execute('INSERT INTO effects VALUES (?)', (msg_id,))
        return ('committed', msg_id)  # returned only after the transaction context exits
 
class Link:
    def __init__(self, receiver, outcomes):
        self.receiver, self.outcomes = receiver, iter(outcomes)
        self.landed = 0
    def send(self, msg_id, body):
        outcome = next(self.outcomes, 'drop')
        if outcome == 'drop':
            return None
        ack = self.receiver.receive(msg_id, body)
        self.landed += 1
        return None if outcome == 'lose_ack' else ack
 
def deliver(link, msg_id, body, attempts):
    for _ in range(attempts):
        if link.send(msg_id, body) == ('committed', msg_id):
            return 'acknowledged'
    return 'unknown'  # not proof of non-delivery
 
with sqlite3.connect(':memory:') as db:
    db.execute('CREATE TABLE inbox(id TEXT PRIMARY KEY, body TEXT)')
    db.execute('CREATE TABLE effects(id TEXT PRIMARY KEY REFERENCES inbox(id))')
    first = Link(Receiver(db), ['drop', 'lose_ack'])
    assert deliver(first, 'm1', 'hello', 2) == 'unknown'
    assert db.execute('SELECT COUNT(*) FROM effects').fetchone()[0] == 1
    # Receiver object restarts; retained DB state remains. This is not a disk/crash test.
    retry = Link(Receiver(db), ['ack'])
    assert deliver(retry, 'm1', 'hello', 1) == 'acknowledged'
    assert first.landed + retry.landed == 2
    assert db.execute('SELECT COUNT(*) FROM effects').fetchone()[0] == 1
    assert deliver(Link(Receiver(db), ['drop']*3), 'm2', 'later', 3) == 'unknown'
    try:
        Receiver(db).receive('m1', 'different')
    except ValueError:
        pass
    else:
        raise AssertionError('conflicting ID accepted')
    assert db.execute('SELECT body FROM inbox WHERE id=?', ('m1',)).fetchone()[0] == 'hello'
print('lost ACK: unknown then acknowledged; 2 landed deliveries, 1 effect')
print('all drops remain unknown; conflicting ID rejected')

Answer: the first call commits but its ACK is lost; the sender correctly reports unknown after bounded retries. The retried same ID lands again without a second effect. A new Receiver object shares the retained in-memory database, demonstrating state placement, not persistence through power loss. Guarantee scope requires durable storage, transaction isolation, deduplication retention and replay policy. “Exactly once” is not a transport feature or an unconditional user-visible promise.

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

Compare one fixed workload: four authors post once; three viewers each view once with known follow edges. Candidate-read counts exclude ranking, storage indexes and cache behavior. Push materializes every edge; pull scans each viewer’s followed authors; hybrid materializes sources with fewer than three followers and fetches the other source at read time.

from dataclasses import dataclass
 
followers = { 'a': {'u','v'}, 'b': {'u'}, 'c': {'u','v','w'}, 'd': {'w'} }
views = ['u','v','w']
 
def feed_work(followers, views, threshold):
    push = {a for a, users in followers.items() if len(users) < threshold}
    writes = sum(len(followers[a]) for a in push)
    read_entries = sum(sum(user in users for users in followers.values()) for user in views)
    late_entries = sum(sum(user in users for a,users in followers.items() if a not in push)
                       for user in views)
    return writes, read_entries, late_entries
 
assert feed_work(followers, views, 10) == (7,7,0)  # all push
assert feed_work(followers, views, 0) == (0,7,7)   # all pull
assert feed_work(followers, views, 3) == (4,7,3)   # hybrid
heavy = [10]*10000 + [500]*100 + [50000000]*2
assert sum(heavy) == 100150000
assert sum(f for f in heavy if f < 100000) == 150000
# The heavy-tail fixture only counts writes; no invented read workload comparison.
 
stages_ms = [5,20,120,40,600]
ttft = sum(stages_ms)
full_ms = ttft + 99*20
assert (ttft, full_ms) == (785,2765)
 
@dataclass
class Budget:
    available: int
    reserved: int = 0
    spent: int = 0
    def reserve(self, amount):
        if type(amount) is not int or amount < 0 or amount > self.available:
            raise ValueError('reservation denied')
        self.available -= amount
        self.reserved += amount
    def settle(self, reservation, actual):
        if any(type(v) is not int for v in (reservation, actual)) or not 0 <= actual <= reservation <= self.reserved:
            raise ValueError('invalid settlement')
        self.reserved -= reservation
        self.spent += actual
        self.available += reservation-actual
 
# Synthetic integer cost units, not provider prices: input=1, output=4 units/token.
account = Budget(1000)
reservation = 100*1 + 50*4
account.reserve(reservation)
try:
    account.reserve(701)
except ValueError:
    pass
else:
    raise AssertionError('overspend admitted')
account.settle(reservation, 100*1 + 20*4)
assert (account.available,account.reserved,account.spent) == (820,0,180)
assert account.available + account.reserved + account.spent == 1000
print('push/pull/hybrid:', [feed_work(followers,views,t) for t in (10,0,3)])
print('TTFT/full ms:', ttft, full_ms, 'budget available/spent:', account.available,account.spent)

Answer: all three policies expose seven candidate entries for the same three views, but perform different precomputation/late retrieval. Hybrid saves three materialization writes versus push here; it does not make read work vanish or prove a faster service. The heavy-tail example has 100,150,000 potential writes versus 150,000 below the chosen threshold, but choosing that threshold still requires an actual reader workload and resource model.

The budget starts at 1,000, reserves 300, rejects another 701, settles 180 actual and releases 120, leaving 820. This is a single-threaded accounting model. Real reservations need atomic concurrent updates, unique request IDs, cancellation/timeout reconciliation and enforcement that actual work cannot exceed the reservation. A negative balance discovered after unrestricted generation is not a budget control. In particular, the toy tracks a pooled reserved total, not individual reservation identities: reserve 300 twice, then call settle(300,180) twice for the first request, and both calls pass while consuming the second request’s reservation. The sum invariant still holds, so conservation alone does not prove correct attribution or replay safety. A real ledger binds each reservation to one authorized request and atomically accepts at most one terminal settlement (or verifies an identical retry); ambiguous work keeps its reservation until reconciliation.

Answer constraints and corrections

Misconception: memorizing reference designs supplies the right architecture. Reference designs are useful examples, but a new requirement can invalidate their assumptions. If the shortener must revoke links quickly, revisit cached redirects; if chat requires durable acceptance, define the commit ACK; if the feed has few active readers, question eager materialization; if a model turn can invoke tools, bound permissions and cost. Derive and revise each choice. This is a practice rubric, not a statement that hiring evaluates only process and never knowledge.

Quiz and worked answers

1. Why estimate before committing to architecture? Rates, payloads and retention expose resource demands and help test simpler choices. Iterate when requirements change. A small workload does not remove redundancy requirements; a large byte count does not alone choose a shard key. Estimate and measure, rather than drawing boxes first and treating numbers as decoration.
2. Two problems with truncated-hash IDs? Distinct inputs can collide in the smaller namespace, and identical inputs may collapse records that need independent ownership/expiry. Resolve conflicts with an atomic unique operation and a bounded alternate-candidate policy. Deterministic hashing can still be useful; it is not rendered pointless by collision handling.
3. Why an application ACK despite TCP? Send completion and reliable byte-stream behavior do not prove application commit. Define which milestone is acknowledged. The lost-ACK drill demonstrates both duplicate delivery and unknown outcome, with one effect only because stable-ID handling and the effect share a transaction.
4. Why consider hybrid feeds? Follower distribution, activity and freshness can make selective materialization cheaper than all-push and easier to serve than all-pull. It moves work rather than eliminating it. Pure strategies can still be suitable; neither celebrity fanout nor synchronous writes are universal architecture laws.
5. What extra concerns arise in AI chat? Variable/long latency motivates optional streaming with TTFT, stall and whole-response metrics. Variable input/output/tool cost requires reservations and ceilings in addition to rate limits. Model variation requires calibrated quality evaluation alongside ordinary deterministic software tests. Fluent incorrect output requires evidence/quality monitoring beyond HTTP status. Untrusted prompts/documents/images require authorization, constrained tools and output/action gates; delimiters are not a security boundary. Caching also needs privacy, freshness and semantic-equivalence rules. These concerns extend ordinary web engineering; they do not replace it.

Gap analysis + next week preview · 10 min

Score each answer as unaided, hinted or missing. Change one assumption: increase retention, allow duplicate URLs with separate owners, lose an ACK after commit, make only one follower active, or double output-token allowance. Recompute and explain which component changes and why. A correct familiar script does not certify a live system.

There is no scheduled Week 27 in this 26-revision source route. For the next project, write a short design document for one of the three systems with your own workload, invariants, API, failure trace, alternatives and measurement plan. Rebuild one bounded drill later without the solution and compare with the stored oracle. The plan ending is not evidence that its subjects will remain mastered without use.

Corrective source notes

Source-supported contracts: RFC 9110 (June 2022) redirect semantics; RFC 6455 (December 2011) abnormal-closure backoff; Python 3.12 Socket HOWTO for buffers/partial I/O; SQLite live ON CONFLICT documentation and OWASP live prompt-injection guidance, accessed 2026-10-08. The fanout strategy comparison, birthday derivation and budget calculations are explicit mathematical/local design models, not observations of a deployed social network, payment service or LLM provider. All four code blocks were checked locally; no server, real connection, concurrent allocator, crash-durable database, trained recommender or model runtime was reproduced.