NoSQL — document (MongoDB), key-value (Redis), column (Cassandra), graph (Neo4j): Exercises

Figure — NoSQL — document (MongoDB), key-value (Redis), column (Cassandra), graph (Neo4j)

Figure 1 — N = 3 replicas; the coral write-set and dashed mint read-set share node 2, so the quorum read cannot miss the latest write.

Level 1 — Recognition

"Which family is this?" No calculation, just matching a shape to a model.

Recall Solution

Key-value (Redis). Why: you always know the exact key, you need speed, and you need a TTL (time-to-live = auto-expiry). That is exactly the key-value sweet spot — no query engine needed.
Document (MongoDB). Why: the fields differ per item, so a rigid table with fixed columns fights you. A document stores each item's own shape.
Graph (Neo4j). Why: "the relationships ARE the data", and multi-hop traversal is the query. Graph DBs store direct neighbour pointers so each hop is cheap.
Wide-column (Cassandra). Why: extreme append-heavy writes, partitioned by sensor_id, sorted by time — a textbook wide-column table.

Recall Solution

sensor_id is the partition key → it decides which node stores the row (Cassandra hashes it).
ts is the clustering key → it decides the sort order of rows inside that one partition. So all readings for one sensor live together on one node, already sorted by time — perfect for "give me sensor 7's readings from newest to oldest".

Level 2 — Application

Apply one formula or one rule to a concrete input.

Recall Solution

The rule from the parent note: a read is guaranteed to see the latest write iff $W + R > N$ . $W + R = 3 + 2 = 5, N = 5.$ Since $5 > 5$ is false, the condition fails → no guarantee. The 3 nodes that hold the fresh write and the 2 nodes we read could be completely disjoint (3 + 2 = 5 covers all nodes with no overlap), so the read may return stale data.

Recall Solution

We need $W + R > N \Rightarrow 3 + R > 5 \Rightarrow R > 2 \Rightarrow R \geq 3$ . The smallest integer is $R = 3$ . Check: $W + R = 3 + 3 = 6 > 5$ . ✅ Now the 3 written nodes and 3 read nodes must share at least $W + R - N = 6 - 5 = 1$ node — pigeonhole guarantees the overlap.

Recall Solution

Guaranteed overlap $= W + R - N = 2 + 2 - 3 = 1$ node. That single shared node holds the newest value; a version timestamp then lets the read pick the latest among the 2 it saw. This is why $W = R = 2$ on $N = 3$ is the classic "strong on demand" setting.

Figure 2 — Left: $W + R = 4 > 3$ shares node 2 (strong). Right: $W + R = 3 = N$ can be disjoint (eventual).

Level 3 — Analysis

Compare options, explain a tradeoff, reason about a failure.

Definition First: what does "CAP" actually stand for?

CAP names three properties a distributed datastore might want, and the theorem that says you can't have all three at once when the network breaks:

C — Consistency: every read returns the latest completed write (never stale data).
A — Availability: every request gets a non-error answer (the system never refuses).
P — Partition-tolerance: the system keeps working even when the network splits nodes into groups that can't talk (a "partition"). The CAP theorem: during a partition (P), you can keep only one of C or A — not both. Since partitions will happen in real networks, the honest choice is CP (keep Consistency, drop Availability while split) or AP (keep Availability, drop Consistency while split). We use these terms in L3.3 and L5. See also CAP Theorem and BASE vs ACID.

Recall Solution

Both are strongly consistent ( $4 > 3$ each). The difference is which operation you make cheap/robust:

$(W = 2, R = 2)$ : balanced. A write needs 2 of 3 up; a read needs 2 of 3 up. Tolerates 1 node down for both reads and writes.
$(W = 3, R = 1)$ : writes must reach all 3 nodes → if any node is down, writes stop. But reads need only 1 node → reads are super fast and highly available. Pick $(W = 3, R = 1)$ for a read-heavy system where writes are rare and you want the cheapest possible reads. Pick $(W = 2, R = 2)$ when you can't afford writes to fail whenever one node blinks.

Recall Solution

SQL: each hop is a JOIN that must search an index for matching rows across the entire friends table. In a B-tree index a lookup costs $O (lo g M)$ for $M$ rows, and it repeats for every node in the current frontier; the frontier itself multiplies by the branching factor each hop. Cost scales with the total table size and depth — it explodes (this is the repeated-traversal idea behind Graph Traversal Algorithms (BFS/DFS): a breadth-first expansion, but paying an index search at every single step).
Graph DB (index-free adjacency): "index-free" means the DB does not look a neighbour up in a global index at all. Each node record stores direct pointers (memory/disk addresses) to its neighbour records — like a linked list baked into the node. Following one edge is $O (1)$ : dereference a pointer, no search. So 3 hops = 3 cheap pointer-chasings from the local frontier, touching only the reachable nodes, never the whole dataset. Figure 3 draws this contrast.

