Database

In system design interviews, databases are the backbone of any system you design. Every application needs to store data—users, posts, orders, messages—and the choices you make about how to store, replicate, and partition that data directly impact your system's scalability, availability, and performance.

This page covers the essential database concepts you need for interviews: understanding when to use SQL vs NoSQL, how replication ensures availability, and how partitioning enables horizontal scaling. These aren't just theoretical concepts—they're the building blocks you'll use in every system design question.

Why Databases Matter

Before diving into types and strategies, let's understand what databases provide that simple file storage cannot:

• Concurrent access — Multiple users can read and write simultaneously without corrupting data
• Data integrity — Constraints and transactions ensure data remains consistent
• Efficient querying — Indexes and query optimizers make retrieval fast
• Scalability — Replication and partitioning allow growth beyond a single machine
• Security — Access controls protect sensitive data

SQL vs NoSQL: The Fundamental Choice

The first database decision in any system design is choosing between relational (SQL) and non-relational (NoSQL) databases. This isn't about one being "better"—they're optimized for different access patterns.

Relational Databases (SQL)

Relational databases store data in tables with predefined schemas, using SQL for queries. They're the default choice for most applications because they handle complex relationships naturally and provide strong consistency guarantees.

ACID Properties

The power of relational databases comes from ACID transactions:

Databases offer different isolation levels that trade off between consistency and performance: Read Uncommitted (fastest, allows dirty reads), Read Committed (default in PostgreSQL), Repeatable Read, and Serializable (strictest, prevents all anomalies but slowest). In interviews, mentioning that you'd use Serializable for critical operations like payments shows depth.

When to use SQL:

• Data has clear relationships requiring JOINs
• You need transactions (payments, inventory, bookings)
• Query patterns are complex or evolving
• Data integrity is critical

Popular choices: PostgreSQL (feature-rich, extensible), MySQL (widely deployed, good tooling)

SQL vs NoSQL: Same query, different approaches

Fetching a user's recent orders illustrates the trade-off:

-- SQL (PostgreSQL): JOIN across normalized tables
SELECT o.id, o.total, p.name
FROM orders o
JOIN order_items oi ON o.id = oi.order_id
JOIN products p ON oi.product_id = p.id
WHERE o.user_id = 123
ORDER BY o.created_at DESC LIMIT 10;

// NoSQL (MongoDB): Single document read, data pre-joined
db.users.findOne(
  { _id: 123 },
  { orders: { $slice: -10 } }  // Last 10 orders embedded in user doc
)

SQL requires JOINs but handles complex queries flexibly. NoSQL avoids JOINs by embedding data, but you must know your access patterns upfront.

NoSQL Databases

NoSQL databases sacrifice some relational features for specific advantages: horizontal scaling, flexible schemas, or optimized access patterns. They're not "better"—they're different tools for different problems.

Key-Value Stores

Key-value stores are the simplest NoSQL type: you store and retrieve values by their keys, like a giant hash map.

SET user:123:session "abc123def456"
GET user:123:session → "abc123def456"

Use cases:

• Session storage (fast lookup by session ID)
• Caching (store computed results)
• Rate limiting (track request counts)
• Feature flags and configuration

Example: Redis is often used alongside a primary database. Your main data lives in PostgreSQL, but you cache frequently-accessed data in Redis to reduce database load.

Document Stores

Document databases store data as JSON-like documents, allowing flexible and nested structures without a fixed schema.

{
  "user_id": "123",
  "name": "Alice",
  "orders": [
    {
      "order_id": "o1",
      "items": ["item1", "item2"],
      "total": 59.99
    }
  ]
}

Use cases:

• Content management systems
• Product catalogs (variable attributes)
• User profiles with nested preferences
• Event logging

Trade-off: Great for reading entire documents, but querying across documents or updating nested fields can be complex.

Wide-Column Stores

Wide-column databases organize data into rows and column families, optimized for writing large amounts of data and reading specific columns.

Use cases:

• Time-series data (metrics, IoT sensors)
• Event logging at massive scale
• Write-heavy workloads

Example: Cassandra can handle hundreds of thousands of writes per second, making it ideal for logging systems where you're constantly appending new data.

Graph Databases

Graph databases store entities as nodes and relationships as edges, making it efficient to traverse connections.

Use cases:

• Social networks (friends-of-friends queries)
• Recommendation engines
• Fraud detection (finding suspicious patterns)
• Knowledge graphs

Example: "Find all friends of friends who also like jazz music" is a simple query in a graph database but requires complex JOINs in SQL.

Storage Engines: Under the Hood

When an interviewer asks "How does the database actually store this on disk?", they are testing your knowledge of storage engines. The two most common structures are B-Trees and LSM-Trees.

B-Trees (Read-Optimized)

B-Trees are the standard for most relational databases (PostgreSQL, MySQL). They keep data in sorted blocks of a fixed size (pages) on disk.

