Skip to main content
HS
HiSETSuccess
LeetCode Prep

System Design

Comprehensive interview guide: scalability, databases, distributed systems, cloud architecture, and full case-study walkthroughs — plus adaptive quizzes.

Chapter

Data Storage & Scaling

Choosing stores, modeling for access patterns, sharding, replication, and indexing.

SQL vs NoSQL

Pick the database by access pattern, not hype. Relational DBs excel at joins, transactions, and ad-hoc queries with strong schema enforcement. NoSQL stores trade some query flexibility for horizontal scale, flexible schema, or specialized data models.

Store typeExamplesBest for
RelationalPostgreSQL, MySQLACID transactions, complex relations, reporting
DocumentMongoDB, DynamoDBFlexible records, nested JSON, key lookups
Wide-columnCassandra, HBaseMassive write scale, time-series, append-heavy
Key-valueRedis, Memcached, DynamoDBCache, sessions, simple lookups
GraphNeo4j, NeptuneSocial graphs, fraud rings, recommendations
SearchElasticsearch, OpenSearchFull-text search, log analytics, faceted browse
  • SQL when you need multi-row transactions, foreign keys, or complex joins
  • NoSQL when access is key-based, write volume exceeds single-node SQL, or schema evolves rapidly
  • Polyglot persistence: different services use different stores for their domain
  • Managed services (RDS, Aurora, DynamoDB) reduce ops burden at scale

Decision framework

State read/write ratio, consistency needs, query patterns, and expected data size. Then pick — don't name five databases. 'PostgreSQL for transactional core + Redis cache + Elasticsearch for search' is a strong answer.

Data Modeling & Normalization

Normalization reduces redundancy by splitting data into related tables (1NF → 3NF). Each fact lives in one place, updates stay consistent, and storage is efficient. The cost is joins at read time — acceptable for OLTP with moderate read complexity.

Normal formRuleExample violation
1NFAtomic columns, no repeating groupsMultiple phone numbers in one cell
2NFNo partial dependency on composite keyProduct name stored per order line + product ID
3NFNo transitive dependencyStore city + zip when zip determines city
BCNFEvery determinant is a candidate keyRare edge cases in 3NF
  1. Identify entities (User, Order, Product) and relationships (1:N, N:M)
  2. Define primary keys — prefer surrogate keys (UUID, bigint) over natural keys
  3. Model junction tables for many-to-many (user_roles, order_items)
  4. Add constraints: NOT NULL, UNIQUE, FK with ON DELETE policy

Access-pattern-first modeling

In interviews, list the top 3 queries before drawing tables. 'Get user's feed' or 'Get order by ID' drives schema more than textbook normalization alone.

Denormalization & Read Models

Denormalization intentionally duplicates data to optimize reads. Read models (projections, materialized views, CQRS read side) precompute query results so hot paths avoid joins and aggregations at request time.

TechniqueMechanismConsistency
Materialized viewDB-maintained snapshot of a queryRefresh on schedule or trigger
Fan-out on writePush post to each follower's feed tableEventual; write amplification
Fan-out on readMerge posts from followed users at read timeStronger freshness; slow for celebrities
Hybrid fan-outFan-out for normal users; merge for celebritiesTwitter-style approach
Event sourcing + projectionsRebuild read models from event logReplay for new views
  • Accept duplicated fields (user_name on every comment) to avoid join
  • Use change data capture (CDC) to sync read replicas and search indexes
  • Version read models so you can migrate schema without downtime
  • Document staleness SLA: 'feed may lag 30 seconds behind post'

When to denormalize

When reads dominate (100:1), joins are expensive, or p99 latency SLO can't tolerate multi-table queries. Always mention the write-path cost and invalidation strategy.

Sharding & Partitioning

Partitioning splits data across nodes when one machine can't hold or serve it. Sharding is horizontal partitioning across independent database instances. The shard key determines data locality and query routing — a bad key creates hot shards and negates scale benefits.

StrategyHow it worksRisk
Hash-basedshard = hash(key) mod NResharding costly when N changes; use consistent hashing
Range-basedKeys A-M on shard 1, N-Z on shard 2Hot spots on recent ranges (timestamps)
Directory / lookupRouting table maps key → shardLookup service is critical path
GeographicEU users on EU shardsCross-region queries need federation
Hash-based sharding
user_id → hash(user_id) mod N → Shard k

