NoSQL Landscape — KV, Document, Column, Graph

Why this session exists

“NoSQL” is an umbrella, not a transaction or performance contract. Key-value, document, wide-column and graph describe different ways to organize access; products often span families. The goal is to explain all four, model Cassandra queries, reason about graph traversal, and defend a store choice using workload and correctness requirements rather than “ten million users.”

The practical questions are: which reads/writes and peak rates, what working set and growth, and what latency/atomicity/availability contract? Add operational expertise and measured behavior of the existing system. Those questions may justify keeping PostgreSQL, adding a specialized projection, or changing the primary store. There is no universal requirement to exhaust vertical scaling and sharding before selecting a different model.

Prerequisites

Transactions supplies the vocabulary for scope and isolation; query planning supplies the habit of measuring a concrete access path. Do not assume that a nonrelational product necessarily relaxes every ACID property.

Four different kinds of storage rooms

A key-value store resembles lockers addressed by key; a document store resembles searchable folders; a wide-column store resembles partitioned, sorted drawers; a property graph resembles named objects connected by typed links. The analogies identify convenient access, not absolute prohibitions.

• Key-value: Redis supports strings, hashes, lists, sets, sorted sets and more, not just opaque blobs. Memcached is a cache; DynamoDB supports keyed items, indexes and transactions with its own scope. Fast in-memory lookup does not establish a latency at any scale. Command complexity, payload size, network, persistence and contention matter.
• Document: MongoDB groups related fields and arrays in BSON documents and can index/query nested data. Embedding can make an aggregate convenient to read atomically, but unbounded arrays and duplicated attributes create update and growth costs. MongoDB supports schema validation, $lookup joins and multi-document transactions; “document means no schema/joins/transactions” is false.
• Wide-column: Cassandra groups rows by a partition key and orders them by clustering columns. HBase and Bigtable have related sparse-map models, not identical APIs. Cassandra's query-first modeling favors known keyed reads and replicated writes. This is not analytical columnar storage: analytical column stores group values by column for scans; Cassandra organizes access around partitions.
• Graph: Neo4j models nodes, typed relationships and properties. Adjacency-oriented traversal and Cypher can make relationship-heavy questions natural. Traversal still explores edges and produces paths: high degree, cycles and unrestricted depth can make it expensive. Relational adjacency tables with indexes and recursive CTEs can be appropriate too.

The trade you're making, per family

A narrow key API can simplify predictable access but secondary questions need an index or projection. Document embedding reduces some joins but duplicates shared attributes and needs migration/version rules. Cassandra denormalization avoids unsupported joins on the read path but adds write amplification and reconciliation. Graph traversal helps express connectivity but distributed cuts and path explosion remain costs. Relational designs support constraints and flexible joins, and can use replication, partitioning or distributed extensions; “relational means one box” is not a model definition.

Do not turn “schemaless” into the opposite myth that enforcement is impossible. MongoDB 8.0 validation can reject documents that violate configured rules. Validation does not automatically migrate old documents or determine whether missing email means unknown, withheld or absent. Define a version, allowed fields and meaning of null/missing at the data boundary.

Historical context

The original timeline incorrectly dated the Bigtable paper to 2003; the published Google Bigtable paper is OSDI 2006. Amazon's Dynamo paper is SOSP 2007 and describes a particular availability-oriented key-value design, not all later key-value products. PostgreSQL 15 did not introduce JSONB: it appeared in 9.4. Redis, MongoDB, Cassandra and graph systems subsequently expanded capabilities, which is why product/version documentation outranks an old four-box slide. Neither “NoSQL won” nor “Postgres killed 70% of NoSQL” is a supported historical metric.

Matching stored shape to access pattern

A session lookup starts at a known key, a product filter needs an indexed predicate, recent chat messages need a partition plus ordering, and friends-of-friends follows edges. This predicts physical work more usefully than the size of the user table. A global count of yesterday's events cannot be answered by one user partition unless a separate aggregate/index explicitly materializes that question.

Cassandra data modelling: query-first, not entity-first

Start with “latest twenty messages in a chat” and “latest messages from Alice.” A single entity-normalized message table does not optimize both automatically. A Cassandra 5.0 reference design uses separate bounded query tables:

