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.
Staff depth layer
Data Storage — Staff Depth
Storage interviews reward modeling access patterns, not listing databases. Staff answers pick primary keys and sharding keys from query shapes, separate OLTP from analytics, and speak consistency (strong vs eventual) as a product requirement. Indexes, replication, and partitioning are capacity and correctness tools — you name the failure when the wrong key or engine is chosen.
Anti-patterns → say instead
✕ One database for everything
OLTP transactions, full-text search, and time-series analytics fight over the same engine and kill latency.
Say instead: Source of truth for writes; specialized stores for search, cache, warehouse — with clear sync ownership.
✕ Auto-increment as distributed ID
Single-sequence generators don't shard and become a hotspot; clock skew breaks naive time IDs.
Say instead: Snowflake-style or ULID/UUID with shard affinity; discuss coordination vs randomness tradeoffs.
✕ Shard by user_id without query map
Global feeds, admin queries, and cross-user joins become scatter-gather nightmares.
Say instead: List top queries first; choose shard key that localizes hot paths; secondary indexes or dual-write for the rest.
✕ Ignoring replication lag
Read-your-writes fails after create if clients hit lagging replicas; interviewers probe sticky sessions and causal consistency.
Say instead: Route post-write reads to primary or use session tokens / version watermarks until replica catches up.
100M users, 10k write QPS to posts, read fanout later. Need durable writes, partition by author for write locality.
- Shard key = author_id hash → N shards; each write hits one shard.
- Estimate: 10k QPS / 64 shards ≈ 156 QPS/shard avg; size for 5× hotspot on celebrities.
- Secondary index by post_id: either encode shard in ID or maintain ID→shard lookup.
- Analytics: CDC → Kafka → warehouse; never run heavy aggregates on OLTP shards.
- Migrations: consistent hashing or range + orphan cleanup plan for resharding.
- 10k writes/sec × 1 KB ≈ 10 MB/s durable write bandwidth
- Celebrity hotspot: one shard may see 10–50× average — isolate VIP shards or queue
- Replica lag SLO: p95 < 100ms for read-your-writes path
Shard key follows the write/locality pattern; cross-shard queries are an explicit product cost you call out.
Cheat sheet
- Access pattern → schema → engine
- PK/SK: localize hot queries
- Replication: sync vs async; lag SLO
- Partitioning: hash/range/directory
- Indexes: write cost vs read benefit
- OLTP vs OLAP separation via CDC
- Bloom filters / LSM vs B-tree when relevant