Databases — NoSQL Overview: CAP Theorem, Eventual Consistency, and When to Use What

Why NoSQL?

Relational databases have powered applications for decades. But at scale, they hit real walls:

• Schema rigidity — Every schema change requires ALTER TABLE, which can lock production tables for hours. Companies like Meta (Facebook) learned this the hard way when running MySQL at billions of rows.
• Horizontal scaling is hard — SQL databases are designed to scale vertically (bigger machine). Sharding a relational database requires significant application-level logic.
• One-size-fits-all data model — Not all data fits neatly into rows and columns. Social graphs, event streams, and hierarchical configs need different abstractions.

NoSQL emerged as a response to these challenges. Companies like Netflix, Uber, and Discord adopted NoSQL databases to handle massive scale, flexible schemas, and specific access patterns.

---

Four Types of NoSQL Databases

NoSQL isn't one thing. It's a category of databases that trade off the relational model for different strengths.

1. Key-Value Stores

The simplest NoSQL model. Every item is stored as a key and its associated value — like a giant hash map.

When to use:

• Caching (Redis is the gold standard — see Discord's caching strategy)
• Session storage
• Rate limiting counters
• Leaderboards

Trade-offs:

• Blazingly fast O(1) reads/writes
• No complex queries — you can only look up by key
• No relationships between items

2. Document Stores

Documents are stored as JSON, BSON, or similar formats. Unlike key-value stores, the database understands the structure inside each document and can query by fields within it.

When to use:

• Content management systems
• User profiles with varying attributes
• Rapid prototyping (schema-less by default)
• When your application naturally works with JSON

Trade-offs:

• Flexible schema — each document can have different fields
• Rich query support (unlike key-value stores)
• Can be harder to maintain data consistency across documents

3. Column-Family / Wide-Column Stores

Instead of storing data row-by-row, wide-column stores organize data by columns. Each row can have a different set of columns, and columns are grouped into "column families."

Row Key: "user:42" ┌─────────────────────┬──────────────────────────┐ │ Column Family │ Columns │ ├─────────────────────┼──────────────────────────┤ │ profile │ name=Alice │ │ │ email=alice@example.com │ │ │ age=30 │ ├─────────────────────┼──────────────────────────┤ │ activity │ login:ts=1700000000 │ │ │ login:ip=192.168.1.1 │ │ │ purchase:ts=1700000100 │ │ │ purchase:item=book │ └─────────────────────┴──────────────────────────┘

When to use:

• Massive datasets (petabytes)
• Write-heavy workloads (Cassandra handles millions of writes/sec)
• Time-series data (IoT, monitoring, logging)
• When you need to scale across multiple data centers

Trade-offs:

• Excellent write performance (log-structured merge trees)
• Naturally distributed across nodes
• Queries are limited — you typically query by partition key
• Eventual consistency by default (more on this below)

4. Graph Databases

Graph databases store data as nodes (entities), edges (relationships), and properties (attributes on both). They're optimized for traversing relationships.

When to use:

• Social networks (friend recommendations)
• Fraud detection (finding circular transactions)
• Recommendation engines ("people who bought X also bought Y")
• Knowledge graphs and semantic data

Trade-offs:

• Traversing relationships is O(1) — much faster than SQL JOINs for deep queries
• Not great for bulk analytics (aggregate over millions of rows)
• Specialized — use when relationships are the primary query pattern

---

The CAP Theorem

The CAP Theorem is the most important concept to understand when choosing a distributed database. It states that in a distributed system, you can only guarantee two of the three properties simultaneously.

CAP in Practice

CP Systems (Consistency + Partition Tolerance):

• When a partition occurs, the system blocks writes to the unavailable partition
• You'll get an error if you try to write to a downed node
• Example: MongoDB with replica sets — if the primary goes down, writes pause until a new primary is elected

AP Systems (Availability + Partition Tolerance):

• When a partition occurs, the system accepts writes on all nodes
• Different nodes may have different data temporarily
• Example: Cassandra — writes succeed on any node, and data replicates in the background

---

Consistency Models

"Eventual consistency" is a phrase you'll hear often. But it's just one point on a spectrum of consistency models.

Strong Consistency

• Every read sees the latest write
• Example: PostgreSQL, MySQL — a single-node RDBMS is strongly consistent by default
• Distributed example: Google Spanner uses TrueTime (atomic clocks + GPS) to achieve strong consistency globally. Read the Spanner paper for the full story.

Eventual Consistency

• Writes propagate asynchronously
• After some time (milliseconds to seconds), all nodes converge
• Example: DynamoDB, Cassandra, Riak
• How Discord uses it: Discord's architecture relies on Cassandra's eventual consistency to handle billions of messages with high write throughput.

Tunable Consistency

Some databases let you choose the consistency level per query:

Cassandra example: ONE — Only one replica must acknowledge (fast, least consistent) QUORUM — Majority of replicas must acknowledge (balanced) ALL — All replicas must acknowledge (slow, most consistent)

---

When to Use NoSQL vs SQL

Decision Framework

Summary Comparison

Real-World Patterns

Most production systems use polyglot persistence — multiple database types for different workloads:

• Uber: PostgreSQL for core data + Cassandra for trip history + Redis for real-time matching
• Netflix: PostgreSQL for billing/accounts + Cassandra for viewing history and recommendations + DynamoDB for metadata
• Discord: PostgreSQL for core data + Cassandra for messages + Redis for presence and caching

---

What to Remember for Interviews

1. Four NoSQL types — Key-value (Redis), Document (MongoDB), Wide-column (Cassandra), Graph (Neo4j)
2. CAP Theorem — In distributed systems, P is given; choose CP or AP
3. Consistency spectrum — Strong > Sequential > Causal > Eventual
4. Tunable consistency — Cassandra and DynamoDB let you pick per-query
5. Polyglot persistence — Real systems use multiple databases for different needs
6. Default choice — SQL unless you have a specific reason for NoSQL