CREATE TABLE demo.messages_by_chat_day (
  chat_id uuid, day date, sent_at timestamp, message_id uuid,
  sender text, body text,
  PRIMARY KEY ((chat_id, day), sent_at, message_id)
) WITH CLUSTERING ORDER BY (sent_at DESC, message_id DESC);
CREATE TABLE demo.messages_by_sender_day (
  sender text, day date, sent_at timestamp, message_id uuid,
  chat_id uuid, body text,
  PRIMARY KEY ((sender, day), sent_at, message_id)
) WITH CLUSTERING ORDER BY (sent_at DESC, message_id DESC);
SELECT sent_at, message_id, sender, body
FROM demo.messages_by_chat_day
WHERE chat_id=00000000-0000-0000-0000-000000000001
  AND day='2024-08-10' LIMIT 20;

This is CQL reference syntax, not executed SQLite. Assume a separately provisioned demo keyspace and replication policy. (chat_id, day) determines a partition, which is placed on a replica set, not only one node. The clustering columns define order within it. message_id breaks equal-timestamp collisions: a primary key consisting only of chat and timestamp would overwrite a different message at the same timestamp. Use the same stable ID when writing both projections and retrying.

A day bucket bounds time span, not bytes under arbitrary traffic; choose bucket width from volume and retention, monitor hot partitions, and query older buckets until enough messages are found. A multi-bucket latest-N read needs a merge/order policy. Neither “100MB is a hard universal limit” nor “one partition means one network hop” follows from this design.

The sender table is the complete answer to the original extension exercise. Write Alice's event to both tables with identical event identity, time and payload. An interrupted dual write can leave one table missing the event; a durable source/outbox and repair process must reapply it. Denormalization does not make the two tables transactionally synchronized. Cassandra supports indexing options including SAI in 5.0, so “one table per query” is a modeling heuristic, not a prohibition on any secondary index. Compare selectivity and fan-out before choosing an index instead.

Schema migration, CAP and PACELC from first principles

Consider v1 documents with name only, v2 with top-level email and v3 with profile.email. A reader supporting all three must specify precedence and types. Checking only if 'profile' in doc fails when profile is null or a list. The runnable lab below deliberately rejects those shapes and distinguishes missing from invalid.

Now imagine two replicas separated by a network partition. A completed write is visible to the reachable side; an isolated side cannot learn it immediately. If both sides must answer every request, a read can violate linearizability. Preserving linearizability may require delaying or rejecting some operations. CAP's C is linearizability and A is every request to a nonfailed node eventually receiving a response; these are not ACID's C or a 99.9% uptime SLA. A majority side can continue while another side blocks. Replication is one resilience technique, not the only way to distribute all reads; sharding partitions disjoint data.

PACELC adds the normal-operation latency/consistency tradeoff. R+W>N establishes quorum overlap only under assumptions about replica sets; it alone does not establish linearizability with concurrent writes, version resolution and failures. Eventual consistency promises convergence under the system's delivery/repair assumptions if updates cease, not a few hundred milliseconds of maximum staleness. Ask for read-your-writes, conflict handling and an explicit staleness bound if needed.

Consistency belongs to an operation, not a family label

For a customer who updates an address and immediately opens checkout, specify read-your-writes as well as the query shape. MongoDB 8.0 documents all four causal guarantees with durability for operations in a causally consistent session using majority read concern and majority write concern. Those settings do not turn separate calls into a multi-document atomic transaction or promise every other client's latest value. If checkout must atomically update several documents, the transaction boundary is a separate design choice [Mongo causal].

DynamoDB's currently captured documentation distinguishes the access path: tables and local secondary indexes support optional strongly consistent reads; global secondary indexes and streams do not. Thus a successful item write followed by a GSI query can omit the new item. ConsistentRead=true is not a universal switch you can attach to any index query. Global-table guarantees additionally depend on MREC versus MRSC mode; do not extrapolate a single-region API rule to a cross-region deployment [DynamoDB reads].

Cassandra's 5.0 documentation distinguishes ordinary eventually consistent writes from Paxos-based lightweight compare-and-set transactions. Read/write consistency levels and LWT serial consistency settings belong to the concrete operation and replica topology, not the word “wide-column.” Neither a replica-acknowledgment count nor two independent INSERTs makes the chat and sender projections a general cross-table isolated transaction. A logged batch has its own eventual-completion guarantee, which is not a promise that all concurrent readers see every table at once. The saved 5.0 documentation pages display a prerelease banner; this is a documentation-qualified teaching contract, not a claim that a specific deployed patch was tested [Cassandra guarantees].

Choosing among optimization, sharding and specialization

Keep/optimize relational: use measured query/index fixes, pooling, batching and JSONB when those meet the contract with familiar operations. JSONB retains relational joins and transactions around flexible data, but it is not “90% of MongoDB” by a meaningful metric.