Figure 3 — SQL searches an index per hop (left); graph DB follows direct neighbour pointers, $O (1)$ per hop (right).

Recall Solution

Payments ledger = CP (Consistency + Partition-tolerance). It sacrifices Availability during the partition (refuses to answer) so it never returns/commits a wrong balance. Correctness beats uptime here.
Like counter = AP (Availability + Partition-tolerance). It sacrifices Consistency briefly — two partitions might undercount — but stays up and eventually converges when links heal. A momentarily wrong like count is harmless. This is the real CAP choice: not "which of 3 to drop", but CP vs AP while partitioned (see CAP Theorem).

Level 4 — Synthesis

Combine multiple ideas into a design.

Recall Solution

Need	Family	One-line why
(a) session/cart	Redis (key-value)	fetched by one session key, needs speed + TTL
(b) catalog	MongoDB (document)	per-item flexible fields (book vs shirt) → documents
(c) click firehose	Cassandra (wide-column)	huge append-only writes, partition by `user_id`, no master
(d) recommendations	Neo4j (graph)	it's `bought → product ← bought` traversal
The meta-lesson: polyglot persistence — one app, several databases, each matched to its access pattern. There is no single "best" NoSQL.

Recall Solution

Read win: fetching a post + its comments is one document read — no join, one disk locality, fewer round-trips. Ideal when you almost always show post and comments together.
Write cost: if the same user's display-name is duplicated across many embedded comments, renaming that user means touching many documents (updates to duplicated data are painful). The document can also grow unbounded (huge comment threads).
Keep separate when: comments are enormous, edited independently, or queried on their own ("all comments by user X across all posts"). Then reference by id instead of embedding. This is the SQL-vs-document tradeoff (compare SQL Relational Databases).

Level 5 — Mastery

Design under constraints, defend against edge cases, prove a claim.

Recall Solution

Step 1 — consistency (i): need $W + R > N = 3$ . Try $W = 2, R = 2$ : $4 > 3$ ✅. Overlap $= W + R - N = 1$ node guaranteed shared → strong. Step 2 — survive one DC down (ii): with one DC gone, only 2 replicas remain.

Writes need $W = 2$ acks → 2 nodes still alive → writes survive ✅.
Reads need $R = 2$ → 2 nodes still alive → reads survive ✅. So $(W = 2, R = 2)$ meets both (i) and (ii) for a single DC failure. Step 3 — the CAP catch: this only holds while at most one DC is down and the survivors can still talk. If a partition isolates every DC from the others (each alone with 1 replica), then no side can gather 2 acks → to keep consistency (i) the system must refuse requests (lose availability). That is CAP biting: you chose CP, so under a severe partition you sacrifice availability. You cannot have strong consistency and full availability and partition-tolerance at once (see CAP Theorem, BASE vs ACID).

Recall Solution

Suppose, for contradiction, the write set (size $W$ ) and read set (size $R$ ) are disjoint (share no node). Then together they occupy $W + R$ distinct nodes, and all of them must fit inside the $N$ total replicas: $W + R \leq N .$ But we assumed $W + R > N$ . Contradiction. Therefore they cannot be disjoint → they share at least $W + R - N \geq 1 node.$ That shared node witnessed the latest write, so the read (which touched it) sees the newest value once a version/timestamp breaks ties. ∎

Recall Solution

(a) Rate-limit counter → Redis (key-value). INCR is atomic and microsecond-fast; a tiny transient miscount under partition is acceptable (lean AP). Fetched by one known key → key-value.
(b) Audit log → Cassandra (wide-column). Append-only, write-heavy, partition by account_id, cluster by ts → immutable and read back in time order. Its LSM write path (see Database Indexing (B-tree, LSM)) makes the firehose cheap.
(c) Fraud rings → Neo4j (graph). Detecting cycles of money movement is a graph traversal; the same self-join explosion from L3.2 would cripple SQL here.
(d) Customer profiles → MongoDB (document) run at a strong quorum, or an ACID relational store. This is the CAP-sensitive choice. "Strong per-account consistency" means you run it CP: set $W + R > N$ — e.g. $N = 3, W = 2, R = 2$ (overlap $= 1$ ) — and accept that a severe partition may make you reject some profile updates (lose availability) rather than risk two conflicting balances. Mastery point: each subsystem gets its own consistency stance — (a) leans AP for speed, (d) is CP for correctness. You do not apply one global CAP choice to the whole app; you match model and consistency to each access pattern (compare BASE vs ACID).