System Design Intro

# ===== The map: DSA pattern -> system design lever =====
#
# Hashing                -> sharding key, cache key, idempotency key
# Sorted structures      -> time series buckets, ordered queues, indexes
# Heap / priority queue  -> rate limit token bucket, retry backoff, scheduler
# Trie / inverted index  -> autocomplete, full-text search
# Graph traversal        -> friend-of-friend, dependency resolution, blast radius
# Bloom filter           -> cache miss filtering, dedup before expensive lookup
# HyperLogLog            -> approximate cardinality (DAU, unique IPs)
# Reservoir sampling     -> uniform sample of an unbounded stream
# Consistent hashing     -> shard with minimal rebalance on node add/remove
# Skiplist / B+tree      -> on-disk indexes (LSM compaction tradeoffs)
# Topological sort       -> dependency builds, DAG schedulers (Airflow style)

# ===== Worked example: design a URL shortener =====
# Reqs: 1B URLs over 5y, < 100ms p50 read, sequential id leak-free
# DSA hooks:
#  - Base62 encoding of 64-bit id -> 11 chars
#  - Bloom filter in front of DB: 'this short code may exist'
#     -> avoid DB hit on most lookups for random typos
#  - Consistent hashing for write shards
#  - Skiplist memtables + SSTables (Cassandra/Scylla) for write-heavy
#  - Edge cache (CDN) keyed by short code

# ===== Worked example: design a chat fan-out =====
# Reqs: 100M users, group chats up to 1000, < 1s message delivery
# DSA hooks:
#  - Heap per user: priority = chat last-activity (push notifications)
#  - Inverted index: word -> chat ids (search)
#  - LRU cache: recent conversations in memory
#  - Bloom filter: per-user 'has unread' to skip empty queries
#  - Graph: friend-of-friend for invite suggestions

# ===== Capacity sketches you should be able to do in 90 seconds =====
# DAU 10M, msgs/user/day 50 -> 500M msgs/day -> 6k msgs/s avg, 60k peak
# Each msg ~1KB stored -> 500GB/day raw, ~150GB compressed
# Search index ~30% of raw -> 45GB/day

# ===== Tradeoffs interviewers probe =====
# - Read-heavy vs write-heavy: indexes vs LSM
# - Strict ordering vs throughput: log-structured vs unordered fan-out
# - Exact vs approximate: HLL, bloom, count-min sketch
# - In-memory vs on-disk: capacity vs latency
# - Single-region vs multi-region: consistency model dictates DSA choice

# ===== Patterns to internalise =====
# - Identify hot operation FIRST, then pick the structure
# - Cache key = hash that distributes evenly and includes versioning
# - Approximate structures (HLL, bloom) earn back orders of magnitude
# - Sharding key is a one-way decision; choose with care
# - Backpressure with bounded queues + heap-ordered scheduling

# ===== Pitfalls =====
# - Reaching for a fancy structure when an array + binary search is plenty
# - Choosing a graph DB because the data is 'linked' (most relations are joins)
# - Bloom filter without considering false-positive rate vs traffic
# - Consistent hashing without virtual nodes -> uneven shards
# - Ignoring write amplification of LSM trees on small-update workloads

// LB → API → cache → DB → queue → workers → store. Pick consistency vs availability.
// Quote QPS, latency budget, storage estimate, single point of failure.