Shard relational: choose a tenant-like key when most operations stay within it. Cross-shard transactions/queries and rebalancing depend on the selected platform, not an absolute rule that the application must implement all of them. Growth is limited by hot shards and shared dependencies, not automatically linear.

Use a specialized store: justify it with stable locality, graph semantics, document atomicity, managed scaling or other concrete requirements. Verify constraints, backup/restore, deletion, replication and transaction scope for that product/version. Polyglot persistence adds data synchronization and incident domains; CDC is one way to feed a projection, not a free consistency guarantee.

Hands-on: four access models with exact answers

The bounded Python 3 lab executes data-shape and access algorithms without running Redis, MongoDB, Cassandra or Neo4j. It preserves the four original tasks—session/counter/TTL, same-element document filtering, ordered messages and two-hop traversal—and adds negative controls. Its outputs establish semantics of this code, not service latency or compatibility.

from collections import defaultdict
 
class KV:
    def __init__(self):
        self.values, self.expires = {}, {}
    def set(self, key, value):
        self.values[key] = value
        self.expires.pop(key, None)
    def get(self, key, now):
        if now >= self.expires.get(key, float("inf")):
            self.values.pop(key, None)
            self.expires.pop(key, None)
        return self.values.get(key)
    def expire(self, key, seconds, now):
        if key not in self.values:
            return False
        self.expires[key] = now + seconds
        return True
 
kv = KV()
kv.set("session:abc", {"user_id":42})
assert kv.expire("session:abc", 3600, 0)
assert kv.get("session:abc", 3599) == {"user_id":42}
assert kv.get("session:abc", 3600) is None
counter = 0
for _ in range(3): counter += 1
assert counter == 3
products = [
 {"sku":"A1","tags":["led","home"],"variants":[{"color":"warm","stock":12}]},
 {"sku":"B2","tags":["usb"],"variants":[{"color":"black","stock":88}]},
 {"sku":"C3","tags":["wifi","home"],"variants":[{"color":"grey","stock":5}]},
 {"sku":"D4","tags":["home"],"variants":[{"color":"warm","stock":30},{"color":"grey","stock":5}]}]
selected = [p["sku"] for p in products if "home" in p["tags"] and any(v["color"]=="warm" and v["stock"]<20 for v in p["variants"])]
assert selected == ["A1"]
# Separate any() tests would incorrectly accept D4.
bad = products[-1]
assert any(v["color"]=="warm" for v in bad["variants"]) and any(v["stock"]<20 for v in bad["variants"])
 
def get_email(doc):
    source = doc.get("profile", doc)
    if not isinstance(source, dict): raise ValueError("profile must be an object")
    value = source.get("email")
    if value is not None and not isinstance(value,str): raise ValueError("email type")
    return value
assert [get_email(d) for d in [{"name":"A"},{"email":"b@x.com"},{"profile":{"email":"c@x.com"}}]] == [None,"b@x.com","c@x.com"]
for invalid in [{"profile":None},{"profile":[]},{"email":42}]:
    try: get_email(invalid)
    except ValueError: pass
    else: raise AssertionError("invalid shape accepted")
by_chat, by_sender = defaultdict(dict), defaultdict(dict)
events = [("c1","2024-08-10",100,"m1","alice","hey"), ("c1","2024-08-10",100,"m2","bob","hi"), ("c2","2024-08-10",101,"m3","alice","next")]
for chat,day,ts,mid,sender,body in events * 2:
    by_chat[(chat,day)][(ts,mid)] = (sender,body)
    by_sender[(sender,day)][(ts,mid)] = (chat,body)
assert len(by_chat[("c1","2024-08-10")]) == 2
assert [k[1] for k in sorted(by_sender[("alice","2024-08-10")],reverse=True)] == ["m3","m1"]
# Timestamp-only storage loses a message: it is the wrong primary key.
assert len({e[2]:e for e in events[:2]}) == 1
edges = {"Alice":{"Bob"},"Bob":{"Carol"},"Carol":{"Alice"}}
fof = {v for u in edges["Alice"] for v in edges[u]}
assert fof == {"Carol"}
def reachable(start, depth):
    seen, frontier = {start}, {start}
    for _ in range(depth):
        frontier = {v for u in frontier for v in edges.get(u,set())} - seen
        seen |= frontier
    return seen - {start}
assert reachable("Alice",4) == {"Bob","Carol"}
print({"counter":counter,"document_match":selected,"same_timestamp_messages":2,"alice_latest":["m3","m1"],"two_hops":sorted(fof)})

Reference commands and what each block means

