System Design Data Storage and Databases Syllabus

What is a key-value store and its core operations?

The simplest NoSQL model: an associative map of unique keys to opaque values, supporting $O(1)$ average get(key), put(key, value), and delete(key). Examples: Redis, DynamoDB, Riak.

What data model does a document store use and how does it differ from key-value?

It stores semi-structured documents (JSON/BSON/XML) whose fields can be indexed and queried, unlike opaque key-value blobs. Examples: MongoDB, CouchDB.

Describe the wide-column store data model.

Data is stored in tables of rows keyed by a row key, where each row can have different columns grouped into column families; optimized for large-scale writes and sparse data. Examples: Cassandra, HBase, Bigtable.

What problem are graph databases optimized for, and what are their core primitives?

They model highly connected data using nodes (entities) and edges (relationships with properties), enabling efficient traversal of relationships (e.g., social graphs) that would require many costly joins in SQL. Examples: Neo4j, Amazon Neptune.

What does the BASE acronym stand for?

Basically Available, Soft state, Eventual consistency. It is the availability-favoring counterpart to ACID common in NoSQL systems.

Contrast the consistency philosophy of ACID versus BASE.

ACID enforces strong, immediate consistency and isolation (favoring correctness). BASE relaxes consistency to eventual, prioritizing availability and partition tolerance and scaling.

State the CAP theorem.

A distributed data store can simultaneously guarantee at most two of: Consistency, Availability, and Partition tolerance. Under a network partition you must choose between C and A.

What is database replication and its two primary goals?

Maintaining copies of data on multiple nodes. Goals: high availability/fault tolerance (survive node failure) and read scalability (spread reads across replicas).

Contrast synchronous versus asynchronous replication.

Synchronous replication waits for replicas to acknowledge before committing (strong consistency, higher latency). Asynchronous commits on the primary first and propagates later (lower latency, risk of data loss / stale replicas).

Compare single-leader (master-slave) and multi-leader replication.

Single-leader: one primary accepts writes, replicas are read-only copies; simple, no write conflicts. Multi-leader: multiple nodes accept writes; higher write availability but requires conflict resolution.

What is the difference between horizontal partitioning (sharding) and vertical partitioning?

Horizontal partitioning splits rows across shards by a shard key. Vertical partitioning splits columns/tables across servers by feature or access pattern.

What is a shard key and why is its choice critical?

The attribute used to route a row to a shard. A poor key causes hotspots and uneven load; a good key distributes data and queries evenly and avoids cross-shard operations.

Compare range-based versus hash-based sharding.

Range sharding assigns contiguous key ranges to shards (good for range scans, risks hotspots on sequential keys). Hash sharding applies a hash to the key for uniform distribution (even load, but range queries hit all shards).

What is consistent hashing and what problem does it solve in sharding?

A hashing scheme mapping keys and nodes onto a ring so that adding/removing a node remaps only about $\frac{1}{n}$ of keys instead of nearly all, minimizing reshuffling. Virtual nodes improve balance.

What is database federation?

Splitting databases by function/feature (e.g., separate DBs for users, products, orders) so each handles its own read/write load, reducing contention and replication lag on any single database.

What is denormalization and when is it used?

Deliberately adding redundant/duplicated data (e.g., precomputed joins or aggregates) to avoid expensive joins and speed reads, at the cost of extra storage and the need to keep copies in sync on writes.

What are read replicas and what scaling problem do they address?

Read-only copies of a primary database that serve read queries, offloading the primary to scale read-heavy workloads. They do not scale writes and may return slightly stale data due to replication lag.

Why is scaling writes harder than scaling reads, and what technique addresses it?

All writes must reach the authoritative copy, so replicas cannot absorb them. Write scaling requires sharding/partitioning to split write load across independent primaries.

What is replication lag and one consequence for application design?

The delay between a write on the primary and its appearance on a replica. It can cause read-your-writes inconsistency, so apps may route a user's reads to the primary or use monotonic-read techniques.

What is an LSM Tree (Log-Structured Merge Tree)?

A write-optimized structure that buffers writes in an in-memory memtable, flushes them as immutable sorted files (SSTables) to disk, and periodically merges (compacts) them. Used by Cassandra, RocksDB, LevelDB.

What is an SSTable?

A Sorted String Table: an immutable on-disk file storing key-value pairs sorted by key, enabling efficient sequential writes, merges, and binary-search/index lookups. It is the persistent unit of an LSM tree.

In an LSM tree, what is compaction and why is it needed?

A background process that merges multiple SSTables, discarding overwritten and deleted (tombstoned) entries, to reclaim space, keep read amplification bounded, and maintain sorted order.

Compare the write and read characteristics of LSM trees versus B-Tree storage engines.

LSM trees favor writes (sequential appends, high write throughput, higher read/space amplification). B-Trees favor reads and do in-place updates (random writes, lower read amplification, better for read-heavy/range workloads).

What is write amplification and why does it matter for storage engines?

The ratio of bytes physically written to disk versus bytes of logical data written by the application. High write amplification (from B-Tree page rewrites or LSM compaction) wears out SSDs and consumes I/O bandwidth.

What is Write-Ahead Logging (WAL) and the rule it enforces?

A durability technique where every change is appended to a sequential log on stable storage before the change is applied to the main data files. The rule: log the intent before mutating data, so crashes can be recovered by replaying the log.

How does WAL support Atomicity and Durability?

Durability: committed changes are safely in the log even if data pages are not yet flushed. Atomicity: on recovery, committed transactions are redone and uncommitted ones are undone/ignored, ensuring all-or-nothing effects.

What is a Bloom filter and what does it answer?

A space-efficient probabilistic bit-array structure that answers set membership. It can return false positives but never false negatives: 'possibly in set' or 'definitely not in set'.

For a Bloom filter with $m$ bits, $n$ elements, and $k$ hash functions, what is the approximate false-positive probability?

$$p \approx \left(1 - e^{-kn/m}\right)^{k}$$ and the optimal number of hash functions is $k = \frac{m}{n}\ln 2$.

How do LSM-tree databases use Bloom filters to speed reads?

Each SSTable has a Bloom filter; before reading a file for a key, the engine checks its filter and skips the disk read entirely if the filter says the key is definitely absent, cutting read amplification.

What is a time-series database optimized for, and name two examples?

Storing and querying timestamped data points (metrics, sensor readings) with high write throughput, time-range queries, downsampling, and retention/rollup policies. Examples: InfluxDB, Prometheus, TimescaleDB.

Why do time-series databases favor append-heavy, time-partitioned storage?

Time-series workloads are write-mostly with immutable, chronologically ordered inserts and queries over recent time windows; partitioning by time enables efficient appends, compression of similar values, and cheap dropping of expired partitions.