System Design Capstones

Produce evidence for a design decision

This module assumes queues, caches, partitioning, replication, and basic consistency trade-offs. If you cannot yet explain a retry or a stale read, review those foundations before choosing products. Your output here is a short design document with workload arithmetic, one successful request trace, one failure trace, and tests that could disprove your claims.

The worked design below is a fictional course workload. Its rates, sizes, service capacities, and latency budgets are assumptions to test, not measured facts about an existing service. Build the regional baseline first, then explain what changes for global users. The other three briefs test transfer to different bottlenecks; they are exercises, not already-completed designs.

Worked example: a chronological news feed

1. Requirements and limits

Users create public text posts, follow authors, and request the latest 50 posts from followed authors. Results are ordered by (created_at, post_id) descending; post_id breaks timestamp ties. Return each post at most once per page.

For the baseline, follow relationships are fixed during the request/failure traces. Posts are immutable, retained for seven days, and have no media, edits, or private visibility rules. These exclusions make the trace small enough to inspect; a production design must add those behaviors explicitly.

Requirement or assumption	Value and interpretation
Active viewers	10 million daily
Feed reads	20 per viewer per day; provision for 25,000 requests/s peak
Post creation	2 million/day; provision for 250 ordinary-author posts/s peak
Ordinary fanout	mean 200 recipients/post; separately test skew
Exceptional author	one post can have 10 million recipients
Viewer follows	at most 500 authors, including at most 20 exceptional authors
Payload assumptions	1,000 bytes/post; 32 bytes/feed reference, before overhead
Feed latency target	end-to-end p99 below 200 ms at the stated peak in the region
Successful-read target	at least 99.9% during the peak-load test; errors and admission rejections count as failures
Freshness target	99% of ordinary posts visible within 5 s in steady state
Failure target	after a 120 s worker outage, oldest queued work clears within 6 min of recovery
Durability requirement	an acknowledged post survives a single-zone failure

The 5 s freshness target does not apply during the declared outage drill. The exception is observable: record the affected interval and lag instead of calling a delayed feed fresh. Whole-region loss is outside the baseline durability claim. These are acceptance targets; the paper design has not passed them yet.

2. Calculate load before choosing components

10,000,000 * 20 = 200,000,000 feed reads/day, or about 2,315/s on average. The 25,000/s peak assumption is roughly 10.8 times the average. Average post creation is 2,000,000 / 86,400 ≈ 23.1/s; the specified peak is 250/s.

Pure fanout on write copies a reference into every follower's feed. Ordinary peak work is 250 * 200 = 50,000 feed inserts/s. Assume a measured target of 10,000 inserts/s per worker with the chosen database and batch size; eight workers would provide 80,000/s, leaving 30,000/s for recovery. This is a planning hypothesis: a shared database bottleneck can invalidate linear worker scaling.

A single 10-million-follower post would consume 10,000,000 / 80,000 = 125 s even with all workers and no ordinary traffic. With ordinary peak traffic continuing, its extra work takes about 10,000,000 / 30,000 ≈ 333 s to drain. Neither estimate supports the 5 s freshness goal.

Choose hybrid fanout: ordinary authors use fanout on write; exceptional authors are merged at read time. This removes their burst of follower writes, but charges each interested read for extra sources. Classification is stable in this baseline. A later threshold change needs an overlap interval, dual source reads, and post-ID deduplication so that routing changes do not hide posts. The follower-count threshold must come from measured work and the freshness budget; the mean of 200 alone does not bound every author's burst.

Capacity estimates with all 2 million daily posts treated as ordinary give:

Quantity	Arithmetic	Raw estimate
Post bytes written/day	2,000,000 * 1,000	2 GB
Seven-day post retention	2 GB * 7	14 GB
Feed references written/day	2,000,000 * 200	400 million
Feed-reference bytes/day	400,000,000 * 32	12.8 GB
Seven-day references	12.8 GB * 7	89.6 GB
Three replicas, posts plus references	(14 + 89.6) * 3	310.8 GB

Here GB means 10^9 bytes. Indexes, row encoding, follower edges, the durable outbox, cache contents, replication traffic, and compaction headroom are extra. A seven-day retention rule is not a promise to keep only 50 references per viewer. Storing references avoids duplicating the 1,000-byte body for every recipient.

3. Make the source of truth and derived views explicit

Create request → Post service → transaction: Posts + Outbox
                                         ↓ relay, may retry
                                   Durable queue
                                         ↓ fanout workers
Feed request → Feed service ───────────→ ViewerFeed references
                    ├─────────────────→ Exceptional author streams
                    └─────────────────→ Post bodies (cache → Posts store)

Use these logical records before selecting storage products:

• Posts(post_id, author_id, created_at, body): authoritative posts, indexed by author and time; the exceptional-author stream is this index, not a separately best-effort write.
• CreateRequests(author_id, request_id, payload_hash, post_id): the stable result of a create retry. Reusing a request ID with a different payload fails.
• Outbox(event_id=post_id, author_id, delivery_state): created in the same transaction as the post and its request record.
• Follows(author_id, viewer_id): recipient lookup; also support the reverse view to list a viewer's followed exceptional authors.
• ViewerFeed(viewer_id, post_id, created_at): unique (viewer_id,post_id), with a time-ordered index for each viewer; a derived view that can be rebuilt.

Partition viewer feeds by viewer ID; partition post data by author or post ID with an author/time index. Hot exceptional-author reads need replicated caches and batching; hashing identifiers does not make a single hot key disappear. The post transaction must use storage configured to durably commit across the failure domain promised by the acknowledgement. Merely writing to a cache or one zone does not meet the durability requirement.

The transactional outbox couples database state and pending delivery. A relay can still publish twice, so consumers must handle duplicates; this is the pattern's documented boundary. See AWS's transactional outbox guidance.

4. Trace the successful write and read

For ordinary author A, a client sends request key r17. One database transaction creates post p42, stores (A,r17) → p42, and creates outbox event p42. Only after commit does the service acknowledge the post. A relay publishes p42. Workers enumerate A's followers in restartable chunks and upsert each (viewer,p42) reference. A chunk is acknowledged after its writes commit. Reprocessing a chunk is safe because its recipient/post keys already exist.

For a read, fetch the newest 50 ordinary references and the newest 50 posts from each followed exceptional author, all within the seven-day window and below the requested pagination cursor. With at most 20 such authors, merge at most 50 + 20*50 = 1,050 candidates. Deduplicate by post ID, choose the newest 50, and batch-fetch their bodies. Fifty from each source is sufficient: a post below a source's own newest 50 cannot be in the overall newest 50.

At 25,000 reads/s, that bound is 26.25 million candidate references/s before cache reuse. That is a load-test input, not a claim that merging is cheap. Batch author-stream lookups, share cached author streams across readers, and measure CPU, storage reads, bytes, and hot-key contention. If the follow limit or candidate count grows, revisit the algorithm and budget.

Use the last returned (created_at,post_id) as an exclusive cursor for the next page. This avoids timestamp-tie duplication. It does not create a snapshot of asynchronously populated feeds: a delayed fanout entry can arrive behind an already-consumed cursor and be missed in that pagination session. Refreshing the first page is eventually consistent; exact snapshot pagination would need a stronger delivery/snapshot contract.

Allocate a deadline budget of 20 ms for routing/authentication, 70 ms for parallel candidate fetches, 30 ms for merging/body hydration, and 30 ms for serialization/network, leaving 50 ms within 200 ms for variation. These are stage deadlines to instrument. Adding independently measured stage p99s would not establish the end-to-end p99; measure whole requests at peak, with warm and cold caches. A cache miss falls back to the durable store. Apply admission and concurrency limits so a cold cache does not overload it.

5. Trace ambiguous outcomes, retries, and recovery

Event	Persisted state	Required next behavior
Transaction for r17 commits; response is lost	post p42, request result and outbox all exist	retry r17 returns p42, not a second post
Relay publishes p42, then crashes before marking delivery	queue may contain p42; outbox still pending	relay republishes safely after restart
Worker commits reference (V,p42), then crashes before chunk acknowledgement	reference exists; chunk will be retried	upsert leaves one reference for V
All fanout workers stop for 120 s at 50,000 inserts/s	authoritative posts remain; 6 million reference writes wait	reads may be stale; report oldest pending age
Workers resume at 80,000 inserts/s while arrivals stay 50,000/s	spare service rate is 30,000/s	drain extra backlog in 6,000,000/30,000 = 200 s

The recovery estimate is 200 s after restart, or 320 s from outage start. It assumes no added bottleneck and enough queue/outbox retention. The drain calculation uses service rate minus arrival rate; dividing by 80,000 would incorrectly assume new work stops. If capacity is at or below arrivals, backlog cannot drain. Monitor oldest pending age as well as queue length, and retain pending events until delivery is confirmed rather than expiring them on the ordinary post-retention timer.

Stable request IDs and atomic request-result recording address an ambiguous create response; feed upserts address duplicate event delivery. These are separate boundaries. Retry safety depends on the side effect, key, and durable record, as discussed in AWS's idempotent API guidance.

6. Decide what the design has and has not demonstrated

The arithmetic rules out ordinary write fanout for the exceptional burst and provides a recovery hypothesis. It does not prove the latency or freshness objectives. The acceptance plan must include:

1. Sustained 25,000 feed reads/s and 250 ordinary posts/s, with a skewed follower distribution: record whole-request p99, visibility delay, successful-read fraction, and database load.
2. An exceptional author posting to 10 million followers: observe write work, hot author-cache reads, and read latency under cold-cache conditions.
3. Crash injections at each row of the retry table: one stable post ID per create request, one feed reference per recipient/post, and eventual delivery.
4. The 120 s worker outage: verify the measured drain time against 200 s and the six-minute recovery target; reject the design if storage caps throughput.
5. Single-zone loss immediately after acknowledgement: verify the acknowledged post and pending outbox survive in the promised storage configuration.

