Distributed Storage: CAP Theorem & NoSQL Systems
CAP theorem fundamentals, the NoSQL landscape, and an architectural comparison of Bigtable (CP, wide-column) and Dynamo (AP, key-value).
Distributed storage systems must make explicit trade-offs between consistency, availability, and partition tolerance — as formalized by Brewer's CAP theorem. This section covers the two most studied systems in the DSA-AS exam: Google Bigtable (a CP wide-column store) and Amazon Dynamo (an AP key-value store).
💡 Why do we need distributed storage?
CAP Theorem
Brewer's CAP theorem (2000, formally proved by Gilbert & Lynch 2002) states that a distributed system can guarantee at most two of the three properties: Consistency, Availability, and Partition Tolerance. Since partitions are inevitable in real networks, every distributed system must choose between CP or AP.
Click a zone (CP, AP, or CA) to see which systems live there and why.
Every read receives the most recent write (or an error). All nodes see the same data at the same time. Equivalent to linearizability.
Every request receives a response (not an error), though the response may be stale. Every non-failing node must return a response.
The system continues operating despite arbitrary network partitions (messages lost or delayed between nodes). Required by all distributed systems.
Exam tip: PACELC model
CAP only addresses behavior during partitions. The PACELC model extends it: even without partitions (E), systems must trade Latency (L) for Consistency (C). Dynamo is PA/EL (available during partition, low-latency otherwise). Bigtable is PC/EC (consistent during partition, consistent otherwise).
NoSQL System Classification
NoSQL systems are classified by their data model. Each type optimizes for a different query pattern and makes different trade-offs.
Simplest model: opaque key → opaque value. Extremely fast, no schema, no range queries.
Row key + dynamic columns. Efficient for sparse data, supports range scans on row key.
JSON/BSON documents with nested structures. Supports secondary indexes and rich queries.
Nodes and edges with properties. Optimized for relationship traversal queries.
Storage Layout: Row-Oriented vs Column-Oriented
How data is physically stored on disk dramatically affects query performance. Row-oriented stores are optimized for OLTP (transactional) workloads; column-oriented (columnar) stores for OLAP (analytical) workloads.
| Property | Row-Oriented | Column-Oriented |
|---|---|---|
| Physical layout | All columns of a row stored together | All values of a column stored together |
| Examples | MySQL, PostgreSQL, Bigtable (per-tablet) | BigQuery, Redshift, Parquet, ORC |
| Read pattern | Efficient for SELECT * (all columns of few rows) | Efficient for SELECT avg(col) (one column, all rows) |
| Write pattern | Fast single-row writes (one seek) | Slow writes (update N column files) |
| Compression | Limited (heterogeneous row data) | Excellent (column values are homogeneous, similar values together) |
| OLTP suitability | Excellent | Poor |
| OLAP suitability | Poor | Excellent |
| Projection pushdown | Not applicable | Skip unneeded columns entirely (no I/O) |
💡 Bigtable's column families
Deep Dives
Explore each storage system in detail with interactive diagrams and exam questions.
Google's distributed storage system. 3-level tablet hierarchy, SSTable + memtable internals, Chubby integration, and the webtable data model.
Amazon's always-available shopping cart storage. Consistent hashing ring, vector clocks, sloppy quorum, hinted handoff, and Merkle tree anti-entropy.