On separately authorized local test instances, Redis SET, GET, three INCRs and EXPIRE key 3600 illustrate a value, counter=3 and a TTL that declines over time, not an exact latency claim. This lab models expiry at a known clock; actual Redis expiration and persistence have their own implementation behavior. The MongoDB 8.0 predicate below requires the same array element to satisfy both conditions [Mongo elemMatch].

db.products.find({tags: "home", variants: {$elemMatch: {stock: {$lt: 20}, color: "warm"}}})

With the four products above only A1 matches; D4 is the negative control. Cassandra's CQL answers latest rows within one chat/day, then the sender projection answers Alice's history. Neo4j 5's bounded variable-length relationship pattern expresses the two-hop FRIEND query:

MATCH (a:User {name:'Alice'})-[:FRIEND*2..2]->(fof)
RETURN DISTINCT fof.name;

The original three-node FRIEND chain returns Carol. The equivalent edge-table SQL needs two edge instances for two hops, not an obligatory triple self-join. Path enumeration and reachability have different duplicate/cycle contracts; use DISTINCT and depth bounds consciously. A graph database does not make the number of possible paths constant.

The former all-in-one Docker script mixed mutable image tags, fixed sleeps, fixed container names, credentials and cleanup that could remove someone else's containers. Its setup is replaced by these isolated reference operations plus the executed lab, not a claim of four service deployments. If provisioning independently, use unique resources, readiness probes, loopback bindings, masked credentials and cleanup limited to resources you created. Default client ports—Redis 6379, MongoDB 27017, Cassandra 9042, Neo4j Bolt 7687 and browser HTTP 7474—are conventions to verify, not a reason to expose them publicly.

Four-hop reachability is not the two-hop FRIEND query

The original stretch question asked for users within four hops of Alice through any relationship, deduplicated. The two-hop directed FRIEND query above solves a different question. In Neo4j 5 legacy variable-length relationship syntax, an undirected version of the original query is:

MATCH (a:User {name:'Alice'})-[*1..4]-(b:User)
WHERE b <> a
RETURN DISTINCT b.name;

Assume one Alice node and unique names for this toy output; otherwise return stable node IDs instead. Omitting the relationship type includes FRIEND and FOLLOWS, and omitting arrowheads permits traversal either way. Cycles can revisit nodes along a path; b <> a removes Alice from the results and DISTINCT deduplicates endpoints, not all work. Path enumeration can still be large. For endpoint reachability only, a bounded breadth-first frontier with a seen set avoids revisiting an endpoint at greater depth:

from collections import defaultdict
adj = defaultdict(set)
for u, v, kind in [('Alice','Bob','FRIEND'), ('Bob','Carol','FRIEND'),
                   ('Alice','Carol','FOLLOWS'), ('Carol','Dana','WORKS_WITH'),
                   ('Dana','Eve','FRIEND'), ('Eve','Finn','FRIEND')]:
    adj[u].add(v)
    adj[v].add(u)  # undirected, all relationship types
seen, frontier = {'Alice'}, {'Alice'}
for _ in range(4):
    frontier = {v for u in frontier for v in adj[u]} - seen
    seen |= frontier
assert seen - {'Alice'} == {'Bob','Carol','Dana','Eve','Finn'}
assert len(adj['Alice']) == 2
print(sorted(seen - {'Alice'}))

Finn is four edges away via Alice–Carol–Dana–Eve–Finn. The Python result is an endpoint-set oracle, not an emulator of Cypher path enumeration. A recursive relational CTE can express this too; SQL does not require a fixed four-self-join expansion. All vendor commands remain unexecuted references.

Production reality

Discord's published message design: the first-party account describes bucketing channel messages and the difficulties encountered with MongoDB and Cassandra. The lesson is bounded partitions and a stable message-order key, not that MongoDB B-trees cannot implement recent-message access. Reads may cross buckets. Historical scale and workloads must not be carried forward as current capacity guarantees [Discord].

Migration versus product verdict: a migration can be driven by replication, write amplification, operations or query fit, not solely SQL versus NoSQL. The old Uber-to-Yugabyte anecdote is not established by a primary passage here. The retained design exercise is to compare the same trip workload's write/read paths, replication costs and failure handling before choosing a store; a migration elsewhere does not prove that one database is insufficient at your scale.

Stack Overflow as a counterexample to simplistic labels: Nick Craver's 2016 first-party architecture describes SQL Server and Redis; it is not “one Postgres.” A relational system plus caching can serve a substantial workload, but a historical page-view figure cannot predict another application's write contention or availability. Use the design as a reason to measure, not a universal “you won't saturate it” promise.

Where this connects next