Shard-0   Shard-1   Shard-2
  │         │         │
Repl-A    Repl-B    Repl-C  (read replicas)
  • Shard key must be high-cardinality and evenly distributed
  • Avoid monotonically increasing keys (auto-increment ID) on range shards
  • Cross-shard queries (aggregations, joins) require scatter-gather — expensive
  • Re-sharding: consistent hashing, virtual nodes, or dual-write migration

Hot shard problem

Celebrity user or viral product concentrates traffic on one shard. Mitigate with sub-sharding, key splitting, or caching hot entities separately.

Replication Strategies

Replication copies data across nodes for availability, durability, and read scale. The replication topology and sync mode determine consistency guarantees, failover behavior, and write latency.

TopologyWrite pathTradeoff
Single-leaderAll writes → primary; replicas async/syncSimple; primary is bottleneck & SPOF without failover
Multi-leaderWrites accepted at multiple nodesWrite availability; conflict resolution required
Leaderless (quorum)Write to W of N; read from R of NR + W > N for strong reads; tunable consistency
Chain replicationPrimary → secondary → tertiaryOrdered durability; higher write latency
  • Synchronous replication: zero data loss on failover; higher write latency
  • Asynchronous replication: lower latency; possible data loss on primary crash
  • Read replicas offload read traffic; replication lag causes stale reads
  • Automatic failover with Raft/Paxos or managed service (Aurora, Cloud SQL HA)

Quorum math

N=3 replicas, W=2, R=2 → strong consistency (R+W>N). W=1, R=1 → fast but stale reads possible. Dynamo/Cassandra use this model with tunable CL.

Indexing & Query Tuning

Indexes are auxiliary data structures (B-tree, hash, GiST, inverted) that accelerate lookups at the cost of write overhead and storage. Query tuning aligns indexes, query shape, and execution plans with actual access patterns.

Index typeStructureBest for
B-treeBalanced tree, sortedRange queries, equality, ORDER BY
HashHash tableExact equality only; no range scans
CompositeMultiple columns, left-prefix ruleMulti-column WHERE clauses
CoveringIncludes all SELECT columnsIndex-only scan; no table lookup
PartialSubset of rows (WHERE condition)Smaller index for filtered queries
GIN/GiSTInverted / generalized searchFull-text, JSON, geospatial
  1. EXPLAIN ANALYZE the slow query — look for Seq Scan on large tables
  2. Index columns in order of selectivity and query filter order
  3. Avoid SELECT * when a covering index could serve the query
  4. Don't over-index write-heavy tables — each index adds insert/update cost

N+1 query problem

ORM loads parent then N children in separate queries. Fix with JOIN, batch IN clause, or DataLoader pattern. Mention in any API design deep dive.

Storage Engines Overview

Storage engines determine how data is written, stored, and read on disk. B-tree (PostgreSQL, MySQL InnoDB) optimizes in-place updates with read-optimized pages. LSM-tree (RocksDB, Cassandra, LevelDB) batches writes into sorted runs, excelling at write-heavy workloads.

Engine familyWrite pathRead pathExamples
B-tree (update-in-place)Find page, updateFew disk seeksInnoDB, PostgreSQL
LSM-tree (log-structured)Append to memtable → flush SSTablesMerge multiple levels; bloom filters helpRocksDB, Cassandra, HBase
ColumnarBatch column writesScan columns onlyParquet, ClickHouse, Redshift
In-memoryRAM-resident structuresMicrosecond latencyRedis, MemSQL
  • WAL (Write-Ahead Log): durability before in-memory apply
  • Compaction in LSM merges SSTables — I/O spikes during compaction
  • Bloom filters reduce disk reads for non-existent keys in LSM
  • Page cache / buffer pool keeps hot B-tree pages in memory

Why this matters

When asked 'why Cassandra for writes?', say LSM append-only writes vs B-tree random I/O. When asked 'why Postgres?', say ACID + rich queries + B-tree index versatility.