• How it works: A balanced tree structure where each node contains multiple keys and pointers to child nodes.
• Strengths: Fast random reads, excellent for range queries, mature and stable.
• Weaknesses: Every write may require updating multiple pages on disk, which can be slow and cause "write amplification."

LSM-Trees (Write-Optimized)

Log-Structured Merge-Trees are used by many NoSQL databases (Cassandra, LevelDB, RocksDB) to handle massive write volumes.

• How it works: Writes are first appended to a Write-Ahead Log (WAL) for durability, then added to a memory buffer (MemTable). When the buffer is full, it's flushed to disk as a sorted file (SSTable). Background processes later merge these files.
• Strengths: Extremely high write throughput, efficient use of sequential disk I/O.
• Weaknesses: Reads can be slower because they might need to check multiple SSTables. Bloom Filters are often used to skip files that definitely don't contain the key.

Summary Comparison

OLTP vs OLAP

In large-scale systems, you'll often separate your "transactional" database from your "analytical" database.

OLTP (Online Transactional Processing)

OLTP systems handle many small, frequent transactions from end-users.

• Focus: High concurrency, low latency, data integrity.
• Storage: Row-oriented (PostgreSQL, MySQL). Good for "Get user 123's latest order."
• Example: A bank's core ledger or an e-commerce order system.

OLAP (Online Analytical Processing)

OLAP systems handle complex queries over massive datasets for business intelligence.

• Focus: High throughput, complex aggregations, scanning millions of rows.
• Storage: Column-oriented (BigQuery, ClickHouse, Snowflake). Good for "What was the average order value per country last month?"
• Example: Marketing dashboard or sales trend analysis.

Why Columnar Storage for OLAP?

In a row-oriented DB, reading one column requires reading the entire row from disk. In a columnar DB, only the requested columns are read, which is much faster for analytical queries that only look at a few fields across millions of records.

Data Replication

Replication means keeping copies of your data on multiple machines. It's essential for:

• Availability — System keeps running if one machine fails
• Fault tolerance — No single point of failure
• Read scalability — Distribute read load across replicas
• Latency reduction — Serve users from geographically closer replicas

Replication Models

There are three main approaches to replication, each with different trade-offs:

Single-Leader (Primary-Secondary)

One node (the primary/leader) handles all writes, then replicates changes to secondary nodes (replicas/followers). Reads can go to any node.

How it works:

1. Client sends write to primary
2. Primary writes locally and logs the change
3. Primary sends change to all secondaries
4. Secondaries apply the change

Advantages:

• Simple to understand and implement
• No write conflicts (single source of truth)
• Secondaries can serve reads, scaling read capacity

Disadvantages:

• Primary is a bottleneck for writes
• If primary fails, need to elect a new one (failover)
• Replication lag can cause stale reads from secondaries

Use cases: Most applications with moderate write load. PostgreSQL, MySQL, and MongoDB all support this model.

Multi-Leader

Multiple nodes can accept writes, then synchronize with each other. Useful when you need writes in multiple locations.

Use cases:

• Multi-datacenter deployments (each datacenter has a leader)
• Offline-capable applications (mobile apps that sync later)
• Collaborative editing (Google Docs-style)

Challenge: Conflict resolution

When two leaders accept conflicting writes (e.g., two users edit the same document), you need a strategy:

• Last-write-wins — Use timestamps, most recent wins (risks data loss)
• Merge — Combine changes (complex, application-specific)
• Conflict-free data types (CRDTs) — Data structures designed to merge automatically

Leaderless (Peer-to-Peer)

No designated leader—any node can accept reads and writes. Nodes coordinate using quorums.

Quorum reads and writes:

With n replicas, configure:

• w = number of nodes that must acknowledge a write
• r = number of nodes you read from

If w + r > n, you're guaranteed to read at least one node with the latest value.

Example: With 3 replicas, set w=2 and r=2. Writes succeed when 2/3 nodes acknowledge. Reads query 2/3 nodes. Since 2+2 > 3, at least one node in your read set has the latest write.

Advantages:

• High availability (no single leader to fail)
• Good write throughput (writes go to multiple nodes in parallel)

Disadvantages:

• More complex consistency model
• Conflict resolution still needed for concurrent writes

Use cases: Cassandra and DynamoDB use this model for high availability at scale.

Synchronous vs Asynchronous Replication

Synchronous: Primary waits for secondaries to confirm before acknowledging the write to the client.

• Pros: All replicas always have the latest data
• Cons: Higher latency, availability depends on all replicas

Asynchronous: Primary acknowledges immediately, replicates in the background.

• Pros: Lower latency, primary availability independent of replicas
• Cons: Replicas may lag behind, data loss possible if primary fails before replicating

In practice: Most systems use semi-synchronous—one replica is synchronous (guarantees durability), others are asynchronous (for performance).

Consistency Models

Replication introduces trade-offs between consistency and availability. The main models you'll encounter:

• Strong consistency — All reads see the most recent write. Requires synchronous replication or coordination.
• Eventual consistency — Replicas converge over time, but reads may return stale data temporarily.
• Read-your-writes — You always see your own writes, even if others don't yet.

Data Partitioning (Sharding)

When your data grows beyond what a single machine can handle, you need to split it across multiple machines. This is partitioning (or sharding).

Why Partition?

• Storage capacity — More data than fits on one machine
• Write throughput — More writes than one machine can handle
• Read throughput — When replication alone isn't enough

Partitioning Strategies

Vertical Partitioning

Split tables by columns, putting different columns on different servers. This separates "hot" data (frequently accessed, small) from "cold" data (rarely accessed, large).

Example: Separate user profiles from user activity logs.

Server A (hot): users (id, name, email)        -- Small, accessed on every request
Server B (cold): user_activity (user_id, action, timestamp, details)  -- Large, accessed rarely

Use case: When you have a mix of frequently-accessed core fields and large, rarely-accessed data like logs, images, or historical records. Keeping hot data on faster storage improves performance.

Horizontal Partitioning (Sharding)

Split tables by rows, distributing rows across multiple servers based on a partition key.

Key-Range Partitioning

Assign ranges of keys to each partition.

Partition 1: user_id 1-1,000,000
Partition 2: user_id 1,000,001-2,000,000
Partition 3: user_id 2,000,001-3,000,000

Advantages:

• Range queries are efficient (find all users 1-1000)
• Data locality for related keys

Disadvantages:

• Risk of hotspots if keys aren't evenly distributed
• If one range is accessed more (new users), that partition gets overloaded

Hash-Based Partitioning

Apply a hash function to the key, use the result to determine the partition.

partition = hash(user_id) % num_partitions

Advantages:

• Even distribution of data (assuming good hash function)
• No hotspots from key patterns

Disadvantages:

• Range queries require hitting all partitions
• Adding/removing partitions requires rehashing (data movement)

Consistent Hashing

The main disadvantage of hash-based partitioning is that adding or removing nodes causes massive data movement—with hash % n, changing n means nearly all keys get reassigned.

Consistent hashing solves this by mapping both keys and nodes to positions on a circular hash ring. When you add a node, only keys adjacent to it on the ring move—typically just 1/n of the data instead of nearly all of it.

This is such an important concept that we cover it in depth on its own page: Consistent Hashing.

Handling Hotspots

Even with good partitioning, some keys might receive disproportionate traffic. For example, if a celebrity with 100M followers posts an update, all reads for that post hit a single partition—potentially overwhelming it while other partitions sit idle.

Strategies:

• Split hot partitions — Further subdivide when detected
• Add randomness — Append random suffix to hot keys, aggregate on read
• Caching — Put a cache in front of hot data

Rebalancing Partitions

As data grows or nodes change, partitions need rebalancing. The goal is to redistribute data evenly while minimizing disruption—rebalancing moves data over the network, which temporarily increases load.

Fixed number of partitions: Create many more partitions than nodes initially (e.g., 1000 partitions for 10 nodes). When adding nodes, move entire partitions. Simple and predictable. Used by Elasticsearch, Riak.

Dynamic partitioning: Split partitions when they get too large, merge when too small. Adapts to data distribution automatically. Used by HBase, MongoDB.

Proportional to nodes: Each node has a fixed number of partitions. Adding nodes splits existing partitions. Balances load as cluster grows. Used by Cassandra.

In practice, rebalancing is often triggered manually or semi-automatically to avoid surprise load spikes. Monitor partition sizes and schedule rebalancing during low-traffic periods.

Choosing the Right Database

Here's a practical decision framework for interviews:

Common Interview Patterns

Quick Reference

Database Type Comparison

Replication Model Comparison

Partitioning Strategy Comparison

Interview Checklist

When discussing databases:

• Justified SQL vs NoSQL choice
• Considered ACID requirements (transactions needed?)
• Identified primary access patterns
• Addressed read vs write heavy workload
• Mentioned replication strategy for availability
• Discussed partitioning if data is large
• Considered caching layer (Redis)
• Acknowledged trade-offs in your choices

What Interviewers Look For

1. Justified decisions — Don't just pick a database; explain why. "PostgreSQL because we need transactions for payments" beats "PostgreSQL because it's popular."

2. Understanding of trade-offs — Show you know what you're giving up. "NoSQL gives us write scaling but we lose JOINs and need to denormalize."

3. Replication awareness — Know that replication provides availability and read scaling, and understand the consistency implications.

4. Partitioning knowledge — Understand when and how to shard, and the trade-offs between strategies.

5. Practical thinking — Start simple (single PostgreSQL), scale up only when requirements demand it. Over-engineering is a red flag.

You don't need to know every database's internals. What matters is demonstrating that you can analyze requirements, choose appropriate tools, and articulate why your choices make sense for the problem at hand.