📚 Study Notes / Home / HLD / Cheat Sheet
HLD · 1-Page Cheat Sheet

High Level Design 101 — Cheat Sheet

Every scaling building block — load balancing, caching, replication, NoSQL internals & case studies — on one page for fast revision.

← Full sessions

S1 System Design Intro & Scaling

  • HLD = arrange components (servers, DBs, caches, LBs) so a system stays fast & available at scale; trade-offs over single "right" answer.
  • Vertical scaling (scale up): bigger machine — simple, no code change, but a hard ceiling + single point of failure + costly.
  • Horizontal scaling (scale out): more machines — near-infinite, fault-tolerant, but needs a load balancer & stateless servers.
  • Latency = time per request; throughput = requests/sec. Goal: low latency, high throughput.

S1 How the Internet Works

  • DNS resolves domain → IP (the phonebook); results are cached with a TTL.
  • Client → TCP handshake → HTTP(S) request → server response. TLS encrypts.
  • Client–server model; many clients hit a fleet of servers behind one entry point.
  • Single server can't serve millions → must distribute work (next sessions).

S2 Load Balancing

  • Load balancer spreads requests across servers; also does health checks & removes dead nodes.
  • Algorithms: Round Robin, Weighted RR, Least Connections, Least Response Time, IP/URL hash.
  • Stateless servers let any node handle any request; keep sessions in a shared store, not local memory.
  • LB itself must be HA → active-passive pair / DNS-level LB to avoid SPOF.

S2 Consistent Hashing

  • Plain hash(key) % N reshuffles almost everything when N changes — terrible for caches/shards.
  • Hash ring: map servers & keys onto a circle; key goes to next server clockwise.
  • Add/remove a node → only that node's neighboring keys move (≈1/N keys).
  • Virtual nodes: each server placed at many ring points → smooths uneven load & hotspots.

S3 Caching Basics

  • Cache = fast store of recent/popular answers to avoid redoing slow work (DB, compute).
  • Hierarchy: browser → CDN (edge, static assets) → app/backend cache (e.g. Redis) → DB.
  • Local cache (in-process, fast, not shared) vs distributed cache (shared, network hop, scalable).
  • Hit = found in cache; miss = fetch from source then store. Track hit ratio.
  • Cache works because of locality (80/20: few items get most traffic).

S4 Eviction Policies

  • Cache is small → must evict when full. LRU: drop least-recently-used (most common).
  • LFU: drop least-frequently-used; FIFO: drop oldest inserted.
  • TTL: each entry expires after a fixed time regardless of use.
  • LRU implemented with hashmap + doubly-linked list → O(1) get/put.

S4 Write Strategies & Consistency

  • Cache-aside (lazy): app reads cache, on miss loads DB & populates; most common.
  • Write-through: write cache+DB together — consistent, slower writes.
  • Write-back: write cache now, DB later (async) — fast but risk data loss.
  • Write-around: write straight to DB, skip cache (avoids polluting cache).
  • Invalidation: on update, delete/refresh stale keys to keep cache honest; stale data is the core risk.

S5 Caching Case Studies

  • Code Judge: cache compiled results / test verdicts to avoid re-running identical submissions.
  • Leaderboard: Redis sorted set (ZSET) — ZADD score, ZRANGE/ZREVRANK give top-N & rank in O(log n).
  • Newsfeed: fan-out on write (push to followers' feeds, fast reads) vs fan-out on read (build at request time).
  • Hybrid: fan-out on write for normal users, on read for celebrities (avoid huge write amplification).

S6 Microservices & Chat App

  • Monolith (one deployable, simple, hard to scale parts) vs microservices (independent services, scale & deploy separately, more ops complexity).
  • REST over HTTP: resources + verbs (GET/POST/PUT/DELETE), stateless.
  • HTTP (general, human-readable) vs RPC (call remote func directly, e.g. gRPC — fast, typed).
  • Blob storage (S3) for media/files; store URL in DB, not the bytes.

S7 CAP & PACELC

  • CAP: during a network Partition pick Consistency or Availability — can't have both.
  • CP (reject/stall to stay correct) vs AP (answer maybe-stale to stay up).
  • PACELC: if Partition → A or C; Else (normal) → trade Latency vs Consistency.
  • No partition is rare-but-real; most real systems tune per use case.

S7/8 Replication, Sharding & Quorums

  • Replication = copies of same data (read scale + fault tolerance); sharding = split data across nodes (write/storage scale).
  • Master–slave: one writer, many read replicas; replica lag → eventual consistency.
  • Tunable consistency: N replicas, W write acks, R read acks.
  • W + R > N ⇒ strong consistency (read sees latest write).
  • Failover promotes a replica to master if the master dies.

S9 SQL vs NoSQL & Sharding Key

  • SQL: relational, schema, joins, ACID, strong consistency — great for complex queries & transactions.
  • NoSQL: flexible schema, horizontal scale, often BASE/eventual — great for huge scale & simple access patterns.
  • Pick SQL when relationships/transactions matter; NoSQL when scale & write volume dominate.
  • Sharding key: choose high-cardinality, evenly-distributed field matching query pattern; bad key → hotspots & cross-shard queries.

S10 LSM Trees (Write Path)

  • Write-optimized engine (Cassandra, RocksDB): only append, never random-write.
  • Write → WAL (durability) + memtable (in-memory sorted structure).
  • Memtable full → flush to immutable SSTable on disk (sorted).
  • Compaction: merge SSTables, drop overwritten/deleted (tombstone) rows → reclaims space, fewer files.

S11 LSM Trees (Read Path)

  • Read checks memtable first, then SSTables newest→oldest.
  • Sparse index: in-memory index of some keys → seek near the block, then scan.
  • Bloom filter: probabilistic "is key here?" — skips SSTables that definitely lack the key (no false negatives).
  • Trade-off: writes O(1)-ish append, reads may touch many SSTables (read amplification); compaction keeps it bounded.

S12/13 Search Typeahead (Trie)

  • Trie (prefix tree): each path spells a prefix; nodes store top suggestions for that prefix.
  • Precompute & cache top-k at each node so lookup is fast on every keystroke.
  • Rank by frequency/popularity; update counts asynchronously (batch), not per query.
  • Scale: shard trie by prefix, cache hot prefixes at edge; debounce client requests.

S16 IRCTC — Concurrency & Booking

  • Core problem: double-booking the same seat under concurrent requests.
  • Fix with locking: pessimistic (SELECT … FOR UPDATE) or optimistic (version check on write).
  • Wrap seat reservation in a DB transaction (ACID) so it's all-or-nothing.
  • Ties the course together: LB + cache + sharded DB + replication + consistency choices.

S14 Messaging & Netflix Video

  • Chat: persistent WebSocket for real-time push; messages queued & stored for offline delivery; delivery/read receipts.
  • Store messages in a write-heavy NoSQL store keyed by conversation; blob storage for media.
  • Netflix: upload → transcode into many bitrates/resolutions; serve via CDN edge.
  • Adaptive bitrate streaming: client switches quality to match bandwidth.

S15 NoSQL Types

  • Key-value (Redis, DynamoDB): fast lookups, simple — caches, sessions.
  • Document (MongoDB): JSON-like docs, flexible schema — catalogs, profiles.
  • Column-family (Cassandra, HBase): wide rows, write-heavy, time-series, chat.
  • Graph (Neo4j): nodes+edges — social graphs, recommendations.
  • Choose by access pattern, not by hype.