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 type | Examples | Best for |
|---|---|---|
| Relational | PostgreSQL, MySQL | ACID transactions, complex relations, reporting |
| Document | MongoDB, DynamoDB | Flexible records, nested JSON, key lookups |
| Wide-column | Cassandra, HBase | Massive write scale, time-series, append-heavy |
| Key-value | Redis, Memcached, DynamoDB | Cache, sessions, simple lookups |
| Graph | Neo4j, Neptune | Social graphs, fraud rings, recommendations |
| Search | Elasticsearch, OpenSearch | Full-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 form | Rule | Example violation |
|---|---|---|
| 1NF | Atomic columns, no repeating groups | Multiple phone numbers in one cell |
| 2NF | No partial dependency on composite key | Product name stored per order line + product ID |
| 3NF | No transitive dependency | Store city + zip when zip determines city |
| BCNF | Every determinant is a candidate key | Rare edge cases in 3NF |
- Identify entities (User, Order, Product) and relationships (1:N, N:M)
- Define primary keys — prefer surrogate keys (UUID, bigint) over natural keys
- Model junction tables for many-to-many (user_roles, order_items)
- 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.
| Technique | Mechanism | Consistency |
|---|---|---|
| Materialized view | DB-maintained snapshot of a query | Refresh on schedule or trigger |
| Fan-out on write | Push post to each follower's feed table | Eventual; write amplification |
| Fan-out on read | Merge posts from followed users at read time | Stronger freshness; slow for celebrities |
| Hybrid fan-out | Fan-out for normal users; merge for celebrities | Twitter-style approach |
| Event sourcing + projections | Rebuild read models from event log | Replay 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.
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.
| Topology | Write path | Tradeoff |
|---|---|---|
| Single-leader | All writes → primary; replicas async/sync | Simple; primary is bottleneck & SPOF without failover |
| Multi-leader | Writes accepted at multiple nodes | Write availability; conflict resolution required |
| Leaderless (quorum) | Write to W of N; read from R of N | R + W > N for strong reads; tunable consistency |
| Chain replication | Primary → secondary → tertiary | Ordered 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 type | Structure | Best for |
|---|---|---|
| B-tree | Balanced tree, sorted | Range queries, equality, ORDER BY |
| Hash | Hash table | Exact equality only; no range scans |
| Composite | Multiple columns, left-prefix rule | Multi-column WHERE clauses |
| Covering | Includes all SELECT columns | Index-only scan; no table lookup |
| Partial | Subset of rows (WHERE condition) | Smaller index for filtered queries |
| GIN/GiST | Inverted / generalized search | Full-text, JSON, geospatial |
- EXPLAIN ANALYZE the slow query — look for Seq Scan on large tables
- Index columns in order of selectivity and query filter order
- Avoid SELECT * when a covering index could serve the query
- 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 family | Write path | Read path | Examples |
|---|---|---|---|
| B-tree (update-in-place) | Find page, update | Few disk seeks | InnoDB, PostgreSQL |
| LSM-tree (log-structured) | Append to memtable → flush SSTables | Merge multiple levels; bloom filters help | RocksDB, Cassandra, HBase |
| Columnar | Batch column writes | Scan columns only | Parquet, ClickHouse, Redshift |
| In-memory | RAM-resident structures | Microsecond latency | Redis, 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.