NoSQL Databases: Picking the Right Non-Relational Tool

TL;DR: Default to Postgres. Reach for NoSQL only when you can state the specific access pattern or scale wall that forces it. DynamoDB peaked at 151 million requests per second during Prime Day 2025^[1], and Discord cut read p99 from 125 ms to 15 ms by migrating from Cassandra to ScyllaDB^[2]. These are real wins, but they required years of operational investment in query-first data modeling, tunable consistency, and denormalization. If you cannot articulate which Postgres limit you are hitting in a number, a NoSQL migration will move the problem, not solve it.

Learning Objectives#

After this module, you will be able to:

• Classify a NoSQL product into key-value, document, wide-column, or graph
• Pick the right family given access patterns, scale, and consistency needs
• Model data for DynamoDB single-table design and Cassandra query-first schemas
• Recognize when "we need NoSQL" is actually "we need an index"
• Reason about consistency guarantees (eventual, tunable, strong) per product

Intuition#

Imagine you run a massive warehouse. A SQL database is a cross-referenced library: every book has a catalog card, and you can find any book by author, title, subject, or publication year because the catalog links everything together. Powerful, but the catalog itself becomes a bottleneck when millions of people search simultaneously.

NoSQL databases are specialized storage rooms. One room has numbered lockers (key-value): hand over the number, get the contents instantly, no browsing allowed. Another room stores filing cabinets where each drawer holds a complete folder of related documents (document store): you can search inside folders, but cross-referencing between cabinets is your problem. A third room has enormous shelves sorted by date (wide-column): perfect for grabbing "everything from last Tuesday," terrible for ad-hoc questions. The last room is a corkboard with pins and strings connecting them (graph): follow any thread to find connections, but counting all the pins is slow.

Each room trades the library's universal flexibility for speed at one specific task. The engineering question is never "which room is best?" but "which room matches the way my application actually retrieves data?" Most applications retrieve data in ways the library handles fine. You only move to a specialized room when the library's catalog is provably the bottleneck.

Theory#

What NoSQL means (the four families)#

"NoSQL" is a marketing umbrella, not a technical category. It covers four product families that each rejected a different part of the relational contract.^[3][4][5] The three foundational papers, Bigtable (OSDI 2006), Dynamo (SOSP 2007), and Cassandra (LADIS 2009), all emerged within three years as reactions to the same pain: relational replication, schema changes, and joins did not scale horizontally on commodity hardware at Google, Amazon, and Facebook.^{[6][4:1][5:1]}

The four NoSQL families share a rejection of the relational model but differ fundamentally in data structure, access path, and trade-offs.

Key-value stores#

A key-value store is a hash map: opaque key to opaque value, O(1) point lookup. DynamoDB adds a sort key and optional secondary indexes on top. Redis adds typed value structures (lists, sorted sets, streams) and single-threaded command execution that gives atomic operations for free.^{[4:2][1:1][7]}

Redis benchmarks show ~180,000 ops/sec for SET without pipelining and ~1,536,000 ops/sec with pipelining (16 commands batched per round trip).^[7:1] That ~8.5x gap is the single most important Redis performance fact: throughput is RTT-bound unless you batch.

DynamoDB is the serverless extreme. You provision read/write capacity units or pay on-demand; there is no cluster to operate. During Prime Day 2025, DynamoDB sustained 151 million requests per second with single-digit millisecond p99.^[1:2][8]

When to use: Session stores, shopping carts, feature flags, caches, leaderboards. Any workload where you always know the key at query time.

Document stores#

A document store holds self-describing JSON (or BSON) documents identified by _id, with indexes on arbitrary fields. MongoDB uses WiredTiger (which defaults to B-tree storage) underneath; Firestore is layered on Spanner.^[9][10]

The promise is "no schema migrations during rapid iteration." The reality is that the schema still exists, it just lives in your application code. After a few releases, a collection holds four implicit schema versions, and new code crashes on missing fields. MongoDB's own documentation prescribes explicit schema_version fields and $jsonSchema validation.^[9:1][11]

MongoDB added multi-document ACID transactions in 4.0 (2018). However, Jepsen's 2020 analysis of MongoDB 4.2.6 found that at the strongest settings (readConcern: snapshot plus writeConcern: majority), the database still exhibited read skew and cyclic information flow.^[12] More concerning: 99.6% of MongoDB Atlas users use the default readConcern, which returns uncommitted data that can be silently rolled back on failover.^[12:1]