Dimensional models choose analytical grain rather than Cassandra's operational query partitions. Kafka uses keyed partitioning for a log, not the same storage/transaction API. CAP reasoning explains replication choices; cache TTLs determine different staleness behavior; chat design reuses the bucket/identity exercise. These are technical connections, not a claim that every chat service or cache uses the same product.

Recall and worked answers

1. Four families and examples? Key-value Redis; document MongoDB; wide-column Cassandra/Bigtable; graph Neo4j. Products overlap.
2. Give up what to gain what? Narrow keyed access, embedded aggregates, partition-local ordered rows, or adjacency traversals each optimize a shape and impose indexing, duplication or distributed-query costs. None implies a universal loss of joins or transactions.
3. Ten million users: three follow-ups? Peak read/write rates and shapes; working-set size/growth versus resources; measured bottlenecks after reasonable indexing/pooling, plus correctness SLOs.
4. Why one table per Cassandra query? Partition/clustering design organizes efficient keyed reads; unsupported query shapes can need another projection or evaluated index. It is a heuristic, not an absolute requirement.
5. Graph easier than SQL example? Bounded variable-length reachability is concise in Cypher; SQL recursive CTEs can express it too. Fan-out grows with reachable edges/paths in either engine, not because SQL syntax itself makes depth exponential.
6. JSONB argument? Keep flexible attributes next to constrained columns, indexes, joins and transactions when that fits the workload; MongoDB also supports validation, joins and transactions, so compare real operations.
7. Eventual consistency? Replicas may disagree temporarily; under repair/delivery assumptions they converge after updates stop. No latency bound follows from the name.
8. Redis speed? In-memory structures and efficient command execution can reduce work; operation complexity, network, persistence and CPU still determine latency. Redis is not free of transaction/persistence costs.
9. Why Discord-style bucket_id? Limit partition growth over time and preserve locality for recent messages. Hot traffic still needs monitoring and multi-bucket reads; a time bucket is not a hard byte limit.

Explain out loud: describe each access shape, defend JSONB or a document store without false capability claims, and explain why writing a sender projection requires a repair strategy.

Sources and next step

Checked 2026-10-07: Redis types, MongoDB 8.0 validation, MongoDB transactions, Mongo elemMatch, Cassandra 5.0 CQL, Neo4j 5 patterns, Discord, Stack Overflow 2016. Historical Bigtable, Dynamo and JSONB claims have separately captured primary evidence in the batch-3 report. Additional operation contracts: Mongo causal, DynamoDB reads, Cassandra guarantees. DynamoDB/Redis latest documentation is a mutable snapshot, not a promise about an older service version; Cassandra 5.0 pages carry the banner noted above.

Next: Data modelling. Service syntax is source-reviewed; only the bounded model was executed. That boundary does not remove the store-selection, schema or consistency teaching.

Explain-out-loud answer guide

1. Four families: Redis keyed structures, MongoDB documents, Cassandra partitioned ordered rows, Neo4j property graphs. Their convenient access shapes bring different indexing, duplication and traversal costs, not universal bans on transactions or joins.
2. Why not just Postgres? JSONB plus indexes, joins and transactions can satisfy flexible-attribute workloads without another operational system; choose by measured access and correctness requirements, not a claim that MongoDB lacks those capabilities.
3. Cassandra's core rule: partition/clustering keys should serve known queries; a sender lookup and a chat lookup may need two projections with one stable event ID and repair after partial writes. Secondary indexes are an evaluated alternative, not forbidden.

Optional archived resources

These links retain the original pre-read route; historical titles are labels, not verified endorsements. Video attribution, duration, playback and external reachability were not revalidated. Use the version-qualified primary references above for correctness; mutable /current or /latest pages may differ.

• 7 Database Paradigms in 100 Seconds Each — archived video/discovery link.
• Distributed Systems 2.1 — Consistency + Availability — archived video/discovery link.
• Scylla Summit 2022: Migrating SQL Schemas for ScyllaDB: Data Modeling Best Practices — archived video/discovery link.
• Dynamo — Amazon's Highly Available Key-Value Store — archived reading link.
• Cassandra vs Relational Data Modeling — archived reading link.
• What is a Graph Database? — archived reading link.

Series route and study format

Hub: The 6-Month Learning Plan. Previous: S043; next: S045. These are navigation pointers, not certification of every linked body or permission to publish it.

The original 130-session series suggests a 90-minute study cycle: intuition → visual explanation → hands-on practice → production failure analysis → recall. Treat that as a pacing suggestion, not a tested completion time. Work the examples and explain the failure cases before moving on; reference-only service exercises need separate execution authority.