For global users, regional serving replicas improve proximity but can be stale. Keeping one write region simplifies ordering and request deduplication while adding remote write latency and region-loss limits. Multi-region writes require an explicit conflict, ownership, and failover policy. State a revised regional latency and recovery objective before claiming the baseline meets global needs.

Complete the capacity argument, then challenge it

Use a changed workload: fanout arrivals are 30,000 reference writes/s, workers stop for 60 s, and recovery capacity is 50,000/s. Fill the two missing values:

backlog = arrival rate * outage duration = 1,800,000 reference writes
spare recovery capacity = service rate - continuing arrivals = ? writes/s
recovery duration after restart = backlog / spare capacity = ? seconds

Check the capacity argument after attempting it

Spare capacity is 20,000 writes/s, and recovery takes 90 s after restart, assuming storage sustains the stated service rate. The entire incident lasts 150 s from outage start. Dividing by 50,000 ignores continuing arrivals.

Now remove the scaffold: suppose a database bottleneck caps all workers at 25,000 writes/s under this workload. Explain whether hiring more workers or waiting longer resolves the backlog. Propose a change, name its user-visible cost, and state the measurement that would make you reject it.

One defensible critique; alternatives need their own evidence

At 30,000 arrivals/s and 25,000 completed writes/s, the backlog grows by 5,000/s even after restart. More workers do not remove the assumed shared storage limit. Moving selected authors to read-time merging can reduce incoming fanout work, but increases read candidate cost; measure both resulting queue lag and end-to-end read latency. Increasing storage throughput is another option, but its benefit must be measured rather than inferred from worker count.

Before using the rubric, write the lost-response trace from memory and identify which durable key protects post creation versus feed insertion. On a later visit, use the analytics brief below: derive replay catch-up without copying the feed numbers or assuming live input stops.

Transfer exercises: change the failure and the scarce resource

Choose one brief and write the design artifact below. State any extra assumptions.

Brief	Given workload and target	Required trace and trade-off
Ride dispatch	100,000 active drivers report every 5 s; 500 ride requests/s peak; assignment decision p99 below 1 s	Calculate 20,000 location updates/s. Show a timed-out offer followed by a late acceptance; define atomic ride and driver reservation states, expiry/version checks and idempotent transitions so neither gets two active assignments. Explain how stale location changes candidate quality.
Video streaming	50,000 concurrent streams averaging 4 Mbit/s; 95% byte cache-hit rate; a cold release can cut that to 50%	Compute edge demand and both origin-miss bandwidths. Trace concurrent misses for one segment; consider coalescing, replication and origin limits. A request hit rate alone cannot determine byte traffic for unequal segment sizes.
Analytics pipeline	40,000 events/s at 500 bytes/event; a 2 h correction window; replay capacity 100,000 events/s shared with live processing	Bound retained input, derive catch-up time while live input continues, and trace a replay overlapping already-counted event IDs. Compare deduplicated incremental writes with a versioned recomputation and atomic output switch. Define late-event and replay boundaries.

For dispatch, a geospatial index proposes candidates; it does not enforce the assignment invariant. For video, a CDN shifts byte delivery, while a cold-cache burst still reaches origin. For analytics, redelivery and recomputation are normal: label the effect that is idempotent instead of asserting “exactly once” for the entire pipeline.

Your capstone artifact and rubric

Submit or keep a two-to-four-page document with: a requirements/workload table, an architecture and data ownership sketch, capacity calculations with units, success and failure traces, one rejected alternative, and an acceptance-test plan. There is no automatic freeform submission in this module: use this rubric for a peer review or self-review. The checkpoint tests the component reasoning; passing it does not grade the design document.

Score each row 0, 1, or 2. Award 2 only when the evidence described is present; 1 means the topic is mentioned but its derivation or boundary is missing; 0 means absent or contradictory.

Dimension	Evidence for 2 points
Requirements	Numeric targets, peak workload, failure scope and explicit exclusions
Capacity	Reproducible rates/storage arithmetic with units, skew and headroom
Data and ownership	Authoritative versus derived records, keys, partitions and consistency boundary
Request path	A concrete write/read sequence including acknowledgement, cache misses and ordering
Failure recovery	Persisted state at each failure, duplicate/late behavior, backlog and catch-up calculation
Trade-off	A rejected alternative with a quantified cost and a condition that changes the decision
Validation	A load test and fault drill with observables and pass/fail thresholds

Aim for at least 11/14, with 2 in failure recovery and no zero in requirements or data/ownership. A diagram full of product names without keys, state transitions, or arithmetic cannot satisfy those rows. For self-review, cover the worked design and reconstruct the outage calculation with 70,000/s recovery service: the spare rate becomes 20,000/s, so the same backlog needs 300 s after restart. Then revise your own weakest rubric row before taking the checkpoint.