When to use: Content catalogs, product listings, user profiles with variable schemas, early-stage products where iteration speed matters more than reporting.

Column-family stores#

A row is identified by a partition key plus clustering columns. Rows within a partition are stored together and sorted by the clustering key. The engine is an LSM-tree: writes append to a commit log plus memtable and flush to immutable SSTables that are compacted later.^{[3:1][5:2][13]}

The critical modeling discipline is query-first schemas: you design one table per read pattern. For a chat app fetching recent messages by channel:

CREATE TABLE messages (
    channel_id  bigint,
    bucket      int,
    message_id  bigint,
    author_id   bigint,
    content     text,
    PRIMARY KEY ((channel_id, bucket), message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);

The composite partition key (channel_id, bucket) forces all rows for a channel-bucket pair onto the same replica set. The clustering column message_id DESC keeps them sorted newest-first on disk. A SELECT ... LIMIT 50 is a prefix scan of one partition, not a merge across the cluster.^[2:1][14]

Cassandra's tunable consistency lets each query name a level: ONE, QUORUM, ALL. A write at QUORUM plus a read at QUORUM with R + W > N gives read-your-write consistency within a partition.^[15][13:1]

When to use: Time-series data, write-heavy workloads, multi-region deployments, messaging at Discord/Netflix scale.

Graph databases#

Nodes and typed edges with property maps, stored so each node keeps direct pointers to its edges (index-free adjacency). A traversal of k hops costs O(d^k) with a small constant, not a join-per-hop cost. Neo4j beats relational engines on multi-hop queries and loses to them on bulk aggregate scans.^[16][17]

Meta's TAO serves over a billion reads and millions of writes per second against many petabytes of social graph data, with a high cache hit rate on the follower tier.^[18][19] TAO keeps MySQL as the source of truth and puts a graph-aware cache on top, because Facebook found that lookaside memcache did not give the right semantics for graph workloads.

When to use: Social graphs, fraud detection, knowledge graphs, recommendation path queries. Not for general OLTP.

NewSQL hybrids#

NewSQL systems expose SQL and ACID but shard and replicate like NoSQL. They are not a fifth NoSQL family; they exist for teams that want NoSQL's scale with SQL's correctness.

• Google Spanner: globally distributed, synchronously replicated via Paxos, externally consistent via TrueTime. Won the 2025 ACM SIGMOD Systems Award.^[20][21]
• CockroachDB: Raft-replicated ranges (512 MiB default max, 128 MiB default min per zone config), SQL on top, serializable isolation via HLC. Runs Jepsen nightly; in two years of nightly tests, the suite found one real inconsistency bug.^{[22][23][24][25]}
• TiDB: stateless SQL servers speaking MySQL protocol over TiKV (Raft-replicated RocksDB). HTAP via TiFlash columnar replica.^[26][27]
• Vitess: MySQL sharding middleware (not distributed SQL). Powers YouTube, Slack, Shopify, GitHub.^[28][29]

The honest trade-off: Dan McKinley's "innovation tokens" argument cuts hardest here. Distributed SQL is a decade-plus-old category with smaller community scar tissue than Postgres or MySQL.^[30]

When to pick NoSQL (and when NOT to)#

Dan McKinley's "Choose Boring Technology" (2015) argues every team has about three innovation tokens to spend on unfamiliar technology.^[30:1] If you spend one on a new language, one on a new queue, and one on a new database, you have zero left for the actual product.

The heuristic: state the scale wall in numbers before migrating. If you cannot articulate which specific number on Postgres is failing, a NoSQL migration will not help.^[31][30:2]

Common "we need NoSQL" situations that are actually "we need an index":

• A 500 ms table scan fixed by a B-tree or partial index
• A "flexible schema" need covered by Postgres JSONB with GIN indexes^[32]
• A "scale" need that disappears with connection pooling and read replicas

Instagram scaled on sharded Postgres with aggressive partial indexes. Migrations from MongoDB back to Postgres are common and rarely reversed; teams cite reporting pain, cross-entity queries, and schema drift as triggers.^[33][34][35]

Most teams asking "which NoSQL?" end on the Postgres branch. The other branches require a stateable scale or access-pattern reason.

Real-World Example#

Discord: from MongoDB to Cassandra to ScyllaDB (2015 to 2023).

Discord started on MongoDB in 2015, migrated to Cassandra in 2017 with 12 nodes and billions of messages, and by early 2022 ran 177 Cassandra nodes storing trillions of messages.^[2:2]

The Cassandra pain points were specific and measurable:

• Hot partitions. A celebrity channel would blow past per-replica concurrency and drag down cluster tail latency.
• Compaction debt. The team spent on-call time "gossip dancing" nodes out of rotation to catch up on LSM compactions.
• JVM garbage collection. GC pauses caused latency spikes requiring manual node reboots.

Read p99 ranged from 40 to 125 ms; write p99 from 5 to 70 ms.^[2:3]

In May 2022, Discord migrated to 72 ScyllaDB nodes (same CQL wire protocol, C++ implementation, shard-per-core via Seastar). The data model stayed identical: partition by (channel_id, bucket), cluster by message_id DESC. A custom Rust migrator moved data at a peak of 3.2 million messages per second over 9 days.^[2:4]

Results: read p99 dropped to 15 ms, write p99 to 5 ms. Node count fell from 177 to 72 while disk per node grew from ~4 TB to 9 TB.^[2:5][36]

The architectural key was not just the database swap. Discord built Rust "data services" with consistent-hash routing on channel_id. Each service instance holds an in-process request-coalescing layer that deduplicates concurrent reads of the same row into a single database query.^[2:6]

Discord's data model stayed the same across three database engines; the scaling wall moved each time, and the fix was always operational, not schema-level.

Trade-offs#

Common Pitfalls#

Exercise#

Design the primary datastore for a social messaging app: 1B users, 10B messages/day, messages fetched by conversation in reverse chronological order, cross-conversation search, and a 99.99% uptime SLA across three regions. Compare Cassandra, DynamoDB, and sharded Postgres. Pick one and justify.

Key Takeaways#

• Default to Postgres. Reach for NoSQL only when you can state the access pattern or scale wall in a specific number.
• The four NoSQL families (key-value, document, wide-column, graph) solve different problems. Picking the wrong family is worse than staying on SQL.
• Wide-column stores like Cassandra shine for write-heavy, time-series, multi-region workloads but are terrible at ad-hoc queries and joins.
• DynamoDB rewards disciplined single-table modeling and punishes lazy access-pattern design. It proved 89.2M req/sec at Prime Day.
• MongoDB's default settings are unsafe. Override readConcern and writeConcern to majority or accept silent data loss on failover.
• NewSQL (Spanner, CockroachDB) gives you SQL + horizontal scale, but costs an innovation token and a latency tax.
• Model for your reads, not your writes. Every NoSQL family forces this discipline; the ones that succeed embrace it early.

Further Reading#

• How Discord Stores Trillions of Messages - the best single public case study for wide-column operations at scale; covers MongoDB to Cassandra to ScyllaDB with specific latency numbers.
• Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service (USENIX ATC 2022) - the authoritative DynamoDB architecture paper; explains partitioning, adaptive capacity, and the 89.2M req/sec Prime Day result.
• Jepsen: MongoDB 4.2.6 - Kyle Kingsbury's definitive analysis of MongoDB transactional guarantees; essential reading before trusting any NoSQL consistency claim.
• Choose Boring Technology - Dan McKinley's essay on innovation tokens; the philosophical foundation for "default Postgres."
• Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007) - the paper that named the key-value family and introduced consistent hashing, vector clocks, and sloppy quorums.
• Cassandra: A Decentralized Structured Storage System (LADIS 2009) - Lakshman and Malik's short, readable paper; the source of Cassandra's design combining Dynamo's partitioning with Bigtable's data model.
• TAO: Facebook's Distributed Data Store for the Social Graph (USENIX ATC 2013) - Meta's MySQL-backed graph cache serving billions of reads per second; shows that "graph database" can mean "graph API over boring storage."
• CockroachDB's Consistency Model - explains why serializable is not linearizable in distributed SQL and the engineering tax of getting it right.

Flashcards#

DynamoDB gives cross-item ACID at 2x WCU cost via two-phase commit; Cassandra's QUORUM write gives majority durability within a single partition but no multi-partition atomicity.

References#