System Design Case Studies 2 cheat sheet

1. Requirements: what it does, scale, what is out of scope.
2. Numbers: label each as an assumption, show the arithmetic, end with "so this means...".
3. API and data model: the few calls and tables that matter.
4. Architecture: one diagram, then walk each use case through it.
5. Deep dives on the 2-3 hardest parts.
6. Failure modes and trade-offs: say them out loud.
7. A 60-second spoken answer.

1B pages/month = ~400 pages/s
peak ~800; 100 KB/page = 40 MB/s
100 TB/month raw
1 req/s per host -> need >= 400
hosts crawled at once

• Frontier = priority queues plus one queue per host with a next-allowed time. Shard by host.
• Hash content to drop duplicate pages. Cap URL length, depth and pages per host against traps. Honour robots.txt and Retry-After.

10B keys x 1.05 KB = 10.5 TB
x3 copies = 31.5 TB
1.2 TB usable each -> ~30 machines
1M ops/s, 90% reads
-> ~70k replica ops/s per machine

• One node: hash table + write-ahead log + snapshots. The fsync policy is the durability dial.
• Consistent hashing with virtual nodes: 6th node moves 16.7% of keys, hash % N moves 82.8%.
• N=3, R=2, W=2 gives R + W > N. Conflicts: version vectors keep siblings, last-write-wins loses data.
• Repair: hinted handoff, read repair, anti-entropy. If fewer than R replicas are alive, fail with 503.

100M users x 2 GB = 200 PB
dedup 25% -> 150 PB
200M changes/day = ~2,300 commits/s
(peak ~7,000)
1 GB file, 4 MB chunks: ~10 KB meta
1 GB file, 4 KB chunks: ~10 MB

• Name each chunk by its hash: dedup, safe retries, cheap renames. The server re-hashes every chunk.
• Content-defined chunking: a 10-byte insert re-sent 3.4 KiB instead of 400 KiB.
• Upload chunks first, commit last. Resume = ask which hashes are missing.
• Notifications are hints, the journal is the truth. Conflicts: compare-and-set on baseRev, keep both copies.

• Apply edits locally first. 5M open docs, 10% typing at 2 msg/s = 1M msgs/s in.
• Op log is ~400x the text (25 MB vs 60 KB), so snapshot every ~1,000 ops: open = snapshot + short replay.
• Cursors and presence are temporary: throttled, never logged. Dedupe ops by clientSeq; check the ACL on every message.

• Origin load = R x (1 - hit). Think in miss ratio: 90% to 99% is 10x less. (100k req/s, 20 ms hit, 250 ms miss.)
• Edge, then shield, then origin. Edge ends TLS. Users reach it by GeoDNS or anycast.
• The cache key controls hit ratio: one tracking parameter cost 27 points. Coalescing turned 1,603 origin fetches into 4.
• Hashed URLs, purge by tag, stale-while-revalidate. Never cache Set-Cookie or private responses.

add(x):   each row i: t[i][h_i(x)]++
count(x): min over rows of t[i][h_i(x)]

• 5B events/day = ~58k/s, ~175k/s peak. If exact counters fit (50M items ~ 0.9 GB), use them.
• A sketch cannot list keys, so pair it with a min-heap of size K.
• Sliding window = a ring of per-minute sketches, summed. Partition by item: global top-K = top-K of local lists.
• Hot key: pre-aggregate and split into sub-keys. Trending means rising: use ratio to baseline or decay.

1 sign | 41 time | 10 worker | 12 seq
41 bits ms = 69.7 years (own epoch)
1,024 workers
4,096 IDs per ms per worker

• Three failures: clock steps back (wait or refuse), sequence overflow (wait for next ms), duplicate worker number (lease it).
• Send IDs as strings in JSON. They are only roughly time-ordered.

• Distance sets the floor: New York to London is ~56 ms round trip in straight fibre.
• Async replication loses write rate x lag: 1,000 writes/s x 4 s = 4,000. DNS failover = detection + TTL (30 s + 60 s = 90 s).
• Two independent 99.9% sites give 99.9999%, an upper bound: a bad release hits both.
• Split brain: majority vote with a third voter, fencing epochs, leases. The minority stops writing. Each site must carry 100% of load.

• Book = sorted price levels + FIFO queue per level + id map for O(1) cancel. Best price first, then oldest. Trade at the maker's price.
• One sequencer, one thread per symbol group: deterministic. The command log is the truth; replay rebuilds state.
• Volume is small (500M orders/day ~ 21k/s); the tail latency is the product. Reject orders if the log write fails. Never block on a slow feed subscriber.

1B sales/month = ~400/s
reads 100:1 = 40k/s
peak 5x: 2,000 sales/s, 200k reads/s
20M members x 64 B = ~1.3 GB/window
(3 windows ~4 GB)
top-100 x 1,000 categories = ~5 MB

• Write path: stream, dedupe by event id, hourly buckets. Read path: a precomputed Redis sorted set (ZINCRBY) behind a cache.
• 7-day window = 168 hourly buckets: add new, subtract expired. Apply pending changes before expiring.
• Coalescing: 100,000 writes became 200 in a flash sale, only 2.3% fewer on spread data. Hot category: micro-batch, shard and merge.
• Keep raw sales to rebuild into a versioned key, then switch.

1. Link via an aggregator and keep its token, never the bank password (envelope-encrypted).
2. Fetch pages. Upsert on (account_id, provider_txn_id); move the cursor only after the page is saved.
3. Replace pending rows with posted ones using a tombstone.
4. Categorise rules first, model for the long tail; the user override wins.
5. Total, alert (one row per sent alert), reconcile against the bank balance.

Tip: 5B transactions/month = ~2,000 writes/s, 250 GB/month (~9 TB in 3 years). Reads are only ~200/s. The limit is the aggregator and slow banks.

• Change only what a number tells you: load test, profile, fix the bottleneck, repeat. Shard last, multi-region after that.
• Latency 50 ms becomes 500 ms at 90% busy and 5,000 ms at 99%: plan for 70-80%. Cache hit 90% to 99% cuts DB reads from 4,000 to 400/s.